I should point out that this construction is not designed to obscure the
input from the output (especially under differential probing), only
to give you m output bits that depend (each in a different way) on
the entire input.
> > 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).
>
> -matt
>
>
>
