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
participants (5)
-
cman＠caffeine.io.com -
Derek Atkins -
karn＠qualcomm.com -
Matt Blaze -
Stanton McCandlish