From: karn@qualcomm.com (Phil Karn)
Date: Mon, 22 Nov 93 19:37:43 PST
To: mech@eff.org
Subject: Can NSA crack PGP?
In-Reply-To: <199311222336.SAA22403@eff.org>
Message-ID: <199311230337.TAA00569@servo>
MIME-Version: 1.0
Content-Type: text/plain


There is only one cipher that is provably secure: the one-time-pad.
All other ciphers are, at best, only "practically secure". That is,
they could, in theory, be cracked given enough time and computer
power, but in practice your enemy (even the NSA) *is* limited in his
resources.

There are several ways that NSA might crack PGP. Although I think it
relatively unlikely that they are true, there is nonetheless no way to
prove it. These include:

1. Attacking the RSA cryptosystem. This is a very well studied problem
in civilian cryptography, but it is always possible that NSA has found
a breakthrough in factoring that is still unknown to the civilian
world.

2. Attacking the IDEA conventional cipher. IDEA is based on a
relatively new (and different) design technique than DES.  It has not
had nearly the attention of the civilian cryptographic community that
has been spent on RSA and DES.

3. Attacking the random number generators. This is often the weakest
part of many conventional cryptosystems, but the techniques now used
in PGP are thought to be pretty good. Lest people think that timing
keystrokes is a poor way to generate random numbers, I should say that
I once watched somebody key a STU-III (NSA-designed secure phone). At
one point the phone prompted him to hit the "*" key 20 times. It
didn't say why, of course, but it was pretty obvious to me.  And if
it's good enough for NSA...

4. Attacking the PGP implementation itself. A "black bag job" that
modifies the victim's PGP executable to store or transmit pass
phrases, or gives the spooks a chance to search the disk's free list
for old temporary files, is almost certainly the easiest way to attack
PGP.  Don't forget that all computer security ultimately rests, at
some level, on physical security.

Phil