[ANNOUNCE] Android key rotation

[dserrano5]

BitcoinSpinner / Mycelium Wallet

An update has been prepared for Mycelium Wallet and is being pushed out via the Play Store. If you use BitcoinSpinner you are encouraged to upgrade to Mycelium Wallet, which is maintained by the same people.

I just removed Spinner and installed Mycelium. It reports version 0.7.0 beta, is this one safe regarding this problem?

[Diapolo]

It would be nice, it other App stores would also get updates. F-Droid for example doesn't yet show an update for Bitcoin Wallet.

Dia

[niko]

How are the patches working around the problem?

Are they using a different source of entropy, or are they checking that the two R-values don't collide?

In my mind, best practice would be to do both.

I see a lot of cases in code where people need multiple random and unique values, (e.g. UUIDs)... where the only two requirements are that they are indeterminate and unique... but because the domain of random outcomes is so huge they rely on the vanishingly small probability of collision, and don't bother to check uniqueness.

But as we have found, that "vanishingly small probability" isn't so small if the PRNG is broken. A simple collision check isn't a waste of CPU cycles -- it guards against this kind of system problem.

As such, can all Bitcoin clients, Android or otherwise, be updated to check that the two R-values are unique?

On a different note, I don't see much discussion about the broken Android PRNG, does anyone have a link to the bug reports? This must have some pretty far-reaching consequences outside Bitcoinland too...?

Any comments from the developers here?  Checking the uniqueness would require storing past r values along with the private key. Any problematic consequences of this?

And yes, I am surprised that there is not much buzz about the broken android PRNG in general, unrelated to Bitcoin. Does all crypto on Android rely on this broken PRNG?  Who wrote this particular implementation, who let it slip by? What else has slipped by? 

[apetersson]

BitcoinSpinner / Mycelium Wallet

An update has been prepared for Mycelium Wallet and is being pushed out via the Play Store. If you use BitcoinSpinner you are encouraged to upgrade to Mycelium Wallet, which is maintained by the same people.

I just removed Spinner and installed Mycelium. It reports version 0.7.0 beta, is this one safe regarding this problem?

yes it is. it also features a migration wizard if you generated a key inside Mycelium prior to 0.6.5.

[piotr_n]

How are the patches working around the problem?

Are they using a different source of entropy, or are they checking that the two R-values don't collide?

In my mind, best practice would be to do both.

I see a lot of cases in code where people need multiple random and unique values, (e.g. UUIDs)... where the only two requirements are that they are indeterminate and unique... but because the domain of random outcomes is so huge they rely on the vanishingly small probability of collision, and don't bother to check uniqueness.

But as we have found, that "vanishingly small probability" isn't so small if the PRNG is broken. A simple collision check isn't a waste of CPU cycles -- it guards against this kind of system problem.

As such, can all Bitcoin clients, Android or otherwise, be updated to check that the two R-values are unique?

On a different note, I don't see much discussion about the broken Android PRNG, does anyone have a link to the bug reports? This must have some pretty far-reaching consequences outside Bitcoinland too...?

Any comments from the developers here?  Checking the uniqueness would require storing past r values along with the private key. Any problematic consequences of this?

And yes, I am surprised that there is not much buzz about the broken android PRNG in general, unrelated to Bitcoin. Does all crypto on Android rely on this broken PRNG?  Who wrote this particular implementation, who let it slip by? What else has slipped by? 

AFAIK, the patches are using /dev/random as the source of random data. This one has not been screwed up by Google and it seems to be reliable.

No need to keep track of all previews R values, since a chance of picking up the same 256 bit random number again is likely lower than a chance of the h/w failing in a away that it would broadcast such a stored R values from your history buffer.

And yes - all the other Android apps that rely on SecureRandom class are at risk.
I'm also surprised that Google does not give a shit, since it seems that they have known about this specific issue for months.
Maybe someone should sue them, to teach them a lesson.
I bet that there are plenty of (e.g. online banking) apps that are also affected.

[TippingPoint]

Exhibit A

https://developer.android.com/reference/java/security/SecureRandom.html

[blockgenesis]

I discovered this flaw and made it known to Mike Hearn, Andreas Schildbach and Ben Reeves. It's been quite a week.

Very much appreciated, thanks. And thanks to every developers who worked to push updates and instructions in a very short delay.

[grau]

Exhibit A

https://developer.android.com/reference/java/security/SecureRandom.html

So Google discourages seeding SecureRandom .... Why ?
Maybe the default implementation is NSA approved.

[gmaxwell]

IIRC if you seed it before ever pulling a random number from it, it will only be seeded from your (quite likely weak) seed, and not the OS provided randomness. Seeding it should be unnecessary, and it makes it easy to screw yourself.

[piotr_n]

So Google discourages seeding SecureRandom .... Why ?
Maybe the default implementation is NSA approved.

Hehe - as a guy with a "tinfoil hat" label given already, I must say that it is not an entirely unreasonable theory

[TippingPoint]

Seed PRNG with accelerometer, gyroscope, compass, barometer, or GPS if available?
http://www.gsmarena.com/glossary.php3?term=sensors

[piotr_n]

Seed with accelerometer, gyroscope, compass, barometer, or GPS if available?

But that is exactly what the default OS implementation should be doing.
Instead its seeding with a 31 bit value...

[grau]

IIRC if you seed it before ever pulling a random number from it, it will only be seeded from your (quite likely weak) seed, and not the OS provided randomness. Seeding it should be unnecessary, and it makes it easy to screw yourself.

Understood.

If however the "self seeding" of SecureRandom creates low entropy then it creates a master key to all cryptography used on the device including https://, SSL and not only Bitcoin.

The fact that the few Bitcoin transactions that Android Wallet user created was able to expose the weakness tells me that the flaw is serious to such and extent that I ask if it is intentional.

Edit: I mean a back door with "master key" above. Brute forcing all protocols does not require real force in absence of quality randomness.

[TippingPoint]

"law enforcement remains in unanimous agreement that the continued widespread availability and increasing use of strong, non-recoverable encryption products will soon nullify our effective use of court-authorized electronic surveillance."  _{- Louis Freeh, former Director of FBI}

[becoin]

I already updated the second post after my announcement to give some credit to Jean-Pierre, though I guess most of the credit goes to the researchers who uncovered the vulnerabilities in the first place. But still, it was very useful for Jean-Pierre to inform us privately.

The Android JVM is open source. It's called Dalvik. I don't know where anyone would get the idea it's not open source from.

It's a pseudo open source!

It is not strictly a JVM as it is register based VM (opposed to stack based standard JVM) that executes its own Dalvik byte code, not Java byte code. A tool called dx is used to transform some Java classes into special .dex file format. Some structures (magic numbers) of the .dex file format are not well documented. If you create your own VM and file system and tag it open source you have to open source all the tools you use to compile it including the JIT compiler and interpreter.

Few links exposing recent security holes in Dalvik's proprietary .dex file format:
http://www.retrodev.com/android/dexformat.html

Anatomy of a security hole - Google's "Android Master Key" debacle explained
http://nakedsecurity.sophos.com/2013/07/10/anatomy-of-a-security-hole-googles-android-master-key-debacle-explained/

Anatomy of another Android hole
http://www.digitalnewsasia.com/node/2940

[SgtSpike]

Could the OP be updated to include a list of apps that have been updated against this bug?  I don't want to read through the whole 8 pages to find out which apps have and have not been updated, and I'm sure it'd be helpful to other people as well.

[DiamondCardz]

Could the OP be updated to include a list of apps that have been updated against this bug?  I don't want to read through the whole 8 pages to find out which apps have and have not been updated, and I'm sure it'd be helpful to other people as well.

These are the current statuses:



From http://bitcoin.org/en/alert/2013-08-11-android - they should be getting updated daily.

[phatsphere]

another question i have in mind is chrome, firefox, opera mobile or the native android web browser itself. suppose, i'm using one of those on my android phone or tablet, and i'm using a web-wallet like blockchain or a bitaddress generator. do these browsers also rely on this flaw in java or do they circumvent this via native C code?
i think it depends on the browser …

[CurbsideProphet]

Thanks for the heads up.  Guess I'll have to do another vanity addy, although I've never really used it other than for novelty.

[blockgenesis]

Could the OP be updated to include a list of apps that have been updated against this bug?  I don't want to read through the whole 8 pages to find out which apps have and have not been updated, and I'm sure it'd be helpful to other people as well.

These are the current statuses:



From http://bitcoin.org/en/alert/2013-08-11-android - they should be getting updated daily.

Blockchain.info just released v3.54 , I've updated the page, it should refresh in the next minutes. Afterwhile, perhaps that few more details will be added but since all stated wallets now have updates published, I guess that most of it is over. Now it's just a matter of waiting for these updates to deploy and stay around to see how it goes.