Bitcoin Forum

done and done, thanks to you and this community for such watchfulness and timeliness with these kinds of issues.

Thank god I have an iPhone :)

a component of Android responsible for generating secure random numbers contains critical weaknesses

For blockchain.info wallets, even if the keys were generated on a desktop/laptop computer or iPhone, if any payments were made from an Android device, you are also affected. Likewise, if you have imported private keys from elsewhere into an Android wallet and made payments with it, you may also be affected.

Don't get this...
Wallet created with Bitcoin-QT; imported to Blockchain, but created new Address in Browser - still vulnerable?

Could you please clarify:

1. Is this the same, or a different, issue from the one being discussed in the "Bad signatures" thread?

2. Is it absolutely and completely true that this is an Android issue, ie. hosted Blockchain.info wallets and other wallet software written in Java is not affected?

3. I generated my wallet keys off-device. Am I still vulnerable?

4. I generated my wallet keys on-device but have only received funds and not sent any, so no transactions were actually generated by the Android application. Am I still vulnerable?

5. If it turns out from any of the above two reasons that I am not vulnerable, will the update to Android Wallet specifically still rotate my wallet? There are probably a lot of wallets out there who would be greatly hurt by unnecessary transaction fees.

Could this be what was behind all those random 1 mBTC payments that were going around?

As they are spent, if the wallet was Android they are now multiple spends from same address possibly allowing attacker to figure out private key.

pink is a really crappy color, fwiw.

So basically, Google pulled a Sony...

https://i.imgur.com/e9jUO.png

So, this is the same type of attack as was Sony Playstation network hack (ECDSA random numbers not being random) - so you would expect that developers test their software for the same weakness, right?

AFAIK it is a relatively new algorithm chosen because of short signatures produced, so it might even get broken (even with working random number generators). Something should be done about that...

I noticed it instantly, actually.  :-X

This vulnerability is yet another reason address reuse in Bitcoin clients must be eliminated.

Prior to this, using non-deterministic wallets was either a privacy disaster (single key model) or else a usability nightmare (random key model).

Now anything which encourages address reuse should be considered negligent.

in case anyone is confused about the color coding.

This vulnerability is yet another reason address reuse in Bitcoin clients must be eliminated.

Prior to this, using non-deterministic wallets was either a privacy disaster (single key model) or else a usability nightmare (random key model).

Now anything which encourages address reuse should be considered negligent.

Not really.  This is a problem with a specific implementation of a specific secure random number generator (android).

Not really.  This is a problem with a specific implementation of a specific secure random number generator (android).

But that has nothing to do with deterministic wallets. Non deterministic wallets do not require address re-use.

Not really.  This is a problem with a specific implementation of a specific secure random number generator (android).

If addresses are never reused, it doesn't matter if individual private keys are compromised after the fact.

i'm confused--are all blockchain.info wallets vulnerable?  (even if you dont have an android phone)

i'm confused--are all blockchain.info wallets vulnerable?  (even if you dont have an android phone)

Here are the rollout statuses of each wallet I'm aware of:

blockchain.info wallet: An update was released today that adds a new key using a fixed RNG, so you can manually rotate now. Another update will follow in the coming days that will automatically re-send all coins controlled by the previous keys to the new one.

Please note that apps where you don't control the private keys at all are not affected. For example, exchange frontends like the Coinbase or Mt Gox apps are not impacted by this issue because the private keys are not generated or controlled by you at all.

Basic rule of thumb - if you'd lose the money if the phone/tablet were destroyed (assuming no backups), and that device is an Android device, then you need to upgrade ASAP.

For blockchain.info wallets, even if the keys were generated on a desktop/laptop computer or iPhone, if any payments were made from an Android device, you are also affected. Likewise, if you have imported private keys from elsewhere into an Android wallet and made payments with it, you may also be affected.

