Bad signatures leading to 55.82152538 BTC theft (so far)

[BurtW]

Just some references:

http://developer.android.com/reference/java/security/SecureRandom.html
http://www.cs.cmu.edu/~srini/15-446/android/android-sdk-linux_x86-1.0_r2/docs/reference/java/security/SecureRandom.html

Can someone run the following on the phone?

sr = SecureRandom()
String sr.getAlgorithm()
String sr.getProvider().getName()

and let us know what you find so we know where to look next.
 

[Mike Hearn]

Hello,

A few days ago user Xeno-Genesis alerted us to some weaknesses in the default Android SecureRandom implementation. You guys are on the right lines - SecureRandom isn't. More technical details will come in the following days. For now, please see the following announcement:

http://bitcoin.org/en/alert/2013-08-11-android

[bigbeninlondon]

I think the first step for everyone using the apps in question transfer their funds to a new address that hasn't been used before.

Bad idea, IMO.
You can reveal your key at the very moment when transferring out your funds - if someone intercepts your priv-key-compromising tx while routing it, he can try to spend your cons before you.

I'm pretty sure all the compromised keys have already been robbed, so I'd rather advise to wait for the fix, not moving any coins.

Revealing a key for an address that you should already assume is compromised doesn't sound like a serious issue.  More serious is letting coins sit in an address you should already assume is compromised.

[smolen]

Even with correctly chosen k values, there are still theoretical coin-stealing risks to address reuse.

I saw an odd hint in one of http://en.wikipedia.org/wiki/Nicolas_Courtois publications that some very novel approach is being developed in this area. For me that's enough to start worry.

[BurtW]

Android Security Vulnerability
11 August 2013
We recently learned that a component of Android responsible for generating secure random numbers contains critical weaknesses, that render all Android wallets generated to date vulnerable to theft. Because the problem lies with Android itself, this problem will affect you if you have a wallet generated by any Android app. An incomplete list would be Bitcoin Wallet, blockchain.info wallet, BitcoinSpinner and Mycelium Wallet.

In order to re-secure existing wallets, key rotation is necessary. This involves generating a new address with a repaired random number generator and then sending all the money in your wallet back to yourself. If you use an Android wallet then we strongly recommended you upgrade to the latest version available in the Play Store as soon as one becomes available. Once your wallet is rotated, you will need to contact anyone who has stored addresses generated by your phone and give them a new one.

If you use Bitcoin Wallet by Andreas Schildbach, key rotation will occur automatically soon after you upgrade. The old addresses will be marked as insecure in your address book. You will need to make a fresh backup.

Updates for other wallet apps should be released shortly.

Can you tell us which secure random number generator has the problem and also what exactly is meant by the "repaired random number generator".  Are you installing a new secure random number generator provider?

[Remember remember the 5th of November]

I don't think my application is affected https://bitcointalk.org/index.php?topic=101612 as it uses OpenSSL 1.01e internally, so it should be safe I think. However if it is some Linux API that is responsible, then it might be affected too.

[piotr_n]

Hello,

A few days ago user Xeno-Genesis alerted us to some weaknesses in the default Android SecureRandom implementation. You guys are on the right lines - SecureRandom isn't. More technical details will come in the following days. For now, please see the following announcement:

http://bitcoin.org/en/alert/2013-08-11-android

So Google screwed up.

Can you at least disclose if this is version specific, or is it any Android version that is affected?

[smolen]

Are affected phones based on Qualcomm chipset?

[Mike Hearn]

Anything that uses SecureRandom has issues. Yes, we are using a new provider that overrides the old one:

https://code.google.com/p/bitcoin-wallet/source/detail?r=04d2044880d88107ee4a939a516fb4be4cedeaf9&name=bitcoinj-0.10#

You should not assume that using OpenSSL directly is safe. On Jellybean+ the SecureRandom provider is just a shim over the OpenSSL RAND_* functions and Jellybean+ is also affected. However TLS connections are OK.

I realise there's going to be a lot of questions about what exactly is going on here, but I'm not on the Android team and can't talk on their behalf. It's up to them to document exactly how the RNG is broken. Suffice it to say, if you aren't sure if you're affected, you probably are but you are welcome to send me a private message detailing what you're doing and I'll let you know.

Note that reading from /dev/urandom is OK. The kernel level RNG is not broken.

[jl2012]

If we can't fully trust the random number provided by the system, I wonder if this would help:

Let X_n, for n = 1, 2, 3, ........ be a sequence of random numbers that being used as k for signature

Let Y_n, for n = 1, 2, 3, ........ be a sequence of random numbers generated by the system.

