
MessageID: <20110714172604.GA30836@openwall.com> Date: Thu, 14 Jul 2011 21:26:04 +0400 From: Solar Designer <solar@...nwall.com> To: cryptdev@...ts.openwall.com Subject: entropy loss with narrowpipe iterated hashes Hi, Just to bookmark these, so to speak: http://lists.randombit.net/pipermail/cryptography/2010September/000086.html http://lists.randombit.net/pipermail/cryptography/2010September/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 decisionmaking. Some excerpts from the above: "Danilo Gligoroski, Vlastimil Klima: Practical consequences of the aberration of narrowpipe 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(1t(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 SHA256." "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 256bit 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.