Android RNG Weakness Renders Bitcoin Wallets Insecure | Hacker News Reader

Android RNG Weakness Renders Bitcoin Wallets Insecure

bitcoin.org

166 pointsVMG102 comments

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ä!

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.

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

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

On a side note to my side, how many are psyched about Breaking Bad tonight?!

(seriously, downvoted for asking about stats on cryptopals? it is relevant -- #6 has two DSA questions!)

I'm a season behind on Breaking Bad; I don't like watching half-seasons and would rather just watch the whole thing once it's all on Netflix. So: not too excited.

63 people have finished the crypto challenges; about 9000 people have started them.

Whenever I see tptacek tweet the current stats, I try to update this spreadsheet:

https://docs.google.com/spreadsheet/ccc?key=0AscYGzcM4zJNdHR...

I've probably missed a few tweets and typo'd a few numbers along the way, but it should be mostly accurate. Note the tabs (at bottom left) for a derived speadsheet (percent of participants at each level) and a chart.

For those watching from the stands, 'rwg also sent us a spreadsheet that does AES. Entirely in cell formulas. He also sent us a Postscript file that appeared to be a visualization of AES state but was in fact a pure-Postscript implementation of AES that rendered itself into the Postscript document.

To be fair, I've only tweeted screenshots of the AES spreadsheet -- you'll be getting the actual .xlsx file with my set 6 answers. AES128.applescript is waiting in the responses@ and cryptopals@ mailboxes right now, along with my set 5 answers.

I don't know what I'll do for set 7 yet. Maybe Excel implementations of the SHA-3 finalists...

Well then...first I learned something about DSA, and now I'm 1/3 of the way through re-reading The Black Goat of the Woods with a Thousand Young. Jesus Christ I am a nerd. Iä! Iä!

Another interesting thing about DSA is that the signatures allow for public key recovery i.e. given a signed message, you can (usually within 1 or 2 possibilities) determine the public key of the signer. It's a bit like a handwritten signature where everybody can read your name amongst the scrawl.

Most of the time this property is useless, because you want to verify the signature against a known-good key, but it does also mean you're probably not going to want to use DSA to pass signed covert messages.

Schnorr signatures actually have a simpler, and I think more intuitive, construction and don't have this property. They also don't require collision resistant hashes.

Actually, the key-recovery process is quite useful. The reason is that instead of having your public key be the public key itself, you can use the hash of your public key (ie. Bitcoin address) instead. This cuts the required "public key" length in half for the same level of security. The verification protocol then becomes

def verify(msg,sig,addr): return pubkey_to_address(ecdsa_recover(msg,sig)) == addr

Yes, Bitcoin is one exception because of the digested addresses, but if I'm up to date it's not currently used on the network. There's no opcode in the transaction script to perform recovery, so currently you can't reduce transaction size by omitting public keys. I suppose the primary advantage in Bitcoin is the reduced storage space.

It's not currently used on the blockchain, but there's a feature in the Bitcoin client that uses public key recovery in order to sign out-of-band messages with Bitcoin addresses.

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

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.

At blog post 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.

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

Android's SecureRandom uses BouncyCastle prior to 4.2 and OpenSSL in 4.2+ ( 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

This is the paper referenced in the bitcointalk thread: http://www.scribd.com/doc/131955288/Randomly-Failed-The-Stat.... See section 5.4 for Bouncy Castle: Weaknesses/Quality of Entropy Collectors.

discussion on bitcointalk.org: https://bitcointalk.org/index.php?topic=271486.0

blogpost about weakness in java.security.SecureRandom: http://armoredbarista.blogspot.com.au/2013/03/randomly-faile...

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.

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

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.

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/Securi... ) to actually have any effect.

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

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.

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?

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

that is kind of scary. i had a look over the code and the problem seems not obvious. the only issue i saw was multiple instances of SecureRandom share the same state which could cause some problems if you do [1]:

x = new SecureRandom();

y = new SecureRandom();

y.setSeed(predictable);

x.generateBytes(zz);

and also i think the seed is thread local so you can have:

