Stay Ahead With Linux Security News

security advisorycritical advisoryPGP

PGP 5.0 Critical Advisory: Key Generation Issue, Unpredictable Keys

A flaw has been found in the randomness gathering code of PGP 5. PGP 5 will, under certain well-defined circumstances, generate public/private key pairs with no or only a small amount of randomness. Such keys are insecure. Chances are very . . .. A flaw has been found in the randomness gathering code of PGP 5. PGP 5 will, under certain well-defined circumstances, generate public/private key pairs with no or only a small amount of randomness. Such keys are insecure. Chances are very high that you have no problem. So, don't panic. SECURITY FLAW IN PGP 5.0 ======================== EXECUTIVE SUMMARY ----------------- A flaw has been found in the randomness gathering code of PGP 5. PGP 5 will, under certain well-defined circumstances, generate public/private key pairs with no or only a small amount of randomness. Such keys are insecure. Chances are very high that you have no problem. So, don't panic. WHO IS AFFECTED? ---------------- The flaw has been found in the PGP 5.0i code base. It is specific to Unix systems such as Linux or various BSD dialects with a /dev/random device. Versions 2.* and 6.5 of PGP do NOT share this problem. PGP versions ported to other platforms do NOT share this problem. The problem does NOT manifest itself under the following circumstances: - You typed in a lot of data while generating your key, including long user ID and pass phrase strings. - A random seed file PGP 5 could use existed on your system before you generated the key. However, the problem affects you in the worst possible manner if you started from scratch with pgp 5 on a Unix system with a /dev/random device, and created your key pair non-interactively with a command line like this one: pgpk -g WHAT TO DO? ----------- If you have generated your key non-interactively, you may wishto revoke it, and create a new key using a version of PGP which works correctly. DETAILS ------- In order to generate secure cryptographic keys, PGP needs to gather random numbers from reliable sources, so keys can't be predicted by attackers. Randomness sources PGP generally uses include: - a seed file with random data from previous sessions - user input and input timing Additionally, certain Unix systems such as OpenBSD, Linux, and others, offer a stream of random data over a central service typically called /dev/random or the like. If present, this service is used by PGP as a source of random data. PGP 5.0i's reading of these random numbers does not work. Instead of random numbers, a stream of bytes with the value "1" is read. In practice, this implies two things: 1. PGP5 will generally overestimate the amount of randomness available. We have not researched the effects of this in detail. However, we believe that the amount of randomness gathered from input data, timing information, and old random data will be sufficient for most applications. (See below for a detailed estimate.) 2. In situations in which no other randomness sources are available, PGP relies on the /dev/random service, and thus uses predictable instead of random numbers. This is not a flaw of the random service, but of the PGP5 implementation. One particular example of such a situation is non-interactive key generation with a virgin PGP 5 installation, like described above. Example: $ mkdir /tmp/pgp5test $ PGPPATH=/tmp/pgp5test $ pgpk -g RSA 1024 foo@bar.com 0 "passphrase string" In fact, RSA keys generated this way are entirely predictable, which can easily be verified by comparing key IDs and fingerprints. When using DSA/ElGamal keys, the DSA signature key is predictable, while the ElGamal encryption subkey will vary. Note that fingerprints and key IDs of the predictable DSA keys depend on a time stamp, and are themselves notpredictable. Proof of concept key rings generated with pgp 5.0i are available from . GORY DETAILS ------------ 1. Code Here's the flawed code from src/lib/ttyui/pgpUserIO.c: 1314 static unsigned 1315 pgpDevRandomAccum(int fd, unsigned count) 1316 { 1317 char RandBuf; 1318 unsigned short i = 0; 1319 1320 pgpAssert(count); 1321 pgpAssert(fd > = 0); 1322 1323 for(i = 0; i 1324 RandBuf = read(fd, &RandBuf, count); 1325 pgpRandomAddBytes(&pgpRandomPool, (byte *)&RandBuf, sizeof(RandBuf)); 1326 pgpRandPoolAddEntropy(256); 1327 } 1328 1329 return(i); 1330 } The count parameter is always set to the value 1 by the calling code. The byte read from the file descriptor fd into the RandBuf buffer is subsequently overwritten with the read() function's return value, which will be 1. The actual random data are not used. This can be fixed by replacing line 1324 by the following line of code: read (fd, &RandBuf, 1); 2. "Random" data A dump of random data gathered during an interactive key generation session is available at . This was dumped as passed to the pgpRandomAddByte() function, one byte at a time. Note the streams of bytes with the value 1 which should actually contain data gathered from /dev/random. Also note that the pass phrase ("asdf") and the user ID ("This email address is being protected from spambots. You need JavaScript enabled to view it.") are clearly visible, but mixed with timing data from the individual key presses. No random data occuring after the second stream of ones were generated from external events prior to the generation of the DSA key in question. 3. Some estimates We give a back-of-the-envelope upper estimate of the amount of random bits PGP may gather during interactive key generation. We assume that /dev/random reading is flawed, and that no seed file exists prior to running PGP. Timing is assumed to have a resolution of 1 us (gettimeofday()). During a PGP session of one minute, wecan get at most 2^28 different time stamps (2^28 ~ 60*10^6). Note that one time stamp close to the point of time of key generation is known to attackers from the time stamp PGP leaves on the key. So the intervals between individual key presses remain as a source of randomness. Assuming that the user types at a rate of about 120 characters per minute, we have an interval of approximately 0.5 seconds between two key presses. Dropping the upmost non-random bit of the interval length, we get about 18 bits of random timing information per key press. This estimate gets worse for experienced and fast-typing users. With a user ID of 20 characters, and no pass phrase, PGP will have gathered roughly 300-400 random bits interactively. While this is not bad, it is not sufficient by PGP's own standards. CONCLUSIONS ----------- Public code review is a good thing - if it happens. CREDITS ------- This problem was found by Germano Caronni , and verified by Thomas Roessler and Marcel Waldvogel . |-Per Kangru----| |Lasercooling @ Stockholm Univ. +46-(0)8-161136 This email address is being protected from spambots. You need JavaScript enabled to view it. | |Consultant @ Roxen IS AB +46-(0)709-153939 This email address is being protected from spambots. You need JavaScript enabled to view it.| |-PGP-fingerprint-672C8-5632-7DC49-CFECC-E0EE-3DA4-E82E-A036F-59A1| . A flaw has been found in the randomness gathering code of PGP 5. PGP 5 will, under certain well-defi. found, randomness, gathering, under, certain, well-defi. . LinuxSecurity.com Team

May 24, 2000 • LinuxSecurity.com Team Cryptography