Annoyingly the Schildbach wallet seems to now enforce(!) a 0.0001 BTC default fee! >:(

Well, these issues aside - thanks for informing us.

Annoyingly the Schildbach wallet seems to now enforce(!) a 0.0001 BTC default fee! >:(

Well, these issues aside - thanks for informing us.

Ive always thought computers could not generate random numbers.    I once won a large prize buying the last ticket before a lotto draw, computer random number generator was the source though I didnt complain at the time

This is a common misconception. Real-world computers actually have access to any number of sources of real randomness. For example, the offset between the crystal oscillator that drives the CPU and the crystal oscillator that drives the network card is determined by microscopic zone temperature variations that are believed to be truly random. The latency of a hard disk drive is dependent on turbulent airflow drag on the spindle which is also believed to be truly random. Some CPUs and chipsets have true random number generators on them, usually obtained from shot noise which is also believed to be truly random. (And even if they're not truly random, they are entirely unpredictable.)

Well what do you expect? The minimum I always pay is 0.0006 or 0.0005 on the -Qt client. Non-fee transactions usually means hours to days waiting for confirmations.

Ive always thought computers could not generate random numbers.    I once won a large prize buying the last ticket before a lotto draw, computer random number generator was the source though I didnt complain at the time

Nothing can generate a random number. Us included. Only pseudo-random.

I cant find any wallet other than bitcoin-qt that lets you put a 0.00 tx fee. Surprising to see people in here wondering about fees. it's a penny. Go sell something on PayPal and tell me about fees.

I think only if it's generated by Android.

..... Payment addresses should not be re-used after money is spent. If you do not re-use the address then you can not fall victim to this if your random generator is not as random as it should be.

I guess, or understand, that 'receive' addresses can be safely used more than once?

Receive addresses should be used exactly one time, then never again.
If you reuse addresses for receiving bitcoins you have no financial privacy, and you're vulnerable to issues like this.

Oh bother. Thanks. In my case I have never used an android device for any Bitcoin stuff so I trust I am safe from the current non random number issue(?)
However, it has been convenient to gather occasional small amounts from the (get free bitcoins) site http://netlookup.se/free-bitcoins/247552
Just to be very clear here, I now should not offer the same receive address more than once then?
tia
(edit)
I note that  this site mentioned above works on the basis of a receive address being used repeatedly.... Is it a scam site? or is it just  doing rather bad things?

Well what do you expect? The minimum I always pay is 0.0006 or 0.0005 on the -Qt client. Non-fee transactions usually means hours to days waiting for confirmations.

I cant find any wallet other than bitcoin-qt that lets you put a 0.00 tx fee. Surprising to see people in here wondering about fees. it's a penny. Go sell something on PayPal and tell me about fees.

I second this. While mining with deepbit, their tx fees are not included. One payment sat for almost 4 days before being picked up by eligius pool. Just send the penny.

Fees have to be attached due to a strange quirk of bitcoind mining code - it only allocates 27kb per block for free transactions. There's no obvious reason that should be the case and I'm sure it'll get fixed at some point. Even a penny is a high fee to pay, IMO.

I wouldn't mind actually waiting some time if that meant my transaction was free. I didn't want or plan to transfer these funds in the first place and I don't mind them being stuck for some time in limbo. Once the TX is out there, it would be hard to double spend it anyways.

Schildbach allowed this (0 fees) too some time ago so I consider it a regression. If I use PayPal, I pay for a service that goes beyond simple money transfer (I get fraud protection etc.).

This is just stupidity on deepbit's end - they could always include their payouts for free in their own blocks and I suggested something like that (pools accepting each other's payouts for free) long time ago. Back then it was anyways easy to get anything transacted for free, so they never went forward with it. I don't want to pay a whole penny for a few bytes of storage that will be pruned away sooner or later anyways.

The wallet used to have a setting that let me set fees to 0 on my own risk. This setting seems to be gone...
Anyways, fee handling and transaction priorization is a big mess in my opinion still in Bitcoin, especially in the reference client that everyone seems to use unreflected without even thinking about the settings.


About receiving coins at the same address:
In the end it means that you potentially loose privacy (e.g. the free bitcoins site could link your IP to your address, then you sell a obile phone on the web and let them pay to the same address - now the free bitcoin site can see that you received some more coins + the buyer of the phone sees that you probably used this site). Security wise it means that once you send something from your address, you expose the public key belonging to that address. In this case, the signature generated with it is weakening security - there is also the possibility of a breach of ECDSA keys in general. As long as nothing has been transfered off an address, it is as safe as possible from a current security standpoint.

Oh bother. Thanks. In my case I have never used an android device for any Bitcoin stuff so I trust I am safe from the current non random number issue(?)
However, it has been convenient to gather occasional small amounts from the (get free bitcoins) site http://netlookup.se/free-bitcoins/247552
Just to be very clear here, I now should not offer the same receive address more than once then?
tia
(edit)
I note that  this site mentioned above works on the basis of a receive address being used repeatedly.... Is it a scam site? or is it just  doing rather bad things?

If you are receiving miniscule amounts, then it doesn't matter. You can use common sense. The site isn't scam.

Nothing can generate a random number. Us included. Only pseudo-random.

2. It's an Android issue, not a Java issue.

Just wondering, would this affect Electrum as well?

I m asking as it uses Google Scripting Layer & Python for Android

http://electrum.org/android.html

Re: Electrum. I don't know how Electrum on Android does signing. It might well have a similar problem, especially if it uses OpenSSL.

Thank god I have an iPhone :)

How "critical" is it? Has there been any successful attack using this weakness?

You're joking, aren't you? :)

