Can NSA crack PGP?

In a FidoNet debate, it's been charged that PGP is unsafe, and that NSA
can crack it.  The persons holding this viewpoint espouse the idea that
the NSA can crack anything, pretty much, and that anything they could not
crack would not be available to the general public, but would have been
supressed.

Can anyone disprove this notion definitively?  I'm looking for an
ironclad case that this idea is incorrect. It'd especially be appreciated
if anyone with reasonable "credentials" can respond.  

Even if you do post replies to the list/group, please at least Cc me so I
don't miss them.

SO, let's take this opportunity at online education, and spread the news
that under current technology, PGP is in fact a secure cryptosystem.

Thanks, and let the games begin!

-- 
Stanton  McCandlish  mech@eff.org  1:109/1103   EFF  Online  Activist & SysOp
O P E N  P L A T F O R M   C R Y P T O P O L I C Y   O N L I N E  R I G H T S
N  E  T  W  O  R  K  I  N  G      V  I  R  T  U  A  L     C  U  L  T  U  R  E
I   N   F  O :  M   E   M   B   E   R   S   H   I   P  @  E  F  F  .  O  R  G

> 
> In a FidoNet debate, it's been charged that PGP is unsafe, and that NSA
> can crack it.  The persons holding this viewpoint espouse the idea that
> the NSA can crack anything, pretty much, and that anything they could not
> crack would not be available to the general public, but would have been
> supressed.

The basic problem here is not whether the NSA has or hasn't cracked PGP.
Certainly it's safe today from the prying eyes of even a really determined 
FIDO sysop, even if he keeps up with all his mathematical journals and has 
access to commercially available supercomputer power. This should be sufficient
reason for its use... :-)

In all of the literature I have read, it is acknowledged that one
of the two possible things is true:

1) Factoring might not be as hard as we think it is; Bruce Schneier, for
   instance, cautions readers to keep informed about mathematical 
   developments in factoring. It has not been disproved that factoring
   is a hard problem, but neither has it been proved.

2) The NSA may have equipment that, using massively parallel techniques,
   can factor small RSA keys by brute force. However, if factoring is as
   hard as we think it is, very large keys are probably not within the
   scope of the NSAs ability, unless they have access to a different 
   universe where physical laws behave differently.

[...]
>> 
> SO, let's take this opportunity at online education, and spread the news
> that under current technology, PGP is in fact a secure cryptosystem.
> 

Security is always a relative thing, Stanton, and if the transport layer
becomes sufficiently problematic, a really determined opponent will seek
other weaknesses (a spike mike in your house, a tap in your computer,
having burly gentlemen with names like "Butch" grab you and hold you 
upside down over a large body of rapidly moving water).

IMHO, the real point of encrypting is to make it difficult for the NSA 
and their ilk to casually surf the nets for stuff, and stymie more humble
opponents (whether they are sysops, employers, competitors, hackers, or 
France).

Doug

-- 
----------------                                             /\ 
Douglas Barnes            cman@illuminati.io.com            /  \ 
Chief Wizard         (512) 447-8950 (d), 447-7866 (v)      / () \
Illuminati Online          metaverse.io.com 7777          /______\

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

In cypherpunks Phil Karn writes:

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

Minor nit: I agree that keystroke timing is good in principle for getting
"true" random bits, but we should be careful not to extrapolate too much from
the STU-III for general purpose computer systems.  The STU may have a
specially designed keypad timer, while god knows how often some random OS/
hardware combination delivers keyboard interupt times back to user processes.
Compounding the issue is knowing which bits in the interarrival time are
the "hotest" ones to measure on a particular system, which may be surprisingly
far from the lowest order bits depending on the clock granularity and skew.

Obviously the technique works well in some configurations, but there may
be others where it fails badly.  PGP seems to use it too good advantage, but
I'd still be suspicious before trusting it on an untested platform.

-matt

>Minor nit: I agree that keystroke timing is good in principle for getting
>"true" random bits, but we should be careful not to extrapolate too much from
>the STU-III for general purpose computer systems.

I fully agree.

>Compounding the issue is knowing which bits in the interarrival time are
>the "hotest" ones to measure on a particular system, which may be surprisingly
>far from the lowest order bits depending on the clock granularity and skew.

I think this is less of a problem. Given a good cryptograpic hash
function, I would simply hash *all* of the clock bits, without regard
to which are the "hottest" ones. If (important 'if') there is
sufficient total entropy in the input bits, hashing should effectively
"distill" the input entropy into the output bits.

Phil

> I think this is less of a problem. Given a good cryptograpic hash
> function, I would simply hash *all* of the clock bits, without regard
> to which are the "hottest" ones. If (important 'if') there is
> sufficient total entropy in the input bits, hashing should effectively
> "distill" the input entropy into the output bits.

True.  In fact, PGP does this.  However, the problem is knowing how
much raw data you need in order to get enough entropy into the system.
That is the hardest part.  For example, say that only one bit is
random for every 8 you get.  That is a very big difference than if 6
of the 8 bits were truely random.  And each machine-type is different!

Yes, you don't really need to know which bits are the hot-bits, but
you need to know how many hot-bits/byte you have, and this is machine
specific.  You could always deal worst-case, in which you assume the
worst machine-type and on machines with better hot-bit ratios you just
get extra entropy.  (That never hurts).

-derek