Propping up SHA-1 (or MD5)
ben at algroup.co.uk
Thu Mar 24 05:38:40 EST 2005
Charlie Kaufman wrote:
> All hash functions I'm aware of consist of an inner compression function
> that hashes a fixed size block of data into a smaller fixed size block
> and an outer composition function that applies the inner function
> iteratively to the variable length data to be hashed. Essentially you're
> proposing a modification to the outer layer of the hash construction.
> All of the standard hash functions since MD4 have been constructed so
> that a collision in the inner compression function is likely to lead to
> a collision in the hash function. MD2 did not have that property. It
> computed a cheap checksum of the variable length data in parallel with
> the digesting process and digested the checksum following the data. I
> have often wondered whether such a cheap addition would strengthen the
> newer hashes. (It would fix the suffixing attacks that motivated the
> development of HMAC).
> It's not obvious whether this would make the functions more secure or
> just make them harder to analyze. Perhaps someone from the research
> community could comment on why the checksum was removed in the evolution
> from MD2 to MD4.
> Your proposed encoding has the disadvantage that it would require two
> passes over the message being digested. This would be bad news for
> hardware implementations and should be avoided if possible.
I suggested in a later version these two constructions:
H'(x)=H(H(x || H(0 || x) || H(0 || x))
H'(x)=H(H(x || H(0 || x) || H(1 || x))
which only require a single pass (but, unfortunately, two or three
different instances of the hash). This seems similar to the mechanism
used in MD2, except the checksum is expensive.
"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
More information about the cryptography