Topic: Bad signatures leading to 55.82152538 BTC theft (so far) - page 3. (Read 65144 times)

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)

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

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.

It doesn't affect anything other than Bitcoin?

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".

Blockchain is more attractive target than Hirsch index

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?

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)

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.

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.

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?

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.

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?

No you don't.

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.

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.

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?

You understand incorrectly. If K is known a single signature can recover the private key.

But if nonce is selected as "sha256(message||privkey||random value)", you actually don't need a random value.
You can use a simple static 256 bit counter. That would gurantee that no value is ever reused.



What i understand, it does not matter if anyone can guess the nonce, the privkey can ONLY be recovered if 2 signatures share the same nonce.

If then, the counter value could even be published in the transaction, so if multiple clients share the same wallet, they still don't generate conflicting nonces. (The client only search backwards until it reach one of its own transactions, increments that counter with +1 and then signs it own transaction.

I'm not sure if you're being snarky here or what. But I personally, and several other people (e.g. I'm aware of jrmithdobbs testing it pretty extensively too) have checked the RNG used in the reference code.  It's really easy to break (EC)DSA with a bad RNG at runtime and that makes me paranoid (e.g. my minor contribution to a netbsd security advisory).  That isn't to say that any particular flaw might not have gone unnoticed, especially a racy, platform specific, or library version specific issue— go link bitcoind/qt against some some novely broken openssl and all bets are off.

Without knowing all the details here it's hard to do retrospective analysis with the benefit of hindsight to say if something could better have been done here with the android wallets.  The one point I'm aware of is that I think back in January we had some evidence that some bitcoinj users may have had poor nonce entropy, but I think this was chalked up to old bad android. Perhaps in hindsight more exploration should have been done of that issue, or more proactive monitoring of the amount of R reuse.