1993-11-23 - Can NSA crack PGP?

Header Data

From: karn@qualcomm.com (Phil Karn)
To: mech@eff.org
Message Hash: ff20fe2d3e9d9ada731bf8113efc2b61d8d2dd2fdc17f196dd77a4a763c3ad04
Message ID: <199311230337.TAA00569@servo>
Reply To: <199311222336.SAA22403@eff.org>
UTC Datetime: 1993-11-23 03:37:43 UTC
Raw Date: Mon, 22 Nov 93 19:37:43 PST

Raw message

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

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

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.