Bitcoin weak transaction nonce question

Coding Enthusiast

legendary

Activity: 1042

Merit: 2805

Bitcoin and C♯ Enthusiast

Quote from: imjustagirl on December 08, 2019, 08:20:06 AM

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.

imjustagirl

member

Activity: 118

Merit: 11

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?

MixMAx123

full member

Activity: 161

Merit: 168

Yeah right, I do not know how to create two different signatures with the same hash.

gmaxwell

staff

Activity: 4284

Merit: 8808

Quote from: MixMAx123 on December 08, 2019, 06:49:35 AM

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

full member

Activity: 161

Merit: 168

I have generated two signatures that match this case.

h1 (hash 1)

Code:

b2a4c843ae1729600ccf2234766ea6714df86a5df26c48a648149bab255ab2a1

k1

Code:

90cbb088437112179594110b51bab29f505847b0bbafff938dbc539687bffd7b

PrivKey:

Code:

37c4a759c4feaa8db1e8476abff3ad32e74299a52b1f64d8d5c6c9842ac7096b

r1

Code:

b31bca72a506bcb321a637227a7d7c718eb3f4d0d72125315acc685cbb84cc1

s

Code:

6cf0e68558668d918e5de0af1349fa0a5f2a075137416bb2f81adf18c8bdb683

The second signature:

h2 (hash 2)

Code:

649e3f12c7cad731453f306665c723ceb764e93d2039164e02357c9f59bd7530

k2

Code:

c36bc518215d770b6d4f88fdfa2e03996e1b3b1efa89fb69c96ed54fac6c48f5

PrivKey:

Code:

37c4a759c4feaa8db1e8476abff3ad32e74299a52b1f64d8d5c6c9842ac7096b

r2

Code:

a164e62253c067825c1dd8bc5defe0e4e7241bb28853cc41c2e2d43825cd596e

s

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://bitcointalksearch.org/topic/presentation-of-my-ecc-calculator-5202064

MixMAx123

full member

Activity: 161

Merit: 168

@Coding Enthusiast, Ok, they are right.

Coding Enthusiast

legendary

Activity: 1042

Merit: 2805

Bitcoin and C♯ Enthusiast

Quote from: MixMAx123 on December 07, 2019, 08:26:08 AM

Quote from: imjustagirl on December 06, 2019, 07:34:09 AM

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

full member

Activity: 161

Merit: 168

Quote from: imjustagirl on December 06, 2019, 07:34:09 AM

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.

achow101

staff

Activity: 3458

Merit: 6793

Just writing some code

Quote from: imjustagirl on December 06, 2019, 07:34:09 AM

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.

Quote from: imjustagirl on December 06, 2019, 07:34:09 AM

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.

imjustagirl

member

Activity: 118

Merit: 11

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?

Topic: Bitcoin weak transaction nonce question (Read 322 times)