Bitcoin Forum
October 20, 2020, 05:20:50 PM *
News: Latest Bitcoin Core release: 0.20.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Bitcoin weak transaction nonce question  (Read 165 times)
imjustagirl
Jr. Member
*
Offline Offline

Activity: 117
Merit: 6


View Profile
December 06, 2019, 12:34:09 PM
 #1

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!
1603214450
Hero Member
*
Offline Offline

Posts: 1603214450

View Profile Personal Message (Offline)

Ignore
1603214450
Reply with quote  #2

1603214450
Report to moderator
1603214450
Hero Member
*
Offline Offline

Posts: 1603214450

View Profile Personal Message (Offline)

Ignore
1603214450
Reply with quote  #2

1603214450
Report to moderator
1603214450
Hero Member
*
Offline Offline

Posts: 1603214450

View Profile Personal Message (Offline)

Ignore
1603214450
Reply with quote  #2

1603214450
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
achow101
Moderator
Legendary
*
expert
Offline Offline

Activity: 2282
Merit: 3512


Just writing some code


View Profile WWW
December 06, 2019, 04:20:29 PM
Merited by gmaxwell (1), ETFbitcoin (1)
 #2

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
Member
**
Offline Offline

Activity: 83
Merit: 89


View Profile
December 07, 2019, 01:26:08 PM
Merited by piotr_n (1)
 #3

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 Offline

Activity: 839
Merit: 1669


Bitcoin and C♯ Enthusiast


View Profile WWW
December 07, 2019, 07:41:48 PM
Merited by piotr_n (1), ETFbitcoin (1), Heisenberg_Hunter (1)
 #4

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


Projects List+Suggestion box
Donate: 1Q9s or bc1q
|
|
|
FinderOuter(0.5.0)Ann-git
Denovo(0.1.0)Ann-git
Bitcoin.Net(0.6.0)Ann-git
|
|
|
BitcoinTransactionTool(0.11.0)Ann-git
WatchOnlyBitcoinWallet(3.2.1)Ann-git
SharpPusher(0.10.0)Ann-git
MixMAx123
Member
**
Offline Offline

Activity: 83
Merit: 89


View Profile
December 08, 2019, 11:12:32 AM
 #5

@Coding Enthusiast,  Ok, they are right.
MixMAx123
Member
**
Offline Offline

Activity: 83
Merit: 89


View Profile
December 08, 2019, 11:49:35 AM
Last edit: December 08, 2019, 12:13:29 PM by MixMAx123
 #6

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
Moderator
Legendary
*
qt
Online Online

Activity: 3206
Merit: 4389



View Profile
December 08, 2019, 12:24:43 PM
 #7

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
Member
**
Offline Offline

Activity: 83
Merit: 89


View Profile
December 08, 2019, 12:31:14 PM
 #8

Yeah right, I do not know how to create two different signatures with the same hash.
imjustagirl
Jr. Member
*
Offline Offline

Activity: 117
Merit: 6


View Profile
December 08, 2019, 01:20:06 PM
 #9

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 Offline

Activity: 839
Merit: 1669


Bitcoin and C♯ Enthusiast


View Profile WWW
December 08, 2019, 02:03:39 PM
Merited by ETFbitcoin (1)
 #10

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.

Projects List+Suggestion box
Donate: 1Q9s or bc1q
|
|
|
FinderOuter(0.5.0)Ann-git
Denovo(0.1.0)Ann-git
Bitcoin.Net(0.6.0)Ann-git
|
|
|
BitcoinTransactionTool(0.11.0)Ann-git
WatchOnlyBitcoinWallet(3.2.1)Ann-git
SharpPusher(0.10.0)Ann-git
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!