Bad signatures leading to 55.82152538 BTC theft (so far)

[sebastian]

gmaxwell: how? I Think I misused the term "nonce" in my previous text, I mean the random value that is used in nonce calculation, that may not be reused.

If nonce is selected as sha256(message||privkey||R), and you can guess R, you would still need the message (known) and the privkey (secret) to compute the privkey?
so it would be a moment 22 for the attacker?

So then, solving for the private key when one msg is signed with sha256(message||privkey||R) and the other is signed with sha256(message||privkey||R+1), would be impossible unless you can break sha256 in a way allowing solving for privkey?


The flaw here was that if 2 R's was equal, you wouldn't need to compute the unknown value, like solving 2 equations with a unknown, but equal solution X.


Or is it something I have missed?

[1714771736]

1714771736

[1714771736]

1714771736

[1714771736]

1714771736

[gmaxwell]

gmaxwell: how? I Think I misused the term "nonce" in my previous text, I mean the random value that is used in nonce calculation, that may not be reused.
So then, solving for the private key when one msg is signed with sha256(message||privkey||R) and the other is signed with sha256(message||privkey||R+1), would be impossible unless you can break sha256 in a way allowing solving for privkey?

Okay, it wasn't clear that you were still assuming the H(message||private||). Technically you can leave the "R" in that out entirely. The deterministic secret K is fine as far as anyone knows. However, it violates FIPS. So would your counter. For some things people care about this.

[sebastian]

The thing that affects is then that if 2 identical transactions are posted, (same amount and same input and output) then you reveal your privkey.

So I Think that its what happened in android here, identical transactions (m1 == m2) + identical privkey (k1 == k2) and bad RNG (R1 == R2) causes system to generate identical nonces. since sha256(m1||k1||R1) == sha256(m2||k2||R2) if m1 == m2, k1 == k2 and R1 == R2.

if R is then a simple counter, it gurantees against bad RNGs.


Maybe a better idea:

Make nonce be: sha256(message||privkey||random||counter), and "counter" is stored locally.
If RNG is bad/frozen/behaving strange/reusing random numbers, then counter will prevent same nonce from be reused, since its incremented for each transaction, and stored locally.

counter does not need to be published or stored centrally, since its extremely unlikely that 2 RNGs in 2 different clients, generate the same random number for the same transaction, even if the RNGs are extremely bad.

[gmaxwell]

The thing that affects is then that if 2 identical transactions are posted, (same amount and same input and output) then you reveal your privkey.

No you don't.

[sebastian]

gmaxwell:
Then, what causes the privkey to be revealed? (What this thread is about)

What I have understand, is that if the nonce are reused in a ECDSA signature, the privkey can be calculated, given that you know that the 2 nonces are equal, even if the nonce is unknown, since you simply solve a equation to get the privkey?

since nonce = sha256(message||privkey||random), this means, for nonce to be equal in 2 signatures, message must be identical, privkey must be identical, and the random value must be identical.
So when the bad RNG reuses a random value, for a identical transaction, the privkey can be calculated?

[gmaxwell]

gmaxwell:
Then, what causes the privkey to be revealed? (What this thread is about)
What I have understand, is that if the nonce are reused in a ECDSA signature, the privkey can be calculated, given that you know that the 2 nonces are equal, even if the nonce is unknown, since you simply solve a equation to get the privkey?

Two things can happen,  given two distinct messages with the same unknown K you can recover K, or Given K you can recover the private key.  (also, knowing fairly small amounts of K in several signatures can also allow you to recover the key through more complicated techniques)

If the nonce is H(message||secret)  then if you have identical data being signed you will get a completely identical signature and learn nothing (otherwise I could crack any key by just writing another copy of the same transaction down! ).  If you have non-identical data being signed you will have non identical nonces.

[sebastian]

now I understand fully...

I misintepreted your post in the beginning of the thread, that the CURRENT technology was that nonce was generated as sha256(message||privkey||Random).
And that had been "cracked" due to bad RNGs.


So if I understand your correctly, the developers have did just nonce = Random_value, where Random_value come from a bad RNG?

[gmaxwell]

So if I understand your correctly, the developers have did just nonce = Random_value, where Random_value come from a bad RNG?

Correct! (and this is what is normally described, e.g. FIPS DSA, so the developers can hardly be blamed).

