11 ms·

Android RNG Weakness Renders Bitcoin Wallets Insecure

166 points by VMG 13y ago

VMG 13y ago
discussion on bitcointalk.org: https://bitcointalk.org/index.php?topic=271486.0 https://bitcointalk.org/index.php?topic=271486.0 blogpost about weakness in java.security.SecureRandom: http://armoredbarista.blogspot.com.au/2013/03/randomly-failed-weaknesses-in-java.html http://armoredbarista.blogspot.com.au/2013/03/randomly-faile...
- Buge 13y ago
  That second link doesn't seem to be the current problem. The current problem is that the same random number is being returned more than once.
  - VMG 13y ago
    On the other hand, the author of the Bitcoin Wallet Android app thinks it's a SecureRandom problem: https://code.google.com/p/bitcoin-wallet/source/detail?name=bitcoinj-0.10&r=04d2044880d88107ee4a939a516fb4be4cedeaf9# https://code.google.com/p/bitcoin-wallet/source/detail?name=...
    - Buge 13y ago
      Yeah but the current problem with SecureRandom is that it returns the same random number more than once. That armoredbarista page only describes cases where the numbers are less random than they should be, not that they are returned multiple times.
    - lwf 13y ago
      That commit series doesn't actually appear to use the new class, besides initialising it. Simply initialising it is insufficient, because you need to call addProvider() (cf. https://developer.android.com/reference/java/security/Security.html https://developer.android.com/reference/java/security/Securi... ) to actually have any effect.
      - gojomo 13y ago
        The LinuxSecureRandom class has a 'static initializer' block, which will run as soon as the class is loaded. (That is, triggered by the reference and initialization call, but just before.) It purports to install LinuxSecureRandom as a new systemwide default (LinuxSecureRandom, lines 56-57).
LAMike 13y ago
this could be a big blow to Bitcoin adoption... Is this a part of Android that can't be touched by anyone but Gooogle? Or is it a piece of software that can be improved upon by open source devs?
- nwh 13y ago
  They can use /dev/random if they so choose.
- javert 13y ago
  I don't think it's a very big deal. For the most part, people who use bitcoin now are still very early adopters and are techies. Also, IMHO, it would be idiotic to have significant bitcoin value stored on an Android phone, and very few people (if anyone) would do that.
  - Buge 13y ago
    People are saying it's a problem with Android's SecureRandom implementation. That would be a pretty big problem if it returns repeated random numbers. But it seems strange that such a large obvious problem would make it into Android. The other explanation is that Android bitcoin developers are all implementing it incorrectly and either don't realize it or are trying to push the blame somewhere else.
    - jadeddrag 13y ago
      It is very likely that the bitcoin community would be the first to stumble onto a crypto bug in SecureRandom. Google should thank that community for their discovery.
      - makomk 13y ago
        Extremely likely, in this case. It looks like the way it was discovered is that various people have set up bots to take Bitcoins from transactions with repeated r values, and they took coins from Android Bitcoin clients that on paper were doing everything right.
lcedp 13y ago
Does it concerns only Bitcoin wallets? What about other encryption under Android - like files, etc?
- tptacek 13y ago
  This is a Bitcoin software implementation bug, and an illustration of why you should use your OS's CSPRNG (here, /dev/random) to the exclusion of any other RNG.
  - gwillen 13y ago
    As far as I know that is NOT correct. The wallets in question were all -- to my knowledge -- using the Android platform-provided Java SecureRandom generator.
    - tptacek 13y ago
      If the story here is that Java SecureRandom on Android is bad enough to break DSA, the headline on this story is wrong; it should be something more like "Android Doomed". Can you provide a link to something corroborating this?
      - VMG 13y ago
        Well there is this paper: http://www.scribd.com/doc/131955288/Randomly-Failed-The-State-of-Randomness-in-Current-Java-Implementations http://www.scribd.com/doc/131955288/Randomly-Failed-The-Stat... Quote: > Apache Harmony revealed multiple weaknesses caused by implementation bugs. As a part of Android a plethora of cryptographic functions [17] rely on this PRNG. One of the bugs addresses directly the Android platform, where as the second one only targets Apache Harmony.
        tptacek 13y ago
        The bug described here isn't sufficient to generate repeated DSA k-values, even if it is still in the code†, which is unlikely. It seems more likely that the application code used SecureRandom insecurely, as described upthread. † It's virtually certain not to be in the code, since Android's CSPRNG is based on OpenSSL now, not Harmony's built-in CSPRNG.
