[ANNOUNCE] Android key rotation

[TippingPoint]

Listen to him ^  ^

[justusranvier]

...or use BIP32 to generate the addresses.

[weavejester]

A quick question. Is there any way of getting to the rotated keys of the Bitcoin Android app from a backup of the old keys? Or is there any auto-backup facility for the application? Or an auto-backup after the key rotation?

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.

Please tell me that the update didn't automatically transfer all the bitcoins over to a new address without making some form of backup first? It definitely looks like that's the case, but it's such an obviously terrible idea that I have difficulty believing anyone could have actually done it without some form of safeguard.

[TheKoziTwo]

"apetersson" says that "nobody knows" if bitaddress.org is safe... but even in the worst case scenario that there is a problem with the random algorithm wouldn't the entropy by mouse movement requirement be enough to ensure keys are still random?

I don't see how it can not be safe... thoughts?

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?

[casascius]

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

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)

[WinVery.com]

This will never happen as required in full.  Sounds like a job for a mop.

[molecular]

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.

[niko]

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.

[Hawkix]

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.

There's a lot of XORing inside SHA256, do not worry ;-).

[Hawkix]

...

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.

...

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?

[JoelKatz]

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.

[🏰 TradeFortress 🏰]

On certain environments (like Chrome/Firefox with no hardware RNG access through JS), Blockchain.info is susceptible to the same attack (reused R value) outside of Android.

See this thread for more information: https://bitcointalk.org/index.php?topic=277595.0

[Lauda]

Listen to him ^  ^

+1
He is a wise amn.

[weavejester]

...

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.

...

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?

It was the bitcoin-wallet app I was using. I checked the blockchain.info website to trace the transactions the app took. I've got no idea if the blockchain android app does the same thing as bitcoin-wallet.

[TheKoziTwo]

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

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)

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.

[molecular]

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.

doesn't make much difference if you feed it through sha256 in the end.

[molecular]

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.

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

[molecular]

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

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)

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.

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

[casascius]

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 danger with XOR is nonexistent if you're combining entropy from two different sources.  If you are XORing keyboard gibberish with the output of securerandom, the odds of them being identical are for practical purposes zero, unless securerandom becomes suddenly broken in a way that it just happens to return user keyboard input instead of random-looking numbers, which is pretty unlikely.

"Rolling your own crypto" = trying to reinvent AES.

XORing two completely independent sources of likely good random data = simple enough to not be crossing the line of rolling your own crypto, in my opinion.

[casascius]

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

If you can take the timing into account, then sure, that's extra entropy, better than not having it.  But the keystrokes themselves, as biased as they will be toward "asdf" and such, are still going to have at least a couple useful bits of entropy a piece, and importantly, they preserve the ability to positively verify that the string you entered gets passed to the hash function as part of the input string to be hashed.