Bad signatures leading to 55.82152538 BTC theft (so far)

[TiagoTiago]

And wouldn't that expose data encrypted by other apps to similar security issues?

No. The issue has nothing to do with exposing encrypted data but with signatures exposing private keys.

Encryption isn't weakened when the random number generator is bad like this?

[1714148696]

1714148696

[1714148696]

1714148696

[1714148696]

1714148696

[JoelKatz]

Encryption isn't weakened when the random number generator is bad like this?

It depends on the type of encryption and the exact details of the bug (which, to my knowledge, still haven't been released). Generally, programs on "small" devices tend to use asymmetric encryption as clients and then they really don't have anything to compromise.

I would be surprised if Bitcoin wallets were literally the only programs affected, but I wouldn't expect there to be very many others.

[bitpop]

Thankfully ssl wasn't affected. Hope my encfs isn't either.

[Jesse James]

Google posted an official post-mortem of the issue with SecureRandom as well as a fix.

However, I'm kinda confused. My read of the OpenSSL code would lead me to believe that it seeds itself [1] [2] with at least 32 bytes from /dev/urandom when you neglect to seed it yourself before hitting up RAND_bytes for randomness.

The proposed fix seeds OpenSSL manually from /dev/urandom (or if the OpenSSL-based SecureRandom isn't being used (non-JellyBean), simply serves randomness directly from /dev/urandom).

It's unclear to me how the proposed fix helps unless there is a flaw in OpenSSL's self seeding.  

Their fix does get rid of the Apache Harmony SecureRandom provider ... which, while bad (64 bits of entropy), mathematically could not have been the cause of the repeated signature nonces given their prevalence.

Even more confusing to me is how an OpenSSL self-seeding issue could lead to the particular pattern of repeated signature nonces observed ... in particular the majority of nonce repeats occurred in the context of the same transaction for sequential inputs. E.g. look at this offending transaction: 5 signatures; the first 2 share the same nonce as do the last two.  This transaction exhibits the exact same pattern.  For this bug to be responsible, the PRNG would literally need to spit out the same 32-bytes back to back. I don't see how this could happen with a thread-locked digest-based PRNG with singleton state (like OpenSSL's default) ... even if it's state was statically initialized.

I'm sure I'm missing something but if there are any other randomness nerds out there ... I'd love to hear your take.

[Mike Hearn]

Suffice it to say, the workarounds used in the bitcoin apps and the one given in the blog post will resolve the issue with OpenSSL. I presume there are reasons why the exact nature of the bug wasn't disclosed but yes, it can cause repeats in the RNG output.

[Remember remember the 5th of November]

Google posted an official post-mortem of the issue with SecureRandom as well as a fix.

However, I'm kinda confused. My read of the OpenSSL code would lead me to believe that it seeds itself [1] [2] with at least 32 bytes from /dev/urandom when you neglect to seed it yourself before hitting up RAND_bytes for randomness.

The proposed fix seeds OpenSSL manually from /dev/urandom (or if the OpenSSL-based SecureRandom isn't being used (non-JellyBean), simply serves randomness directly from /dev/urandom).

It's unclear to me how the proposed fix helps unless there is a flaw in OpenSSL's self seeding.  

Their fix does get rid of the Apache Harmony SecureRandom provider ... which, while bad (64 bits of entropy), mathematically could not have been the cause of the repeated signature nonces given their prevalence.

Even more confusing to me is how an OpenSSL self-seeding issue could lead to the particular pattern of repeated signature nonces observed ... in particular the majority of nonce repeats occurred in the context of the same transaction for sequential inputs. E.g. look at this offending transaction: 5 signatures; the first 2 share the same nonce as do the last two.  This transaction exhibits the exact same pattern.  For this bug to be responsible, the PRNG would literally need to spit out the same 32-bytes back to back. I don't see how this could happen with a thread-locked digest-based PRNG with singleton state (like OpenSSL's default) ... even if it's state was statically initialized.

I'm sure I'm missing something but if there are any other randomness nerds out there ... I'd love to hear your take.

Darn, looks like my Android application may be affected after all, I am rolling with my own statically linked OpenSSL library 1.01e I think, so it's not being seeded properly?

[Jesse James]

Suffice it to say, the workarounds used in the bitcoin apps and the one given in the blog post will resolve the issue with OpenSSL. I presume there are reasons why the exact nature of the bug wasn't disclosed but yes, it can cause repeats in the RNG output.

Thanks for the clarification.

I initially overlooked how the Google fix overrides the SecureRandom provider for all releases to date including the JellyBean ones.  I was distracted by the logic in applyOpenSSLFix() thinking it was what was responsible for curing SecureRandom ills on JellyBean ... but now I see it's kinda irrelevant in this context since the OpenSSLRandom provider is simply getting kicked to the curb for now.

[JoelKatz]

Is there any link to the actual bug and the actual fix? I see descriptions of the affects of the bug and suggested workarounds, but not the actual bug itself nor the fix itself.

[grau]

And wouldn't that expose data encrypted by other apps to similar security issues?

No. The issue has nothing to do with exposing encrypted data but with signatures exposing private keys.

In contrary, this is a much bigger issue.

The Android PRNG must be extremely weak (say a joke) that this surfaced in the insignificant number of keys android wallets repeatedly used.

Encryption software usually use a key generated with PRNG, so do secure communication protocols. Pass phrases and asymmetric algorithms often only encrypt that pseudo random key. It is the pseudo random key that is really the secret, and is protecting the data.
Knowing the weakness of the PRNG makes brute forcing of encryption feasible since key space in question is reduced to a joke.

Therefore yes, a lot of encrypted data and communication (that was recorded in the past) is potentially affected by this "bug".
We will never know if it was gross negligence or NSA compliant engineering at work.

[Mike Hearn]

The underlying bug was reported by academics, it wasn't discovered internally by Google. So at some point they will publish a paper just like the guys who found the Harmony bugs did, and you will know the exact details.

Suffice it to say the failure was subtle. It isn't something easily found via code inspection. The NSA doesn't need to engage in monkey tricks anyway, they can just go pressure the providers that most people use or hack the endpoints and circumvent encryption entirely.

[grau]

Suffice it to say the failure was subtle. It isn't something easily found via code inspection.

Sounds like a sophisticated backdoor.

The NSA doesn't need to engage in monkey tricks anyway, they can just go pressure the providers that most people use or hack the endpoints and circumvent encryption entirely.

This is the first time you do not embrace encryption as a solution for a problem.

[grau]

It is known that the NSA employs a lot of bright guys, who certainly not only work on breaking code but also on how to prevent strong code in the first place.
A subtly but still seriously flawed PRNG planted into major operating systems could be a masterpiece of their effort.

It does not need complacency of Google to happen, just brilliance and social engineering on the other side.

[Dougie]

Sue google for your losses! Maybe not. Pretty unfortunate really. I guess someone was bound to write a script to look for these transactions.

[Mike Hearn]

Encryption is a useful tool, I wouldn't want to be without it. It's obviously not a silver bullet. The cypherpunks in the 90's thought writing crypto software would bring about a social revolution. 20 years later we can see they were wrong - no social revolution happened and the state is larger and more powerful than ever. We exist in a world where totalitarian surveillance is the norm.

How much worse would things be without strong crypto? Worse, I'm sure, but significantly worse? Unclear.

I'm very skeptical when people claim Bitcoin will bring about a massive social revolution, or that governments can't control it. Satoshi explicitly disavowed such a claim and I agree with him. The US Government can terminate Bitcoin globally, if it so chooses, which is why extensive lobbying is so essential. It really lives or dies at the whims of some congressmen.

As to the Android RNG bug being an NSA plant - this theory doesn't hold water. There are two RNG failures. One, the Harmony bug published in the RSA paper, has been around for a long time but the Harmony authors couldn't have known Google would build a hugely successful OS on top of their work. For the NSA to somehow get a weak RNG into Harmony would mean they own a time machine and we might as well give up right now. The second failure only impacts Jellybean+ because the SecureRandom implementation was replaced with a shim over OpenSSL. It took less than a year for the problem to be found. Heck most phones don't even run Jellybean yet. If that's their grand plan to undermine crypto, then they suck at it.

[grau]

I'm very skeptical when people claim Bitcoin will bring about a massive social revolution, or that governments can't control it. Satoshi explicitly disavowed such a claim and I agree with him.

Yes, Bitcoin merely redistributes some riches from those who got lazy and trust their lobby to those who are innovative and trust their math.

The US Government can terminate Bitcoin globally, if it so chooses, which is why extensive lobbying is so essential. It really lives or dies at the whims of some congressmen.

I doubt they could achieve more than a few years of setback. I trust that there are congressmen who recognize, that this is a chance of redistributing on Wall Street, and would love to see that happen.

If that's their grand plan to undermine crypto, then they suck at it.

Hope you are right.

[justusranvier]

I'm very skeptical when people claim Bitcoin will bring about a massive social revolution, or that governments can't control it. Satoshi explicitly disavowed such a claim and I agree with him. The US Government can terminate Bitcoin globally, if it so chooses, which is why extensive lobbying is so essential. It really lives or dies at the whims of some congressmen.

You've got the correlation/causation backwards. Bitcoin will not cause a social revolution. Bitcoin will be successful as a consequence of an ongoing social revolution.

[2112]

If that's their grand plan to undermine crypto, then they suck at it.

Hope you are right.

How do you guys know what was the objective? Maybe Android was just an unintended collateral damage?

Wasn't Crypto AG compromised through the similar means?

http://en.wikipedia.org/wiki/Crypto_AG

Personally I wouldn't know.

So I guess the answer lies somewhere in the changelogs for the affected projects.

[smolen]

So I guess the answer lies somewhere in the changelogs for the affected projects.

Hire incompetent manager, let him hire incompetent programmers, wait for suitable defect, withhold testcase from QA lab half globe away from your headquarter, enjoy plausible deniability.

[molecular]

I know this is an extremely rough estimage, but guesstimating from Number of Transactions excl. popular we can speculate that roughly 20 kBTC have been moved from android wallets (assuming the spike is just that).

55 / 20k = 0.2% of funds stolen due to the bad RNG... could've been worse. I feel with the people who lost money, of course.

[piuk]

I know this is an extremely rough estimage, but guesstimating from Number of Transactions excl. popular we can speculate that roughly 20 kBTC have been moved from android wallets (assuming the spike is just that).

55 / 20k = 0.2% of funds stolen due to the bad RNG... could've been worse. I feel with the people who lost money, of course.

As of today only 51% of users of the Blockchain.info app have upgraded to a patched release, if the pattern is similar with other apps a fair number of wallets might still be vulnerable. But you are right it definitely could have been worse.