Possible non-extension property for hash functions

[Ben Laurie]

Bill Frantz wrote:
> In Steve Bellovin and Eric Rescorla's paper, "Deploying a New Hash
> Algorithm"*, the author's note the well known property of hash
> functions:
> 
> For two different stings x and y,
> 
> H(x) = H(y) ==> H(x||s) = H(y||s)

It may be well-known, but it isn't actually true. Or rather, it isn't 
true as stated: s has to be chosen carefully for it to be true (or x any 
y have to have particular properties).

> 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.

And this doesn't use the property above. It uses a stronger type of 
collision (i.e. a collision of internal state) - this allows s to be 
chosen freely.

Cheers,

Ben.

-- 
>>> ApacheCon Europe<<<                   http://www.apachecon.com/

http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

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