|
Title: Bitcoin weak transaction nonce question Post by: imjustagirl on 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? Title: Re: Bitcoin weak transaction nonce question Post by: achow101 on December 06, 2019, 04:20:29 PM 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. Title: Re: Bitcoin weak transaction nonce question Post by: MixMAx123 on 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. Title: Re: Bitcoin weak transaction nonce question Post by: Coding Enthusiast on 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 Title: Re: Bitcoin weak transaction nonce question Post by: MixMAx123 on December 08, 2019, 11:12:32 AM @Coding Enthusiast, Ok, they are right.
Title: Re: Bitcoin weak transaction nonce question Post by: MixMAx123 on December 08, 2019, 11:49:35 AM I have generated two signatures that match this case.
h1 (hash 1) Code: b2a4c843ae1729600ccf2234766ea6714df86a5df26c48a648149bab255ab2a1 Code: 90cbb088437112179594110b51bab29f505847b0bbafff938dbc539687bffd7b Code: 37c4a759c4feaa8db1e8476abff3ad32e74299a52b1f64d8d5c6c9842ac7096b Code: b31bca72a506bcb321a637227a7d7c718eb3f4d0d72125315acc685cbb84cc1 Code: 6cf0e68558668d918e5de0af1349fa0a5f2a075137416bb2f81adf18c8bdb683 The second signature: h2 (hash 2) Code: 649e3f12c7cad731453f306665c723ceb764e93d2039164e02357c9f59bd7530 Code: c36bc518215d770b6d4f88fdfa2e03996e1b3b1efa89fb69c96ed54fac6c48f5 Code: 37c4a759c4feaa8db1e8476abff3ad32e74299a52b1f64d8d5c6c9842ac7096b Code: a164e62253c067825c1dd8bc5defe0e4e7241bb28853cc41c2e2d43825cd596e Code: 6cf0e68558668d918e5de0af1349fa0a5f2a075137416bb2f81adf18c8bdb683 public key for both signatures is: Code: 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 Title: Re: Bitcoin weak transaction nonce question Post by: gmaxwell on 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. Title: Re: Bitcoin weak transaction nonce question Post by: MixMAx123 on December 08, 2019, 12:31:14 PM Yeah right, I do not know how to create two different signatures with the same hash.
Title: Re: Bitcoin weak transaction nonce question Post by: imjustagirl on 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?
Title: Re: Bitcoin weak transaction nonce question Post by: Coding Enthusiast on 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 (https://tools.ietf.org/html/rfc6979). |