This post (https://bitcointalk.org/index.php?topic=251743.0) is over one month old, while this one (http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html) over half a year...
Watchfulness my ass :)

The exploit isn't in the algorithm, it's in generating a secure random number. It also wasn't the PSN hack, it was the PS3 hack.

With Sony, they used the same number every single time. It simply wasn't random, and was a horrible, or rather, *not* an implementation of the encryption in the right manner.

With Android, the same random number apparently comes up once in a while. Still horrible considering the money involved (probably worse), but there's only a chance to get the same random number (as opposed to guaranteed with Sony).

So you believe that radioactive decay is deterministic? If so, you are in the minority. Say I have two uranium atoms and one of the decays before the other, what do you think accounts for that?

i randomly received .15 btc yesterday to one of my android generated addresses.  Why would I randomly get free money?  this never happened to me before, is this related to the flaw?

i randomly received .15 btc yesterday to one of my android generated addresses.  Why would I randomly get free money?  this never happened to me before, is this related to the flaw?

i randomly received .15 btc yesterday to one of my android generated addresses.  Why would I randomly get free money?  this never happened to me before, is this related to the flaw?

Of course it must work multiple times - just like PGP/RSA has been working, ever since it was invented.
And nobody says that you using the same PGP key twice "should be considered negligent" - it would just defeat the purpose of a digital signature :)

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

http://bitcoin.org/en/alert/2013-08-11-android

We recently learned that a component of Android responsible for generating secure random numbers contains critical weaknesses, that render all Android wallets generated to date vulnerable to theft. Because the problem lies with Android itself, this problem will affect you if you have a wallet generated by any Android app. An incomplete list would be Bitcoin Wallet, blockchain.info wallet, BitcoinSpinner and Mycelium Wallet.

as a former Google employee I thank you for your vigilance!

The new bitcoinj release that will be announced shortly has some initial code for BIP32. It's definitely something I want to integrate. It's difficult on mobile devices because they don't have any swapfile, so you can't just use as much memory as you want. You have to define a key window in which money can be received. Coins sent to keys that fall outside that window won't show up which is obviously very problematic. All in all, it's delicate and will require some careful experimentation and testing to make it work.

What about other Android wallets that are derived from Schildbach's code, such as Litecoin-Qt and Feathercoin-Qt??? I assume they have the same vulnerability. Any plans to update those?

@millsdmb, that's not helpful. Your opinion about Litecoin is less important than helping prevent theft, and hope others in this forum will have useful information for the community at large.

i randomly received .15 btc yesterday to one of my android generated addresses.  Why would I randomly get free money?  this never happened to me before, is this related to the flaw?

The reason that clients reuse addresses is because random key wallets are unsuitable for general use.

Requiring users to update their backups after every n transactions results in permanently lost funds.

The solution is to implement BIP32.

So you believe that radioactive decay is deterministic? If so, you are in the minority. Say I have two uranium atoms and one of the decays before the other, what do you think accounts for that?

