2004-01-30

PGP encryption can been cracked no matter what key size

I love PGP and think more people should use it more of the time.

The main reason I think this, is because the more people use PGP the harder it will be for systems like ECHELON to organize/filter/categorize the content that they filter. (ECHELON is the international side of the NSA-sponsored system that intercepts all fax, phone, email, internet traffic and analyzes it. I am convinced there is a domestic US equivalent, that is most probably integrated with its global counterpart)

Many people think ECHELON simply targets 'keywords'. However, based on patents filed by various government agencies you can assume it is *much* more sophisticated than that, for instance rudimentary 'language recognition' patents as well as 'topic classification' patents.

The topic classification patent is especially interesting, because, if they are able to create a map of all the, types of people, types of conversations that people have, then they can more easily filter out all the 'Jana's having a baby!' conversation and zero in on the 'lets organize a march' conversation of radicals and other undesirables (oh, yeah, and "terrorists" and "drug dealers" - the only problem here is that to find the largest number of these in the most cost effective way all they would need to do is walk down the hall start arresting people.. ).

Anyway the point I am trying to make is that - partly based on conversations with people who have actually worked for GCSB (NZ version of NSA) and the DSD (Australian version of NSA) - I am firmly of the opinion that PGP encryption can been cracked no matter what key size. Sure, its just an opinion but I personally am convinced that if they wanted to spend the computing power on it (and these are 100 million dollar institutions, so, yeah, it doesn't come cheap) then the NSA, at least, would most certainly be able to do so.

Yes, brute force cracking does suffer from limitations of the theory of computer science. However, in practice there are almost always little faults or problems of the actual implementation in practice that can be exploited to get at the real data. This may or may not include aspects of 'physical' data such as key logging, keyboard heat scanning, but it really doesn't have to .. at various times various software only vulnerabilities have been demonstrated with just about all encryption systems, and you can be sure if the NSA ever found such they wouldn't tell anyone.

Furthermore, we mustn't be forgetting that:

1. These are the folks that actually invented the whole idea of an actual "computer" itself, for precisely the reason of cracking encryption (during WWII)

2. They have an absolutely obscene black budget to play with, as demonstrated by the $1.1 trillion in unsupported accounting entries that appeared in the official federal Audit of the DOD budget for FY 2000. Of course, given that they claim to have just, woops, accidentally 'lost' this money then yeah its hard to make the case that they spent it all on the NSA, but I mean, lets just say that *someone* has a lot of money in their piggy back. [ Actually lets just back up for a second here, did I just say they "lost" 1.1 *trillion* dollars ?? how much are we talking here ? ... Weeell... if you consider the fact the *total* US federal budget, including all military spending, is usually just a bit 2 trillion then you get some idea. Oh my god, suddenly I can't breathe.)

3. (Getting back to the point) The purely theoretical idea of a quantum computer that can crack just about any level of encryption has existed in the public domain since at least 1997 and simplistic, real world quantum computer implementations (that, to be fair, are far from being able to do this) have also appeared in the public domain in recent years.

4. That the NSA (or whatever it was back then) kept the truth of what they had achieved (in cracking all the german codes during WWII) secret not only throughout the war but for *decades* afterwards, and at considerable cost in life by the way.

--

Just one final point. This doesn't mean don't use PGP by any means! It just means, that in my unsupported opinion, any message you send is undoubtedly completely breakable, if the NSA really wanted to, not that that really matters because they probably don't (unless you mention BOMB, NUCLEAR, ECHELON, PRESIDENT, and THE PLAN IS GO enough times that is).


4 comments:

Anonymous said...

You are definitaely an idot. no offense.

Anonymous said...

PGP can be broken by NSA/GCHQ/..??? :shock:

If you are in the business of assassination of prime ministers or presidents then well wtf are you using PGP for?

If your storing your bank details on your computer & don't want the chav round the corner to have a lucky day then PGP wins.

WOW i've summed up your article in 62 words

Trenton D. Adams said...

Sure, its just an opinion but I personally am convinced that if they wanted to spend the computing power on it (and these are 100 million dollar institutions, so, yeah, it doesn't come cheap) then the NSA, at least, would most certainly be able to do so.
----

Huh? You're talking about brute forcing? No, that will NEVER happen with the technology today. The most powerful computer on the planet, with hundreds of thousands of parallel processors could not increment through 256 bit keys in our life time, using every single CPU cycle.

Now you're talking about adding actual processing of algorithms, which take up 10s of thousands of times more cycles? No, not going to happen.

But, most PGP keys are WAY bigger than 256 bits. Even 257 bits is sooooooooooo much bigger, now we're talking 4K, 8K, etc, etc? HUGE.

The only way of cracking PGP, would be to do it cryptographically, by finding a flaw in the algorithm.

utunga said...

@Trenton - thanks for your comment - but that's really my point. Yes you're absolutely right the back of the envelope calculation shows that GPP is just about mathematically impossible to crack regardless of computing power, as you say - "that will NEVER happen with the technology today".

The problem is the assumption that these are the same type of computers as we have today. Just one possibility but let's say the NSA is 20 years ahead Quantum computer wise. Would that potentially open up the ability to crack GPG? Yes absolutely. (Fundamental shift in the type of technology involved). Would they let on about this fact? Hell no. Not on your life.

Furthermore, on a more prosaic level, it is very likely that there are still other more technical deficincies to GPG that haven't been found yet (think timing attacks and the like).

Of course I can't imagine what the actual technology shift is, but if you consider that 'break codes' is the thing that took us from 'computers don't even exist in theory' to 'first, working digital computers' and given budgets involved it seems to me, not unlikely that some organisations would in fact be able to crack GPG today.

Ask again in 30 years, we'll see.