[ANNOUNCE] Android key rotation

[niko]

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.

[JoelKatz]

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.

[grau]

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]

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]

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]

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

[niko]

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.

[TippingPoint]

More amateur cryptography:

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

[apetersson]

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.

[phatsphere]

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?

[JoelKatz]

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.

[casascius]

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]

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.

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]

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.

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.