Reading al Qaedas Encrypted Email

Strategypage ^ | August 5, 2004 | James Dunnigan

[Lonesome in Massachussets]

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.

[Ichneumon]

That would be a 1 followed by 77 zeros. Just like 1 times 10^2 is a one followed by 2 zeros.

D'oh!

Sigh, it was the wee hours of the morning, and I've spent a lot of time correcting people who say that 10^X 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. :-)

[proxy_user]

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.

[Lonesome in Massachussets]

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.

[ScuzzyTerminator]

How many machine cycles will be needed to test each decryption for plaintext?

I doubt that the NSA would use CPUs to crack well known algorithms. I assume they use hardware designed for the task, like the EFF DES Cracker project. The "randomness meter"  would likely be a module that works in parallel without slowing anything down.

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.

Steganography before encryption doesn't help because you know you found the key when you've found, for example, a .jpg  or a uuencode. Generally, you need to encrypt before you hide.

The brute-force cracker cannot be programmed to recognize to many variants...

Variants don't matter. You're not looking for recognizable data patterns but just measuring randomness. Any message with meaningful information, no matter what the format, will be manifest as non-random if you have a sample at least as big as the unicity distance.

[zeugma]

This fool should shut his mouth, or have it shut for him.

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.

[zeugma]

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.

I call keys like that 'heat death' keys, because they'll take longer to decrypt than the ultimate fate of the universe.

[Finalapproach29er]

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.

[js1138]

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.

[Quix]

THX. Will try and check it out.