[<prev] [next>] [day] [month] [year] [list]
Message-ID: <20110714172604.GA30836@openwall.com>
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.
