home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / crypt / 6556 < prev    next >
Encoding:
Text File  |  1993-01-08  |  4.5 KB  |  93 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!enterpoop.mit.edu!bloom-picayune.mit.edu!daemon
  3. From: tytso@ATHENA.MIT.EDU (Theodore Ts'o)
  4. Subject: Re: Zimmermann's responses to Sidelnikov's PGP critique
  5. Message-ID: <1993Jan8.223337.14551@athena.mit.edu>
  6. Sender: daemon@athena.mit.edu (Mr Background)
  7. Reply-To: tytso@ATHENA.MIT.EDU (Theodore Ts'o)
  8. Organization: The Internet
  9. Date: Fri, 8 Jan 1993 22:33:37 GMT
  10. Lines: 81
  11.  
  12.    Crossposted-To: alt.security.pgp
  13.    From: strnlght@netcom.com (David Sternlight)
  14.    Date: Fri, 8 Jan 1993 19:31:53 GMT
  15.  
  16.    Maybe Sidelnikov is trying to tell us something here that goes beyond
  17.    the theoretical.
  18.  
  19. Maybe Mr. Sternlight is trying (once again) to raise Fear, Uncertainty,
  20. and Doubt.  You really don't like PGP, don't you?  Unfortunately for
  21. you, if what Dr. Sidelnikov says is true, then PEM and RIPEM will also
  22. be vulnerable......
  23.  
  24.    >
  25.    >>    - when considering the hashing function as the automatic  device
  26.    >>without output,  it  is  enough  simply possible to construct the
  27.    >>image of reverse automatic device and with using  the  blanks  in
  28.    >>text files  (or  free fields in some standard formats as in DBF),
  29.    >>to  compensate  the  hashing function  at  changed  file  to  former
  30.    >>significance.
  31.  
  32. I interpreted this to mean that Dr. Sidelnikov believes that there is a
  33. design flaw in MD5, which is the hashing function used by PGP.  Perhaps
  34. there is; MD5 hasn't been out there for all that long.  But if it were
  35. as simple as just changing the number of blanks in text files, someone
  36. should have noticed by now.  The whole point of a "cryptographic
  37. checksum" such as MD5 is that it is not computationally feasible to
  38. change the text in such a way to produce a given hash value, and thus
  39. "compensate the hashing function at changed file to former
  40. significance".  To quote from RFC1321, "The MD5 Message-Digest
  41. Algorithm":
  42.  
  43.    The MD5 message-digest algorithm is simple to implement, and provides
  44.    a "fingerprint" or message digest of a message of arbitrary length.
  45.    It is conjectured that the difficulty of coming up with two messages
  46.    having the same message digest is on the order of 2^64 operations,
  47.    and that the difficulty of coming up with any message having a given
  48.    message digest is on the order of 2^128 operations. The MD5 algorithm
  49.    has been carefully scrutinized for weaknesses. It is, however, a
  50.    relatively new algorithm and further security analysis is of course
  51.    justified, as is the case with any new proposal of this sort.
  52.  
  53. If what Dr. Sidelnikov is true, then not only is PGP's signatures
  54. insecure, but also everything else which uses MD5 --- which includes
  55. PEM, RIPEM, SNMP security, and many other things.  This does not mean
  56. that what he says may not be true; but it is a major disaster if it is
  57. really the case.
  58.  
  59. One final point; Mr. Sternlight seems to be saying that we should
  60. believe everything posted by Sidelnikov because he is a Soviet
  61. Academician.  I would like to remind everyone that we have no
  62. *authentication* that said posting was really posted by a Dr.
  63. Sidelnikov, and even if it was, we have no *proof* that he really is an
  64. Academician.  This is not a slight against Dr. Sidelnikov; he may very
  65. well be who he claims to be.  But given the seriousness of his claims, I
  66. think it is quite understandable that we request a some proof that what
  67. he has claimed.
  68.  
  69. If he really does have an algorithm for breaking MD5, there are some
  70. easy ways for him to demonstrate this without divulging the algorithm,
  71. however.  In RFC1321, Prof. Rivest published a MD5 test suite, which
  72. included the following test items:
  73.  
  74. MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
  75. MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
  76. MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
  77. d174ab98d277d9f5a5611c2c9f419d9f
  78. MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a
  79.  
  80. If Dr. Sidelnikov can produce text strings which are different from the
  81. above, and which evaluate to the same MD5 Message digests, then he will
  82. have provided proof of his statement --- and a lot of people all over
  83. the world will be scrambling to stop using MD5.  :-)
  84.  
  85. [ If Dr. Sidelnikov isn't reading sci.crypt, could whoever originally
  86.   forwarded his message to sci.crypt kindly forward this message back to
  87.   him?  Thanks! ]
  88.  
  89. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
  90. Theodore Ts'o                bloom-beacon!mit-athena!tytso
  91. 72 Marathon St, Arlington, MA 02155        tytso@athena.mit.edu
  92.    Everybody's playing the game, but nobody's rules are the same!
  93.