Android RNG Weakness Renders Bitcoin Wallets Insecure • Hacker News Board

Re: Android RNG Weakness Renders Bitcoin Wallets Insecure

#41

Post by gwillen » Sun, Aug 11, 2013, 7:31 PM UTC

tptacek wrote: post #16

gwillen wrote: post #14

Earlier quoted context omitted.

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.

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?

Ok, more source diving. Bitcoin Wallet calls into bitcoinj java/com/google/bitcoin/core/Wallet.java sendCoinsOffline(...), which calls completeTx(...), which calls core/Transaction.java signInputs(...), which calls calculateSignature(...), which calls core/ECKey.java sign(...), which performs:

        ECDSASigner signer = new ECDSASigner();
        ECPrivateKeyParameters privKey = new ECPrivateKeyParameters(privateKeyForSigning, ecParams);
        signer.init(true, privKey);
        BigInteger[] sigs = signer.generateSignature(input.getBytes());
        return new ECDSASignature(sigs[0], sigs[1]);

This _appears_ to be a correct invocation of spongycastle-formerly-bouncycastle, initializing the signer with an instance of ECPrivateKeyParametes, and NOT an instance of ParametersWithRandom, so that, on org/spongycastle/crypto/signers/ECDSASigner.java line 41, we call SecureRandom() with no arguments.

I don't see spongycastle ever calling setSeed, and I don't see it ever leaking its SecureRandom instance, so unless calling setSeed on ANY SecureRandom instance is a problem, this _looks_ like a correct usage.

Also, I now remember how much I hate reading Java.

Re: Android RNG Weakness Renders Bitcoin Wallets Insecure

#42

Post by glurgh » Sun, Aug 11, 2013, 7:51 PM UTC

tptacek wrote: post #38

glurgh wrote: post #31

Earlier quoted context omitted.

Not in the bitcoinj library they all appear to be using, no. That, in turn, uses bouncycastle. Bitcoinj is not explicitly seeding SecureRandom, I'm reasonably sure.

I couldn't find a line of code in bitcoinj that explicitly seeded SecureRandom, or used the explicit-seed constructor.

Neither could I. Maybe it is SecureRandom itself but then that would be a bigger deal than some broken BitCoin wallets, one would think.

Re: Android RNG Weakness Renders Bitcoin Wallets Insecure

#43

Post by marshray » Sun, Aug 11, 2013, 7:53 PM UTC

tptacek wrote: post #37

cperciva wrote: post #26

Earlier quoted context omitted.

you should use your OS's CSPRNG (here, /dev/random) to the exclusion of any other RNG Bad advice. Use your OS's CSPRNG to get a seed, but work with your own PRNG (say, HMAC_DRBG) internally. Going to the OS every time you want a few bits is both very slow and makes it far easier for local attackers to see when you're using entropy.

Strongest possible disagree. For instance, the Debian OpenSSL bug was an entirely unforced error stemming from applications that chose to use Debian OpenSSL's terrible CSPRNG on top of the OS's CSPRNG. The local attacker scenario you're talking about is a theoretical risk when there are attackers running code in the same OS as your CSPRNG; a far more likely concrete flaw is, for instance, a SecureRandom implementatio…

The Debian OpenSSL bug was a result of Debian patching OpenSSL's RNG to make it utterly broken. Unless you're going to claim Debian couldn't have patched an equivalent bug into the kernel, you can't generalize this as support for the claim that kernel RNGs are inherently superior to library RNGs.

Re: Android RNG Weakness Renders Bitcoin Wallets Insecure

#44

Post by gojomo » Sun, Aug 11, 2013, 7:56 PM UTC

patio11 wrote: post #13

tptacek wrote: post #6

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 attem…

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.

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

Re: Android RNG Weakness Renders Bitcoin Wallets Insecure

#45

Post by makomk » Sun, Aug 11, 2013, 8:07 PM UTC

tptacek wrote: post #28

VMG wrote: post #23

Earlier quoted context omitted.

Well there is this paper: 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.

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.

According to Mike Hearn's comment over at the Bitcoin forums[1]:

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

[1] https://bitcointalk.org/index.php?topic=271486.msg2911376#ms...

Re: Android RNG Weakness Renders Bitcoin Wallets Insecure

#46

Post by fixxer » Sun, Aug 11, 2013, 8:30 PM UTC

tptacek wrote: post #6

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 attem…

On a side note, what are the current stats for the Matasano crypto challenge? How many have finished all 6?

Re: Android RNG Weakness Renders Bitcoin Wallets Insecure

#47

Post by tptacek » Sun, Aug 11, 2013, 8:34 PM UTC

marshray wrote: post #43

tptacek wrote: post #37

Earlier quoted context omitted.

Strongest possible disagree. For instance, the Debian OpenSSL bug was an entirely unforced error stemming from applications that chose to use Debian OpenSSL's terrible CSPRNG on top of the OS's CSPRNG. The local attacker scenario you're talking about is a theoretical risk when there are attackers running code in the same OS as your CSPRNG; a far more likely concrete flaw is, for instance, a SecureRandom implementatio…

The Debian OpenSSL bug was a result of Debian patching OpenSSL's RNG to make it utterly broken. Unless you're going to claim Debian couldn't have patched an equivalent bug into the kernel, you can't generalize this as support for the claim that kernel RNGs are inherently superior to library RNGs.

I'm saying the error was unforced because the effort the OpenSSL CSPRNG went through was duplicative.

Re: Android RNG Weakness Renders Bitcoin Wallets Insecure

#48

Post by 0x0 » Sun, Aug 11, 2013, 8:56 PM UTC

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

Re: Android RNG Weakness Renders Bitcoin Wallets Insecure

#49

Post by andrewcooke » Sun, Aug 11, 2013, 8:59 PM UTC

tjohns wrote: post #39

acqq wrote: post #25

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

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 ob…

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.

Re: Android RNG Weakness Renders Bitcoin Wallets Insecure

#50

Post by andrewcooke » Sun, Aug 11, 2013, 9:02 PM UTC

tptacek wrote: post #9

lcedp wrote: post #4

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

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.

"This is a Bitcoin software implementation bug,"

where are you getting your info from?

as far as i can tell previous code was buggy, and android 4.2 "fixed" things by making it impossible (well...) to screw up the PRNG (setSeed in OpenSSL augments state, previously with BouncyCastle it replaced state, afaict).

but that doesn't explain why current software has problems (not the kind of problems that should make it insecure - they may have problems with being unable to recreate keys if they were using seeded PRNG output as keys(!), but 4.2's changes should just screw them completely, rather than make things insecure), or why the article link blames the platform libraries.

so why are you saying this is a problem now in bitcoin library code? is there another link somewhere i've missed? (i agree it's suspicious that everything is bitcoin-related, but i can't see any certain evidence...)