🚀 go-pugleaf

   Crossposted-To: alt.security.pgp
   From: strnlght@netcom.com (David Sternlight)
   Date: Fri, 8 Jan 1993 19:31:53 GMT

   Maybe Sidelnikov is trying to tell us something here that goes beyond
   the theoretical.

Maybe Mr. Sternlight is trying (once again) to raise Fear, Uncertainty,
and Doubt.  You really don't like PGP, don't you?  Unfortunately for
you, if what Dr. Sidelnikov says is true, then PEM and RIPEM will also
be vulnerable......

   >
   >>    - when considering the hashing function as the automatic  device
   >>without output,  it  is  enough  simply possible to construct the
   >>image of reverse automatic device and with using  the  blanks  in
   >>text files  (or  free fields in some standard formats as in DBF),
   >>to  compensate  the  hashing function  at  changed  file  to  former
   >>significance.

I interpreted this to mean that Dr. Sidelnikov believes that there is a
design flaw in MD5, which is the hashing function used by PGP.  Perhaps
there is; MD5 hasn't been out there for all that long.  But if it were
as simple as just changing the number of blanks in text files, someone
should have noticed by now.  The whole point of a "cryptographic
checksum" such as MD5 is that it is not computationally feasible to
change the text in such a way to produce a given hash value, and thus
"compensate the hashing function at changed file to former
significance".  To quote from RFC1321, "The MD5 Message-Digest
Algorithm":

   The MD5 message-digest algorithm is simple to implement, and provides
   a "fingerprint" or message digest of a message of arbitrary length.
   It is conjectured that the difficulty of coming up with two messages
   having the same message digest is on the order of 2^64 operations,
   and that the difficulty of coming up with any message having a given
   message digest is on the order of 2^128 operations. The MD5 algorithm
   has been carefully scrutinized for weaknesses. It is, however, a
   relatively new algorithm and further security analysis is of course
   justified, as is the case with any new proposal of this sort.

If what Dr. Sidelnikov is true, then not only is PGP's signatures
insecure, but also everything else which uses MD5 --- which includes
PEM, RIPEM, SNMP security, and many other things.  This does not mean
that what he says may not be true; but it is a major disaster if it is
really the case.

One final point; Mr. Sternlight seems to be saying that we should
believe everything posted by Sidelnikov because he is a Soviet
Academician.  I would like to remind everyone that we have no
*authentication* that said posting was really posted by a Dr.
Sidelnikov, and even if it was, we have no *proof* that he really is an
Academician.  This is not a slight against Dr. Sidelnikov; he may very
well be who he claims to be.  But given the seriousness of his claims, I
think it is quite understandable that we request a some proof that what
he has claimed.

If he really does have an algorithm for breaking MD5, there are some
easy ways for him to demonstrate this without divulging the algorithm,
however.  In RFC1321, Prof. Rivest published a MD5 test suite, which
included the following test items:

MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
d174ab98d277d9f5a5611c2c9f419d9f
MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a

If Dr. Sidelnikov can produce text strings which are different from the
above, and which evaluate to the same MD5 Message digests, then he will
have provided proof of his statement --- and a lot of people all over
the world will be scrambling to stop using MD5.  :-)

[ If Dr. Sidelnikov isn't reading sci.crypt, could whoever originally
  forwarded his message to sci.crypt kindly forward this message back to
  him?  Thanks! ]

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Theodore Ts'o				bloom-beacon!mit-athena!tytso
72 Marathon St, Arlington, MA 02155		tytso@athena.mit.edu
   Everybody's playing the game, but nobody's rules are the same!