Author

Topic: Can two signatures be identical? (Read 1578 times)

hero member
Activity: 793
Merit: 1026
May 08, 2016, 08:13:50 AM
#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.
hero member
Activity: 798
Merit: 722
May 08, 2016, 01: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?
staff
Activity: 3458
Merit: 6793
Just writing some code
May 08, 2016, 12: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.
legendary
Activity: 938
Merit: 1002
May 08, 2016, 12: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.
sr. member
Activity: 469
Merit: 253
May 06, 2016, 06:47:08 AM
#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.
legendary
Activity: 1624
Merit: 2481
May 06, 2016, 03: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?
sr. member
Activity: 266
Merit: 250
One world One currency, Bitcoin.
May 06, 2016, 02:15:14 AM
#5
The probability is very less but , in past it has happened
https://bitcointalksearch.org/topic/announce-android-key-rotation-271831
Now it rarely occurs.
full member
Activity: 138
Merit: 102
May 05, 2016, 07:41:05 AM
#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
sr. member
Activity: 467
Merit: 267
May 05, 2016, 03:57:35 AM
#3
Just to be clear, that's in addition to having the same message and private key,  right?
staff
Activity: 4284
Merit: 8808
May 05, 2016, 02:49:28 AM
#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.
sr. member
Activity: 467
Merit: 267
May 04, 2016, 11:27:08 PM
#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
Jump to: