Bitcoin weak transaction nonce question

[imjustagirl]

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?

[1714892192]

1714892192

[1714892192]

1714892192

[1714892192]

1714892192

[achow101]

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]

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]

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]

@Coding Enthusiast,  Ok, they are right.

[MixMAx123]

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://bitcointalk.org/index.php?topic=5202064.0

[gmaxwell]

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]

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

[imjustagirl]

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?

[Coding Enthusiast]

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.