tptacek 13y ago
Iä! Digital Signature Algorithm! The Black Goat of the Woods with a Thousand Crypto Bugs! I don't know the Bitcoin software involved at all, but I can sketch out an attack that might shed some light on it, and, more importantly, instill an appropriate fear of DSA into you: To generate a DSA key, you come up with primes p and q and a generator g, which process is a paralytic non-Euclidian brain injury I will not attempt to describe. Then you do like Diffie Hellman: generate a random private key x and from it a public value y = g^x % p. The pubkey that validates signatures is the tuple (p, q, g, y). To sign, you generate a random k value, which must never be reused, Iä! Iä! never, and: r = g^k % p % q s = k^-1 (H(m) + x•r) % q The signature is (r, s). If ever you should fail to heed these words and generate two signatures with the same k value, Iä Cthulhu Ftaghn! then simple high school algebra can be used to beat DSA. The attacker doesn't even need to know what the k was, and the attack is so fast you can just try it to see if k was repeated (I skipped the algebra and just dumped the formulas for the attack here): H(m1) - H(m2) k = ------------- S1 - S2 x = ((S1•k) – H(m1))• r^-1 % q This bug (also in an ECDSA implementation) is what broke the Playstation 3, too. You see that comment on the Bitcoin thread about the repeated r-values; a repeated r-value (r as in the r parameter of a DSA signature) just tells you that someone repeated a k. Iä! Iä!
- patio11 13y ago
  For folks wondering -- why yes, you can scan the entire blockchain for repeated k values. It's about O(n^2) for an N so small as to be effectively constant (n = outgoing transactions per address), and will be dominated by the time it takes you to actually download the blockchain.
  - gojomo 13y ago
    ...which appears to be how the problem was brought to public attention. Someone was draining balances held by keys so compromised, within a few hours after the repeated 'random' value. So anyone new jumping on this would have to race the one or more existing exploiters.
- pbsd 13y ago
  Lest we think everything's lost, Thomas Pornin's RFC to fix (EC)DSA's need for good randomness when signing was published this month [1]. The approach is similar to Dan Bernstein et al's EdDSA. [1] http://tools.ietf.org/html/rfc6979 http://tools.ietf.org/html/rfc6979
DanBC 13y ago
I always wonder if some people are watching announcements to try to grab unsecured bitcoins before other people implement fixes?
- runeks 13y ago
  The reason it was discovered in the first place was that coins were suddenly disappearing from wallets. So it's very likely that someone has already set up a bot that scans new transactions from the same address for repeating r values.
acqq 13y ago
Seems that some invocations of SecureRandom were able to always get the same result. http://blog.kchandrahasa.com/blog/2013/08/09/android-4-dot-2-and-javax-dot-crypto-dot-badpaddingexception-pad-block-corrupted/ http://blog.kchandrahasa.com/blog/2013/08/09/android-4-dot-2... However I've read somewhere that now apparently even Android 4.2 is affected which would mean there's something more? Whoever knows more, please write more technical details.
- tjohns 13y ago
  To be specific, since I spent a lot of time on that bug... Older versions of Android's SecureRandom could return the same value if (a) you were manually seeding SecureRandom and (b) no prior crypto operations were performed on that SecureRandom instance before seeding, There was some (very) bad advice circulating on blogs which advised using this technique to generate local encryption keys from a seed, in order to obfuscate the key. This was fixed in Android 4.2 when we switched from BouncyCastle to OpenSSL as the underlying crypto provider. I don't know why you'd still be seeing this on Android 4.2, but you shouldn't be doing this anyway. SecureRandom is seeded by the system. Manually seeding it is a bad idea. (And trying to force deterministic output from is a very bad idea.) There's a blog post I wrote which goes into a bit more detail: http://android-developers.blogspot.com/2013/02/using-cryptography-to-store-credentials.html http://android-developers.blogspot.com/2013/02/using-cryptog... The linked article is a bit light on details, so I don't know if this is what they were doing or not. I doubt it though, since that would have meant they were seeding SR with the same value, and I'd like to believe the Bitcoin devs wouldn't make that mistake.
  - andrewcooke 13y ago
    the linked article was using deterministic output from an explicitly seeded PRNG as a key. it broke with openSSL which uses setSeed only to augment, not replace, state (as you know, just being complete). so i don't think the parent link explains the current issue.
