Thursday, September 09, 2010

One-time encryption in Today's World

One-time pad encryption is a most basic encryption algorithm where a truly random key is applied on the same amount of data. The nice thing about it is that this method, which was invented 93 years ago, is mathematically unbreakable. There's no way to crack it with current or future computer power, simply because it is mathematically impossible. Although this sounds impressive, there are some drawbacks. The key must be truly random, must be as long as the actual data that should be encrypted, and you can use a particular key only once. The consequence is a cumbersome key distribution with associated security problems.

Before we go any further, I must point out here that we're going to talk about modern one-time encryption applications, not the pencil-and-paper spy craft (see image). Neither is this article about small one-time passwords or one-time keys which are only valid for a single encryption session with some algorithm under control of that key, and certainly not about the many snake-oil applications that pretend to be unbreakable because they claim to be using one-time encryption, while they actually are not. Remember: key as long as the data, truly random and used only once. There's no way around these three conditions without messing up the unbreakable part (although many wrongly claim to have a solution)!

So, cumbersome key distribution...and that's where the mathematicians, or crypto-experts as you like, come in the play. In 1973, they invented asymmetric encryption which solves the problem of key distribution. Symmetric encryption requires the same key for encryption and decryption, and all people involved need a copy of that same key. With asymmetric public key cryptography however, you have key pairs that consist of a public key for encryption which you can share openly with everybody, and a private key for decryption that you keep secret. This solves the problem of key exchange. Since the invention of asymmetric key encryption, many crypto experts are buzzing around that it is the holy grail. Well...not quite.

Their system has nothing to do with the message security, only with the - unproven - key exchange security. Unfortunately, asymmetric encryption is not suitable for the encryption of large amounts of data. Hence, we only use it to encrypt a random key. Next, the actual data is encrypted with a traditional symmetric encryption algorithm, under control of that key. Finally, we send the complete package, encrypted key and encrypted data, to the recipient. Key distribution problem solved! What actually happened is that they took traditional symmetric algorithms, of which they are are not really sure whether they are secure (they are not, as they are deterministic), but hey, they found an easy/lazy way to exchange the keys for those traditional algorithms. Problem solved. Doooh!?

Bearing this in mind I just love David Boak's (NSA) magnificent quote: "the ‘approved’ systems have simply been shown to adequately resist whatever kinds of crypto-mathematical attacks we, with our finite resources and brains, have been able to think up. We are by no means certain that the [opponent] equivalent can do no better". This says alot, if not all.

How secure their asymmetric encryption might be, it doesn't change the fact that the actual data is encrypted with a traditional symmetric encryption algorithm and that's not a question of so-called insurmountable mathematical problems to crack asymmetric encryption, but a question of cryptanalysis of man-made algorithms, prone to weaknesses (not to mention mathematical shortcuts, back doors or bluntly faulty application). By the way, didn't Auguste Kerckhoffs and Claude Shannon learned us that, if we don't know how to break it, it isn't unbreakable, and any system that reduces a large secret (the data) to a smaller secret (a key) is deterministic and will never be unbreakable,

What happened is that, by focusing on the practical advantages of asymmetric key encryption and welcoming its large scale application and commercialisation, many mathematicians lost track of what really matters: message security. They say that one-time encryption is rendered superfluous in the era of asymmetric encryption. Just because it's less practical? By saying this, they actually prove themselves wrong, as the one has nothing to do with the other. They solved the key distribution problem and not the message security problem.

