For the love of one time pads, or Why we still mess up crypto
I know, "Oh great, another crypto post". I'll try to get back to talking about password cracking next week, (as I have a bunch of stuff I'm just polishing up right now). Also, I'm still trying to reply to all of the e-mails I've received since Defcon so if I haven't gotten back to you yet, I apologize and I'm working on it.
Well, on with the show. Bruce Schneier reposted a writeup from another blog by Steve Bellovian, (it's like Twitter), that talked about the history of one time pads, (which I'll refer to as OTPs). More to the point, why you should generally avoid using them, and instead use standard cryptography, (RSA, AES, etc). This certainly isn't news. In fact Bruce has been writing about it since 2002. I have to say I enjoyed it simply since it introduced me to Bellovian's blog which is really good. This post isn't about OTPs though, despite the title and the fact that I'll be talking about them a bit. What interests me more is how the security community as a whole deals with cryptography.
People love OTPs since they are the only crypto algorithm that has a valid mathematical proof that shows they are unbreakable. I'll spare you the long proof, but it has to deal with the fact that every single bit is encrypted with its own key. Aka even if you know 99.9% of the plaintext message, it doesn't help you when trying to decrypt the other 0.1% since the encryption of the known 99.9% has no bearing on the encryption of the unknown 0.1%. Letter frequency analysis, machine cryptanalysis, known plaintext attacks, quantum computers; all these prove worthless against a properly implemented OTP.
The problem is, everything I just said depends on the assumptions in the proof being true in real life. Another way to say it is that the cow really needs to be a sphere. The two biggest assumptions are that
- The key has to be truly random, and
- The key must only be used once.
If either one of these is not true, OTPs become subject to attack, just like any other form of cryptography.
We've been using OTPs since at least 1917. The fact is we still have a hard time getting them right. Our random number generators turn out to be not so random. People reuse keys because key distribution is a major problem. Multiple groups share the same key. With the defender shipping out so much key material, some of it gets intercepted. The list goes on and on. After a certain point, you need to stop blaming the users, and instead try to come up with an alternate solution.
As of when I'm writing this, there are currently 37 comments in Bruce's original thread. Of these comments, there were 29 different posters. Going through the comments trying to figure out if they were pro-OTPs or not, I came up with 15 people supporting the use of OTPs, 10 people against their use, and 4 people I couldn't classify. (On a side note, going through numbers like this is why I'm so far behind on my e-mail...). Of the 15 people supporting OTPs, two came up with their own mathematical functions to create random numbers, and 4 people suggested that key size doesn't matter as storage space becomes cheaper. The very first comment turned out be my favorite:
"I think that there is a bias against OTP among cryptographers because OTP takes a problem that you need a cryptographer to solve -- message security -- and turns it into a problem that you don't need a cryptographer to solve -- key distribution. Cryptographers do not like approaches to problems that make them irrelevant."
Snark aside, I think the above comment brings up a lot of good points, though not the ones the poster intended. People have a tendency to get fixated on the crypto algorithm used. You can see a good depiction of it in this xkcd comic, (another reason why xkcd rocks). In reality, very rarely is the crypto algorithm the weak link. That's why I'm into password cracking. Quite simply, there is no way I'm going to crack AES. Heck 3DES is beyond me. Attacking the user though is something I can do. Likewise, in my last overlong post, I mentioned that I didn't trust RC4 encryption. This isn't because RC4 itself is broken, (in fact it can be very strong), but that implementing it correctly is almost impossible. Key exchange, key storage, identification, authentication, modes of operation, (ECB anyone?!); these are the areas where crypto implementations run into problems. Referencing the above comment again, the poster is mostly right. Most cryptographers don't like OTPs because while they solve the problem of encryption algorithm, we already have a lot of good solutions for that already, (let me mention AES again). Why cryptographers caution against using OTPs is because they are the absolute worst algorithm to use when it comes to key exchange, and key exchange is a much harder problem. Heck, public key cryptography was invented specifically to deal with the fact that key exchange can be too difficult even for block cyphers like AES.
I could go more into the implementation problems with OTPs, (Sysadmin analogy: It's like trying to maintain the patch level of servers all over the world when the servers don't have internet access), but I want to get back to talking about the security community. Your typical programmer should not have to worry about designing their own crypto protocols, (aka how the crypto algorithm, key exchange, authentication, etc all go together). The fact that many programmers still have to, is a failure on our part. Furthermore, we as a security community need to become less fixated on the encryption algorithms, and instead look at the crypto protocols instead. Saying that you use AES is like saying the car you are trying to sell me has wheels. Yes, it's a good and necessary starting point, but there's a lot of other requirements that would be good to know before I make a purchase. That's why I like IPSec. I hear that one word, and I can be fairly certain that the encryption protocol the program is using is solid, since IPSec not only deals with the encryption algorithm, but all the other stuff as well. Yes, there are issues where people allow "aggressive mode," (don't do that), but for the most part, if you don't set IPSec up securely it doesn't work. Also, the fact that there are multiple libraries, which have been vetted, available for it means that programers don't have to worry about coding it up themselves.
One last thing: to those who say OTPs are useful for spies since they don't require a computer to encrypt/decrypt a message. Let me point out that the last time I flew on an airplane I had a grand total of four different computational devices on me. The era where carrying around an Ipod made you suspicious has passed. Carrying around a code booklet filled with random numbers on the other hand...
Comments