[ANNOUNCE] Android key rotation | Bitcointalksearch.org

casascius

vip

Activity: 1386

Merit: 1140

The Casascius 1oz 10BTC Silver Round (w/ Gold B)

Quote from: JoelKatz on August 23, 2013, 01:50:12 PM

Quote from: casascius on August 23, 2013, 12:43:50 PM

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.

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.

Quote

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

Given the assumption of doing something to hedge against a bad RNG versus nothing, I agree with you on both points.

JoelKatz

legendary

Activity: 1596

Merit: 1012

Democracy is vulnerable to a 51% attack.

Quote from: casascius on August 23, 2013, 12:43:50 PM

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.

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.

Quote

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

casascius

vip

Activity: 1386

Merit: 1140

The Casascius 1oz 10BTC Silver Round (w/ Gold B)

Quote from: niko on August 22, 2013, 04:30:06 PM

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.

(e.g. source #1 = keyboard mash, source #2 = /dev/urandom, and the likelihood of the hash of my keyboard mashing having any coincidence with the output of /dev/urandom being zilch. The only plausible worst case scenario - which would have to be "/dev/urandom is really just a keylogger that returns the hash of recent keyboard input" is something easily proven to be false to anyone even remotely familiar with how /dev/urandom really works)

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.

JoelKatz

legendary

Activity: 1596

Merit: 1012

Democracy is vulnerable to a 51% attack.

Quote from: TippingPoint on August 22, 2013, 10:36:17 PM

More amateur cryptography:

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

I don't think there's any defect in using the hash of the concatenated seeds. Of course you have to choose an appropriate hash function, but other than that you should be fine. The output should be at least as strong as the strongest of the seeds you concatenated, up to the strength of the hash function.

phatsphere

hero member

Activity: 763

Merit: 500

Quote from: apetersson on August 23, 2013, 04:41:11 AM

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

the google opensource/android blog just recently featured a workaround with a code example. have you seen it?

apetersson

hero member

Activity: 668

Merit: 501

instead of toying around with XOR and | you want to feed it in a cryptographic hash function such as sha256 to accumulate the entropy. "simply" feed every new genuine randomness to a MessageDigest
and read the randomness from it. A proper application of this approach is the Fortuna PRNG. I will dedicate some resources into providing a library for Android + java from it, so we no longer have to trust /dev/urandom exclusively.

TippingPoint

legendary

Activity: 905

Merit: 1000

More amateur cryptography:

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

niko

hero member

Activity: 756

Merit: 501

There is more to Bitcoin than bitcoins.

Quote from: JoelKatz on August 22, 2013, 02:34:13 PM

Quote from: grau on August 22, 2013, 01:32:03 PM

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

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 that case, xoring will be at least as strong as the stronger source itself (the extreme case of broken source always returning the same number).
Having said all that, I can't remember why I thought concatenation might be worse - I was imagining a broken hash function whose output depends, for example, more on the first half of the input block, and less on the second half. But that still wouldn't help my original claim, since presumably my two inputs are the same size or larger than the block size - definitely not smaller, as that would be a glaring mistake.
Thanks for being patient with this. I've obviously realized a few things in the process, most importantly that amateur cryptography makes as much sense as amateur brain surgery.

JoelKatz

legendary

Activity: 1596

Merit: 1012

Democracy is vulnerable to a 51% attack.

Quote from: grau on August 22, 2013, 01:32:03 PM

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

grau

hero member

Activity: 836

Merit: 1030

bits of proof

Quote from: JoelKatz on August 22, 2013, 01:05:48 PM

Quote from: grau on August 22, 2013, 03:48:32 AM

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.

JoelKatz

legendary

Activity: 1596

Merit: 1012

Democracy is vulnerable to a 51% attack.

Quote from: grau on August 22, 2013, 03:48:32 AM

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.

grau

hero member

Activity: 836

Merit: 1030

bits of proof

Quote from: JoelKatz on August 20, 2013, 06:23:24 PM

Quote from: niko on August 20, 2013, 01:04:44 PM

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.

JoelKatz

legendary

Activity: 1596

Merit: 1012

Democracy is vulnerable to a 51% attack.

Quote from: niko on August 20, 2013, 01:04:44 PM

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.

niko

hero member

Activity: 756

Merit: 501

There is more to Bitcoin than bitcoins.

Quote from: JoelKatz on August 20, 2013, 01:49:29 AM

Quote from: niko on August 20, 2013, 01:39:12 AM

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.

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.

casascius

vip

Activity: 1386

Merit: 1140

The Casascius 1oz 10BTC Silver Round (w/ Gold B)

Quote from: molecular on August 20, 2013, 09:36:38 AM

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.

casascius

vip

Activity: 1386

Merit: 1140

The Casascius 1oz 10BTC Silver Round (w/ Gold B)

Quote from: molecular on August 20, 2013, 09:35:46 AM

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.

molecular

donator

Activity: 2772

Merit: 1019

Quote from: TheKoziTwo on August 20, 2013, 08:51:32 AM

Quote from: casascius on August 19, 2013, 10:15:17 PM

Quote from: TheKoziTwo on August 19, 2013, 09:18:11 PM

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?

molecular

donator

Activity: 2772

Merit: 1019

Quote from: JoelKatz on August 20, 2013, 01:49:29 AM

Quote from: niko on August 20, 2013, 01:39:12 AM

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

donator

Activity: 2772

Merit: 1019

Quote from: niko on August 20, 2013, 01:39:12 AM

Quote from: molecular on August 20, 2013, 01:22:20 AM

Quote from: casascius on August 19, 2013, 04:57:36 PM

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.

TheKoziTwo

legendary

Activity: 1552

Merit: 1047

Quote from: casascius on August 19, 2013, 10:15:17 PM

Quote from: TheKoziTwo on August 19, 2013, 09:18:11 PM

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.

Topic: [ANNOUNCE] Android key rotation (Read 66313 times)