> I'm not sure this is so good. In particular, it is entirely linear.
>
> The function f_{m,n} sending the one-bit input x to the one-bit output
> H(m|n|x) is always linear in its input (it always has the form f_{m,n}(x)
> = ax + b for appropriate a,b; the value of a,b depends on H,m,n but not
> on x).
>
> The sum of linear functions is linear.
>
> So OutputBit_m is a (known) linear function of the input bits.
>
>
> How about the following alternative proposal?
> Output = H(1 | Input) | H(2 | input) | ...
> You might not get any more than 160-bit strength, if H = SHA-1, but
> other than that, it seems plausibly ok.
I'd considered that, but unfortunately, in this construction the strength is
limited to the size of the state of H, which is the problem I'd like to avoid.
You could also do
Output_m = H(1 | H(Input_{1..n}) | Input_1) + ...
+ H(n | BigHash(Input_{1..n}) | Input_n)
Where BigHash is, say, all 160 bits of SHA1 output and need only be
calculated once. This adds the nonlinearity, at least for 160 bits.
In the case of the password -> key material application, I'm not sure that
linearity is actually a problem, but clearly it is in other applications.
The construction I proposed takes a very extreme position on this, of
course.
-matt
