combining entropy

Sandy Harris sandyinchina at gmail.com
Sat Oct 25 22:47:34 EDT 2008


John Denker <jsd at av8n.com> wrote:

> To say the same thing in more detail:  Suppose we start
> with N generators, each of which puts out a 160 bit word
> containing 80 bits of _trusted_ entropy.  That's a 50%
> entropy density.

So you need a 2:1 or heavier compression that won't lose
entropy. If you just need one 160 word out per N in, then
hashing them is the obvious way to do that.

> We next consider the case where N-1 of the generators have
> failed, or can no longer be trusted, ...

> XOR is provably correct because it is _reversible_ in the
> thermodynamic sense.  That means it cannot increase or
> decrease the entropy.

Yes, but the proof holds for any reversible mapping. XOR
makes each output bit depend on exactly two inputs bits.
Sometimes you want a mapping that mixes them better.

If one input is entirely random, XOR is fine; random ^ x is
random for any x. It is also fine in the case above, where
only one generator works.

If  > 1 inputs have some entropy but none have enough,
which seems to me the commonest case, XOR is not
the best choice; it does not mix well enough.

Nyberg's perfect s-boxes are in some ways the ideal
mixer. 2n bits in, n out, all columns and all linear
combinations of columns are bent functions. Big
S-boxes are expensive though, and building even
small Nyberg S-boxes is going to take significant
effort. Designing something that uses a bunch of say
8 by 4 S-boxes to do good mixing on 160-bit chunks
is not trivial either.

You could use IDEA multiplication in mixing. Two 16-bit
words in, one out, and every output bit depends on all
input bits.

If every 16-bit input word has 50% entropy density
(not the same as every 160-bit word does, but perhaps
close enough) then the output should have 100%.

For N > 1, you need to combine those and worry about
overall mixing. If entropy density is known to be ~50%,
you can combine pairs with IDEA to get ~100%, then
use cheaper operations for any other mixing needed.
I'd use addition, which costs about the same as XOR
but gives slightly better mixing because of carries.

For N > 2 and density < 50%, you could use a cascade
of IDEA operations 8->4->2->1 or whatever. Or do
something like: combine two 160-bit chunks with 10
IDEA multiplications, circular shift the result 8 bits,
combine with next 160-bit input, ...

At some point, you may find yourself designing a hash.
If that happens, just give up and use a standard hash.

-- 
Sandy Harris,
Quanzhou, Fujian, China

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list