Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [day] [month] [year] [list]
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.