home *** CD-ROM | disk | FTP | other *** search
/ The Unsorted BBS Collection / thegreatunsorted.tar / thegreatunsorted / old_apps / pgp / pgp26.bug < prev    next >
Text File  |  2001-02-10  |  10KB  |  231 lines
  1. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
  2. From: colin@nyx.cs.du.edu (Colin Plumb)
  3. Subject: I screwed up - PGP bug
  4. Date: 1 Jun 1994 08:06:17 -0600
  5.  
  6. -----BEGIN PGP PUBLIC KEY BLOCK-----
  7. Version: 2.5
  8.  
  9. mQCNAi3L864AAAEEAKRe8j9QUqL4PDQSsliTKQ0yTkdLL8BFBm7c03RC9Ol5PP9K
  10. j/RtnsdxFMTtW7wkMwTpY1jF23HR+x54LrOpi8ig6HEmiXVVWuNByRjSMgz8jvrn
  11. MM0/tIOCPAgNMxiANUWqretPEWCZE9sLbylkJrrOd54ZKyXBTw/D7AL7u4qxAAUR
  12. tCFDb2xpbiBQbHVtYiA8Y29saW5Abnl4LmNzLmR1LmVkdT6JAJUCBRAtyxCUZXmE
  13. uMepZt0BAeiyA/4tNXz6loqEwyMv65TMGtqxTlT5ocGNzyE8mkZXvbmoS0m7sdsd
  14. aVBvHfK8lrkQz/anrzAHJMBOaZ0V6T7aCLAK6GnjHoeanP8ZyhaXpc2e7EVut4Zi
  15. hCpmq45uiA/1diwLXhC8OoHwKqZDT+uNnJLLdlAzrJiOaELAzXXeOvtMXokAYAIF
  16. EC3L/BnKPaH9hlqn8wEBXWgCWMgIh8Lsww5pFHRFbAe2HehjGIiOmQ+ZcnL3pOhw
  17. tLdoGm6lqWZ4njDSTULxDpKUtbe4pWNv6Go13t9p+1GmTh+RrnGoq6rs3Mlg+IkA
  18. lQIFEC3L+zgPw+wC+7uKsQEBDZkEAJYkHK5n02GXLwEEgFKpxQvWLqI2xz33rPDa
  19. 0eT6+RYMDcr/1vzTqX7CwNpCuTaFTVNRbRznvwNTDcQXVsnyPg5yGdRIIMPnWuGf
  20. gSEP7vjm8zzvfdh5te4ag6jobCN1PVyqIIxIV5S8iPv632gm4vQboJiQ+4+53qoS
  21. WJ6BNDq9
  22. =Wjfi
  23. -----END PGP PUBLIC KEY BLOCK-----
  24.  
  25. -----BEGIN PGP SIGNED MESSAGE-----
  26.  
  27. I have the unpleasant task of reporting a significant bug in PGP's
  28. random number generation (for making primes), and that it's my fault.
  29.  
  30. It *is* a significant problem, although it is *not* end-of-the-world
  31. severity.  That is, the code is not doing performing as intended,
  32. and the results aren't as random as intended.  On the other hand,
  33. this does not appear to make any generated keys easier to break.
  34. Because it has to do with random-number generation, there are
  35. no interoperability issues raised.  Please read on for details.
  36.  
  37. Thanks to the many people who have submitted other bug reports and
  38. porting patches.  A new release from MIT is forthcoming with more
  39. cleanups.
  40.  
  41. * The Bug
  42.  
  43. In pgp 2.6 (and 2.5), there is a file named "randpool.c", which
  44. accumulates entropy from keyboard timings.  These random numbers are
  45. used in generating session keys, although the primary random number
  46. generator for session keys, based on IDEA, is unaffected.  The main
  47. use of these random numbers is the much more sensitive task of
  48. generating RSA secret keys.
  49.  
  50. In that file, a tiny helper function is xorbytes:
  51.  
  52. static void
  53. xorbytes(byte *dest, byte const *src, unsigned len)
  54. {
  55.         while (len--)
  56.                 *dest++ = *src++;
  57. }
  58.  
  59. A character is missing.  '^', to be precise.  That "=" should be "^=".
  60.  
  61. I wrote it, and I knew when I was writing it that it was critical
  62. code.  Since you can't test a random-number generator (except for the
  63. most trivial of flaws), you have to walk through the code very carefully.
  64. I did, or thought I did, yet still managed to miss this.
  65.  
  66. Oops is too mild.  That code is not supposed to have ANY bugs.
  67.  
  68. In other words, I screwed up.  There's a lesson in there somewhere.
  69. I'll try to learn it.
  70.  
  71. * The Effect
  72.  
  73. The randpool.c code works by maintaining a pool (buffer) of random bits
  74. and adding in new "noise" from the environment each time a key is
  75. pressed.  This "adding" is done by exclusive-oring it with successive
  76. bytes from the existing pool.  When the pool is "full", a cryptographic
  77. stirring operation is performed to mix all the information in the pool
  78. together and get ready for new noise.  The bytes in the pool at the end
  79. are intended to be uncorrelated with the noise bytes that will be added,
  80. so the XOR adding does not cause any sort of "cancellation" of
  81. information.  This stirring is done with a key, which is taken from the
  82. pool at the end of each pass.
  83.  
  84. With the bug in place, the noise bytes *replace* the bytes in the pool
  85. rather than being added to them.  So the information that was in the
  86. pool is obliterated.  The only trace that remains is what's stored in
  87. the key.  This is at most the size of the key, 512 bits, rather than the
  88. size of the whole pool, 3072 bits.
  89.  
  90. PGP tries to ensure that generated RSA keys are completely unpredictable
  91. by accumulating enough Shannon information to make the whole key.  Thus,
  92. infinite computational power would not let you predict a generated
  93. secret RSA key.  This bug subverts that.
  94.  
  95. * Security Analysis
  96.  
  97. What effect does this have on someone's chances of breaking an RSA
  98. secret key generated with PGP 2.6?  Not much, as far as I can tell.
  99. But it requires more careful thought and that eats into the comfort
  100. margin that should be there.
  101.  
  102. Just for comparison, the RSAREF library's random number generation
  103. routines are also based on MD5, but use 16 bytes of seed.  Successive
  104. random bytes are taken by computing the MD5 hash of the 16-byte seed,
  105. using those 16 bytes, incrementing the seed by 1 (taken as a 128-bit
  106. number), and repeating.
  107.  
  108. Taking the MD5 of a 16-byte value involves one pass of the MD5Transform
  109. function, with 16 of the 64 key bytes unknown, 48 bytes are known
  110. (fixed, in fact), and the input hash is known (fixed, in fact).
  111. Compared to this, PGP 2.6, even with the bug, is excellent.  All 64
  112. bytes of key to MD5Transform are dependent on all of the seed, the input
  113. hash varies widely, and the output is XORed with some
  114. difficult-to-predict data.
  115.  
  116. The reason that you can get away with less than perfect random numbers
  117. (less Shannon information than the size of the generated key) is that
  118. you only have to make sure that the weakness does not make any attack
  119. easier than the best known attack without the weakness.
  120.  
  121. As long as guessing is only useful to a brute-force attack, it remains
  122. far easier to factor.
  123.  
  124. Paul Leyland estimated that the work to try all possible 128-bit
  125. IDEA keys is equivalent to factoring a 3100-bit RSA key.  Now,
  126. recent work by Arjen Lenstra on the number field sieve (Paul Leyland
  127. was assuming the MPQS used in RSA-129) has raised this RSA key
  128. length somewhat.  Thus, an argument can be made in favour of
  129. RSAREF's use of a 128-bit random number seed, since that's all that
  130. is necessary.
  131.  
  132. PGP prefers to be a little bit more paranoid.  Still, once you have
  133. 512 bits of uncertainty, trying all possibilities is more work than
  134. trying to break a 1024-bit RSA key by trial division.
  135.  
  136. So let's see just how much entropy is in there.
  137.  
  138. Each keystroke, the following data is added to the random pool:
  139.  
  140. - - The cahracter typed, an int (2 or 4 bytes)
  141. - - the time_t result of time() (4 bytes)
  142. - - the clock_t result of clock() (4 bytes)
  143. - - On MS-DOS, 2 bytes of hardware timer 0
  144. - - On Unix, 8 bytes of gettimeofday() and 20 bytes of times() results
  145. - - On VMS, 8 bytes of high-resolution timer.
  146.  
  147. The total is 12 bytes on MS-DOS, 32 bytes on Unix (this may vary, but
  148. that's very common), and 20 bytes on VMS.
  149.  
  150. The information content of the bytes is taken at a maximum of 8 bits,
  151. although it's actually closer to 15 bits on MS-DOS, and less (maybe
  152. as low as 1 or 2) on a Unix system with a fast typist and a slow (60 Hz)
  153. clock.  VMS is in between.
  154.  
  155. This means that the entropy density in the added bytes varies from 1/12
  156. (or better) in MS-DOS to 1/256 on Unix.  Thus, the content of a pool's
  157. worth (3072 bits) is 256 bits (or more) under MS-DOS and may be as low
  158. as 12 bits on some flavours of Unix.
  159.  
  160. The random number accumulation operation adds bytes to the pool
  161. until it is either full or the desired number of bits have been
  162. accumulated.  Then it stors the pool.
  163.  
  164. For a maximum-sized key (1024 bits), it will take many passes through
  165. the pool to accumulate the entropy, but owing to the bug, each time
  166. the pool is overwritten with the most recently collected data.
  167. The only entropy that remains from the previous pass is in the 512-bit
  168. key buffer.
  169.  
  170. This applies to every stirring pass until the last, after the last noise
  171. data has been added and new data is about to be withdrawn from the pool.
  172. This last pass is very likely to be incomplete; some of the data at the
  173. tail of the pool is probably not overwritten.  This can carry over
  174. extra entropy from the previous pass.  No more than is there (the 12
  175. to 256 bit range observed before), and then you have to add an unknown
  176. fraction of that for data that has been added in the current pass,
  177. but the total will vary from 12 bits (an average of 18) to 256 bits
  178. (an average of 384).
  179.  
  180. Plus the entropy preserved in the key buffer.  So there is from
  181. just over 512 to an average of 896 bits of entropy in the pool.
  182. 1016 random bits are used to make the starting values for the
  183. two primes in a 1024-bit key.  This is clearly not the perfect
  184. Shannon entropy PGP aims for.
  185.  
  186. As long as the stirring operation is still considered cryptographically
  187. strong, this reduction in the possible range of generated keys is
  188. not useful to a factoring algorithm, so it doesn't make a factoring
  189. attack any easier, yet a factoring attack is still far easier than
  190. a guessing attack, so the easiest attack is no easier.
  191.  
  192. So I don't think anything is more attackable.  Still, it's NOT
  193. what was intended, and that's always bad.
  194.  
  195. My apologies to users of PGP.
  196. - -- 
  197.         -Colin
  198.  
  199. -----BEGIN PGP SIGNATURE-----
  200. Version: 2.5
  201.  
  202. iQCVAgUBLeyVSw/D7AL7u4qxAQEjCQP/YlzY5DWT4FrSErQ8W0TP9ibRqpck4gKL
  203. YOkUgiMQnvCE2XHEvP1VTfUANgU9O/P7lClJ1oaOXIEbt5GW45DAVPgSZk5PoJ10
  204. TZ5Ly4wqDzMa8YLDu4I2l2Use5wwIIYl5IbGEdZiRlYdox7eWaGRLfOiA8CPVb9p
  205. yZ7PgFZU10Y=
  206. =Bj83
  207. -----END PGP SIGNATURE-----
  208. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
  209. From: mathew@mantis.co.uk (mathew)
  210. Subject: Re: I screwed up - PGP bug (MIT release)
  211. Date: 2 Jun 1994 12:24:31 +0100
  212.  
  213. In article <2si4kp$sjg@nyx.cs.du.edu>, Colin Plumb <colin@nyx.cs.du.edu> wrote:
  214. >I have the unpleasant task of reporting a significant bug in PGP's
  215. >random number generation (for making primes), and that it's my fault.
  216. [...]
  217. >static void
  218. >xorbytes(byte *dest, byte const *src, unsigned len)
  219.  
  220. For what it's worth, PGP 2.6ui has no xorbytes function that I can
  221. find, and indeed doesn't have the randpool.c file which contains the
  222. buggy code in 2.5 and 2.6.  I conclude that 2.6ui does not suffer from
  223. this bug.
  224.  
  225.  
  226. mathew
  227. -- 
  228. Seeking a decent bug-tracking system for Windows, DOS, UNIX, Mac...
  229. http://www.mantis.co.uk/~mathew/
  230. =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=