From: Ben.Goren@asu.edu
Date: Sun, 17 Jul 94 13:59:45 PDT
To: cypherpunks@toad.com
Subject: PGP bug *NOT* yet fixed
Message-ID: <aa4f46110202101e9059@[129.219.97.131]>
MIME-Version: 1.0
Content-Type: text/plain


Y'all remember that bug that Colin Plumb told us about in the true random
number generation part of PGP? It's still there, in the version from
net-dist.mit.edu, as of late yesterday evening. There is *no* mention of
the bug anywhere, in any readme files, in the documentation, anything.

This strikes me as irresponsible. I would expect PGP 2.6a to have been
released the day of the announcement, with the bug fixed. If there's some
reason why that couldn't be done, then at least there should be some sort
of prominent notice detailing the change, and probably a diff file--or even
a simple shell script--to apply the (very simple!) fix.

The signature on the following file checks as follows:

>File has signature.  Public key is required to check signature. .
>Good signature from user "Colin Plumb <colin@nyx.cs.du.edu>".
>Signature made 1994/06/01 14:04 GMT

That's a month and a half ago.

The *only* copies of PGP 2.6 out there that are free of the bug are those
that have been fixed by hand. That's probably not all that many of them.

I'm going to bite the bullet and paste in the original message here. Feel
free to flame me if this is unnecessary re/cross-posting, but I'm not aware
of any place to get this aside from digging through archives, and....

b&

-----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-----

--
Ben.Goren@asu.edu, Arizona State University School of Music
 net.proselytizing (write for info): Protect your privacy; oppose Clipper.
 Voice concern over proposed Internet pricing schemes. Stamp out spamming.
 Finger ben@tux.music.asu.edu for PGP 2.3a public key.