CERT Advisory CA-2000-09 Flaw in PGP 5.0 Key Generation Original release date: May 30, 2000 Last Revised: -- Source: CERT/CC A complete revision history is at the end of this file. Systems Affected * UNIX systems having a /dev/random device running any version of PGP 5.0, including U.S. Commercial, U.S. Freeware, and International versions * Keys created non-interactively on such a system * Documents encrypted with such a key * Signatures generated with such a key Overview Under certain circumstances, PGP v5.0 generates keys that are not sufficiently random, which may allow an attacker to predict keys and, hence, recover information encrypted with that key. I. Description In order to generate cryptographically secure keys, PGP (and other products) need to use random numbers as part of the input to the key generation process. Generating truly random numbers is a difficult problem. PGP has traditionally solved that problem by prompting the user to type some random characters or to move the mouse in a random manner, measuring the time between keystrokes and using this as a source of random data. Additionally, PGP uses a file (usually called randseed.bin) as a source of randomness. However, PGP also provides the ability to generate keys non-interactively (useful, for example, if you need to generate a large number of keys simultaneously or provide a script to generate a key). When generating keys non-interactively, PGP needs a source of random numbers; on some systems PGP v5.0 uses the /dev/random device to provide the required random numbers. PGP v5.0, including U.S. Commercial, U.S. Freeware, and International versions, contains a flaw in reading the information provided by /dev/random. This is not a flaw in /dev/random but instead is the result of a flaw in how PGP processes the information returned from /dev/random. Thus, when a key is generated non-interactively using a command such as pgpk -g it does not contain sufficient randomness to prevent an attacker from guessing the key. If such a command were issued on a system with no available randseed.bin file, then the resulting key may be predictable. This problem was discovered and analyzed by Germano Caronni , and verified by Thomas Roessler and Marcel Waldvogel . A copy of their analysis can be found at http://www.securityfocus.com/templates/ archive.pike?list=1&msg=20000523141323.A28431@olymp.org II. Impact Keys produced non-interactively with PGP v5.0 on a system with a /dev/random device may be predictable, especially those produced in an environment without a pre-existing randseed.bin file. Documents encrypted with a vulnerable key may recoverable by an attacker. Additionally, an attacker may be able to forge a digital signature corresponding to a vulnerable key. Signatures produced using a vulnerable key, including signatures in certificates, may be untrustworthy. III. Solution If your PGP key was generated non-interactively using any version of PGP v5.0 on a system with a /dev/random device, you may wish to revoke it. Documents encrypted with a predictable key may need to be re-encrypted with a non-vulnerable key, if your particular circumstances warrant it; that is, if the information still needs to be encrypted. You may need to resign documents signed with a vulnerable key if your circumstances warrant it. Appendix A Vendor Information Network Associates Network Associates Security Advisory Date: May 30, 2000 Author: PGP Engineering Background: A security issue has been discovered in the following PGP products: PGP 5.0 for Linux, US Commercial and Freeware editions PGP 5.0 for Linux, Source code book (basis for PGP 5.0i for Linux) The following PGP products are NOT affected by this issue: + PGP 1.x products + PGP 2.x products + PGP 4.x products + All other PGP 5.x products + PGP 6.x products + PGP 7.x products Synopsis: During a recent review of our published PGP 5.0 for Linux source code, researchers discovered that under specific, rare circumstances PGP 5.0 for Linux will generate weak, predictable public/private keypairs. These keys can only be created under the following circumstances: + Keys are generated using PGP's command line option for unattended batch key generation, with no user interaction for entropy (random data) collection + No keys were generated interactively on this system previously (e.g., a PGP random seed file is not present on this system prior to unattended batch key generation) + PGP is able to access the UNIX /dev/random service to gather entropy during unattended batch key generation PGP 5.0 for Linux does not process the data read from /dev/random appropriately, and therefore does not gather enough entropy required to generate strong public/private keypairs. This issue affects both RSA and Diffie-Hellman public/private keypairs, regardless of keysize. Network Associates has verified that this issue does not exist in any other version of PGP. Solution: Users who generated keys in the manner described above are strongly urged to do the following: + Revoke and no longer use keys suspected to have this problem + Generate new public/private keypairs with entropy collected from users' typing and/or mouse movements + Re-encrypt any data with the newly generated keypairs that is currently encrypted with keys suspected to have this problem + Re-sign any data with the newly generated keypairs, if required Users are also urged to upgrade to the latest releases of PGP, as PGP 5.0 products have not been officially supported by Network Associates since early 1999, or distributed by Network Associates since June 1998. Additional Information: US commercial and freeware versions of PGP 5.0 for Linux were released in September 1997 by PGP, Inc., a company founded by Phil Zimmermann. Source code for the PGP 5.0 product family was published in September 1997. PGP, Inc. was acquired by Network Associates in December 1997. Acknowledgements: PGP appreciates the efforts of Germano Caronni, Thomas Roessler and Marcel Waldvogel in identifying this issue and bringing it to our attention. A pgp signed version of this statement is also available at http://www.cert.org/advisories/CA-2000-09/pgp.asc __________________________________________________________ The CERT Coordination Center thanks Germano Caronni, Thomas Roessler, and Marcel Waldvogel for initially discovering and reporting this vulnerability, and for their help in developing this advisory. Additionally we thank Brett Thomas for his insights. __________________________________________________________ Shawn Hernan was the primary author of this document. _______________________________________________________________ This document is available from: http://www.cert.org/advisories/CA-2000-09.html _______________________________________________________________ CERT/CC Contact Information Email: cert@cert.org Phone: +1 412-268-7090 (24-hour hotline) Fax: +1 412-268-6989 Postal address: CERT Coordination Center Software Engineering Institute Carnegie Mellon University Pittsburgh PA 15213-3890 U.S.A. CERT personnel answer the hotline 08:00-20:00 EST(GMT-5) / EDT(GMT-4) Monday through Friday; they are on call for emergencies during other hours, on U.S. holidays, and on weekends. Using encryption We strongly urge you to encrypt sensitive information sent by email. Our public PGP key is available from http://www.cert.org/CERT_PGP.key If you prefer to use DES, please call the CERT hotline for more information. Getting security information CERT publications and other security information are available from our web site http://www.cert.org/ To be added to our mailing list for advisories and bulletins, send email to cert-advisory-request@cert.org and include SUBSCRIBE your-email-address in the subject of your message. * "CERT" and "CERT Coordination Center" are registered in the U.S. Patent and Trademark Office. _______________________________________________________________ NO WARRANTY Any material furnished by Carnegie Mellon University and the Software Engineering Institute is furnished on an "as is" basis. Carnegie Mellon University makes no warranties of any kind, either expressed or implied as to any matter including, but not limited to, warranty of fitness for a particular purpose or merchantability, exclusivity or results obtained from use of the material. Carnegie Mellon University does not make any warranty of any kind with respect to freedom from patent, trademark, or copyright infringement. __________________________________________________________ Conditions for use, disclaimers, and sponsorship information Copyright 2000 Carnegie Mellon University. Revision History May 30, 2000: initial release - ANEXO III. Mensagem original enviada por Germano Caronni, descobridor da vulnerabilidade: ---------- Forwarded message ---------- Date: Tue, 23 May 2000 14:13:23 -0700 From: gec@acm.org To: BUGTRAQ@SECURITYFOCUS.COM Subject: Key Generation Security Flaw in PGP 5.0 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 wish to 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 not predictable. 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 <= count; ++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 ("roessler@guug.de") 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, we can 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 .