Possible non-extension property for hash functions

[John Kelsey]

>From: Bill Frantz <frantz at pwpconsult.com>
>Sent: Aug 6, 2005 6:27 PM
>To: cryptography at metzdowd.com
>Subject: Possible non-extension property for hash functions

...
[Talking about the length-extension property.]
>H(x) = H(y) ==> H(x||s) = H(y||s)

>It seems to me that there might be a class of hash
>functions for which this property did not hold.  While
>hashes in this class might require random access to the
>entire input, they could prevent the "message extension"
>class of attack exploited by Lucks and Daum (see
><http://th.informatik.uni-mannheim.de/people/lucks/HashCollisions>)
>when they generated two Postscript files with very
>different output, but the same MD5 hash.

There are actually a couple ways to do this.  Either:

a.  Process the message sequentially, but do a final
operation on the intermediate result before putting out an
output hash, which introduces new collisions.  Any truncated
hash like SHA384 or SHA224 does this.  As an added benefit,
once you truncate enough bits (SHA384 truncates 128 bits),
the length extension attack on prefix MAC goes away, and the
Joux multicollisions and long message second preimage
attacks Bruce and I came up with become much more
difficult.  (On the other hand, it doesn't seem easy to do
any nice reduction proof from the strength of the SHA256
compression function to the strength of the SHA384 hash
function.)

b.  Process the message multiple times, or give yourself
random access, or whatever.  Just processing through the
message twice sequentially does eliminate the simple
length-extension property, but there are variations on it
that can still be used--that's why Joux multicollisions can
be found even when you process the message twice
sequentially. 

Are there other ways I'm not seeing to do this?   

...
>Cheers - Bill

--John Kelsey


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com