> Does anyone have a good idea on how to OWF passphrases without
> reducing them to lower entropy counts?  That is, I've seen systems
> which hash the passphrase then use a PRF to expand the result --- I
> don't want to do that.  I want to have more than 160 bits of entropy
> involved.

What kind of application are you running, that > 150 bits of entropy is

> I was thinking that one could hash the first block, copy the
> intermediate state, finalize it, then continue the intermediate result
> with the next block, and finalize that.  Is this safe?  Is there a
> better alternative?

As I understand your proposal, you split up the passphrase P into L Blocks
P_1, ..., P_L, (padding the last block P_L as neccessary) and then you
output L*160 bit like this:

        F(P) = ( H(P_1), H(P_1,P_2), ..., H(P_1, P_2, ..., P_L) ).

This does not look like a good idea to me:

   1.   If the size of the P_i is the internal block size of the hash
        function (e.g., 512 bit for SHA-1, SHA-256, or RIPEMD-160) and
        your message P=P_1 is just one block long, you definitively end
        with (at most) 160 bit of entropy, how large the entropy in P_1
        is (could be 512 bit).

   2.   If the local entropy in each block P_i (or even the conditional
        entropy in P_i, given all the P_{i-1}, ..., P_1) is low, then you
        can step by step find P. This function F(P) is thus *much* *worse*
        than its simple and straight counterpart H(P).

   3.   In fact, to calculate the entropy of F(P), you can take the
        conditional entropy in P_i. The entropy of F(P) is close to the
        maximum of these conditional entropies ...

Any better solution I can think of will be significantly less performant
than just applying H(P). One idea of mine would be the function G:

   *    Let <i> be a counter of some fixed size, say 32 bit.

   *    Let J+1 be the number of 160-bit values you need (e.g., J = 4*L).

   *    G(P) = ( H(P_1,<0>,P_1,P_2,<0>,P_2, ..., P_L,<0>,P_L),
                 H(P_2,<1>,P_2, ..., P_L,<1>,P_L,P_1,<1>,P_1),
                 H(P_L,<J>,P_L,P_1,<J>,P_1, ..., P_{L-1},<J>,P_{L-1})

Would that be OK for you application?

In any case, I think that using a 160-bit hash function as a building
block for a universal one-way function with (potentially) much more than
160-bit of entropy is a bit shaky.

Stefan Lucks      Th. Informatik, Univ. Mannheim, 68131 Mannheim, Germany
            e-mail: [EMAIL PROTECTED]
            home: http://th.informatik.uni-mannheim.de/people/lucks/
------  I  love  the  taste  of  Cryptanalysis  in  the  morning!  ------

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Reply via email to