x = new SecureRandom();

x.setSeed(xxx);

then on another thread x.generateBytes()

won't do what you think it will do. i don't think this would cause dupes because i assume apps are isolated from each other and these apps aren't calling setSeed...

[1] this is assuming android people haven't patched openssl to have different behaviour and also setSeed might be safe in openssl because it uses the value to augment and not replace the state.

I have done a bit of source diving in response to your question, and the answer is that all I can provide is the bitcoiners' announcement:

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

They claim the problem lies with 'a component of Android'. One of them told me that the solution was to switch from using SecureRandom to reading /dev/urandom directly. The actual source changes appear not to be public, and he wouldn't tell me details about the issue.

I tried to find the usages of SecureRandom in a couple of the apps that are supposed to be affected, but a cursory search didn't turn up much. I suspect it's inside some library that I don't know to look inside. The question, I guess, is whether all the affected apps share the same library or not -- I don't _think_ so, but if they do it would dramatically reduce my confidence that the issue lies with the Android platform, as claimed.

That's the lib, if you're bored enough to keep diving

https://code.google.com/p/bitcoinj/

OK, I dove a little more. The actual signing happens in org.spongycastle.crypto.signers.ECDSASigner . I haven't dug into _that_ yet.

But one thing I'm wondering is: would any setSeed on any SecureRandom instance cause a potential problem? Or just on the same instance being used for signing? In other words, do I only need to check that spongycastle -- which I presume is a fork of bouncycastle -- handles things reasonably? Or could any other messing about with SecureRandom mess it up?

Not seeing any relevant code that sets seeds in SpongyCastle, either.

if they are using SecureRandom backed by openssl then i think any instance is a problem. However, the 'seed' is used to augment the state and not override it. I'm not sure if it is possible or how much data would be required to get predictable output from SecureRandom by calling setSeed.

http://www.openssl.org/docs/crypto/RAND_add.html

the only other thing i see is the openssl securerandom code doesn't properly check the return value. it is possible for RAND_bytes to fail and for the securerandom code to not throw an exception. i think this is quite unlikely to happen. so basically:

1) reading from /dev/urandom takes more than 10ms causing an entropy error

2) a malloc fails causing the error to be saved to the fallback ERR_STATE instead of the thread local ERR_STATE

3) java sees failing code and tries to read the last error but now malloc succeeds so it reads it from its local thread ERR_STATE which succeeds or some other thread has clobbered the fallback ERR_STATE

4) java doesn't throw an exception because it sees no error

the other possibility is the openssl random state is shared between processes due to forking. i hear there is a process called the zygote that warms up the vm and forks to create apps. if it initialises openssl then it is possible child processes could get the same random state.

SpongyCastle is a repackage of BouncyCastle specifically for the Android platform, an unfortunate necessity due to Android shipping with a cut-down version of Bouncy Castle (see https://code.google.com/p/android/issues/detail?id=3280 & http://rtyley.github.io/spongycastle/ ).

...I'm the packager of SpongyCastle (a task a well-trained monkey could do, I don't alter the code other than package-renaming it), and I confess some relief that the issue is with Android's in-built SecureRandom class, rather than anything in (Bouncy|Spongy)Castle.

Actually, someone elsewhere in the thread has found, and linked, the bugfix commit, in another Android bitcoin wallet:

https://code.google.com/p/bitcoin-wallet/source/detail?name=...

So literally they're just ripping out SecureRandom and replacing it with their own stub that reads /dev/urandom.

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.

As tptacek has mentioned many, many times, SecureRandom is one of those things which is very secure if you understand exactly what it is doing and do not shoot yourself in the foot.

One easy way to shoot yourself in the foot with SecureRandom is to use seed values from a source with low entropy.

http://developer.android.com/reference/java/security/SecureR...

If one were to copy/paste the sort of code samples which show up when one Googles for [Android SecureRandom], one would more than likely call setSeed, possibly in such a fashion as to duplicate seeds and, predictably, make the output of the random number generator deterministic.

