[17144] in cryptography@c2.net mail archive
Re: Propping up SHA-1 (or MD5)
daemon@ATHENA.MIT.EDU (Ben Laurie)
Fri Mar 25 10:24:20 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Thu, 24 Mar 2005 10:38:40 +0000
From: Ben Laurie <ben@algroup.co.uk>
To: Charlie Kaufman <charliek@microsoft.com>
Cc: Cryptography <cryptography@metzdowd.com>, saag@mit.edu
In-Reply-To: <F5F4EC6358916448A81370AF56F211A505A4B411@RED-MSG-51.redmond.corp.microsoft.com>
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))
or:
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.
Cheers,
Ben.
--
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@metzdowd.com
