On Thu, Sep 9, 2010 at 2:28 PM, Marsh Ray <[email protected]> wrote: > On 09/08/2010 05:06 PM, [email protected] wrote: >> >>>> On Fri, Sep 03, 2010 at 09:45:20AM +0100, Ben Laurie wrote: >>>> >>>> ...narrow-pipe designs have a huge null space for messages which >>>> are exactly as big as the compression function input size. For >>>> instance hashing inputs that are multiples of 512 bits, SHA-256 >>>> will only produce about 63% of the possible 2^256 outputs. >>>> >>> So we deal with SHA-255.33 instead of SHA-256. Not a big enough >>> difference to worry about. > > But without a fresh injection of entropy, the effective entropy in the > resulting hash is reduced more than half a bit per log2 > of the iteration count. > First of all, half a bit per log2 isn't quite true.
See "Random Mapping Statistics", Flajolet, A Odlyzko, Advances in cryptology, EUROCRYPT'89, 1990 <http://www.springerlink.com/index/32q2qh4n325evy7f.pdf>. The paper shows the bits of entropy lost is: log2(1-t(k)) where: t(k+1) = e^(t(k)-1) So, for instance, by the 256rd iteration, you have only lost 7.01 bits of entropy, not 8 bits. And, you will never get below ( ( pi*(2^n) )/2 )^0.5 where 'n' is the number of bits in the hash you iterate over. This is about 128.3 bits for SHA-256. Restated with no equations: An iterated hash will make a graph with multiple trees attached to multiple cycles. If you start on a tree, each iteration walks down the tree and eventually lands on a cycle. It looks like a pile of hairy loops or a flock of flying spaghetti monsters. At every iteration, the entropy goes down simply because of a reduced possibility of states. This happens because the state cannot possibly be at a branch terminal after one iteration. The state cannot possibly be at a branch terminal or next to it after two iterations. Once you have iterated enough that you cannot possibly be on a tree but must be in a cycle, the entropy will never go down again. Second of all, the vast majority of discussions about losing entropy this way is completely mute. These entropy discussions are mute because in the real world we don't care about 'entropy' we care about what I have heard referred to as 'conditional computational entropy' or the entropy experienced by somebody with a real device, not a device that can enumerate all states in an iterated 256-bit hash and know which states can be excluded. Back in the real world, we don't lose any 'conditional computational entropy' upon iteration. We don't lose any 'conditional computational entropy' upon iteration because we have no machines powerful enough to know what states are at branch-terminals or next to branch-terminals or next to those, etc. ---- -Michael Heyman _______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