It's possible a user exportet a single key from his electrum wallet and used it in mycelium (for example). It could get compromised by the bad RNG in android and compromise all keys of the wallet.

I just don't ever export private keys from them.

How vulnerable is electrum to the seed issue that android has
particularly on the various OS's

eg

OSX 10.8 +
WIN7 / WIN 8
UBUNTU

etc
etc

does any one even know???

how can we check we are not doing

http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html

this?

The BOP android wallet to be released in conjunction with our payment solution uses BIP32.

The mobile uses the next even index of BIP32 as change and odd as next receiver addresses. The server implements a single pass scan using a BIP32 public key, that generates an increasing look ahead window from last seen address on the block chain.

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

Well done!

The Daily Telegraph is claiming it was known about since January. Is this media disinformation?

Depends how you define "it".
http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html

as far as I know it's only very recently that it was found that Android PRNG also suffered from this issue.

Got error 157 'Unknown error code' from NDBCLUSTER

when trying to check sigs on blockchain.info.....

is this deliberate!!!!

while this is sorted out

I discovered the flaw thanks to a small stash of stolen bitcoins.

It all started with a missed call from a friend at 00:30 on August 5, and a subsequent SMS telling me that he got 0.91 bitcoins stolen from his Android wallet. "Somebody hacked my Android phone" he would repeat. I did not believe this to be likely. He is the most security conscious person I know. Besides, he is a computer scientist and knows the Bitcoin protocol in and out. Android phones are known to be vulnerable, but it's very unlikely that a phone that only ran reputable apps from Google Play got hacked. I thought about Spock, who quoted Arthur Conan Doyle: "Once you eliminate the impossible, whatever remains, no matter how improbable, must be the truth". The impossible was that his phone got hacked. The truth then should be that somebody found his private key through cryptanalysis on the Bitcoin blockchain (the public ledger were all transactions are kept).

A lookup on the address that the funds were sent to revealed a forum post https://bitcointalk.org/index.php?topic=251743, so I put on my detective hat and read the post. I also published a message to it stating what had happened to my friend. The common factor seemed to be Android, and I immediately thought about the possibility of a flaw in its pseudo-random number generator (PRNG).

I investigated online and found this paper http://www.scribd.com/doc/131955288/Randomly-Failed-The-State-of-Randomness-in-Current-Java-Implementations#page=9, which I sent to Mike Hearn pointing him to page 9 in which the flaw in Apache Harmony's PRNG (the one used by Android) was described. I also pointed to him that his BitcoinJ code was using that PRNG in the regular non-seeded way, which triggered the flaw.

I originally suggested that private key collisions may have being found and exploited. Later on the weekend a reply to the Bitcoin forum post by johoe clarified that the issue with the PRNG was leading to collisions in the random number parameter k that the elliptic curve signature algorithm needs in order to be secure, making it trivial to extract the private key from two transactions that used the same k.

The Daily Telegraph is claiming it was known about since January. Is this media disinformation?

blockchain.info has been sort of offline, for over 5 hrs already.

Moreover blockexplorer.com has also been stopped - somewhere yesterday.

hmm deliberate


but surley bitcoind can do this as well. a program tha compares sigs must be able to run through and auto check

What do I do?? I have 20 BTC in Blockchain.info and now it doesn't even load

Did someone steal my coins??

Got error 157 'Unknown error code' from NDBCLUSTER

You're joking, aren't you? :)

This post (https://bitcointalk.org/index.php?topic=251743.0) is over one month old, while this one (http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html) over half a year...
Watchfulness my ass :)

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

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

As always, Bitcoin is mercilessly exposing every shady practice on everything it touches. I don't trust Google. Like MS they are also in bed with the US government. They try to promote Android as open source but keep the JVM for Android closed. This is why every Java based app for Android is not truly open sourced! Period. Paragraph.

also, one should answer the question, if imported vanity addresses are a problem. i would say no, only the possible other addresses where some change might have gone.

It's a pretty disturbing oversight on the part of those who wrote the Android PRNG library.