X₁ = Y₁

X_n = SHA256(SHA256(X_n-1)+Y_n), for n > 1

Which means when the first random number is generated by the system, we record its SHA256 hash. The hash will be used as a nonce for the next random random

Therefore, even if Y_n is constant, X_n is still a pseudo-random number guaranteed by SHA256.

[Mike Hearn]

For what it's worth more modern elliptic curve DSA schemes don't use a random number during signing, exactly to try and avoid this kind of problem (though in our case the keys are weak too - crypto can't really survive a weak RNG). As a result signatures are deterministic. I'm not sure if ECDSA with secp256k1 like we use can be upgraded to use such a scheme - if it could be, that's worth doing.

[piotr_n]

I think the first step for everyone using the apps in question transfer their funds to a new address that hasn't been used before.

Bad idea, IMO.
You can reveal your key at the very moment when transferring out your funds - if someone intercepts your priv-key-compromising tx while routing it, he can try to spend your cons before you.

I'm pretty sure all the compromised keys have already been robbed, so I'd rather advise to wait for the fix, not moving any coins.

Scanning code would be rather trivial, but to use it on the fly one have to be powerful miner or have very well connected bitcoin network nodes. After funds arrive at fresh address they can be considered safe. Sitting funds protected by disclosed keys are up to the first person to grab.
I'm not going to exploit this situation, I'll just sit back and enjoy the chaos

Well, after all, considering what we have just learned, that not only the random K value, but also private keys are affected by the broken RNG - moving the coins ASAP to a properly generated address might be a less risky step, indeed.

[Andreas Schildbach]

In case you missed it: I put up beta versions of Bitcoin Wallet with a fixed RNG and key-rotation.

https://bitcointalk.org/index.php?topic=271846.0

[JoelKatz]

If a wallet were to keep track of the k values per address, could that then mitigate these kinds of issues?

If you have an actually working RNG, the chance of picking up the same 256 bit value for a second time is basically zero.

Sure, but keeping track would make "basically zero" into "actually zero".  And since the wallet has your private keys anyway, adding a small dictionary seems trivial and doesn't add any vulnerability.  What's the downside?

No, it wouldn't make it actually zero. You have to consider the possibility that the code that checks has a bug in it, fails due to a hardware problem, and so on. If you account correctly, you may find that the added complexity (especially since now you're keeping the old values around instead of getting rid of them) actually increases the chances of a value being reused.

[bigbeninlondon]

If a wallet were to keep track of the k values per address, could that then mitigate these kinds of issues?

If you have an actually working RNG, the chance of picking up the same 256 bit value for a second time is basically zero.

Sure, but keeping track would make "basically zero" into "actually zero".  And since the wallet has your private keys anyway, adding a small dictionary seems trivial and doesn't add any vulnerability.  What's the downside?

No, it wouldn't make it actually zero. You have to consider the possibility that the code that checks has a bug in it, fails due to a hardware problem, and so on. If you account correctly, you may find that the added complexity (especially since now you're keeping the old values around instead of getting rid of them) actually increases the chances of a value being reused.

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.  Additionally, this approach places less trust in delivered libraries, which is obviously (according to the topic of this discussion) a good approach.  

K must be unique per address per transaction and random.  It is known that most math libraries use PSEUDO-RANDOM generators.  So random is not always guaranteed.  But you CAN guarantee through code that K is unique per address per transaction, even if you cannot guarantee randomness.

[smolen]

a collision from a random number generator having probability X becomes probability 0 if you iterate until you get a unique number

and random number generator becomes random permutation generator

[JoelKatz]

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

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 even while it makes no sense to do this to prevent the absurdly improbable collisions from a working RNG.

[molecular]

Just some references:

http://developer.android.com/reference/java/security/SecureRandom.html
http://www.cs.cmu.edu/~srini/15-446/android/android-sdk-linux_x86-1.0_r2/docs/reference/java/security/SecureRandom.html

Can someone run the following on the phone?

sr = SecureRandom()
String sr.getAlgorithm()
String sr.getProvider().getName()

and let us know what you find so we know where to look next.
 

found the info that android uses apache harmony implementation:

BTW: The Android implementation is the one from Apache Harmony project. The main implementation is in the file org.apache.harmony.security.provider.crypto.SHA1PRNG_SecureRandomImpl.

EDIT: this might be the implementation (not sure, though): https://android.googlesource.com/platform/libcore-snapshot/+/ics-mr1/luni/src/main/java/org/apache/harmony/security/provider/crypto/SHA1PRNG_SecureRandomImpl.java

[gmaxwell]

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

[Andreas Schildbach]

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.