filipmaertens 13y ago
At blog post https://cryptocow.com/?p=201 https://cryptocow.com/?p=201 we've been experimenting with using sensors to upgrade PRNG's, and we frankly can't understand why this isn't been used natively in Android RNG implementations... It's trivial, easy and tremendously increases the RNG quality.
- tptacek 13y ago
  Because a sensor provides an entropy source, not a whole CSPRNG. Most modern CSPRNGs have interfaces to feed entropy into the system, but CSPRNG designs do more than simply route entropy from one place to another. This is a really common misconception people seem to have about cryptographic random number generation, and a topic Ferguson and Schneier do an extremely good job breaking down in _Cryptography Engineering_.
kllrnohj 13y ago
Android's SecureRandom uses BouncyCastle prior to 4.2 and OpenSSL in 4.2+ ( http://android-developers.blogspot.com.au/2013/02/security-enhancements-in-jelly-bean.html http://android-developers.blogspot.com.au/2013/02/security-e... ) It'd be interesting to know what the bug is and if that bug affects Bouncy Castle and/or OpenSSL as well, or if Google screwed up the glue code somehow
- sirk390 13y ago
  This is the paper referenced in the bitcointalk thread: http://www.scribd.com/doc/131955288/Randomly-Failed-The-State-of-Randomness-in-Current-Java-Implementations http://www.scribd.com/doc/131955288/Randomly-Failed-The-Stat.... See section 5.4 for Bouncy Castle: Weaknesses/Quality of Entropy Collectors.
0x0 13y ago
Could this affect stuff like ssh key generation or HTTPS traffic on Android, as well?
dobbsbob 13y ago
I use the feudal security of blockchain.info wallets w/2FA on android since phones tend to get lost, stolen or fubard
mikeash 13y ago
Looks like a terrifyingly buggy SecureRandom implementation that results in only 31 bits of entropy when seeding: http://armoredbarista.blogspot.com.au/2013/03/randomly-failed-weaknesses-in-java.html http://armoredbarista.blogspot.com.au/2013/03/randomly-faile...
- tptacek 13y ago
  As I understand it, Android doesn't use Harmony's CSPRNG. But maybe it did in an earlier version? Maybe that's the problem?
oakwhiz 13y ago
Would it be possible to design Android Bitcoin wallets to consume their entropy from a file on your SD card? You could just periodically refill the entropy from another device that you trust.
mydpy 13y ago
Can anyone reference me to an article that explores a technical analysis of how their random number generator was exploited? Did it not have full coverage (read: RANDU style error) or otherwise? http://www.pnas.org/content/61/1/25.full.pdf+html http://www.pnas.org/content/61/1/25.full.pdf+html
- mydpy 13y ago
  Actually, I found it here. Pretty interesting issue, I recommend the read. I'll summarize the paper here: Java implementations primarily used on lightweight mobile platforms have a method called SecureRandom which generates pseudo random numbers for cryptographic operations. The integrated seed generator on some platforms provides a systematic means of determining the seed value and predicting seemingly secure outputs. http://www.scribd.com/doc/131955288/Randomly-Failed-The-State-of-Randomness-in-Current-Java-Implementations http://www.scribd.com/doc/131955288/Randomly-Failed-The-Stat...
  - glurgh 13y ago
    Yes but that's not the problem being reported.
swayvil 13y ago
Why don't we have a real rng in our computing devices? It appears to be a trivial bit of electronickry. I'm talking about one of those little quantum event listener thingies. http://en.wikipedia.org/wiki/Hardware_random_number_generator http://en.wikipedia.org/wiki/Hardware_random_number_generato...

