One cryptographic cipher has been mathematically proven to be unbreakable when it is used correctly, but it is only very rarely used. Chad Perrin breaks down the one-time pad cipher.
It seems to be a truism of cryptography that any cipher, no matter how strong it is considered to be in its heyday, eventually becomes a weak cipher. What people fear when they use the current favorite strong cipher is that someone will crack it — will find a shortcut that greatly reduces the time required to use brute force calculation to decrypt something without the key.
Even if a cipher is never broken, and we forever-more need the same average number of CPU clock cycles to decrypt something encrypted by a given cipher without using the key; it still takes less time every few months to achieve the same goal than it did a few months ago. This is because computers keep getting faster, allowing us to squeeze the same number of CPU clock cycles into a shorter period of time.
Ever-more complex and clever algorithms are designed to provide ever greater resistance to brute force cryptanalysis, and to replace older algorithms that have been broken or otherwise become obsolete. It is always an arms race — privacy against the attempt to penetrate that privacy.
Amongst all the wreckage of the broken and rusty ciphers that have fallen by the wayside through history, one cipher has endured for the last 93 years. It is called the one-time pad. In 1917, Gilbert Vernam developed a cipher known as the Vernam Cipher, which used teletype technology with a paper tape key to encrypt and decrypt data. The result was a symmetric cipher that was quite strong for its time.
U.S. Army Captain Joseph Mauborgne realized that by using truly random keys, where no part of the key was repeated (except perhaps at random), the Vernam cipher could be made much stronger. From the idea of using paper tape keys, a pad of paper with rows of random letters or numbers on each page as the means of recording keys was developed. Two copies of the same pad could be given to two people, and by using each character on each page only once (and destroying each page as its last character is used to encrypt or decrypt a message), they could pass encrypted messages between them without fear of an intercepted message ever being decrypted without the help of the key. Because of the technique of distributing key stream data on pads of paper, this cipher became known as the one-time pad.
Claude Shannon, known as the father of information theory, mathematically proved the unbreakability of the one-time pad cipher when it is used properly — including destroying any pages containing used key data so that it will not be used, and so that unauthorized copies of any messages cannot later be decrypted if someone gets his hands on your used pages from the pad. The same concept for key management can be employed digitally, of course, with the proviso that one must be very careful to avoid letting the inherent weaknesses of computers introduce flaws into the one-time pad system. For instance, expensive data recovery operations might be able to reconstruct “deleted” files, including used one-time pad data. There are things you can do to help obscure such data when simply deleting files is not enough, but one must be careful.
The one-time pad cipher can be extremely inconvenient at times, which is why it is not used more often. We do actually need theoretically weaker (if cleverer) ciphers, such as AES/Rijndael and Twofish because of that inconvenience:
- Because the one-time pad cipher is a symmetric cipher, both parties to an encrypted communication must have the exact same key data. For certain use cases for encryption, this makes a one-time pad completely useless, because to securely exchange the key data so both parties have it, one must have a secure means of sharing data that would work just as well for sharing the eventual messages themselves. Only in cases in which you do not know what messages you will need to send, and where you will not be able to use whatever secure means was used to exchange the key data (such as physically handing it to the person) at the later time, is the one-time pad cipher useful.
- A one-time pad encryption key must be as long as the message it is used to encrypt and decrypt. Thus, if you want to encrypt or decrypt a three gigabyte file, you need three gigabytes of one-time pad key data.
- The same one-time pad data can not be shared securely among more than two people; for example, in cases where different messages will be sent between some recipients of the key data, which should not be readable to other recipients, using the same one-time pad amongst all of them subverts the security of the cipher. By contrast, with an asymmetric cipher you can provide the same public key to dozens of people, and they will all be able to use that same public key to encrypt messages for you without any fear the other people who have the public key will be able to read it — as long as the cipher is not broken and the state of the art of computing technology does not advance enough to reasonably brute force decrypt the messages. This is because when something is encrypted with the public key, only the associated private key can be used to decrypt it.
- Reusing a key potentially breaks the security of the one-time pad cipher because it suffers a known-plaintext vulnerability. Kerckhoffs’ principle states that a cryptosystem should be secure so long as the the key remains secret, but where the encrypted and unencrypted (plaintext) versions of a given message are both known, the key can be derived in the case of the one-time pad cipher. This is not a problem if each string of key data is used only once, because if the plaintext is captured by the “enemy” you have already lost the game anyway. If a key is reused, however, one message’s plaintext can be used as part of the set of tools used to determine the key for decrypting another message. The moral of the story is: Don’t use a given one-time pad key more than once. There is a reason it is called a “one-time” pad.
- When the last of your one-time pad is used up, you cannot securely send messages back and forth — encrypted using that same cipher — any longer unless you securely exchange new random key data. This kind of thing can really cramp your style when trying to communicate with someone on the other side of the world.
Other factors come into play in making use of the one-time pad cipher impractical in some circumstances, too, but these should give you a good start on seeing why other, theoretically weaker ciphers are still important.
The way the one-time pad works is deceptively simple. It involves merely comparing each of two datums, such as two letters or numbers, and using that comparison to produce a new datum. This is done for every such datum in the message you want to encrypt. The process of performing this comparison is simple and easy, one datum at a time, and (relatively) computationally cheap. A simple operator known as the XOR operator can be used to perform such a comparison. In its simplest form, the XOR operator as applied to binary numbers works something like this:
- First, you need a message. Let’s use the word “short” as our message. Yes, that is a short message.
- Next, you translate that message into a binary representation. Using ASCII encoding to translate the word “short”, you end up with the following string of ones and zeros:
- The last thing you need is a key that is exactly as long as the message. In this case, let’s use this string of ones and zeros as our key:
- Finally, with the XOR operator, you basically perform a simple subtraction. Where the first character in each case is a zero, you see that
0 - 0 = 0. Similarly, the second character in each is a one, and
1 - 1 = 0. Where one character is a one and the other a zero, though, you get either a
-1result. If you take the absolute value of the result, that means that both will give you a
1result. Thus, subtracting and taking the absolute value provides the following:
Of course, there are no ASCII translations for some of those groups of eight binary characters in the resulting string of ones and zeros, so it is difficult to represent the data in a concise form. Using ASCII encoding is well-suited to computer use, but the traditional number-and-letter approach to implementing the one-time pad cipher is much better suited to analog, by-hand translations.
The core algorithm for the one-time pad cipher is obviously incredibly simple. It is only in designing the rest of the software that surrounds this algorithm, and finding the right use case for the cipher, that the real problems of secure cryptographic software development arise. On the other hand, if it absolutely, positively has to be securely encrypted, the one-time pad is the only cipher that is provably unbreakable when used properly — given our current understanding of mathematics.