I will leave it to one's individual judgement as to whether "It is unlikely a serious developer would copy/paste in crypto code into a project that has real money on the line" is descriptive of the prevalent standard of care in engineering in the Bitcoin community.

They were explicitly seeding SecureRandom?

Don't know. This just seemed like the high-percentage guess.

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.

If that's the problem, it does lead to a beautiful solution of fixing bugs by removing code entirely.

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 implementation that allows developers to specify insecure seed values.

I'll go to bat on this disagreement. Don't use application-layer CSPRNGs. Use the one the OS provides, to the exclusion of alternatives.

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.

So your position is that Debian didn't go far enough?

They should have disabled OpenSSL's CSPRNG entirely and redirected its internal calls to perform IO operations on /dev/[u]random?

Modulo the fact that Debian shouldn't be mucking with the inner workings of packages in the first place, sure; stubbing out OpenSSL's CSPRNG with calls to the OS CSPRNG seems like a reasonable plan. It is, by the way, part of the NaCL design too.

Last I heard, there were still some "security oriented" OSes using RC4 for their /dev/random.

arc4random predates modern OS CSPRNGs.

So does OpenSSL. I think it's just not reasonable to expect a widely-portable crypto primitive and protocol library to judge the quality of the host /dev/[u]random and delegate to it. Of course, they seed from the host device and try to estimate the entropy it provides.

Even that OS with the biased /dev/[u]random using RC4 because it was fast would keep a separate RC4 state in each process' libc to avoid the overhead of kernel calls.

So then, you think NaCL's design decision to rely on /dev/urandom was a mistake?

I think if NaCL ever gets popular that design decision will bite somebody, somewhere, on some OS.

Our crypto libraries need to provide their own belt to wear with the OS-provided suspenders. Yes, I know about potential fork() bugs, but our modern VM-crazed deployments introduce that possibility at kernel level too. We need our good crypto implementers shipping good lightweight CSPRNGs, rather than the kernel developers who try to compensate with 6000 bit entropy pools.

If some OS screws up urandom so much that it bites someone, it'll bite a huge number of different apps, and not just the ones that use NaCL. Like it or not, urandom has to work; all sorts of things depend on it. The urandom ship has sailed.

Meanwhile, better to have just one codebase to review, rather than 100 crappy ones, like the SecureRandom from Harmony.

OK, so NaCL will not be guilty and they will be in good company.

I'm sure these principles of minimal redundancy will be of great comfort to those users who get their private keys exposed.

Do you see the paradox here? Find me these developers who are undoubtedly competent to implement their own CSPRNG, but prefer not to. These are the folks I want implementing the CSPRNG that will be generating my keys, rather than kernel developers who find entropy pools exciting.

You see my point, right? A lot of your security already depends on urandom working. Everyone knows this, and a lot of effort has gone into validating the kernel random driver (there have been some pretty good systems security papers on it). Given that you already depend on urandom, all a new CSPRNG gets most developers is a second single point of failure.

I get your point and I agree it's at least not a wrong way to look at it. But you say "the kernel random driver" as if there were only one for a crypto app developer to worry about.

We have already seen a huge number of bad keys generated. Is it that obvious at this point that kernel (and embedded system) developers are so much better at this than OpenSSL?

Is it possible that you just tend to look at more broken library and app crypto code during the course of your work? If you worked primarily with broken kernel crypto code, would you perhaps prefer (for your own use) a CSPRNG in a library written by your favorite experts?

It is true that we see a lot of broken randomness code, and it is also true that we pay a lot of attention to failures of different CSPRNGs, but my point of view on this is also influenced by things like the design paper Daniel Bernstein wrote for Nacl.

I'll wager your team has reviewed more crypto code, and more recently, than DJB.

Meh, this conversation needed to be over

      do random_beverage(); while (self->is_conscious());

Tell you what: I will ask DJB tonight and see what he says.

This seems the complete opposite of your usual advice to use a library. You want every app developer to memorize the intricacies of which of random or urandom or srandom they should use on which OS and whether they need to worry about blocking or short reads and whether the entropy returned is good, or really good, or just good enough? You don't think people are going to dick that up? I'd trust the OpenSSL devs to figure this mess out before John Q. Random developer. Any day.