166 points by VMG 13y ago

VMG 13y ago

discussion on bitcointalk.org: https://bitcointalk.org/index.php?topic=271486.0 https://bitcointalk.org/index.php?topic=271486.0 blogpost about weakness in java.security.SecureRandom: http://armoredbarista.blogspot.com.au/2013/03/randomly-failed-weaknesses-in-java.html http://armoredbarista.blogspot.com.au/2013/03/randomly-faile...

Buge 13y ago
That second link doesn't seem to be the current problem. The current problem is that the same random number is being returned more than once.
- VMG 13y ago
  On the other hand, the author of the Bitcoin Wallet Android app thinks it's a SecureRandom problem: https://code.google.com/p/bitcoin-wallet/source/detail?name=bitcoinj-0.10&r=04d2044880d88107ee4a939a516fb4be4cedeaf9# https://code.google.com/p/bitcoin-wallet/source/detail?name=...
  - Buge 13y ago
    Yeah but the current problem with SecureRandom is that it returns the same random number more than once. That armoredbarista page only describes cases where the numbers are less random than they should be, not that they are returned multiple times.
  - lwf 13y ago
    That commit series doesn't actually appear to use the new class, besides initialising it. Simply initialising it is insufficient, because you need to call addProvider() (cf. https://developer.android.com/reference/java/security/Security.html https://developer.android.com/reference/java/security/Securi... ) to actually have any effect.
    - gojomo 13y ago
      The LinuxSecureRandom class has a 'static initializer' block, which will run as soon as the class is loaded. (That is, triggered by the reference and initialization call, but just before.) It purports to install LinuxSecureRandom as a new systemwide default (LinuxSecureRandom, lines 56-57).

LAMike 13y ago

this could be a big blow to Bitcoin adoption... Is this a part of Android that can't be touched by anyone but Gooogle? Or is it a piece of software that can be improved upon by open source devs?

nwh 13y ago
They can use /dev/random if they so choose.
javert 13y ago
I don't think it's a very big deal. For the most part, people who use bitcoin now are still very early adopters and are techies. Also, IMHO, it would be idiotic to have significant bitcoin value stored on an Android phone, and very few people (if anyone) would do that.
- Buge 13y ago
  People are saying it's a problem with Android's SecureRandom implementation. That would be a pretty big problem if it returns repeated random numbers. But it seems strange that such a large obvious problem would make it into Android. The other explanation is that Android bitcoin developers are all implementing it incorrectly and either don't realize it or are trying to push the blame somewhere else.
  - jadeddrag 13y ago
    It is very likely that the bitcoin community would be the first to stumble onto a crypto bug in SecureRandom. Google should thank that community for their discovery.
    - makomk 13y ago
      Extremely likely, in this case. It looks like the way it was discovered is that various people have set up bots to take Bitcoins from transactions with repeated r values, and they took coins from Android Bitcoin clients that on paper were doing everything right.

lcedp 13y ago

Does it concerns only Bitcoin wallets? What about other encryption under Android - like files, etc?

tptacek 13y ago
This is a Bitcoin software implementation bug, and an illustration of why you should use your OS's CSPRNG (here, /dev/random) to the exclusion of any other RNG.
- gwillen 13y ago
  As far as I know that is NOT correct. The wallets in question were all -- to my knowledge -- using the Android platform-provided Java SecureRandom generator.
  - tptacek 13y ago
    If the story here is that Java SecureRandom on Android is bad enough to break DSA, the headline on this story is wrong; it should be something more like "Android Doomed". Can you provide a link to something corroborating this?
    - VMG 13y ago
      Well there is this paper: http://www.scribd.com/doc/131955288/Randomly-Failed-The-State-of-Randomness-in-Current-Java-Implementations http://www.scribd.com/doc/131955288/Randomly-Failed-The-Stat... Quote: > Apache Harmony revealed multiple weaknesses caused by implementation bugs. As a part of Android a plethora of cryptographic functions [17] rely on this PRNG. One of the bugs addresses directly the Android platform, where as the second one only targets Apache Harmony.
      - tptacek 13y ago
        The bug described here isn't sufficient to generate repeated DSA k-values, even if it is still in the code†, which is unlikely. It seems more likely that the application code used SecureRandom insecurely, as described upthread. † It's virtually certain not to be in the code, since Android's CSPRNG is based on OpenSSL now, not Harmony's built-in CSPRNG.

