home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / crypt / 6573 < prev    next >
Encoding:
Internet Message Format  |  1993-01-09  |  5.6 KB
  1. Xref: sparky sci.crypt:6573 alt.security.pgp:476
  2. Path: sparky!uunet!wupost!waikato.ac.nz!aukuni.ac.nz!cs18.cs.aukuni.ac.nz!pgut1
  3. Newsgroups: sci.crypt,alt.security.pgp
  4. Subject: Re: Zimmermann's responses to Sidelnikov's PGP critique
  5. Message-ID: <1993Jan9.001928.27417@cs.aukuni.ac.nz>
  6. From: pgut1@cs.aukuni.ac.nz (Peter Gutmann)
  7. Date: Sat, 9 Jan 1993 00:19:28 GMT
  8. References: <1993Jan8.173701.8858@ncar.ucar.edu> <bontchev.726522074@fbihh>
  9. Organization: Computer Science Dept. University of Auckland
  10. Lines: 123
  11.  
  12. The following was my initial reaction to the posting - I forwarded it to
  13. the other PGPeople a day or two ago, may as well post it here too -
  14.  
  15. Some thoughts on the recently posted comments on PGP (I've squashed the text up
  16. a bit to save space).  This isn't a language flame, but some of the English is
  17. a bit hard to make out, so maybe I got a few things I commented on wrong...
  18.  
  19. >About using the electronic signature for protection of commercial information:
  20. >
  21. >The analysis of PGP ver.2.0 program.
  22. >
  23. >---------------------------------------------------------------------
  24. >     THE MOSCOW STATE UNIVERSITY named after m.V. Lomonosov
  25. >   ______________________________________________________________
  26. >
  27. >
  28. >       THE MATHEMATICAL CRYPTOGRAPHY PROBLEMS LABORATORY
  29. >
  30. >The MSU mathematical cryptography problems laboratory employeers with some
  31. >addition specialists were executed the preliminary analysis of PGP ver.2.0
  32. >program.
  33. >
  34. >The preliminary study of working and program source code analysis result in
  35. >following PGP features and problems:
  36. >
  37. >1. The common character problems
  38. >
  39. > - the sequence of random numbers has strong prevalences on bytes (up to 0.05
  40. > ...  0.1 on material of 10000 byte) and strong correlation dependence between
  41. > contiguous bytes;
  42. >
  43. > - the program doesn't check it's own integrity, so it can be infected by
  44. > "virus" which intercept confidential keys and passwords used for their
  45. > protection and save them onto magnetic carriers;
  46.  
  47. The problem is that the virus check itself can be subverted.  There are
  48. solutions in the PGP documentation to this problem...
  49.  
  50. > - the program has not optimal exponentiation algorithm in GF(P) field, when P
  51. > - prime number, which result in low performance;
  52. >
  53. >2. The RSA algorithm realization problems
  54. >
  55. > - the prime numbers reception using in this program (R and q in RSA
  56. > algorithm) permits not less than on two order to reduce the labour-
  57. > intensiveness of factorization; with 256 bit blocks of data lenght it is
  58. > possible to execute the cryptanalysis in real time;
  59.  
  60. Presumably meaning that you can factor 256-bit (~77 digit) keys?  (Hmm, if it's
  61. in real time I'd love to get my paws on the code :-).  I can belive that
  62. keys of this length are easily factored, but what about keys of the size PGP
  63. uses?
  64.  
  65. > - before using RSA the program executes compression and block encryption that
  66. > positively affects on the common stability encryption.
  67. >
  68. >3. The electronic signature problems
  69. >
  70. > - for signature calculation the program originally executes hashing of file
  71. > into number of given length (256, 512 or 1024 bit), but hashing function does
  72. > not corresponds the ISO recommendations;
  73.  
  74. PGP uses a hash function with a 128-bit block size, not 256, 512, 1024.  By
  75. "ISO recommendations" I presume this refers to something like ISO 8731 or ISO
  76. 9797, one of the DES-as-a-MAC standards?  This has been shown to be
  77. compromisable...
  78.  
  79. > - when considering the hashing function as the automatic device without
  80. > output, it is enough simply possible to construct the image of reverse
  81. > automatic device and with using the blanks in text files (or free fields in
  82. > some standard formats as in DBF), to compensate the hashing function at
  83. > changed file to former significance.
  84. >
  85. > Thus, it is possible to forge the electronic signature without analysis of
  86. > RSA algorithm.
  87.  
  88. Basically this means breaking MD5, which noone has done yet (the closest was
  89. Tom Berson who broke a severely reduced version at Eurocrypt '92).
  90.  
  91. >4. The block encryption algorithm problems
  92. >
  93. > - when executing analysis on plaintext and ciphertext the linear correlation
  94. > dependences with encryption key were founded (0.01 and more degree);
  95. >
  96. > - also the effective method of decreasing security which reduces the order of
  97. > time necessery to key definition in two times in comparison with exhaustive
  98. > search of all keys (i.e.  algorithm has the labour-intensiveness which is
  99. > equal the root square from labour-intensiveness of the exhaustive search
  100. > algorithm) have been found.
  101.  
  102. Most interesting - I'm sure Xuejia Lai and James Massey would be interested in
  103. this - what is the method used?
  104. [Footnote: The two people metioned above are the inventors of the IDEA cipher] 
  105.  
  106. >The conclusions:
  107. >
  108. > It is recommended to use encryption with 1024 bit key length.
  109.  
  110. Basically the standard recommendation for RSA.
  111.  
  112. > The using of electronic signature is not recommended and requires the
  113. > additional study.
  114.  
  115. ie "How strong is MD5"?
  116.  
  117. > The block encryption algorithm has temporary stability.
  118. >
  119. > The hashing function should be reduce in conformity with ISO recommendations.
  120.  
  121. Which ISO recommendations?  ISO 8730?
  122.  
  123. Is there any way of contacting the people who did the analysis?  They've raised
  124. all sorts of interesting points which I'd like to look at in more detail...
  125.  
  126.                            -------------------------------
  127.  
  128. Peter.
  129. --
  130.  pgut1@cs.aukuni.ac.nz||p_gutmann@cs.aukuni.ac.nz||gutmann_p@kosmos.wcc.govt.nz
  131. peterg@kcbbs.gen.nz||peter@nacjack.gen.nz||peter@phlarnschlorpht.nacjack.gen.nz
  132.               (In order of preference - one of 'ems bound to work)
  133.            -- Whoever dies with the most email addresses ... wins --
  134.  
  135.