C'punks: a friend of mine forwarded this to me to post with the following question: Should this bug preclude the use of the MIT PgP2.6 executable as distributed? As I personally am more of a tool-user than a tool builder I defer to the more knowlegeable... thanks in advance claude ############################################################### begin forwarded post ======================================================================== Date: 06-01-94 06:06 = Message #: 10210 NITELOG From: Colin Plumb Status: PUBLIC To: ALL Ref #: 0 Subject: I screwed up - PGP bug Conf: AltSecurePGP |29 (2042) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - @FROM :colin@nyx.cs.du.edu Message-ID: <2si4kp$sjg@nyx.cs.du.edu> Newsgroups: alt.security.pgp,talk.politics.crypto,sci.crypt Organization: /usr/lib/news/organi[sz]ation -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.5 mQCNAi3L864AAAEEAKRe8j9QUqL4PDQSsliTKQ0yTkdLL8BFBm7c03RC9Ol5PP9K j/RtnsdxFMTtW7wkMwTpY1jF23HR+x54LrOpi8ig6HEmiXVVWuNByRjSMgz8jvrn MM0/tIOCPAgNMxiANUWqretPEWCZE9sLbylkJrrOd54ZKyXBTw/D7AL7u4qxAAUR tCFDb2xpbiBQbHVtYiA8Y29saW5Abnl4LmNzLmR1LmVkdT6JAJUCBRAtyxCUZXmE uMepZt0BAeiyA/4tNXz6loqEwyMv65TMGtqxTlT5ocGNzyE8mkZXvbmoS0m7sdsd aVBvHfK8lrkQz/anrzAHJMBOaZ0V6T7aCLAK6GnjHoeanP8ZyhaXpc2e7EVut4Zi hCpmq45uiA/1diwLXhC8OoHwKqZDT+uNnJLLdlAzrJiOaELAzXXeOvtMXokAYAIF EC3L/BnKPaH9hlqn8wEBXWgCWMgIh8Lsww5pFHRFbAe2HehjGIiOmQ+ZcnL3pOhw tLdoGm6lqWZ4njDSTULxDpKUtbe4pWNv6Go13t9p+1GmTh+RrnGoq6rs3Mlg+IkA lQIFEC3L+zgPw+wC+7uKsQEBDZkEAJYkHK5n02GXLwEEgFKpxQvWLqI2xz33rPDa 0eT6+RYMDcr/1vzTqX7CwNpCuTaFTVNRbRznvwNTDcQXVsnyPg5yGdRIIMPnWuGf gSEP7vjm8zzvfdh5te4ag6jobCN1PVyqIIxIV5S8iPv632gm4vQboJiQ+4+53qoS WJ6BNDq9 =Wjfi -----END PGP PUBLIC KEY BLOCK----- -----BEGIN PGP SIGNED MESSAGE----- I have the unpleasant task of reporting a significant bug in PGP's random number generation (for making primes), and that it's my fault. It *is* a significant problem, although it is *not* end-of-the-world severity. That is, the code is not doing performing as intended, and the results aren't as random as intended. On the other hand, this does not appear to make any generated keys easier to break. Because it has to do with random-number generation, there are no interoperability issues raised. Please read on for details. Thanks to the many people who have submitted other bug reports and porting patches. A new release from MIT is forthcoming with more cleanups. * The Bug In pgp 2.6 (and 2.5), there is a file named "randpool.c", which accumulates entropy from keyboard timings. These random numbers are used in generating session keys, although the primary random number generator for session keys, based on IDEA, is unaffected. The main use of these random numbers is the much more sensitive task of generating RSA secret keys. In that file, a tiny helper function is xorbytes: static void xorbytes(byte *dest, byte const *src, unsigned len) { while (len--) *dest++ = *src++; } A character is missing. '^', to be precise. That "=" should be "^=". I wrote it, and I knew when I was writing it that it was critical code. Since you can't test a random-number generator (except for the most trivial of flaws), you have to walk through the code very carefully. I did, or thought I did, yet still managed to miss this. Oops is too mild. That code is not supposed to have ANY bugs. In other words, I screwed up. There's a lesson in there somewhere. I'll try to learn it. * The Effect The randpool.c code works by maintaining a pool (buffer) of random bits and adding in new "noise" from the environment each time a key is pressed. This "adding" is done by exclusive-oring it with successive bytes from the existing pool. When the pool is "full", a cryptographic stirring operation is performed to mix all the information in the pool together and get ready for new noise. The bytes in the pool at the end are intended to be uncorrelated with the noise bytes that will be added, so the XOR adding does not cause any sort of "cancellation" of information. This stirring is done with a key, which is taken from the pool at the end of each pass. With the bug in place, the noise bytes *replace* the bytes in the pool rather than being added to them. So the information that was in the pool is obliterated. The only trace that remains is what's stored in the key. This is at most the size of the key, 512 bits, rather than the size of the whole pool, 3072 bits. PGP tries to ensure that generated RSA keys are completely unpredictable by accumulating enough Shannon information to make the whole key. Thus, infinite computational power would not let you predict a generated secret RSA key. This bug subverts that. * Security Analysis What effect does this have on someone's chances of breaking an RSA secret key generated with PGP 2.6? Not much, as far as I can tell. But it requires more careful thought and that eats into the comfort margin that should be there. Just for comparison, the RSAREF library's random number generation routines are also based on MD5, but use 16 bytes of seed. Successive random bytes are taken by computing the MD5 hash of the 16-byte seed, using those 16 bytes, incrementing the seed by 1 (taken as a 128-bit number), and repeating. Taking the MD5 of a 16-byte value involves one pass of the MD5Transform function, with 16 of the 64 key bytes unknown, 48 bytes are known (fixed, in fact), and the input hash is known (fixed, in fact). Compared to this, PGP 2.6, even with the bug, is excellent. All 64 bytes of key to MD5Transform are dependent on all of the seed, the input hash varies widely, and the output is XORed with some difficult-to-predict data. The reason that you can get away with less than perfect random numbers (less Shannon information than the size of the generated key) is that you only have to make sure that the weakness does not make any attack easier than the best known attack without the weakness. As long as guessing is only useful to a brute-force attack, it remains far easier to factor. Paul Leyland estimated that the work to try all possible 128-bit IDEA keys is equivalent to factoring a 3100-bit RSA key. Now, recent work by Arjen Lenstra on the number field sieve (Paul Leyland was assuming the MPQS used in RSA-129) has raised this RSA key length somewhat. Thus, an argument can be made in favour of RSAREF's use of a 128-bit random number seed, since that's all that is necessary. PGP prefers to be a little bit more paranoid. Still, once you have 512 bits of uncertainty, trying all possibilities is more work than trying to break a 1024-bit RSA key by trial division. So let's see just how much entropy is in there. Each keystroke, the following data is added to the random pool: - - The cahracter typed, an int (2 or 4 bytes) - - the time_t result of time() (4 bytes) - - the clock_t result of clock() (4 bytes) - - On MS-DOS, 2 bytes of hardware timer 0 - - On Unix, 8 bytes of gettimeofday() and 20 bytes of times() results - - On VMS, 8 bytes of high-resolution timer. The total is 12 bytes on MS-DOS, 32 bytes on Unix (this may vary, but that's very common), and 20 bytes on VMS. The information content of the bytes is taken at a maximum of 8 bits, although it's actually closer to 15 bits on MS-DOS, and less (maybe as low as 1 or 2) on a Unix system with a fast typist and a slow (60 Hz) clock. VMS is in between. This means that the entropy density in the added bytes varies from 1/12 (or better) in MS-DOS to 1/256 on Unix. Thus, the content of a pool's worth (3072 bits) is 256 bits (or more) under MS-DOS and may be as low as 12 bits on some flavours of Unix. The random number accumulation operation adds bytes to the pool until it is either full or the desired number of bits have been accumulated. Then it stors the pool. For a maximum-sized key (1024 bits), it will take many passes through the pool to accumulate the entropy, but owing to the bug, each time the pool is overwritten with the most recently collected data. The only entropy that remains from the previous pass is in the 512-bit key buffer. This applies to every stirring pass until the last, after the last noise data has been added and new data is about to be withdrawn from the pool. This last pass is very likely to be incomplete; some of the data at the tail of the pool is probably not overwritten. This can carry over extra entropy from the previous pass. No more than is there (the 12 to 256 bit range observed before), and then you have to add an unknown fraction of that for data that has been added in the current pass, but the total will vary from 12 bits (an average of 18) to 256 bits (an average of 384). Plus the entropy preserved in the key buffer. So there is from just over 512 to an average of 896 bits of entropy in the pool. 1016 random bits are used to make the starting values for the two primes in a 1024-bit key. This is clearly not the perfect Shannon entropy PGP aims for. As long as the stirring operation is still considered cryptographically strong, this reduction in the possible range of generated keys is not useful to a factoring algorithm, so it doesn't make a factoring attack any easier, yet a factoring attack is still far easier than a guessing attack, so the easiest attack is no easier. So I don't think anything is more attackable. Still, it's NOT what was intended, and that's always bad. My apologies to users of PGP. - -- -Colin -----BEGIN PGP SIGNATURE----- Version: 2.5 iQCVAgUBLeyVSw/D7AL7u4qxAQEjCQP/YlzY5DWT4FrSErQ8W0TP9ibRqpck4gKL YOkUgiMQnvCE2XHEvP1VTfUANgU9O/P7lClJ1oaOXIEbt5GW45DAVPgSZk5PoJ10 TZ5Ly4wqDzMa8YLDu4I2l2Use5wwIIYl5IbGEdZiRlYdox7eWaGRLfOiA8CPVb9p yZ7PgFZU10Y= =Bj83 -----END PGP SIGNATURE-----