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

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.

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?

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.

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.

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

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?

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?

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.

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.

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.

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

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.

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

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.

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

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.

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

See also: https://github.com/vbuterin/pybitcointools

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.

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

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.

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.

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

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

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