yes. that's what's baffling me, too. especially given the fact, that an android device has much more sources of random information than a commodity pc. just think about gyroscope, magnetism, acceleration, ...

Oh yeah, why the developers never think about it.. using sensors as random generator that almost impossible to generate same pattern, brilliant!

Oh yeah, why the developers never think about it..

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.

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

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

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? 

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

Exhibit A

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

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

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

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.

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.

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:

http://gyazo.com/df6e717b5c840bf39878ad069b445088.png

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

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 …

Just wondering, would this affect Electrum as well?

http://electrum.org/android.html

Shouldn't the key rotation be performed only on private keys known to be influenced (generation, transaction signatures) by this random generator flaw? I do not want to run Blockchain on my Android to realize that it will re-send and merge (automatically .. ugh) all my savings into another address!

These are the current statuses:

http://gyazo.com/df6e717b5c840bf39878ad069b445088.png

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

I'm wondering if this means they aren't updating Bitcoin Spinner?  Got my phone set up the way I want it, and this means switching yet another app out.  I don't have any bitcoins in it right now, and probably won't in the near future anyway.  Haven't sent anything from it in months, so I'm not in too big a hurry to update it.

According to Jan, an update to bitcoinspinner was pushed to google play, will appear soon.

what do i do if my wallet address is locked onto another site and I've updated my wallet already? will it go to the old address then be transferred internally into the new one?

BTCy the way, my import/export keys menu options are greyed out.  What do I do?  How can I get my BTC?

@casascius: do you know about this page: http://www.random.org/bytes/ ? that could also be a source, which could replace the mouse-moving-timestamp thing because it comes from an external source.

When creating a self seeding SecureRandom instance (by calling the constructor without arguments and subsequent setSeed() call), the code fails to adjust the byte offset (a pointer into the state buffer) after inserting a start value. This causes a counter and the beginning of a padding (a 32 bit word) to overwrite parts of the seed instead of appending.

Sure, though I have every reason to believe their bytes are truly random, for security purposes, I don't.  When I generate keys, the machine doesn't have internet access anyway, so I suppose it's just an alternative (sub)string to paste as a response to the "keyboard mash" if I want to copy it in with a flash drive etc.

very quick。

I have the blockchain.info app installed on my Android device, but I am sure that I never created a new address within it and I'm also sure that I never created a transaction on that device. Basically the app only acted as a way to check the wallet balance and transaction history (i.e. read-only actions).

Are my private keys and transactions at risk if I don't do a key rotation? With the many small and non-mature inputs I have on my many addresses, I am heading for maybe over 0.02 btc for transaction fees... last time I did a key sweep it was something like 0.01 btc, and to be honest I think my wallet is even more fragmented now.

I don't think the app ever had any reason to request random numbers unless it is creating addresses without user intervention.

On a related thought: many online wallets generate private keys client side with JavaScript. How secure is the PRNG used by JS, or is it not used in a direct way (are there other sources of entropy)?

My understanding is that if you sent Bitcoins from any of the addresses in your blockchain.info wallet more than once, it could reveal the private key of said addresses to anyone clever enough looking at the blockchain.  If you didn't generate any addresses or send any Bitcoins from it, then you should be fine.

Did anyone get their mobile wallet BTC stolen?

Did anyone get their mobile wallet BTC stolen?

It would be a huge problem if it wasn't quick enough.

So, I think it's a huge problem, check the date of this post:
http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html

So, I think it's a huge problem, check the date of this post:
http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html

That post is unrelated to issues on Android.

Sure, though I have every reason to believe their bytes are truly random, for security purposes, I don't.  When I generate keys, the machine doesn't have internet access anyway, so I suppose it's just an alternative (sub)string to paste as a response to the "keyboard mash" if I want to copy it in with a flash drive etc.

So, I think it's a huge problem, check the date of this post:
http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html

You should make your own hardware for pulling random data for your coins. Something like a geiger counter near a radiation source. Now that would be truly the best source for truly random data.

(Unless if you distrust the laws of physics  :D )

You should make your own hardware for pulling random data for your coins. Something like a geiger counter near a radiation source. Now that would be truly the best source for truly random data.

