[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: AH-MD5


"Theodore Ts'o" says:
>    From: "Perry E. Metzger" <perry@imsi.com>
> 
>    "Theodore Ts'o" says:
>    > You will recall that MD5 was designed and pushed out the door not
>    > because the author could prove any weaknesses about MD4 --- as far as
>    > he knew there are been no attacks on MD4 ---
> 
>    Other than the ones by Bert den Boer, Antoon Bosselaers, Ralph Merkle,
>    and Elli Biham, all of whom broke two out of three rounds? I'll point
>    out that they used different techniques, adding insult to injury!
>    If you insist, I'll post references.
> 
> When were those papers published?

Don't know when the results were first known on the grapevine, but I
know for sure that at least some were presented long (i.e. a year)
before the MD5 document. I got these two just doing a cursory scan of
Schneier; I'm sure I could dig for more.

1) B. den Boer and A. Bosselaers, "An Attack on the Last Two Rounds of
   MD4", Advances in Cryptology -- Crypto '91 Proceedings, Berlin,
   Springer-Verlag, 1992, pp 194-203 [Crypto '91 was substantially
   before MD5 came out, although the proceedings lagged a bit in
   publication.]

2) E. Biham, "On the Applicability of Differential Cryptanalysis to
   Hash Functions," lecture at Workshop on Cryptographic Hash
   Functions, March 1992 [This was also before MD5 came out; I suspect
   the work was done earlier and conveyed to Rivest, though I
   haven't asked -- never came up before now.]

> The MD5 RFC (April 1992) refereneced
> none of those papers when it discussed why MD5 was released:

Its an RFC, not a scholarly document. Also, the MD5 document told the
literal truth when it said that MD4 had not been broken -- it hadn't
been completely broken, just two out of three rounds. It was enough of
a partial break to be of cryptographic significance and to disturb
people.

I'm trying to make sure that the RFCs coming out of the stuff Bill and
I are doing will be a bit better in the scholarship department -- I'm
including substantial notes in the security considerations section on
the known cryptographic problems in these systems and enough
references to let people follow the trail if they like.

> Notice words such as "felt" and "likelihood"...... those are hunch-like
> words don't they?

Maybe, but there was serious scholarship out breaking multiple rounds
of MD4 well in advance of MD5 coming out.

As I've noted, there are also partial breaks of MD5. There are no
known attacks other than brute force against the current SHA. I've
just completed an SHA-AH document; Bill is editing it as I write this.

Again, can we be serious here? The append vs. including length debate
hasn't been conducted with any real scholarship. Anyone care to
attempt to prove the security of the system assuming that the
underlying hash actually has the claimed properties of a cryptographic
hash? (Dunno if I have time, but I suspect it won't be hard.)

And on another serious note, I again raise the question: should we
adopt MD5, or SHA, or something else?

Also, does anyone have benchmarks of SHA?

Perry
Follow-Ups: References: