Possible non-extension property for hash functions

[Bill Frantz]

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

* A draft of Bellovin and Rescorla's paper is available at <http://www.cs.columbia.edu/~smb/papers/new-hash.ps> and <http://www.cs.columbia.edu/~smb/papers/new-hash.pdf>.)

Cheers - Bill

---------------------------------------------------------------------
Bill Frantz        | The first thing you need   | Periwinkle 
(408)356-8506      | when using a perimeter     | 16345 Englewood Ave
www.pwpconsult.com | defense is a perimeter.    | Los Gatos, CA 95032

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