[7351] in cryptography@c2.net mail archive
Re: Extracting Entropy?
daemon@ATHENA.MIT.EDU (Ben Laurie)
Mon Jun 19 22:46:24 2000
Message-ID: <394EAA6F.6A609AC1@algroup.co.uk>
Date: Tue, 20 Jun 2000 00:19:11 +0100
From: Ben Laurie <ben@algroup.co.uk>
MIME-Version: 1.0
To: Matt Blaze <mab@research.att.com>
Cc: Coderpunks <coderpunks@toad.com>, Cryptography <cryptography@c2.net>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Matt Blaze wrote:
>
> > OK, so if I've got a passphrase of arbitrary length, and I wish to
> > condense it to make a key of length n bits (n > 160), what's the
> > approved method(s) of doing that?
> >
> > I assume it goes without saying that we wish to preserve as much entropy
> > as we can, but I'll say it anyway.
>
> I've thought about this problem from time to time. I assume that you
> want every bit of the output to depend on every bit of the input, and for
> there to be no correlations between bits, for arbitrary size inputs and
> outputs. I know of no "standard" cryptographic primitive that does
> exactly this.
>
> The best (albeit rather expensive) construction I've come up with for n input
> bits to produce m output bits is to set
>
> OutputBit_m = H(m| 1 | InputBit_1) + H(m | 2 | InputBit_2)
> + ... + H(m | n | InputBit_n)
>
> where H is a one bit cryptographic hash function with the usual properties,
> "|" is bit concatenation, "+" is bitwise XOR, and "m" and "n" are binary
> representations of the output and input bit positions, respectively. (The
> idea being to use H to approximate mn different random one bit to one bit
> functions). I'm not sure that you need to include n in the hash calculation,
> but it couldn't hurt.
>
> Proving that this has the properties you want depends on the properties of
> the cryptographic hash function. Presumably taking one bit of the output
> of SHA1 would be good enough in practice, but I've not proven anything
> about this construction. This is an expensive calculation, mn evaluations
> of H (though perhaps you could use different bits of a more than one bit
> hash function for different output bits).
Generalising a bit, we could do:
OutputBits_{m,k}=H_k(m | 1 | InputBits_{1,k})+H_k(m | 2 |
InputBits_{2,k})+...+H_k(m | n | InputBits_{n,k})
where OutputBits_{m,k} is the k bits starting at bit m, H_k is a k bit
cryptographic hash function, etc. InputBits_{i,k} wraps, and
OutputBits_{i,k} discards excess. Set m=Nk and there you are.
Or even use all m and make OutputBits wrap and xor the chunks together.
Which, if k were, say, 160 and H_160 were, say, SHA-1, well, that'd
reduce the cost by 160. Ish.
Cheers,
Ben.
--
http://www.apache-ssl.org/ben.html
Coming to ApacheCon Europe 2000? http://apachecon.com/