The OS already provides a library for securely generating random numbers. On Unix, that library is called "the random driver". Its interface is file-descriptor based.

You'd rather not be in a position to care about cryptographic randomness regardless. So, by all means, use high-level crypto libraries. But those libraries should also be using the random driver, instead of trying to bolt their own CSPRNG on top of it (or, god forbid, trying to avoid the random driver altogether).

Strongest possible disagree.

Ok, we disagree. It wouldn't be the first time. ;-)

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

I think the biggest problem was that OpenSSL used OpenSSL's CSPRNG after Debian broke it. Having applications all open+read+close /dev/random is not going to prevent that.

a far more likely concrete flaw is, for instance, a SecureRandom implementation that allows developers to specify insecure seed values.

A SecureRandom implementation should not allow the application to provide seed values except as additional input. It should always seed itself from the operating system entropy source, with no option to disable that.

Aside from the issue of performance (which can be severe) and the timing information leakage to local spies, there's a very practical reason to avoid developers read from /dev/random:

  int fd;

  fd = open("/dev/random", O_RDONLY);
  read(fd, buf, buflen);
  close(fd);

I've seen this on a number of occasions, and it works perfectly fine... until your server gets busy, the kernel entropy pool runs down, and /dev/random returns a short read. At that point, all hell breaks loose. To me, this scenario alone is enough to tell developers to use a library's automatically seeded CSPRNG instead of reading from the kernel.

Linux random/urandom is supposed to prevent short-reads for exactly this reason. You raise an interesting point, but I'm not persuaded that the risk of quietly failing to read from the random device is greater than the risks of adopting an entire new CSPRNG to sit on top of the OS's CSPRNG.

Linux random/urandom is supposed to prevent short-reads for exactly this reason.

Oh great, yet another way that Linux developers are going to write broken code because they think the whole unix world behaves like Linux...

The random/urandom devices do originate from Linux, other implementations should be careful about not making incompatible changes.

So then what you should do is write a "libpcap for randomness" that uses the best-practices method of getting randomness from the OS CSPRNG. On Linux it'll be just a couple lines; on BSD it'll be a few more lines for the "atomicio" equivalent read, and on WINAPI it'd set up and call CryptGenRandom.

There's value in having a uniform interface to all the different OS CSPRNGs.

What I'm saying isn't valuable is duplicative effort to build additional CSPRNG logic in the app layer. As we keep seeing, these app-layer CSPRNGs are additional single points of failure; they don't add defensive depth.

How is OpenSSL RAND_bytes not that uniform interface?

OpenSSL provides its own CSPRNG. When that CSPRNG breaks, as it has in the past, no amount of careful validation of the OS CSPRNG helps you. The OpenSSL CSPRNG is thus a second single point of failure.

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

You might be right! I'd be surprised if there was an OS or even framework-level CPSRNG bug in Android, but it's possible, and the obvious bug Patrick mentioned downthread is nowhere to be seen in bitcoinj or SpongyCastle.

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

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

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

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

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

Yes but that's not the problem being reported.

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

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.

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

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.

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

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?

They can use /dev/random if they so choose.

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.

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.

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.

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.

This is the most likely scenario. While I don't know Java technically, .NET has a similar "vulnerability" if you use more than one RNG. It uses time to seed new values and the general rule is you use this as a singleton/static app-wide. If you don't do this, all your rng's share the exact same value.

It's really awkward to stumble into as all the evidence points to the framework but when you rtfm you realize no, its really pebkac.

I'm not saying this can't be a vulnerability in the framework, just this is the most likely scenario.

A secure random number generator wouldn't seed based on time in the first place, though.

Even Java's non-secure RNG doesn't do that (anymore):

public Random() { this(++seedUniquifier + System.nanoTime()); }

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

Correct. The standard recommendation is to store significant savings in wallets that you use as little as possible (ideally offline).

Reply on news.ycombinator.com