Solar Designer
2011-07-14 17:26:04 UTC
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
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