Re: This Week's Finds in Mathematical Physics (Week 226)

In message <dsn1ji$sfj$1@xxxxxxxxxxxx>, John Baez <baez@xxxxxxxxxxxxxxxxxxxxxxxx> writes

"I think it's usually credited to a small set of coinventors,
and I think Ralph Merkle is a coinventor either of MD5 or one
of its immediate ancestors."

I'd like more information on this.

The book "Applied Cryptography" by Bruce Schneier goes into detail on these algorithms and has loads of references. Schneier credits Rivest as the designer of MD4, saying Bert den Boer and Antoon Bosselaears successfully crpytanalysed the last of the algorithms three rounds, while Ralph Merkle successfully attacked the first two rounds. Others are credited (with attacks and analysis on MD4) too. Schneier credits Rivest as strengthening MD4 with the result being MD5. While Rivest himself outlined the improvement of MD5 over MD4 in
"The MD5 Message Digest Algorithm", RFC 1321, Apr 1992

If you want more references, Schneier's book has another 1652 of them :)

A quick google also turns up citations like "At Crypto '91 Ronald L. Rivest introduced the MD5 Message Digest Algorithm as a strengthened version of MD4, differing from it on six points".

Of course, if deliberate tampering is what you fear, you have
to send the digest by a different channel than the original file,
or use some other trick.

By coincidence my Masters thesis, soon due for submission, was on the use of one of those other tricks, in business: digital signatures. Nothing interesting mathematically, it was only as interesting a subject as I could manage to get a degree in IT to be :)

But if you prove that P *does* equal NP, you might make more money by
breaking cryptographic hash codes and setting yourself up as the Napoleon
of crime.

For a bit of fun I once wrote a program that would generate random programs, spitting out and testing something like 50,000 a minute. It would quickly output programs for polynomial time problems, like finding greatest common divisors or whatever, but the only ones it spat out for NP problems like factoring were polynomial solutions, such as iterating through odd numbers until the square root of n. As I say it was nothing scientific and it would probably be unlikely to spit out anything useful anyway, just too many combinations. Not sure if that was a new idea, but probably not.

--
Stephen Riley

.

Relevant Pages

  • Re: SHA-1 vs. triple-DES for password encryption?
    ... even if the attack wasn't practical. ... > somehow break MD5 that was not done since 1992? ... >>> the hash algorithms as MD5 and MD4. ... >> than you would of SHA1 to get the difficulty up to the same level. ...
    (SecProg)
  • Re: OT: MD4 encryption
    ... what is MD4 used for? ... and just replaced by MD5 and is no longer used? ... Shortly after MD4 was published a number of attacks were demonstrated against parts of it. ... SHA1 isn't without problems either and discussion rages on about what is the best cryptographic hash algorithm out there. ...
    (comp.sys.mac.system)
  • Re: compare-by-hash (was Re: sharing /etc/passwd)
    ... No, md4 and md5 are broken, in the sense that it's known how to ... das@VARK:~> hexdump md4c_1 ... The md5 data comes from the page ...
    (FreeBSD-Security)
  • Re: [OT] Firefox 3.0
    ... Again, FWIW, signcode uses MD5 or SHA1, both of which are public ... algorithms, I have no idea what Wise Install uses (or indeed, what it ...
    (uk.rec.motorcycles)
  • Re: Slow but secure has function for small data
    ... Of course they don't contradict each other. ... The assumption that MD4 or MD5 behave like a PRF is not true. ...
    (sci.crypt)