Bad signatures leading to 55.82152538 BTC theft (so far)

[bigbeninlondon]

Fine, you never hit "actually zero" if you always must assume the possibility of your code having bugs in it.  But assuming you code properly, a collision from a random number generator having probability X becomes probability 0 if you iterate until you get a unique number for an address based on historical usage.

No, because hardware is not perfect. Keeping the old values around increases the chance that a hardware failure will cause you to use one of them.

Yea, ok, I can see that.  

You have a probability that is so absurdly small on one side that you can't ignore probabilities on the other side just on the grounds that they are very small.

True; for a working package.

If you get to assume the code is proper, why don't I get to assume that a properly-code RNG won't produce collisions?

No, I'm not saying to assume your own code is proper.  My point was that you limit trust in third parties.  Your own code should be verified as well, but you can limit trust on code that you didn't write.

Additionally, this approach places less trust in delivered libraries, which is obviously (according to the topic of this discussion) a good approach.

That's a completely different issue. I agree that it might make sense to do this to protect against a broken RNG

This was my primary point.

Edit: I see that I switched them in my original post.  This one should have come first.

even while it makes no sense to do this to prevent the absurdly improbable collisions from a working RNG.

This was a secondary point that adds value (even if small).

[Kyle91]

55...... Holy shit

[Valle]

That paper says that without /dev/random devices (what is a very rare case I believe) SecureRandom use only 31 bits of entropy. It is a horrible situation, but even in this case it is very unlikely that there will be two equal random numbers in signature creation in the whole world.

[piotr_n]

A forum newbie emailed me and suggested this link would be informative for the thread: http://www.scribd.com/doc/131955288/Randomly-Failed-The-State-of-Randomness-in-Current-Java-Implementations

Yes, that's the document that started it all... and it was published >5 months ago.

Unbelievable

That paper says that [...] SecureRandom use only 31 bits of entropy. It is a horrible situation, but even in this case it is very unlikely that there will be two equal random numbers in signature creation in the whole world.

Maybe. But having only 31 bits of entropy it's very easy to brute force anything. And we have actually seen two equal random numbers cases - many of such pairs are in the block chain, so it's somehow likely after all.

[P_Shep]

I have to say, I'm somewhat disappointed in the devs not checking to ensure that the random number generator they use, actually works properly and assuming it's all OK, given they know how important the randomness is.

[piotr_n]

I have to say, I'm somewhat disappointed in the devs not checking to ensure that the random number generator they use, actually works properly and assuming it's all OK, given they know how important the randomness is.

Only human.
But I guess that gave all of us a very good lesson.

[bitpop]

I say they add even more entropy. Why not have us swipe around the screen a bit during a transaction?

[P_Shep]

I say they add even more entropy. Why not have us swipe around the screen a bit during a transaction?

I think If I were coding this up, I'd add another layer of entropy on top of the system generated number, just to be sure.
A phone's got to have any number of entropy sources... touch screen, signal levels, compass, g-sensor, time, location, light level...

[molecular]

I say they add even more entropy. Why not have us swipe around the screen a bit during a transaction?

I think If I were coding this up, I'd add another layer of entropy on top of the system generated number, just to be sure.
A phone's got to have any number of entropy sources... touch screen, signal levels, compass, g-sensor, time, location, light level...

Such code would clearly belong into the RNG itself. Doesn't sound good to me to try to add more entropy on the application side. Better approach is to make sure the underlying RNG is secure.

This is not (necessarily) the app developers responsibility.

Problem for the app developer is that RNG is usually "native" in the sense that it's provided by OS/java runtime/(js implementation) as probably should be (better access to hardware). In java you can't even be sure which native implementation is chosen and as an app developer you'd have to check them for all target platforms somehow. On linux for example you also can't be sure what's hiding behind /dev/urandom.

If we were playing "pointing fingers", I'd probably point at google or apache in this case, but not Jan, Andreas,...

[bitpop]

Of course no one is blaming the developers

[TierNolan]

I have to say, I'm somewhat disappointed in the devs not checking to ensure that the random number generator they use, actually works properly and assuming it's all OK, given they know how important the randomness is.

It is pretty much the opposite.  Creating your own cryptographic code is highly risky.

The recommendation is to trust the "professionals".

Having said that, adding extra randomness to a RNG can never make things worse.  Ofc, the devs may break that too, but that is less likely.  Most of the complexity is getting the randomness in the first place.

The SecureRandom class even has a method to do that.

secureRandom.setSeed(long seed).

Calling this method can never make things worse.

Well, except in one case (see risk ).

You have to call .nextInt() (or at least to make it generate at least 1 number).

If you don't then it doesn't seed internally.

This code causes the RNG to be seeded only with the given number.

Code:

SecureRandom r = SecureRandom.getInstance(....);

r.setSeed(0x0123456789ABCDEFL);

However, this code causes it to be seeded with its internal seeding system and then have the number as an extra seed.

Code:

SecureRandom r = SecureRandom.getInstance(....);

r.nextInt();

r.setSeed(0x0123456789ABCDEFL);

The 2nd one is always at least as good as the first.

[P_Shep]

Problem for the app developer is that RNG is usually "native" in the sense that it's provided by OS/java runtime/(js implementation) as probably should be (better access to hardware). In java you can't even be sure which native implementation is chosen and as an app developer you'd have to check them for all target platforms somehow. On linux for example you also can't be sure what's hiding behind /dev/urandom.

Which is why the app developer should sprinkle their own magic dust on the numbers, by whatever means.
If the app developer absolutely, positively knows the numbers generated have to be absolutely, positively unique and random, then they should not rely on that which they can't control or fully understand/know. It's an assumption to far for something that is so crucial.

[Abdussamad]

This is called a leaky abstraction:

http://www.joelonsoftware.com/articles/LeakyAbstractions.html

[Valle]

Okay, but what android device doesn't have /dev/random?

[Mike Hearn]

It's actually quite hard to detect if a RNG is working properly. That's one reason there are occasional failures like this. If it were trivial to write a unit test for an RNG I doubt there'd ever be failures. The problem is bad randomness looks almost the same as good randomness.

[Remember remember the 5th of November]

I have to say, I'm somewhat disappointed in the devs not checking to ensure that the random number generator they use, actually works properly and assuming it's all OK, given they know how important the randomness is.

Right, because the -Qt devs ensured their PRNG was working well.

[xenog]

It's reasonable to expect that the RNG will work fine. You entrust cryptography to cryptography experts. It's an abstraction that usually works well, and if you mess with it even for bening purposes, you may end up breaking it.

See what happened to OpenSSH in Debian a few years ago for an example on why usually writing your own crypto or even messing with existing crypto code is a bad idea.

[gmaxwell]

I have to say, I'm somewhat disappointed in the devs not checking to ensure that the random number generator they use, actually works properly and assuming it's all OK, given they know how important the randomness is.

Right, because the -Qt devs ensured their PRNG was working well.

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.

[sebastian]

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.

[gmaxwell]

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.

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