Date: Thu, 14 Jul 2011 21:26:04 +0400 From: Solar Designer <solar@...nwall.com> To: crypt-dev@...ts.openwall.com Subject: entropy loss with narrow-pipe iterated hashes Hi, Just to bookmark these, so to speak: http://lists.randombit.net/pipermail/cryptography/2010-September/000086.html http://lists.randombit.net/pipermail/cryptography/2010-September/000130.html This is relevant in case we choose to use crypto cores with relatively little internal state (to fit more cores per chip). Summary: the entropy loss rate is low, but we need to be aware of what it is or may be, and keep it in consideration for our decision-making. Some excerpts from the above: "Danilo Gligoroski, Vlastimil Klima: Practical consequences of the aberration of narrow-pipe hash designs from ideal random functions, IACR eprint, Report 2010/384, pdf. http://eprint.iacr.org/2010/384.pdf The theoretical loss is -log2(1/e) = about 0.66 bits of entropy per log2(N additional iterations)." "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." "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." Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.