Hi. I just signed up for the boards, and this is my first post.
Anyways, I’ve been curious about something ever since 128-bit encryption was allowed to be exported to foreign countries a few years ago. Even before 9/11 and the war on terror, I wondered if this was really a smart idea. Since 128-bit encryption is still uncrackable at the moment (I read somewhere once that it would take all of the combined computing power on earth working for 10,000 years to crack a 128-bit key), what does (or can) the government do if they intercept messages between known terrorists that have been encrypted with 128-bit keys? Does the CIA or NSA have some sort of “backdoor” or some other secret method of cracking these messages?
The NSA certainly has access to computer power and encryption theory that the rest of us won’t get ahold of for years, but encryption of sufficient strength will remain secure long enough for the data to become meaningless. Naturally, if they do have some secret method to crack encryption, we won’t find out about it for awhile:)
As to the question of whether export restrictions are effective, if any encryption is developed and becomes publicly available, it WILL become available worldwide. It only takes one sleeper agent to mail a CD back to a terrorist organization. Whether strong encryption should be outlawed for everyone would be a matter for Great Debates.
I think the main reason the export ban was lifted was that it was a hopelessly lost cause. The fundamental mathematics encryption are not that hard to grasp (though it is, of course, much much more difficult to use them to make a provably secure system). Public Key cryptography, once the idea was shown to be feasible, could not be reliably confined within the United States since there were people all over the world clever enough to re-invent it.
The mathematics of strong public key crypto were recently shown to have been first explored by British mathematicians working for GCHQ. They weren’t developed into working cryptosystems since the existing communications infrastructure was well developed enough that they didn’t need such techniques at the time, but the essential discovery was there. This research goes back as far as 1960. It was only a matter of time before someone else did the same thing after the US export ban, especially since they knew the general areas to explore.
You’re right to say that this does potentially place strong cryptography in the hands of terrorists, but once this genie was out of the bottle it was impossible to put it back in.
On a side-note, one-time pads are indeed very secure, but only if they are used, as their name implies, once. Their efficacy relies on a secure and prompt system of delivering copies of the keys to all participants and of synchronising the use of the keys. If a one-time pad is used two or more times then careful cryptographic analysis can be used to begin extracting the messages. I suspect that terrorist organisations that operate on a system of distributed cells would have trouble distributing one-time pads securely.
Back in the day, the NSA made a few changes to the civilian-designed DES algorithm to prevent an attack that wasn’t known to civilians for 15 years. One could assume that the NSA’s decryption techniques are 15 years ahead of the civilian world.
According to Dr. Ron Rivest’s estimates, civilians will be able to crack RSA keys of somewhere between 142 and 567 decimal digits (468 to 1871 bits) in the year 2015–depending on budget and the acutal rate of technological progress–and 147 to 607 decimal digits (485 to 2003 bits) in the year 2020.
This means the NSA can probably crack 128-bit encryption easily today, and they can probably crack 1024-bit encryption as well, if they’re willing to spend billions of dollars on the attempt.
Well, if you believe this website, the NSA is far enough ahead of the rest of the world in math theory to crack any encryption our puny human minds can come up with
Having interviewed for a position with the NSA some years ago, I think the aforementioned webpage overstates their capabilities slightly.
Note that the US is not the soul source of crypto software. The silly US restrictions on export was hurting American businesses. Note that crypto is part of many mundane computer packages: word processors, spread sheets, etc.
Bin Laden’s group appears to not have used real crypto very well, if at all. Lot’s of stuff has been found on computers completely unencryped and a few things that were encrypted has easily found passwords. The only cryto-ish security that they have used successfully are code words and the like. Which don’t require any computers at all and are hardly modern.
(People really have to get off this “Terrorists used X so let’s control X.” nonsense. Terrorists breathe oxygen, drink water, use toothpaste, etc. Want to control those too? Crypto is a very mundane everyday necessity that is required to protect your stuff.)
FYI, I recognized or was able to find everything mentioned in that…treatise on the NSA and aliens, with the exception of “interstice theory”. Not even a terribly good fake.
I have a question… Has it been yet shown that terrorists or even criminals have bothered with encryption so far, and if so, to what extent? Everything I’ve read points to that the main use was buisness, and terrorists using it is very little more than a worry at this point.
There are several points to be made here. First, RSA encryption has not been shown secure. I think it is, but it is certainly not provably so, not yet anyway. It is known to be insecure, but if NSA has discovered how to break it, they are not saying. If I broke it, I might not say either, but try to sell it to someone.
Second, it takes about 2 minutes (or less) to describe the RSA system to a mathematician. There are certain well-known caveats that take a few more minutes to describe (don’t use primes p for which p-1 or p+1 has certain factorization properties) and implementation will take longer, but the restriction on export was silly. Unless, the real reason was to discourage Americans a cryptographic system that NSA could not break. Meantime, the rest of the world was using it. Only the NSA knows the real reason, but it was certainly not to keep it from the rest of the world.
Third, the only encryption system that is certain to be secure is the one-time pad. It is not just thought to be secure; it is proved unbreakable in principle. But beware: use it twice and I guarantee that anyone with even a modicum of decryption experience will readily break it. Of course, they have to know to try. The hardest part is generating a list of random numbers. The best way I am aware of uses the randomness of a lava lamp.
RSA is unquestionably “semi-broken”. There are a few known rules, as Hari Seldon mentions, for avoiding weak keys. Presumably there are many, many other rules relating to other weak keys. I assume the NSA knows about a whole lot of these. Hence, by going thru a list of public keys and applying their knowledge, there are probably some they are going to break. So the NSA (and no doubt others) can read all the encrypted mail etc. of a few unlucky folk.
OTOH, which ones they can break is somewhat random. It doesn’t nec. help them if they are targeting one particular person who happens to have lucked out in generating a key.
So RSA is a bit untrustyworthy IMHO. This has been well known since at least the time the original RSA MIT tech report came out. (I know, I discussed this issue with Ron Rivest at the time.) And no satifactory fix has ever been proposed. (Note that some of the rec.s for things to avoid were published after the original MIT tech report.)
BTW, on the export issue: the hard disk encryption system I use was developed in England and I downloaded it from there. Can anyone explain to me how US export laws would prevent terrorists from also using this system? Thought not. Bye.
Essentially, a one-time pad is an encryption using a key as long as the message. Both sender and receiver have a copy of the key. [em]And[/em] they never never use it more than just the one time.
It’s easy to show that it’s unbreakable–if you don’t know the key, of course. When methods of breaking encryption are discussed, it is usually assumed that someone knows the method of encryption, but not the key.
Say your keypad is &*6$, four characters long. If your message is LONG, then you just might add each of the four key characters to each of the characters of your message. To decrypt it, you just subtract &*6$, and the message (LONG) pops out. However, take any four letter word (heh) and subtract it–what pops out is the key that would have encrypted that word. So, your message could have been any word at all, depending on the keypad. And there’s nothing to indicate that it wasn’t, without the keypad.
Use that keypad twice though, and you introduce some redundancy that can be exploited to crack the message.
Actually, Public Key Crypto was first developed by James Ellis, working for England’s GCHQ in 1970. The work was classified, so it was only years later – when it was developed independently by Merkle, Diffie, and Hellman in 1976 – that it became public. So all the hubbub about export restrictions is irrelevant. It’s silly to think the US has a monopoly on intelligent people.
Anyway, it still isn’t a valid argument against encryption even if terrorists ARE using it. They won’t quit just because it becomes illegal, and there are many more legitimate uses.
And the only real problem with the one-time pad is key distribution. If you have a secure channel for distributing keys the size of your message, then you can (usually) just as easily distribute the messages securely.
Sure, if you’re talking about terabytes of daily banking information or something, but if you mean simple telegrams, or text-based email, then a DVD one-time pad along with your computer (everybody’s got one) could do you for a long long time.
You probably realize this, but I wanted to make it clear that you’re comparing apples to oranges. RSA is a public-key algorithm, and a 2000-bit key is relatively short by today’s standards. Most serious users have 3-4000 bit keys. When the OP referenced a 128-bit key, they’re presumably talking about a symmetric encryption algorithm like AES. Mathematically, this is a completely different problem and you can’t just compare key length between the two problems and say one is stronger. A 128-bit RSA key would be laughably short; a 128-bit AES key is very strong.
I don’t know if NSA can brute-force a 128-bit AES key very quickly or not. I’m willing to bet that even if they can, the process is so expensive (in processing time) that you’ve got to be NSA-enemy #1 before they bother. That makes the business proposals I carry on my laptop pretty safe.
You obviously understand the issues with a one-time pad, but I’d like to clarify for the record. I don’t want to drag this off topic, but I feel obliged to point out the problems with OTPs when they come up because many people read the first few chapters of a crypto book, learn that OTPs are provably secure, and think they don’t need anything else. This is naive and bears rebuttal.
One-time pads are provably secure as an algorithm, but when implemented as a usable system, they have to follow a number of very specific rules about key generation, distribution and use in order to remain secure. In most cases, these requirements make them completely unusable in the real world. In some very limited cases, they are useful. As you cite, I can generate a DVD full of key material, store it separate from my computer, and use it to encrypt my data or my communication to another person who I’ve previously shared my key data with. That’s great, but it’s a very specific use. It doesn’t allow for things like SSL (which essentially makes ecommerce possible). It doesn’t permit me to send secure communications to anyone I haven’t previously shared key data with, so I can’t communicate with new clients or any of my virtual friends I’ve never met, but PGP does. It doesn’t allow me to use portable embedded hardware where memory or bus limitations prevent the use of my large offline key data. In short, OTP is a very specific tool that works very well for a very specific job, but is completely useless for most of the things that need to get done in the real world. While we should keep them in mind for the narrow range of problems they solve, citing them as the obvious solution in a discussion of general crypto security is pointless and misleading.
Breaking an enciphered message is called cryptanalysis.
A couple of things. Other than an one time pad, all ciphers are breakable if you throw sufficient resources (including time) at it. The purpose of a cipher then is not to keep a message secure forever, but to keep it long enough until the data is no longer needed to be kept secret.
