PGP Attack FAQ: The pseudo-random number generator (PRNG)
PGP needs (pseudo-) random numbers, amongst others to generate temporary keys. To generate these numbers, PGP uses two so-called pseudo-random number generators or PRNGs. The first is the ANSI X9.17 generator. The second is a function which measures the entropy from the latency in a user's keystrokes. The random pool (which is the randseed.bin file) is used to seed the ANSI X9.17 PRNG (which uses IDEA, not 3DES). Randseed.bin is initially generated from trueRand which is the keystroke timer. The X9.17 generator is pre-washed with an MD5 hash of the plaintext and postwashed with some random data which is used to generate the next randseed.bin file. The process is broken up and discussed below.
Table of contents
How does ANSI X9.17 work?
The ANSI X9.17 is the method of key generation PGP uses. It is oficially specified using 3DES, but was easily converted to IDEA. X9.17 requires 24 bytes of random data from randseed.bin. (PGP keeps an extra 384 bytes of state information for other uses...) When cryptRand starts, the randseed.bin file is washed (see below) and the first 24-bytes are used to initialize X9.17.
In X9.17, a random number is generated by
R = E[E(T) XOR V] and V = E[E(T) XOR R]
where
- E() = an IDEA encryption, with a reusable key used for key generation
- T = timestamp (data from randseed.bin used in place of timestamp)
- V = Initialization Vector, from randseed.bin
- R = random number to be generated
How does the trueRand latency timer work?
The trueRand generator attempts to measure entropy from the latency of a user's keystrokes every time the user types on the keyboard. It is used to generate the initial randseed.bin which is in turn used to seed to X9.17 generator.
The quality of the output of trueRand is dependent upon its input. If the input has a low amount of entropy, the output will not be as random as possible. In order to maxmize the entropy, the keypresses should be spaced as randomly as possible.
How does the prewash with MD5 work?
In most situations, the attacker does not know the content of the plaintext being encrypted by PGP. So, in most cases, washing the X9.17 generator with an MD5 hash of the plaintext, simply adds to security. This is based on the assumption that this added unknown information will add to the entropy of the generator.
In the event that the attacker has some information about the plaintext (perhaps the attacker knows which file was encrypted, and wishes to prove this fact) the attacker may be able to execute a known-plaintext attack against X9.17. However, it is not likely that, with all the other precautions taken, this would weaken the generator.
How does the randseed.bin wash work?
The randseed is washed before and after each use. In PGP's case a wash is an IDEA encryption in cipher-feedback mode. Since IDEA is considered secure (see PGP Attack FAQ: The symmetric cipher), it should be just as hard to determine the 128-bit IDEA key as it is to glean any information from the wash. The IDEA key used is the MD5 hash of the plaintext and an initialization vector of zero. The IDEA session key is then generated as is an IV.
The postwash is considered more secure. More random bytes are generated to reinitialize randseed.bin. These are encrypted with the same key as the PGP encrypted message. The reason for this is that if the attacker knows the session key, she can decrypt the PGP message directly and would have no need to attack the randseed.bin. (A note, the attacker might be more interested in the state of the randseed.bin, if they were attacking all messages, or the message that the user is expected to send next).