Messages in this thread | | | Date | Fri, 15 Aug 2003 13:48:57 +0100 | From | Jamie Lokier <> | Subject | Re: [RFC][PATCH] Make cryptoapi non-optional? |
| |
Val Henson wrote: > See Matt Mackall's earlier post on correlation, excerpted at the end > of this message. Basically, with two strings x and y, the entropy of > x alone or y alone is always greater than or equal to the entropy of x > xored with y. > > entropy(x) >= entropy(x xor y) > entropy(y) >= entropy(x xor y)
No.
Let x have zero entropy, i.e. a known value. Let y be random, i.e. entropy(y) == bits(y), and non-empty, i.e. bits(y) > 0.
Then, entropy(x xor y) == entropy(y)
=> entropy(x) < entropy(x xor y)
In general, either condition is possible depending on the relationship between x and y.
Entropy vs. information hiding ==============================
For our purpose, maximising entropy in F or G is one goal, to ensure each output bit is maximally independent, but another goal is preventing knowledge of the pool state, and that's a _different_ goal.
Reducing entropy in the output actually makes acquiring knowledge of the pool state _more difficult_.
This is because the amount of information you can deduce about the pool state is limited by (a) the output entropy and (b) the strength of the hash function.
To xor or not to xor ====================
For an attacker unable to break SHA, F or G are equally unbreakable. For an attacker who knows a weakness in SHA, then whether F or G is stronger depends entirely on the nature of that weakness. It could even be that F is stronger against one attacker and G is stronger against a different one.
Which begs the question, why throw away 50% of the bits? Why not 25%, or 75%? The choice is arbitrary and not based on any known (perhaps not knowable) properties of the hash function. We are speculating about weaknesses, yet cannot know which weaknesses to protect against.
-- Jamie - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |