From: patrick@Verity.COM (Patrick Horgan)
Date: Tue, 24 Oct 95 13:12:24 PDT
To: fc@all.net
Subject: MD5 concerns, was Re: Netscape Logic Bomb detailed by IETF
Message-ID: <9510242008.AA07416@cantina.verity.com>
MIME-Version: 1.0
Content-Type: text/plain


> channel.  I think that Netscape uses an MD5 checksum which the members
> of this list seem to place unlimited trust in (incorrectly in my view,

This is the second time you've implied that an MD5 checksum might not be
as secure as we think.  Could you share your thinking on this?  I had
believed from reading the algorithm that it's not possible to predict how
a change in the input will affect the checksum.  Given a modified version
of netscape for example, how would you change some non-critical portion of
the code to get the same checksum that the original should have.  I suppose
that give n bits of non-critical space in the code, (non-critical meaning
that changing them will have no effect on the execution of the code, and
assuming that you don't want to change the length of the code), that you
could try all possible combinations of those bits, or 2^n trials and
see if you get the correct MD5 checksum.  If you do, then on average you'd
actually only have to try 2^(n-1) trials. What if you don't?  What would
you do then?  MD5 produces a 128 bit output, and it would seem likely that
this would be hard.  As far as I know there are no known attacks for any
MDx algorithms in spite of Ron's worries about MD4.  It's a subject of
on-going research though, and it is only "conjectured that it is
computationally infeasible to produce two messages having the same
message digest, or to produce any messages having a given prespecified
target message digest." (RFC 1321)  So, if you have newer information,
or pointers to any papers, (other than the ben Boer and Bosselaers papers),
could you let me know?

Thanks,

Patrick

   _______________________________________________________________________
  /  These opinions are mine, and not Verity's (except by coincidence;).  \
 |                                                       (\                |
 |  Patrick J. Horgan         Verity Inc.                 \\    Have       |
 |  patrick@verity.com        1550 Plymouth Street         \\  _ Sword     | 
 |  Phone : (415)960-7600     Mountain View                 \\/    Will    | 
 |  FAX   : (415)960-7750     California 94303             _/\\     Travel | 
  \___________________________________________________________\)__________/