imjustagirl (OP)
Member
Offline
Activity: 118
Merit: 11
|
|
December 06, 2019, 12:34:09 PM |
|
I finally have some free time to dive deeper into bitcoin studies, so I have a question (or two maybe). I read an article about lattice attacks when a bad k (nonce) is used. I found some addresses in which the signatures (s part) start with the same bytes, is that a sign that an address has been using a weak nonce? If the same r is used (exact same nonce) in different transactions, then the formula for calculations would be K((z1*s2 - z2*s1)/(r*(s1-s2))). What would it be, if the same s is re-used in the formula, but the r's are different?
|
1JPnqMd1Q43L3KbZ7SoTSdRCD2aLj2sikF Tip Me!
|
|
|
|
|
If you see garbage posts (off-topic, trolling, spam, no point, etc.), use the "report to moderator" links. All reports are investigated, though you will rarely be contacted about your reports.
|
|
|
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
|
|
|
achow101
Moderator
Legendary
Offline
Activity: 3388
Merit: 6635
Just writing some code
|
I found some addresses in which the signatures (s part) start with the same bytes, is that a sign that an address has been using a weak nonce?
Not necessarily. It depends on how many bytes are the same. What would it be, if the same s is re-used in the formula, but the r's are different?
I don't believe that it is possible to get the private key when s is repeated. The reason that a repeated R works is because R is part of the calculation for s which allows you to rearrange the formula for s so that you can compute the private key. The nonce term disappears in that formula because you know it is the same so it can be rearranged and written out. But s is not used in any formula. It is a single calculation and I don't think a repeated s gives any more meaningful information about the nonce or the private key.
|
|
|
|
MixMAx123
|
|
December 07, 2019, 01:26:08 PM |
|
What would it be, if the same s is re-used in the formula, but the r's are different?
s = (h+r*P)/k h=hash P=privateKey k=nonce If s is to be equal, then r, k and h must be the same.
|
|
|
|
Coding Enthusiast
Legendary
Offline
Activity: 1039
Merit: 2783
Bitcoin and C♯ Enthusiast
|
|
December 07, 2019, 07:41:48 PM |
|
What would it be, if the same s is re-used in the formula, but the r's are different?
s = (h+r*P)/k h=hash P=privateKey k=nonce If s is to be equal, then r, k and h must be the same. Not true. If f(x)=a+b=12 then (a,b) can be (0,12), (1,11), (2,10),... Things aren't different for modular arithmetic. Here is an example: s = k-1 * (e + r*key) % N N=17
e=4; key=7; k=1; r=7 => s=2 e=4; key=7; k=2; r=0 => s=2 e=4; key=7; k=3; r=10 => s=2
e=12; key=3; k=1; r=8 => s=2 e=12; key=3; k=2; r=3 => s=2 e=12; key=3; k=3; r=15=> s=2
e=12; key=10; k=1; r=16=> s=2
|
|
|
|
MixMAx123
|
|
December 08, 2019, 11:12:32 AM |
|
@Coding Enthusiast, Ok, they are right.
|
|
|
|
MixMAx123
|
|
December 08, 2019, 11:49:35 AM Last edit: December 08, 2019, 12:13:29 PM by MixMAx123 |
|
I have generated two signatures that match this case. h1 (hash 1) b2a4c843ae1729600ccf2234766ea6714df86a5df26c48a648149bab255ab2a1 k1 90cbb088437112179594110b51bab29f505847b0bbafff938dbc539687bffd7b PrivKey: 37c4a759c4feaa8db1e8476abff3ad32e74299a52b1f64d8d5c6c9842ac7096b r1 b31bca72a506bcb321a637227a7d7c718eb3f4d0d72125315acc685cbb84cc1 s 6cf0e68558668d918e5de0af1349fa0a5f2a075137416bb2f81adf18c8bdb683 The second signature: h2 (hash 2) 649e3f12c7cad731453f306665c723ceb764e93d2039164e02357c9f59bd7530 k2 c36bc518215d770b6d4f88fdfa2e03996e1b3b1efa89fb69c96ed54fac6c48f5 PrivKey: 37c4a759c4feaa8db1e8476abff3ad32e74299a52b1f64d8d5c6c9842ac7096b r2 a164e62253c067825c1dd8bc5defe0e4e7241bb28853cc41c2e2d43825cd596e s 6cf0e68558668d918e5de0af1349fa0a5f2a075137416bb2f81adf18c8bdb683 public key for both signatures is: 636b810584ffbb5b90247903e6f1941cbab04940337fc4a51cf59656ade957ed , 2de3d4ed0603fd637bb8e7e1b486c7a8c25ca88d5d9e7a3059bbecf465f6359c But I had to calculate hash2 with: s * k2 - r2 * P I calculated this with my ECC Calculator: https://bitcointalk.org/index.php?topic=5202064.0
|
|
|
|
gmaxwell
Moderator
Legendary
Offline
Activity: 4172
Merit: 8420
|
|
December 08, 2019, 12:24:43 PM |
|
I have generated two signatures that match this case.
Your examples use different hashes. If you are freely setting the hash values and do not know the hash preimage then your "signature" is not an ECDSA signature. The requirement that the hash input is actually as hash is utterly critical to ECDSA security.
|
|
|
|
MixMAx123
|
|
December 08, 2019, 12:31:14 PM |
|
Yeah right, I do not know how to create two different signatures with the same hash.
|
|
|
|
imjustagirl (OP)
Member
Offline
Activity: 118
Merit: 11
|
|
December 08, 2019, 01:20:06 PM |
|
Thank you all, very informative. I will check out your tool MixMAx123. I am still puzzled though, when there is a case of reused r values, it's obvious. How would anyone know if the program they use generates weak transaction nonces though?
|
1JPnqMd1Q43L3KbZ7SoTSdRCD2aLj2sikF Tip Me!
|
|
|
Coding Enthusiast
Legendary
Offline
Activity: 1039
Merit: 2783
Bitcoin and C♯ Enthusiast
|
|
December 08, 2019, 02:03:39 PM |
|
How would anyone know if the program they use generates weak transaction nonces though?
You'll have to go through the code and see how ECDSA is implemented in the software you are using. A good way to avoid this bug and a bunch of similar ones is generating k deterministically instead of randomly. One way that is used in most Bitcoin implementations is RFC-6979.
|
|
|
|
|