(Unless if you distrust the laws of physics  :D )

I would have, but at the time, I was fresh out of radioactive material. Maybe next time.

I would have, but at the time, I was fresh out of radioactive material. Maybe next time.

I would have, but at the time, I was fresh out of radioactive material. Maybe next time.

dismantle a smoke detector

I would have, but at the time, I was fresh out of radioactive material. Maybe next time.

Or a bowl of brazil nuts

Formerly known as ...

the hero of?

Good luck patching Android with third parties between Google and your phone.

So, does this only affect Android wallets (Private Keys) generated by the Android wallet apps, or would my BTC address which I already had and then added to the blockchain wallet app also be affected? I hope not, cause I like keeping the same address for Public use, and then moving the BTC into my private addresses, never revealing public keys or addresses.

I would have, but at the time, I was fresh out of radioactive material. Maybe next time.

It only affects addresses/keys that are generated on Android.

a component of Android responsible for generating secure random numbers contains critical weaknesses

or did someone just forget to seed it properly?

"Everytime I give a seed and try to generate 100 numbers, they all are the same. Please help."
http://stackoverflow.com/questions/12458383/java-random-numbers-using-a-seed

 ;)

I would feel much better if bitcoin wallets generated new addresses using the following method:

SHA256(something_from_SecureRandom + some_user_supplied_constant + some_incrementing_counter + current_system_time/tickcount)

The "some_user_supplied_constant" could be nothing more than a string collected from the user upon first invocation of the program, and perhaps even saved to a config file.  It serves the same purpose as salt.  Because the user supplies it, it's pretty easy to verify that it isn't predictable.  It will have relatively poor entropy, but would successfully serve the purpose of making mass cracking of insecure random numbers pretty much impossible, as well as verifiably ensuring that there is some portion of the input that is truly unpredictable by an outside attacker.

This user supplied constant is the same as the mouse entropy used at bitaddress right?

I would feel much better if bitcoin wallets generated new addresses using the following method:

SHA256(something_from_SecureRandom + some_user_supplied_constant + some_incrementing_counter + current_system_time/tickcount)

My first thought about this idea was: No, an app dev should not concern himself with crypto primitives. The underlying rng used should already do that (combine different sources). Best practice is to leave implementation of primitives to experts and crowd-scrutiny. Obviously this best practice failed.

Seeing that combination of different sources doesn't remove any entropy (this is the case, right?), I changed my mind.

I would be more comfortable xoring than concatenating multiple inputs.

...

From a look on blockchain.info, it looks like the Android bitcoin wallet generated a new key and transferred all of my existing bitcoins across to the new address without any user intervention. However, the application cache for the bitcoin app has been cleared, so it doesn't appear to have the private key to the new address.

...

I would be more comfortable xoring than concatenating multiple inputs.

Listen to him ^  ^

Are you telling us that the new BlockChain Android app did this automatically, without asking user?

I've never generated a key or send transaction from my Android app yet, and I do not want to have all my addresses here mixed together and sent to another private address.

Can you describe how this automatic process (SCARY) works, when running updated Blockchain app?

Sort of.  A keyboard mash is much easier to audit that it's properly being added to the entropy pool.  If I can verify that the generator is producing private keys that are a hash of my chosen string plus some other data, I think it's fair game to assume that if my string is decently unpredictable and secret, that my private keys aren't going to be predictable to an outside guessing attack.  The problem with mouse data is it's hard to know if it was any good.  What if the user has a touchscreen and doesn't generate mouse movement events unless you actually press something etc...?  Bitaddress.org moves on with whatever additional entropy it presumably got from the mouse, which could be zero, and which someone might later find it may dangerously be not enough.

I think keyboard mashes have low entropy per character (e.g. I bet "asdf" is quite overrepresented in them) but if they're forced to be very long (like a line or two of text) I see them as a very decent way to "cut" the output of a "securerandom" that might be later found to be broken ("cut" as in cut a deck of cards)

I would be more comfortable xoring than concatenating multiple inputs.

Your better off concatenating and then hashing the concatenation to the needed size. XORing is not a good idea. To see why, consider which of these is safer (where | is concatenation).

