Posted on 08/04/2004 11:09:02 PM PDT by Straight Vermonter
The U.S. and Pakistan may have found a way to read months, or years, worth of secret al Qaeda messages. No one is saying anything about that, but it works like this.
The recent warnings that al Qaeda was planning attacks on specific targets in the United States was said to come from recent people, and information, captured in Pakistan. One of the two key al Qaeda people captured was Mohammed Naeem Noor Khan, an English speaking Pakistani computer engineer. Khan was running an al Qaeda communications network, using email and encryption to distribute messages that could not be read with out the decoding keys. What was left out of these reports was any mention of public key cryptography, PGP (a version of public key cryptography freely available to Internet users), the National Security Agency (NSA) and cracking (decoding) PGP. There’s more to Mister Khan’s capture than meets the eye.
During the 1990s, the NSA was frequently in court trying to keep PGP off the market. In the 1980s, NSA was trying to get the key length of commercial ciphers kept shorter than business wanted. NSA is in charge of developing systems to keep American government messages secret, and figuring out how to crack the codes other nations use. Although the NSA never admitted it, most cryptography experts believed NSA wanted to keep longer keys out of use, because NSA did not have powerful enough techniques, or computers, to crack longer keys.
OK, all this talk of cipers and keys length doesn’t make sense to most people, so let’s offer a brief explanation. It starts with the appearance of inexpensive computers, when it became possible to use new methods to turn messages into apparent gibberish with coding systems. This was done using a “key”, which was a string of letters and numbers. Think of it a kind of password. If the person receiving the message had the right key, the message could be decoded (using a mathematical routine similar to the one that garbled the message in the first place.) The most popular of these techniques was eventually released as an inexpensive commercial product called PGP (Pretty Good Privacy). Users could post a “public key” that other users of the PGP program could use to scramble an email message or data file. When you received a message scrambled with your public key, you entered your private key into PGP and it descrambled the email or file.
The trouble with PGP was that, as far as NSA was concerned, it was too good. NSA got the U.S. government to declare programs like PGP to be military equipment, and subject to export controls. Trying to stop the spread of PGP was absurd, however, and the government eventually backed off. But NSA’s problem with PGP encoded messages remained. Or did it? NSA, obviously, is not going to admit that it can, or cannot, crack PGP encoded messages.
The most straightforward to read an encoded PGP message, without the decoding key is to use a computer to run through every possible combination of the key, to find the ones that work. A 516 digit key can be cracked using this computerized “brute force” method. For example, if you have a computer that can perform a million instructions per second going at it for 30,000 years, you can read the message encoded with a 516 digit key. That’s a little misleading, as a thousand dollar PC in 2004 can generate several thousand MIPS. So it would only take you ten years to crack that code. Of course, if you got several hundred of these PCs working together, you could get the job done in a few weeks. You can see where this is going. NSA has billions of dollars a year to play with, and building “supercomputers” out of cheap PCs has become quite popular.
However, increase the key to 768 characters, and it takes about 6,600 times longer to crack it. Go to key size of 1024, and it takes 1,500 times longer than the 768 character key. Go to a 2048 key size and it takes a billion times longer than a 1024 character long key. PGP can use a 1024 character key, and many users go for the larger key for obvious reasons.
Down at the NSA, all is not lost. Cracking a PGP code can be done with clever math as well as powerful computers. While we know there are a lot of cheap, powerful computers available to the NSA, we also know the NSA has a lot of clever people who specialize in figuring out better ways to crack codes. What we don’t know is if NSA is able to crack PGP messages scrambled using 1024 character codes.
If al Qaeda’s computer savvy Mohammed Naeem Noor Khan was in charge of an al Qaeda communications network that used the Internet, then he was probably using PGP. Al Qaeda use of PGP has been reported many times, as have complaints about the potential for that providing al Qaeda with an invulnerable encryption system. NSA has remained silent. But if Kahn was the man in charge, and he had many of the decryption keys with him when he was captured, that enables the NSA to read many previous messages. How many? Depends on how many keys were captured. Could be months worth. It’s also possible that months worth of actual messages was captured. This kind of information is invaluable in figuring out what al Qaeda has been doing, and is currently planning. Did Kahn have the keys? This is something you don’t want to discuss, one way or the other. You want the al Qaeda users of Kahns network to sweat a bit, even if the keys were not grabbed. And if the keys were obtained, there are tough times ahead for terrorist users of "invulnerable" encryption.
There is a VERY fine article in the September 2004 Atlantic Monthly about the
Al-Quida goodies found on a desktop and a laptop obtained by a Wall Street Journal reporter
just after his arrival in liberated Kabul.
Reading the terse e-mails between a field operative and his boss at headquarters
over his handling of Al-Quida funds is a hoot.
The U.S. and Pakistan may have found a way to read months, or years, worth of secret al Qaeda messages. No one is saying anything about that, but it works like this.
****
This fool should shut his mouth, or have it shut for him.
This is like when some fool Senator spilled the beans we were listening to Bin Laden's cellphone. Why tip off the enemy? LOOSE LIPS........
It's also possible that the guy didn't bother encrypting the contents of his own hard drive. He could have left a trail of unencrypted messages on the drive through bits of cache files, text files and other stuff on the drive as well.
a one time key is the safest way to communicate.
I think the govt can deciper PGP...I remember they couldnt export, then all of a sudden they could.
Even so, CIA probably has hackers who stole the info from PGP
The nice thing about any strong crypto is that it should stand up to attack even if you know the algorithm and implementation.
Of course if you find a flaw.... it can make anything easier to crack, especially if you have known text to work with.
You might want to check out GPG, the GNU open source version of PGP.
It wasn't a senator. It was the prosecutor in one of the original 1993 WTC bombing case. That's because Bill Clinton treated terrorism as ordinary crime rather than a war crime or piracy.
I would rather plant spyware on the Hotmail page that loads to any computer that accesses it from Pakistan, and pings the CIA computer from there...
Look at all the Phishing exploits going on now....and how many people are unaware!
Nice article. I doubt that the NSA can crack PGP, either due to magical advances in technology, or some implementation flaw that's exploitable.
My guess is sloppy key handling. If they captured the guys laptop, chances are they were able to recover his keys, because most people a) don't change their keys enough, and b) have crappy passwords on their private keys.
I'd guess tossing words/phrases from the Koran at an AQ password would likely be fruitful. Just put together a
dictionary of permutations of 'Allah', and see what you
get.
Someone needs to teach this reporter some math. The actual difficulty figures for a brute force crack are:
A 768-bit key takes 7.24x1075 times as long to crack as a 516-bit key (that's a 7 followed by *74* zeros).
A 1024-bit key takes 1.16x1077 times as long to crack as a 768-bit key (1 followed by 76 zeros).
A 2048-bit key takes 1.80x10308 times as long to crack as a 1024-bit key (about 2 followed by 307 zeros).
In each case the appropriate figure is 2(B2-B1), where B1 is the number of bits in the smaller key, and B2 is the number of bits in the larger key.
I don't know where in the hell the reporter got his figures from, but they're too small by enormous orders of magnitude.
If every single atom in the universe were a computer a trillion times faster than the fastest computer today, and ran for a trillion years, you still wouldn't have enough computer power to crack a single 2048-bit key by brute force.
Maybe they only found the Key in Pakistan...
The new IBM supercomputer "blue ocean" that the US navy is buying would do the job in 13 hours.
A quantum computer can break a PGP key in O((log N)3) time using Shor's algorithm.
I'll bet that quantum computation research has commanded a significant portion of NSA's budget for ten years or more.
"I think there is a world market for about five computers." -IBM founder Thomas Watson Sr.
Ah, good point, thanks for the correction. I was indeed thinking of n-bit conventional keys.
Is the number of valid 516-bit RSA keys known? It would be interesting to figure out how whether it would be feasible to pre-compute all possible keys into a "key dictionary", and then use that to brute-force test encrypted messages.
Odds are PGP still cannot be brute-forced without, literally, hundreds of millions of dollars worth of supercomputers. I DO believe the NSA can brute-force PGP, but only with superhuman super-expensive efforts.
Odds are any messages that were cracked were either decoded by physically capturing the private key, bugging a computer and learning the key that way.
The is some chance that having clear-text messages and their encrypted versions might help crack other encrypted messages.
But I don't find any evidence here that PGP can routinely be cracked.
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.