D'oh!
Sigh, it was the wee hours of the morning, and I've spent a lot of time correcting people who say that 10X is "10 followed by X zeros", when it's really X-1. So I was primed to make the reverse mistake myself out of habit. :-)
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.
How does the computer recognize when the correct key has been used, and a valid result has appeared?
I believe that Blenchley Park solved that problem with "The Bomb". They knew the constraints on enigma machine, they had an electro-mechanical computer that would brute force possible combinations until plain-text German appeared in short snippets. It could false alarm, but just reset and continue.
D'oh!
Sigh, it was the wee hours of the morning, and I've spent a lot of time correcting people who say that 10X is "10 followed by X zeros", when it's really X-1. So I was primed to make the reverse mistake myself out of habit. :-)
I agree it is not a hard problem. My point is speed. How many machine cycles will be needed to test each decryption for plaintext? If you're trying to test a billion keys per second, this definitely becomes a consideration.
There would be many ways around brute-force recognition algorithms for skilled operatives. For example, you could write you text in a graphics application, and save it as a .jpg. Then uuencode it or yenc it to disguise the filetype, and apply your encryption algorithm. The brute-force cracker cannot be programmed to recognize to many variants without slowing it down so much that it would be worthless.
I think the point is that even things like that have headers in them, which would make them even easier to decrypt and recognize. Besides, AQ don't want to be slowed up, they just wanna fire off emails without all the rigamarole.
Nah. This article is mostly just speculation. If the NSA is reading the PGP messages from al Qaeda laptops, it's most likely that it is because they have the 'secret key', and it is protected with a weak password rather than a brute force attack. People are generally pretty stupid when it comes to passwords, which is one reason that PGP always says "pass phrase" in its documentation. MY pgp pasphrase is more than 40 characters, but few people go to such lengths because they simply don't understand the concept of the "weakest link". If the NSA has posession of the encrypted message (cyphertext), the public key, and the private key, it should be obvious that they'll attack the private key because it is the "master" that enables them to decrypt messages at will.
It used to be that the NSA had the best crypto folks on the planet, and while this might still be true to a degree, there are a heck of a lot more high-quality cryptographers out there in the world at large than there used to be.
I'd still bet that absent physical posession of the secret keys, PGP is probably still opaque to the NSA. That's one reason why it is so important to safeguard your keys.
Even without the ability to decrypt messages, traffic analysis is a useful tool in building information about networks of people. Knowing that Alice, Bob, and Chuck are communicating with a bunch of encrypted messages acn tell you a lot about relationships.
I support the universal use of encrypted mail. Unfortunately, most people can't be bothered. They'd rather send their messages on postcards than protect them with an envelope.
I call keys like that 'heat death' keys, because they'll take longer to decrypt than the ultimate fate of the universe.
The more basic question: Why announce it and let them know we can read their mail?
I don't understand the need to tip off the enemy when we succeed at gathering info.
Oddly enough, AQ continues to use satellite phones, even though the CIA owns the satellites. My guess is that NSA can read PGP. All encryption systems have vulnerabilities, fatal ones if you get your hands on even one machine in the chain of communication.
THX. Will try and check it out.
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.