passphrases with more than 160 bits of entropy

[Stefan Lucks]

> 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
insufficient?

> 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: lucks at th.informatik.uni-mannheim.de
            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 majordomo at metzdowd.com