One time encryption, on the other hand, solves the message security perfectly (isn't that what we really need) but has a nasty key distribution issue. It would have been nice if those wizz kids solved that one! Well, maybe they did, but just don't tell us...but I doubt that. Cryptography is always a balancing between effort (comfort), costs and security. You can favor one of those - a bit - to the prejudice of the others, for a particular situation, but you can't say that comfort is better than security, and should never nibble on security in favor of comfort, when security is important.

Modern crypto algorithms provide reasonable but practical security and privacy, essential to our economy and everyday life. Sure, it made our lives easier and how else could we do all those things like buying on the Internet, using credit cards on-line, and many other things. But let us be serious, the combination of traditional encryption algorithms and asymmetric key algorithms provides nothing more or less than 'reasonable' security, and it will never provide real security or long term security.

But what is worse, is that the general public has become blinded by today's easy encryption systems and their commercial success. They don't realize that real privacy and security comes with a price called "effort & discipline", not to be confused and - unfortunately - incompatible with "easy-to-use". This might not be essential to the average man in the street, but it does matter if we talk about a company's production secrets, trade secrets or political activism, to name a few.

Some experts argue that the distribution of large quantities of keys, inherent to one-time encryption, is impractical. However, today’s electronics are capable of generating large numbers of truly random keys, and current one-time encryption software can process large quantities of data at high speed. Current data storage technology such as USB sticks, DVD’s, external hard disks or solid-state drives enable the physically transport of enormous quantities of truly random keys.

Actual sensitive communications are often limited to a small number of users. In such cases, one-on-one communications with the associated key distribution, possibly in configuration with a star topology to connect multiple users, is no longer really a practical problem, especially considering the security benefits (this quote will not be popular with cryptologists, but it is true).

By using a co-called sneakernet (transferring data on removable media by physically couriering), you can reach a throughput (amount of data per unit time) of one-time key material that is greater than what a network can process on data that must be encrypted. In other words, it could take a few hours to get a terabyte of key material, stored on an external drive, by car to someone, but it will take days or even weeks to consume that amount of keys on a broadband network.

A terabyte sized key can easily encrypt you e-mail traffic for a year, including attachments (you just try to send or receive a terabyte of data, most Internet providers won’t even offer such amount of traffic). Therefore, if security is preferred above practical key distribution, and physical key exchange is possible beforehand, then one-time pad is the right choice. Some commercial firms offer such one-time encryption solutions, mostly to government and defense agencies, and for good reasons.

Conclusion: yes, public key algorithms are useful and have earned their place in the market of reasonably secure large scale communications, and yes, one time encryption will stay the preferred solution when unconditional security is required. Stop comparing apples and oranges, we need both! And for anyone who states that one-time encryption is history, I have one advice: provide the actual mathematical proof that your asymmetric system and accompanied symmetric algorithm are safe, today and tomorrow (I can with one-time encryption). Bring it on, Bruce!

I wrote a paper called Is One-time Pad History, about one-time encryption and the illusions of modern computer cryptography. More about the history of one-time pad on my website. On Mils Electronic, a key technology company, there's more about one-time encryption (pdf) and secure message exchange (pdf).

2 comments:

Anonymous said...

Dirk,

This is an outstanding paper, and it should serve to alert thinking people about the false premise that most of the public is operating on—namely, that the ubiquitous public key encryption systems provide complete security. And, make no mistake; that is the conclusion that many have drawn.


The one time pad code encryption is unbreakable. What more can be done to improve its security?

No so long ago, someone suggested that when it comes to one time pad codes, what we really have is an engineering problem—that is, the delivery of random numbers to be used for encoding messages. And to solve that problem, you don’t need an encryption specialist. That fact won’t please everyone. No encryption specialist wants to be made irrelevant. There’s no job security in that situation.

So encryption specialists may not all be as objective as we might hope.

Anyway, there are many situations which require absolute security, and one should only trust the one time pad code for that. Furthermore, the onetime pad codes can be used on so-called “tethered” devices, such as “smartphones”. Such tethered devices usually limit users to programs sold by the company selling them. And encryption usually isn’t an option from the company. But a onetime pad code can usually be used.

To state the obvious: Onetime pad codes ARE quite relevant in the 21st century.

Amber Salm said...

I do enjoyed reading this detail about one time encryption. I am familiar with the concept and read many articles to learn about this scheme.
eSignature