From msuinfo!netnews.upenn.edu!news.cc.swarthmore.edu!psuvax1!news.pop.psu.edu!news.cac.psu.edu!howland.reston.ans.net!europa.eng.gtefsd.com!MathWorks.Com!zombie.ncsc.mil!golf!mizzou1.missouri.edu!C445585 Fri May 20 10:16:18 1994
Path: msuinfo!netnews.upenn.edu!news.cc.swarthmore.edu!psuvax1!news.pop.psu.edu!news.cac.psu.edu!howland.reston.ans.net!europa.eng.gtefsd.com!MathWorks.Com!zombie.ncsc.mil!golf!mizzou1.missouri.edu!C445585
From: C445585@mizzou1.missouri.edu
Newsgroups: sci.crypt
Subject: Re: SHA vs. MD5?
Date: Thu, 19 May 94 17:39:03 CDT
Organization: University of Missouri, Columbia
Lines: 96
Message-ID: <16FBBF839S86.C445585@mizzou1.missouri.edu>
References: <1994May19.083131.3210@news.research.ptt.nl>
NNTP-Posting-Host: mizzou1.missouri.edu

In article <1994May19.083131.3210@news.research.ptt.nl>
rijen@sun007.research.ptt.nl (Lucas van Rijen) writes:
 
>Can anyone compare for me the Secure Hash Alogithme (SHA) with
>the Message Digest 5 algorithme in term of:
 
   Quick reference:  Bruce Schneier's _Applied Cryptography_ book
does a quick comparison on MD5 vs SHA, using the explicit design
(or redesign) goals of MD5 vs. SHA.  This might be a starting point.
 
   The MD5 algorithm is available by anonymous ftp from rsa.com.
The SHA algorithm is available by anonymous ftp, but I don't recall
where I found it.  Someone else will know, hopefully.
 
   Both algorithms use a combination of 32-bit adds (addition modulo
2**32), bit rotations, and binary mixing operations.
 
   Both hashing algorithms boil down to:
 
1.  Padding the message out until  padded_length mod 512 = 448.
    (Pad with a single "1" bit, then all "0" bits.  Always pad
    at least one bit, even if the message starts out at an
    acceptable length.)
2.  Appending the length to the padded message, as a 64-bit integer.
3.  Apply a compression function to the message, 512-bits at a time.
    The compression function takes two inputs:  a 512-bit message
    block, and a 128-bit (MD5) or 160-bit (SHA) value from the previous
    compression function.  There's a predefined starting value for
    the first message block.  Hash of A,B,C,D where A..D are 512-bit
    blocks and I is the initial value goes like this:  (F is compression
    function.  Assume the message has already been hit by 1 & 2.)
 
    H = F(A,I)
    H = F(B,H)
    H = F(C,H)
    H = F(D,H)
    Final_Hash = H
 
>-cryptanalysis ( is it safe)
 
   There is a known way of finding "pseudo collisions" for MD5.
Another term for this is that there's a free-start collision attack
against the compression funtion on MD5.  This doesn't seem to
translate into an attack on MD5 as it's actually used.
 
   There appears to be some kind of problem with SHA, as well.  The
NSA / NIST are working on a redesign.  Nobody seems to be talking
about what the problem is, though.
 
>-brute force attacks (to make the same hash of a different message)
 
   MD5 has an output of 128 bits, which I think is too small for
 good security.  A collision can be found by brute force in 2**64
 operations.
 
>-patents or copyrights.
 
   MD5 is public-domain.  SHA seems to be, but the note I read on it
had some legalese in there about how patent rights might be out there,
or something.  Hopefully, someone who understands the legalities and
such will describe whether there is any chance of patents being claimed.
 
>-performance (speed with which a message is hashed)
>-hardware implications (can it run on a dos machine)
 
   The general operations were chosen by Ron Rivest (with MD4, the parent
of MD5 and SHA) to be as fast as possible on mainstream 32-bit processors.
SHA is slower than MD5, which is slower than MD4.  I don't have any
numbers available for you....
 
>I am asking this because I'm wondering why MD5 is implemented in PGP and
>not SHA which has a longer hash-length, thus IMHO giving more security.
 
   Hmmm.  It's generally dangerous to evaluate the security of an
encryption algorithm by keysize alone, or a hash function by output
hash size alone.  All keysize or hash output size can give you is a
best-case:  If both algorithms are flawless, SHA will require 2**80
ops to generate a hash collision, and MD5 will require 2**64.  I would
be hesitant to use MD5 for anything with really high stakes, because
2**64 MD5 calculations is feasible now for someone with lots of money.
If SHA, or the redesign of SHA, is as secure as it should be, then
it will take 2**80 operations to find a collision.  This is more like
it, though for *really* important signatures (multi-million dollar
signatures that need to last 50 years), I think I'd like a 256-bit
hash output.
 
   Note, though, that *anyone* can design an encryption algorithm with
a huge key, or a hashing function with a huge output size.  The question
is, does it merit that keysize or output size?
 
>With friendly greetings,
 
>                Lucas
 
     --John Kelsey, c445585@mizzou1.missouri.edu