The idea of making the nonce H(message||secret||random) is to just armor against bad RNGs without making K non-random, though it doesn't need to be non-random— it just need to be secret and distinct per message.

[smolen]

Maybe a better idea:
Make nonce be: sha256(message||privkey||random||counter), and "counter" is stored locally.

That's a resonable emergency workaround for broken RNG, but in the long run it will make Bitcoin weaker. Such postprocessing of random value is not fixing RNG (it's work is done when random is generated), it's part of new, modified in ad-hoc way ECDSA algorithm. While the original one is (reasonably) well studies by a lot of researchers, new algorithm will not attract enough research.
Using counter ties together two sign acts that are supposed to be independent.
This new algorithm uses message and privkey twice, if you look at ECDSA as a huge system of boolean equations (OK, such view is a bit crazy ) adding sha256(message||privkey ...) to established ECDSA brings in more equations than variables, thus making XSL-style attack a bit easier.

[gmaxwell]

thus making XSL-style attack a bit easier.

I look forward to your paper, as I'm sure DJB would as well.   (Though sure, if you're not going to go all the way to a deterministic signature, might as well use lots of randomness instead of a counter)

[TiagoTiago]

Given the recent NSA leaks, is it possible the flaw was put there on purpose to make it easier for them to spy on people?

[smolen]

thus making XSL-style attack a bit easier.

I look forward to your paper, as I'm sure DJB would as well.

Blockchain is more attractive target than Hirsch index

[sebastian]

TiagoTiago: No. Revealing or breaking ECDSA in bitcoin does not help anything to reveal anyone's identitity, worse, it would make it even harder to track since 2 users of same wallet make it harder to correlate who owns the wallet.
The anonymity lies in that the correlation between the wallet and the user is unknown. The anonymity is NOT dependant of the secrety of the private key.

The only thing that is dependant of the secrety of the private key, is the safety and ownership of the coins. Eg, if the private key leaks, someone can steal your coins, but nobody can reveal your identity.



smolen: Given that SHA256 is fully safe, the resulting number can be seen as a random value itself. Its not possible to solve for anything in SHA256, since SHA256 is essentially a modulus function, and a modulus function has unlimited number of inputs for a given output.
So a such change is safe. And its not possible to get the counter value and correlate transactions, even if the privkey is stolen. Not even if you know the latest counter value (eg if someone's device is stolen) , since the random value is unknown.
And as you know, there is larger problems than correlated transactions, if the private key is stolen.


So lets implement the change Nonce: sha256(message||privkey||random||counter), that would make the system 100% guranteed safe.
That could be part of the bitcoin specification, so all coders that write a bitcoin client automatically do this by "default".

[TiagoTiago]

It doesn't affect anything other than Bitcoin?

[molecular]

It doesn't affect anything other than Bitcoin?

I've been asking myself this question, also.

Also I still don't know exactly what are the circumstances that have to be met by the environment on the phone for the RNG to produce low-entropy (how low?) random numbers.

It seems to me if these circumstances are met, other apps using SecureRandom would be affected also.

[TiagoTiago]

And wouldn't that expose data encrypted by other apps to similar security issues?

[kuzetsa]

and people keep telling me my brainwallet probably doesn't have enough entropy because a human made up the passphrase... ;-)

Thanks for reminding me...

I'm going to make available a few mirrors of the brain wallet generator I plan to use:

https://www.bitaddress.org/

XKCD recently demonstrated in a charming little coming that getting a few bits of entropy isn't even that hard:

XKCD: password strength (correct horse battery staple)

[smolen]

The small and subtle difference between

is fully safe

Its not possible to solve

such change is safe

its not possible to get

100% guranteed safe

and "based on established expert consensus and published research results Bitcoin can be considered reasonably safe for the foreseeable future" can become something like 1,294,195,554 USD

[bitpop]

Some say there is no difference between "complete" and "finished".

Judges.. Please explain the difference in a way that is easy to understand.

His response was: When you marry the right woman, you are "complete". If you marry the wrong woman, you are "finished". And, when the right one catches you with the wrong one, you are "completely finished".

[JoelKatz]

And wouldn't that expose data encrypted by other apps to similar security issues?

No. The issue has nothing to do with exposing encrypted data but with signatures exposing private keys.