1) XOR(SHA256(X), SHA256(X))

2) SHA256(X | X)

The former is zero no matter what X is. The latter is safe so long as X is safe.

Now, consider this. X and Y are fairly random but, due to a broken PRNG, only differ in a few bits. Which is safer:

1) XOR(X, Y)

2) SHA256(X | Y)

The former can be insecure even if both X and Y are secure alone because all the common bits drop out. 2 is at least as strong as the stronger of X alone or Y alone.

Yeah that makes sense. I make sure to move the mouse around as much as possible before generating addresses. But I guess bitaddress could improve here, they could do like TrueCrypt, letting the user move the mouse around for as long as user wants, I usually move the mouse a few minutes when creating a TrueCrypt container. And they could introduce a minimum amount of movement... If they did that, it would be as good as keyboard input I assume.

Thanks for this explanation! Didn't think of that danger with XOR.

niko just made a point towards "app developers should not concern themselves with coding crypotgraphic primitives, not even combining them". I'm trending back to "best left to experts".

The "keyboard mashes" usually work by timing the keystrokes, no?

Your better off concatenating and then hashing the concatenation to the needed size. XORing is not a good idea. To see why, consider which of these is safer (where | is concatenation).

1) XOR(SHA256(X), SHA256(X))

2) SHA256(X | X)

The former is zero no matter what X is. The latter is safe so long as X is safe.

Now, consider this. X and Y are fairly random but, due to a broken PRNG, only differ in a few bits. Which is safer:

1) XOR(X, Y)

2) SHA256(X | Y)

The former can be insecure even if both X and Y are secure alone because all the common bits drop out. 2 is at least as strong as the stronger of X alone or Y alone.

I was referring to seeded random generators f(xor(A,B)) versus f(A|B). With an ideal function, it shouldn't matter. With a broken one, it might matter.

With a broken one, you're much better off with f(A|B) than f(xor(A,B)). If A and B have too many bits in common, the xor is a disaster.

If the generator is broken no operator will make it better. Feed a shifted pattern to | and see an other sort of disaster.

Agreed, but it's still important to prefer an operator that won't make it worse over one that will.

do not get your point. xor is not worse than or since none of them add any value in this context.

We are comparing XOR to concatenation. And XOR is much worse. If you XOR two values that have a lot of bits in common, even if each of them is secure individually, the result of the XOR may be predictable, even if you hash it afterwards. If you concatenate, the result is at least as strong as the weakest thing you concatenated, even if you hash it afterwards (up to the strength of the hash function).

I will dedicate some resources into providing a library for Android + java from it, so we no longer have to trust /dev/urandom exclusively.

More amateur cryptography:

Is there a compound function that could address both examples of brokenness better than either XORed or concatenated seeds alone?

You have chosen a particular state of brokenness of the two sources of entropy, so they tend to have bits in common, and so that xoring indeed leads to low-entropy seed. I have chosen a particular state of brokenness, so that one of the two sources is broken, the other is not.

In support of this, in my case, I've suggested that two sources of entropy should be so different such that the possibility of them being broken in the same way is negligible.
...
If this is done, then XORing and concatenation should be equally effective.

On the other hand, if source #1 and source #2 are similar or the same RNG that is suspected to be broken, then I believe concatenation and XOR to both be ineffective, because both of them are pretending that it's a safe assumption that an RNG found to lack entropy (i.e. is broken) can suddenly be redeemed by running it twice.

The difference is that XORing can produce an output weaker than either input, concatenation cannot. The point is to protect against very unexpected failures without having to make assumptions about how well the underlying code is working. For example, you might write your code to use two different sources of entropy but then someone realizes that one of your sources is weak and so changes it to use a better source and now you're not using different sources anymore. Concatenation is robust, XOR is not.

The idea is to tolerate the unexpected case where source 1 and source 2 are similar or the same. XOR doesn't. The best imaginable algorithm can't produce an output stronger than the sum of the strengths of all of its inputs.

If we didn't have to tolerate unexpected cases, we wouldn't need any of this. An algorithm that can make things worse in unexpected cases is a bad idea, especially when it's so easy to make algorithms that don't.