Bitcoin Forum

Hello,

i red about the flaw with reused R values in the signature of a transaction.

And i wonder if it possible that the private key is exposed when someone signs the same message with the same private key.

This message was too old and has been purged

Remember algebra?

x + 5 = 8
Solve for x... 3 right?

What about:
x + y + 5 = 23

.... you can't tell me... can you?

However, if I told you that the SAME X and SAME Y could ALSO BE THE FOLLOWING:
x - y + 6 = 8

then you can do:
(x + y + 5) - (x - y + 6) = (23) - ( 8 )
2y - 1 = 15
2y = 16
y = 8
x - 8 + 6 = 8
x = 10

So in order to solve an equation with 2 variables you need 2 different equations that fulfill the variables. 3 for 3... 4 for 4... so on so on.

Now, signatures are just a formula that generates 2 values, r and s.

r = R.x = k x G
(where G is the generator point of the secp256k1 curve... so it is known) (R is the point gained by multiplying them, and r is that point's x value on the coordinate plane)

s = (k^-1) x (z + dr) mod N
(where k and r are from the r equation (so the same), z is the message being signed's hash, d is the private key, and N is the order of the curve (constant) )

if we see the same r value for 2 DIFFERENT transactions: (Where we know d and r are the same... AND WE KNOW k IS THE SAME since r = k x G and G never changes)
s1 - s2 = ((k^-1) x (z1 + dr)) - ((k^-1) x (z2 + dr)) mod N
s1 - s2 = (k^-1)z1 + (k^-1)dr - (k^-1)z2 - (k^-1)dr mod N
s1 - s2 = (k^-1)z1 - (k^-1)z2 mod N
k = (s1 - s2)^-1 x (z1 - z2) mod N

Since we know s1, s2 (they are in the signatures of the 2 transactions) and z1, z2 (they are the transactions themselves) we now know k.

so now we plug in:
s = (k^-1) x (z + dr) mod N
s x k = z + dr mod N
sk - z = dr mod N
d = (r^-1) x (sk - z) mod N

Since we know s, z, and r from the signature and transaction, and learned k from the solution above, we can calculate the private key.

So basically, the k value will give away your private key, and using the same r value (which means using the same k value) for two different z (transactions) allows it all to crumble down.

The solution to this is to make the k value DEPENDENT on the transaction AND the private key.

so if we generate k by performing Hash(z + d) and using that hash, if the z changes, the k WILL HAVE TO CHANGE AS WELL. same thing with if you use a different private key for a different address. because the thing being hashed will always change when the transaction changes or the private key changes, we can know that the same r value for two different transactions is impractical.

This was a very helpful way to mathematically show this.

Thank you for this.

This is why k is usually a large (~256 bit) cryptographically secure random number when creating ECDSA signatures. If the random number generator is working properly there's a very low chance of using the same k twice. It would be about the same chance as guessing a private key which has been used by someone else.

Do you think making k deterministic is better than using a random number ? I heard this is something to avoid.

I know bad random number generators or a complete lack of randomness (sony incident) have created issues leading to key exposure in the past and continue to do so.

making a k that relies on z and d will create a formula that can NEVER be solved for k.

Imagine:

r = R.x = (d+z)G
s = (k^-1)(z + dr) mod N

The weakness of using the same r value with the same private key AND different messages? Impossible. Why?

Because if you change the message z your r will ALWAYS be different. BECAUSE it is used to calculate k, AND it is mixed with an already unknown so no one can predict k. (your private key)

if you just used d as k, the r value would be the same as the x value in your pubkey and you'd be outed, as d = (z)((s - r)^-1) mod N
if you just used z as k, then anyone who saw the message would be able to calculate your key if they picked up on it. (though it might be harder to notice such a vulnerability)

However, by using a combination of both... (please follow RFC6979 and don't just add them together) there is no possible way to solve for k, and as long as the private key remains private, no way for an outside observer to calculate k.

This is why Trezor uses RFC6979 to generate k values. Because there is not enough randomness on such a small device. So it relies on math to guarantee the k is different every time.

nice explanation but would be clearer if x is not used to represent multiplication and variable

Thanks for breaking my brain.

The short answer to the original question is that signing the same message twice is not a problem.

Slightly longer answer:

If the k value is reused (in fact RFC6979 and every other deterministic scheme does this) you get exactly the same signature and an attacker learns nothing new from the second signature.  This is one of the few cases where reusing the k value (and therefore r) is not a problem.

If the k values in the signatures are random and independent from each other then ECDSA should be secure.

Only, if the k values are not random or not independent (e.g. first k is random, second is k+1), then the private key can be computed.  The same is also true if you sign two messages that differ. 

@Evil-Knievel: if you sign a transaction that has several inputs with the same address, the signed messages are still different since the signing algorithm takes the position of the input to be signed into account.

Are you sure about this?  I thought I read otherwise, but I might be thinking of something else.



This doesn't sound right at all.  Can you provide a link to a source that describes how the position of the input effects the resulting signature?

Yes, as @dabura explained, the main point comes from the definition of s = (z+dr)/k: 1 equation, 2 unknowns (d and k). Therefore an infinite number of solutions. If you add another signature, you now have 2 equations and 3 unknowns (d, k1, k2). BUT if you happen to have a relation between k1 and k2, now you can solve it. It's trivial if k1=k2, just a bit harder if k2 = k1 + 1.

When you sign the tx, you replace part of the tx with the previous pubscript and blank out the other scripts. So if you do that for the 1st txin, the resulting tx to sign is different than if you do it for the 2nd...

Grrr, hhanh00 was faster.  He wrote essentially the same...


Of course, you need to detect the dependency. E.g., by noticing that R_2 = R_1 + G.

If you can guess some linear dependency between k_1 and k_2, you have three linear equations (two from the two signatures and the dependency), so you can solve these equations to recover the unknowns k_1, k_2 and the private key d.


I simplified a bit.  The signing algorithm replaces the input script of the input that is signed with the output script of the spent transaction and replaces all other input scripts by the empty script.  See OP_CHECKSIG. This will give different messages for different inputs.

Here is an example: although the r values are the same the s values differ because the messages differ.
https://blockchain.info/tx/6c2d0bbb87350cd18d93ede269817767b84715a6292a022c68b327f704ce486f

@johoe: sorry, didn't want to steal your post. I waited 30mn :)

Just a precision - doesn't have to be linear, any algebric equation between the k and you are good to go.

To add a fun fact, during the blockchain.info problem before I analyzed the RNG, I had noticed that there were twelve signatures involving six different k values and six different private keys, that my script could not break.  So k1 occured only with key d1 and d2, k2 with d2 and d3 and so on until k6 occured with d6 and d1.  This is breakable since these are twelve unknowns and twelve linear equations. I pondered whether I should implement a general linear equation solver just to break these keys, but it looked like a lot of effort just to break six additional keys.

Now this is moot, since by breaking the RNG I could break all keys.

Well, not really. Any non trivial algebraic equation relating k1 to k2 or vice versa.

Example:

Transaction:
5fcc0caeeedf3dcbfd72cf2ce01a32483191245bcc8b485a17f44416afffa1cf

Bitcoin Address:
1JoktQJhCzuCQkt3GnQ8Xddcq4mUgNyXEa


Q:
4972230932324498687212571124350031945292560402225635576575099731139372812950
90093163538124512621582638381287400742297296142742631973794490465505627039656

R1:
92627733765912716076593330327472060525510143496912551296551330375234442403667
52672529767396296781670694918936339003252868214635233297377470505896759805121

R2:
21777747090873872412507702170118124079689680605286211413831315675958103980165
28550945344342225460119170436294446323534473486342579588757092209276196855835

=====================================================================================

Equation 1:
107386812206192895604609907534734551733750359009209085407402092094681165309221(G) +
73497042855564472242350639786242013786650258073778360848595089035161389788260(Q) = R1

=====================================================================================

Equation 2:
103638365080811145359708265527675914061630653196238299508298055558291984536938(G) +
90408099859559077857588671187578958541865517554215233387265259275631437140896(Q) = R2

======================================================================================

Relation:
48201704517020160076565286692925062647683650448021018660686086720974054945943(G) +
94978595896780763074840294256755498914029806222047734373636501931687337209395(R1) = R2