Bitcoin Forum
May 03, 2024, 06:52:33 PM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Can two signatures be identical?  (Read 1552 times)
hhanh00 (OP)
Sr. Member
****
Offline Offline

Activity: 467
Merit: 266


View Profile
May 05, 2016, 04:27:08 AM
Merited by ABCbits (2)
 #1

Assuming we are talking about Bitcoin signatures and we are not using deterministic k.

My understanding is that signing the same message with the same private key will not yield the same signature because of the random factor k. The odds of two signatures being equal is negligible under these conditions. Could someone confirm or refute this?

Thanks,
--h

1714762353
Hero Member
*
Offline Offline

Posts: 1714762353

View Profile Personal Message (Offline)

Ignore
1714762353
Reply with quote  #2

1714762353
Report to moderator
1714762353
Hero Member
*
Offline Offline

Posts: 1714762353

View Profile Personal Message (Offline)

Ignore
1714762353
Reply with quote  #2

1714762353
Report to moderator
Bitcoin mining is now a specialized and very risky industry, just like gold mining. Amateur miners are unlikely to make much money, and may even lose money. Bitcoin is much more than just mining, though!
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1714762353
Hero Member
*
Offline Offline

Posts: 1714762353

View Profile Personal Message (Offline)

Ignore
1714762353
Reply with quote  #2

1714762353
Report to moderator
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8382



View Profile WWW
May 05, 2016, 07:49:28 AM
Last edit: May 05, 2016, 11:55:39 AM by gmaxwell
Merited by ABCbits (2)
 #2

Assuming we are talking about Bitcoin signatures and we are not using deterministic k.

My understanding is that signing the same message with the same private key will not yield the same signature because of the random factor k. The odds of two signatures being equal is negligible under these conditions. Could someone confirm or refute this?

Thanks,
--h
probability of one out of the group order exactly (roughly 1:2^256, or one bit less assuming that both signature were from low-S enforcing signers). The only way two them to be identical is to pick the same k.
hhanh00 (OP)
Sr. Member
****
Offline Offline

Activity: 467
Merit: 266


View Profile
May 05, 2016, 08:57:35 AM
 #3

Just to be clear, that's in addition to having the same message and private key,  right?

2c0de
Full Member
***
Offline Offline

Activity: 138
Merit: 102


View Profile
May 05, 2016, 12:41:05 PM
 #4

Just to be clear, that's in addition to having the same message and private key,  right?

reusal of address(privkey) and the random parameter k can cause trouble

DHjxvnHB9RirtPbvkovSotn1fY2poNffoi
LWeT4wwDVdJ9x49UcXPyS6CznRpbQFM6nx
0x96273C2FD825f0A2745d917bbbfabD6032dC1aDD
bitdumper
Sr. Member
****
Offline Offline

Activity: 266
Merit: 250

One world One currency, Bitcoin.


View Profile
May 06, 2016, 07:15:14 AM
 #5

The probability is very less but , in past it has happened
https://bitcointalk.org/index.php?topic=271831.0
Now it rarely occurs.

bob123
Legendary
*
Offline Offline

Activity: 1624
Merit: 2481



View Profile WWW
May 06, 2016, 08:55:44 AM
 #6

Just to be clear, that's in addition to having the same message and private key,  right?

reusal of address(privkey) and the random parameter k can cause trouble

Can you explain this more?
What kind of trouble?

waxwing
Sr. Member
****
Offline Offline

Activity: 469
Merit: 253


View Profile
May 06, 2016, 11:47:08 AM
Merited by ABCbits (3)
 #7

Just to be clear, that's in addition to having the same message and private key,  right?

reusal of address(privkey) and the random parameter k can cause trouble

Can you explain this more?
What kind of trouble?

Reusing the same nonce value (hence same k value) on two different signatures (ie. different messages) signed with the same private key, leaks the private key. This has happened in Bitcoin due to bad nonce generation code, and quite a few times, and has led to loss of funds.

The wikipedia page on ECDSA explains the algebra; it's a very simple calculation to do.

PGP fingerprint 2B6FC204D9BF332D062B 461A141001A1AF77F20B (use email to contact)
Monnt
Legendary
*
Offline Offline

Activity: 938
Merit: 1000


View Profile
May 08, 2016, 05:03:29 AM
 #8

Correct me if I'm wrong.

K is the RNG variable.

Based on your privkey and K, you come up with a signature. Using the same variables, there are only so many combinations you can come up with. Meaning that an RNG can stumble upon previous combinations.

Simplified:

Imagine your name. That is your private key. The place number of each letter of your name (a=1, b=2, etc) is added and multiplied to a number rolled on a die. There are only 6 outcomes. Signatures are the same, but with alot more than 6 outcomes.
achow101
Moderator
Legendary
*
expert
Offline Offline

Activity: 3388
Merit: 6578


Just writing some code


View Profile WWW
May 08, 2016, 05:37:43 AM
 #9

Correct me if I'm wrong.

K is the RNG variable.

Based on your privkey and K, you come up with a signature. Using the same variables, there are only so many combinations you can come up with. Meaning that an RNG can stumble upon previous combinations.

Simplified:

Imagine your name. That is your private key. The place number of each letter of your name (a=1, b=2, etc) is added and multiplied to a number rolled on a die. There are only 6 outcomes. Signatures are the same, but with alot more than 6 outcomes.
That is true, but considering k is a large number (256 bits IIRC), the probability of randomly selecting the same number twice is extremely low.

Moloch
Hero Member
*****
Offline Offline

Activity: 798
Merit: 722



View Profile
May 08, 2016, 06:04:37 AM
 #10

I could be wrong, but I remember reading somewhere that bitcoin core has already addressed the duplicate nonce issue... something about forcing it to increment... you cannot use a nonce equal to or less than the last one your key used to sign a tx?

Or is this different from the k value?
luv2drnkbr
Hero Member
*****
Offline Offline

Activity: 793
Merit: 1016



View Profile
May 08, 2016, 01:13:50 PM
Merited by ABCbits (4)
 #11

I could be wrong, but I remember reading somewhere that bitcoin core has already addressed the duplicate nonce issue... something about forcing it to increment... you cannot use a nonce equal to or less than the last one your key used to sign a tx?

Or is this different from the k value?

Bitcoin Core and all other up to date software use RFC-6979, which essentially derives the k value by hashing the private key and the hash of the message to be signed, so that the output is a deterministic and verifiable, but still random (or as random as the hashing algo).

If you use an incrementing nonce, if somebody can guess it or guess where you started, they can get your private key.  Better to use RFC-6979.

The vulnerability mentioned before was basically that the software used a bad RNG to make random k values, and as mentioned, repeating the k value *even just once* means your private key is leaked.  So RFC-6979 was made so that there's a good standard for deriving a random unique k value.

You can even scan the blockchain yourself for repeated k values.  Look for signatures from the same address (address re-use), and if the r value -- the first part of the signature -- is the same, that means the k value was re-used, and that private key can be gotten.  This happened a few years ago on a lot of Android wallets because the Android RNG was bad and the wallets re-used addresses.

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!