tptacek 13y ago

Iä! Digital Signature Algorithm! The Black Goat of the Woods with a Thousand Crypto Bugs! I don't know the Bitcoin software involved at all, but I can sketch out an attack that might shed some light on it, and, more importantly, instill an appropriate fear of DSA into you: To generate a DSA key, you come up with primes p and q and a generator g, which process is a paralytic non-Euclidian brain injury I will not attempt to describe. Then you do like Diffie Hellman: generate a random private key x and from it a public value y = g^x % p. The pubkey that validates signatures is the tuple (p, q, g, y). To sign, you generate a random k value, which must never be reused, Iä! Iä! never, and: r = g^k % p % q s = k^-1 (H(m) + x•r) % q The signature is (r, s). If ever you should fail to heed these words and generate two signatures with the same k value, Iä Cthulhu Ftaghn! then simple high school algebra can be used to beat DSA. The attacker doesn't even need to know what the k was, and the attack is so fast you can just try it to see if k was repeated (I skipped the algebra and just dumped the formulas for the attack here): H(m1) - H(m2) k = ------------- S1 - S2 x = ((S1•k) – H(m1))• r^-1 % q This bug (also in an ECDSA implementation) is what broke the Playstation 3, too. You see that comment on the Bitcoin thread about the repeated r-values; a repeated r-value (r as in the r parameter of a DSA signature) just tells you that someone repeated a k. Iä! Iä!

patio11 13y ago
For folks wondering -- why yes, you can scan the entire blockchain for repeated k values. It's about O(n^2) for an N so small as to be effectively constant (n = outgoing transactions per address), and will be dominated by the time it takes you to actually download the blockchain.
- gojomo 13y ago
  ...which appears to be how the problem was brought to public attention. Someone was draining balances held by keys so compromised, within a few hours after the repeated 'random' value. So anyone new jumping on this would have to race the one or more existing exploiters.
pbsd 13y ago
Lest we think everything's lost, Thomas Pornin's RFC to fix (EC)DSA's need for good randomness when signing was published this month [1]. The approach is similar to Dan Bernstein et al's EdDSA. [1] http://tools.ietf.org/html/rfc6979 http://tools.ietf.org/html/rfc6979

DanBC 13y ago

I always wonder if some people are watching announcements to try to grab unsecured bitcoins before other people implement fixes?

runeks 13y ago
The reason it was discovered in the first place was that coins were suddenly disappearing from wallets. So it's very likely that someone has already set up a bot that scans new transactions from the same address for repeating r values.

acqq 13y ago

Seems that some invocations of SecureRandom were able to always get the same result. http://blog.kchandrahasa.com/blog/2013/08/09/android-4-dot-2-and-javax-dot-crypto-dot-badpaddingexception-pad-block-corrupted/ http://blog.kchandrahasa.com/blog/2013/08/09/android-4-dot-2... However I've read somewhere that now apparently even Android 4.2 is affected which would mean there's something more? Whoever knows more, please write more technical details.

tjohns 13y ago
To be specific, since I spent a lot of time on that bug... Older versions of Android's SecureRandom could return the same value if (a) you were manually seeding SecureRandom and (b) no prior crypto operations were performed on that SecureRandom instance before seeding, There was some (very) bad advice circulating on blogs which advised using this technique to generate local encryption keys from a seed, in order to obfuscate the key. This was fixed in Android 4.2 when we switched from BouncyCastle to OpenSSL as the underlying crypto provider. I don't know why you'd still be seeing this on Android 4.2, but you shouldn't be doing this anyway. SecureRandom is seeded by the system. Manually seeding it is a bad idea. (And trying to force deterministic output from is a very bad idea.) There's a blog post I wrote which goes into a bit more detail: http://android-developers.blogspot.com/2013/02/using-cryptography-to-store-credentials.html http://android-developers.blogspot.com/2013/02/using-cryptog... The linked article is a bit light on details, so I don't know if this is what they were doing or not. I doubt it though, since that would have meant they were seeding SR with the same value, and I'd like to believe the Bitcoin devs wouldn't make that mistake.
- andrewcooke 13y ago
  the linked article was using deterministic output from an explicitly seeded PRNG as a key. it broke with openSSL which uses setSeed only to augment, not replace, state (as you know, just being complete). so i don't think the parent link explains the current issue.

