----- Forwarded message from gec(_at_)acm(_dot_)org -----
Date: Tue, 23 May 2000 14:13:23 -0700
From: gec(_at_)acm(_dot_)org
To: undisclosed-recipients: ;
Subject: Key Generation Security Flaw in PGP 5.0
Reply-To: gec(_at_)acm(_dot_)org, roessler(_at_)guug(_dot_)de
Mail-Followup-To: gec(_at_)acm(_dot_)org, roessler(_at_)guug(_dot_)de
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 <DSS or RSA> <key-length> <user-id> <timeout> <pass-phrase>
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(_at_)bar(_dot_)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 <http://olymp.org/~caronni/pgpbug-keyrings.tgz>.
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 <http://olymp.org/~caronni/randlog-keygen>.
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(_at_)guug(_dot_)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 <gec(_at_)acm(_dot_)org>, and
verified by Thomas Roessler <roessler(_at_)guug(_dot_)de> and Marcel Waldvogel
<mwa(_at_)arl(_dot_)wustl(_dot_)edu>.
----- End forwarded message -----