COMMAND
PGP
SYSTEMS AFFECTED
PGP 5.0
PROBLEM
This problem was found by Germano Caronni, and verified by Thomas
Roessler and Marcel Waldvogel. 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.
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.
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>
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.
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. Authors of advisory did not researched the
effects of this in detail. However, it is believed 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
http://olymp.org/~caronni/pgpbug-keyrings.tgz
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);
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@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.
Authors of advisory give a back-of-the-envelope upper estimate of
the amount of random bits PGP may gather during interactive key
generation. They 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.
This vulnerability stands for:
- 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)
SOLUTION
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.
This can be fixed by replacing line 1324 by the following line of
code:
read (fd, &RandBuf, 1);
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.