filipmaertens 13y ago

At blog post https://cryptocow.com/?p=201 https://cryptocow.com/?p=201 we've been experimenting with using sensors to upgrade PRNG's, and we frankly can't understand why this isn't been used natively in Android RNG implementations... It's trivial, easy and tremendously increases the RNG quality.

tptacek 13y ago
Because a sensor provides an entropy source, not a whole CSPRNG. Most modern CSPRNGs have interfaces to feed entropy into the system, but CSPRNG designs do more than simply route entropy from one place to another. This is a really common misconception people seem to have about cryptographic random number generation, and a topic Ferguson and Schneier do an extremely good job breaking down in _Cryptography Engineering_.

kllrnohj 13y ago

Android's SecureRandom uses BouncyCastle prior to 4.2 and OpenSSL in 4.2+ ( http://android-developers.blogspot.com.au/2013/02/security-enhancements-in-jelly-bean.html http://android-developers.blogspot.com.au/2013/02/security-e... ) It'd be interesting to know what the bug is and if that bug affects Bouncy Castle and/or OpenSSL as well, or if Google screwed up the glue code somehow

sirk390 13y ago
This is the paper referenced in the bitcointalk thread: http://www.scribd.com/doc/131955288/Randomly-Failed-The-State-of-Randomness-in-Current-Java-Implementations http://www.scribd.com/doc/131955288/Randomly-Failed-The-Stat.... See section 5.4 for Bouncy Castle: Weaknesses/Quality of Entropy Collectors.

0x0 13y ago

Could this affect stuff like ssh key generation or HTTPS traffic on Android, as well?

dobbsbob 13y ago

I use the feudal security of blockchain.info wallets w/2FA on android since phones tend to get lost, stolen or fubard

mikeash 13y ago

Looks like a terrifyingly buggy SecureRandom implementation that results in only 31 bits of entropy when seeding: http://armoredbarista.blogspot.com.au/2013/03/randomly-failed-weaknesses-in-java.html http://armoredbarista.blogspot.com.au/2013/03/randomly-faile...

tptacek 13y ago
As I understand it, Android doesn't use Harmony's CSPRNG. But maybe it did in an earlier version? Maybe that's the problem?

oakwhiz 13y ago

Would it be possible to design Android Bitcoin wallets to consume their entropy from a file on your SD card? You could just periodically refill the entropy from another device that you trust.

mydpy 13y ago

Can anyone reference me to an article that explores a technical analysis of how their random number generator was exploited? Did it not have full coverage (read: RANDU style error) or otherwise? http://www.pnas.org/content/61/1/25.full.pdf+html http://www.pnas.org/content/61/1/25.full.pdf+html

mydpy 13y ago
Actually, I found it here. Pretty interesting issue, I recommend the read. I'll summarize the paper here: Java implementations primarily used on lightweight mobile platforms have a method called SecureRandom which generates pseudo random numbers for cryptographic operations. The integrated seed generator on some platforms provides a systematic means of determining the seed value and predicting seemingly secure outputs. http://www.scribd.com/doc/131955288/Randomly-Failed-The-State-of-Randomness-in-Current-Java-Implementations http://www.scribd.com/doc/131955288/Randomly-Failed-The-Stat...
- glurgh 13y ago
  Yes but that's not the problem being reported.

swayvil 13y ago

Why don't we have a real rng in our computing devices? It appears to be a trivial bit of electronickry. I'm talking about one of those little quantum event listener thingies. http://en.wikipedia.org/wiki/Hardware_random_number_generator http://en.wikipedia.org/wiki/Hardware_random_number_generato...