[<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

"See "Random Mapping Statistics", Flajolet, A Odlyzko, Advances in
cryptology, EUROCRYPT'89, 1990

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

"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
```

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.