PGP: suggestions from the trench

3 Apr 1993

      After carefully reading RSA.COM's FAQ (version 1.0 draft 1e [14 
Sep 1992] by Paul Fahn; available via anonymous ftp from 
RSA.COM), I have some comments about the various PGP 
implementations.

First of all: well done!  These implementations and ports have 
taken a lot of unremunerated work from a lot of people.  If you 
compare the number of people registering public keys on the PGP 
servers such as pgp-public-keys@toxicwaste.mit.edu to the number 
registering for the RIPEM versions licensed by RSA/PK partners, 
for example, found on rpub.cl.msu.edu, PGP enjoys an order of 
magnitude more popularity.

So regardless of the outcome of legal, support, standards and 
interoperability issues, the PGP experiment has already been a 
tremendous success in letting us common folk learn about 
effective and convenient public key encryption.

One of the great advantages of a popular application is the great 
number of fingers and eyes that can be used to detect and 
document problems to make PGP even a greater success.  Here are 
the thoughts of one user:

1.  PGP RSA bit lengths are too short.  According to RSA's FAQ, 
the US Government (NSA) does not consider export licenses for RSA 
moduli used for privacy greater than 512 bits [section 2.23].  
This may imply something about NSA's capability in attacking RSA 
systems with fewer than 512 bits of modulus; Ron Rivest, a co-
inventor of RSA, estimates the cost of factoring a 512-bit 
modulus *today* at $8.2 million dollars (much less of course in 
the future) [section 2.8].  Although it is true that the time to 
generate a new RSA key goes as the order of 16 times the modulus 
length, this is only done once or a very few times.  Encryption 
and signature verification time on the other hand goes only as 
the order of four time the modulus length [section 2.8].  And the 
faster computers of tomorrow will virtually eliminate this 
performance penalty compared to the vastly increased time 
required for a factoring attack on RSA moduli that increasing its 
size entails.

Taking all these factors into consideration, I would suggest that 
the *minimum* size of the RSA modulus available for PGP is 1024 
bits with a minimum ceiling of 2048 bits (or even more).  If for 
performance reasons on certain platforms 1024 is deemed 
impossibly slow, then a lesser number of bits ought to be 
permitted *provided* that the security level for any key length 
under, say, 768 bits is clearly labeled "TOY GRADE".

And because factoring security is a moving target with increases 
in computer speed and factoring methods, rather than the static 
(and rather melodramatic) labels of "commercial grade," military 
grade", and so on, the labels ought to be specific years that 
intelligent estimates (such as Ron Rivest's) that that size 
modulus will be factored by a determined opponent.  For example, 
512 bits should be labeled "1992", 768 bits labeled "2005", 1024 
bits labeled "2020", and so on, using an estimate of about 15-20 
bits a year of modulus degradation.  This also supplies a clue as 
to selecting intelligent public key expirations given individual 
security goals.

While this may seem too conservative, consider that many public 
moduli kept by a certifying authority may be attacked in 
parallel, similar to cracking a passwd file NOT using a salt.  We 
must be *absolutely sure* that the theoretical basis of the 
encryption function is the paramount consideration in PGP.

2.  The hash function generates too short a digest.  In section 
6.3 of the RSA FAQ, RSA recommends MD5 with its 128 bit digest 
when using 512 bit or shorter RSA keys.  This is because they 
estimate the work factor of breaking a 128 bit digest is on the 
order of 2^64 operations or roughly equivalent today to factoring 
512 bit numbers.

If PGP increases the minimum recommended modulus size but does 
not simultaneously increase the hash digest size, then attacks 
such as "guessed plaintext," where guesses are made as to the 
IDEA key being encrypted under RSA are made compared to a trial 
RSA encryption, will become more and more attractive.

The RSA FAQ recommends using the SHS (Secure Hash Standard) 
[available from csrc.nist.gov] which generates a 160 bit digest 
or a modified MD4 algorithm that produces a 256 bit digest.  In 
any event, the 128 bit IDEA key to be encrypted under RSA ought 
to at the very least have a 64 or 128 bit random salt (that will 
later be discarded) appended before RSA encryption to thwart the 
"guessed plaintext" attack on RSA.  According to the RSA FAQ, MD4 
and MD5 are available for unrestricted use via RSA.COM or 
ftp.nisc.sri.com as rfc1320 (MD4) and rfc1321 (MD5).

3.  Triply encrypted DES with CBC ought to be another 
"conventional encryption" option under PGP menus.  RSA FAQ cites 
Campbell and Wiener's "Proof that DES is not a group" (Advances 
in Cryptology - Crypto '92 Springer-Verlag, New York 1993, To 
appear) that proves that DES with multiple encryption does indeed 
spread the encryption mapping over a broader space and thus 
presumably increases the work factor to direct cryptanalysis.  
IDEA, while attractive in speed, size and theory, has no such 
group-free proof and has not long withstood the public scrutiny 
that DES has endured.  Three 56 bit keys could easily be derived 
from a single MD4 256 bit digest (with an additional 64 bits of 
Initializing Vector, to boot) to double the brute-force key 
guessing DES work factor to roughly 112 bits.  A slightly non-
standard version such as Outerbridge/Lau/Gillogly/Karn's newdes, 
which is provably at *least* as secure as plain DES, might be 
used in order to thwart dedicated DES hardware attacks.

4.  Add a "enter random seed" option in addition to keystroke 
timing.  It is suspected that the timing biases in keystroke 
timing is far more pronounced than rolls of an ordinary die, 
especially over the broad range of platforms that PGP has been 
ported to.  A useful option to make user rest easier about the 
amount of bias in the random seeding for the search for the 
public-key RSA modulus and the generation of conventional (IDEA 
and triple-DES keys) would be to permit the direct data entry of 
fifty or sixty rolls of a die to further disperse the original 
seed.  Given the difficulty of obtaining noisy diodes or sources 
counting radioactive decay, rolling dice is probably the easiest 
and comparatively least biased of ways of selecting random seeds 
[see Knuth v.2] *and* is under the direct personal control of the 
user.

5. Offer a "use strong primes" option in RSA key generation.  
While it is true that as it is said in the RSA FAQ [section 2.7] 
and the PGP documentation that "strong primes" may not now be 
necessary given the non-favoritism of ECM ("elliptic curve 
method") of factoring (Lenstra: Factoring integers with elliptic 
curves. Annals of Mathematics 126:649-673, 1987), there is only 
the one-time penalty of selecting "strong" primes in public key 
generation and, as the RSA FAQ suggests, future breakthroughs in 
factoring technique may very well once again favor the "strong" 
prime over the garden variety one.

6.  Probably my most urgent recommendation:  I use MacPGP 2.2 and 
it did not come with a) a source b) a digitally-signed archive or 
c) a pointer to send bug reports.  Without these features it is 
very hard to make specific implementation bug reports or 
interface improvement suggestions.  As the RSA FAQ says in 
section 2.6: "In practice, most successful attacks will likely be 
aimed at insecure implementations and at the key management 
stages of an RSA system."  Please, please include the source to 
the Mac version (or upon request), or at least an object map so I 
can effectively disassemble and test portions of the code.

Comments appreciated.  Grady Ward  grady@netcom.com

PGP: suggestions from the trench

grady＠netcom.com