Privacy

The enduring cipher: Unbreakable for nearly 100 years

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.

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:

  1. First, you need a message. Let's use the word "short" as our message. Yes, that is a short message.
  2. 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:
    0111001101101000011011110111001001110100
    
  3. 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:
    0110010101101010001110010010011101100100
    
  4. 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 1 or a -1 result. If you take the absolute value of the result, that means that both will give you a 1 result. Thus, subtracting and taking the absolute value provides the following:
    0111001101101000011011110111001001110100
    

    0110010101101010001110010010011101100100

    ----------------------------------------

    0001011000000010010101100101010100010000

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.

About

Chad Perrin is an IT consultant, developer, and freelance professional writer. He holds both Microsoft and CompTIA certifications and is a graduate of two IT industry trade schools.

32 comments
mathew.gauvin
mathew.gauvin

Would it be possible to send an encypted message with a cipher to create new key files from the original key? Nevermind, as I was putting in a theoretical example, I realized I was breaking one of the rules: "Create one-time pads with truly random digits"

Deadly Ernest
Deadly Ernest

With the one time pad you lose all future transmission data is one message is intercepted and never reaches the other end. From that moment on the two sides are completely out of sync. The only way around this is to limit a message to be less than the size of the message possible on any single page, number the pages, and place a page number at the start of the message. Large messages will have to be split between multiple pages and marked as separate messages. This way, you immediately know if a message failed to reach you as the page number for the next message to reach you is NOT the same as that on the top page of the pad. You can also immediately start to safely decipher any future messages that do arrive. For today's use, you can prepare pads to be shared between you and your correspondent on paper and only ever commit the message itself to the electronic realm, if you then use an existing electronic encryption service to further code it using a shared key, the people who crack the first level will not be sure if they actually cracked it as it won't make any sense yet.

Sterling chip Camden
Sterling chip Camden

.. is the generation of the "random" key data to begin with. I don't know that anyone has solved the problem of generating truly random numbers yet.

seanferd
seanferd

And your article really is a good explanation as to why one time pads are impractical for most uses, and difficult to to implement securely in the digital arena. It was a fun read.

apotheon
apotheon

I find it interesting that the strongest known cipher is simple enough that it can be explained -- including a summary of its history, its proper use, the algorithm, and how it compares to other ciphers -- in an article of about 1500 words. Perhaps more exciting is that it's simple enough for me to understand (and explain) it in the first place.

zackers
zackers

In a sense I believe public key encryption does something like that. The actual algorithm for public key encryption is still so compute intensive that the entire message is not encoded with it. What is done instead is a message is encoded via one of several well-known encoding algorithms using a randomly generated key, that (relatively short) key is then encoded via public key encryption (using the public key of the intended recipient), and then the encoded key and the message encoded with that key are sent along together. At the other end the recipient uses his private key to decode the key which then can be used to decode the rest of the message. But in general sending new ciphers encoded with old ciphers buys you little. If you happen to decode the message containing the new cipher you automatically can decode new messages encoded with the new cipher. So basically your security is no better than with the one original cipher.

apotheon
apotheon

Anything that isn't truly random is, at least in theory, reproducible -- which introduces a vulnerability into the system. Yeah, you don't want to violate the "truly random" rule. That'd sorta make the one-time pad a pointless exercise in making extra work for yourself.

apotheon
apotheon

I "missed" several, actually. I decided I needed to stop writing at some point, so I stopped at five problems with one-time pads because it was a nice round number. If I went up to ten, that would be an entire article in itself and, frankly, my articles often get a little too long as it is. I had to stop some time. I stopped when I did. I'm glad you decided to contribute to discussion by mentioning something that occurred to you as a problem, though. It shows you're thinking, and that you want to share what you know. As for the rest . . . When dealing with a digital implementation, the only way to be sure that your encryption and decryption process is free of compromise that would allow someone else to listen in is to maintain two systems separate from what you use for communication: one where you only allow data in (never out) with the possible exception of a plaintext copy of what you've decrypted, and another where you only allow data out (never in) with the possible exception of a plaintext copy of something you want to encrypt. In the case of the in-only, the one exception (getting your decrypted data out of it) should never produce anything you're planning to put into another system that isn't isolated from the world, because otherwise what comes out might conceivably carry data secreted away in it by something that slipped in with an encrypted message. In the case of the out-only, the exception (getting your plaintext data into it so you can encrypt it) should never come from a source that might have somehow "infected" it. If you observe that security discipline, all you have to worry about is stuff like physical security and Van Eck phreaking. If you don't observe that security discipline, and try to protect your one-time pads and the data encrypted with those one-time pads with additional (weaker) encryption, you might as well just use the weaker cipher in the first place and skip the one-time pad.

Demo_Dog
Demo_Dog

I don't know that a one time pad depends on truly random numbers. A pseudo-random generator such as concatenating the n-th bit of the mouse cursor while moving it about the screen for a few minutes ought to suffice. just never use the same key twice. ( read "Cryptonomicon" for a really good yarn with lots of crypto and Japanese gold )

apotheon
apotheon

Actually, we do get random data (not provably random, but certainly random as far as anyone knows) from stars. There are devices that can detect cosmic radiation and, based on that input, generate noise output. That output, when captured by the computer, can be hashed to format it for easy digital digestion, and the hash can then be used as a seed for a PRNG to cram the randomness into a useful range for generating encryption keys. . . . or you could just roll real, physical, analog meatspace dice, I suppose. That's cheaper in terms of equipment costs, but takes a lot longer.

santeewelding
santeewelding

Use the arrangement of stars at night, and let it be known that is what is being used. If the pattern is cracked, let them have the data. We get the secret of the universe.

apotheon
apotheon

I'm glad you liked it. A lot of what goes into cryptography is easier to understand than one might expect -- but also much harder to get right than one might expect.

BaruchAtta
BaruchAtta

I saw a movie once where the spy would use a pre-arranged page of the newspaper (want ads maybe) as a one-time pad. It was a simple ROT code, using the next letter of the pad to determine the rotation. For example, if the next letter on the pad was "e" then the text letter would be rotated 5 places. Each message then would also contain the source of the next pad. Unless the enemy knew the source of the one time pad, it would be impossible to decrypt. That was in WWII. Would it be possible or practical to attempt to use every publication as test key to attempt to decrypt?

nation
nation

The PBS series NOVA had a great report on the use of one-time pad cipher by the Russians for 40 years, starting in the early '40s. A slight error in implementation allowed some of the traffic to be decrypted (with an effort that must have been mind-boggling and mind-numbing). See http://www.pbs.org/wgbh/nova/venona/ Also look up Venona in Wikipedia. As Mr. Perrin points out, the advantage is that, used correctly, it is mathematically provably unbreakable. The disadvantage is that it is *very* difficult to use correctly. (Oops, sorry, this was not intended as a direct comment to zackers only, but to the main thread.)

netwiseit
netwiseit

I'm a newbie to this so please bear with me but if you are to create a message that utilises a random key then doesn't the 'Randomisation' become obselete. The reason I ask this is because the receipient needs some form of clue / key in order to make sense out of the chaos code they've been presented with - so does that mean that within the message they've been sent they will need some key to allow them to reconstruct the original message, therefore eliminating randomness? If this is the case how can the receipent be sure that he's going to receive the same message that the sender intended? Surely both locations can't produce the same 'Random algorithm' at the same time to enable one location to decode the message sent from the other location? p.s. Please take into account I'm just a newbie :)

Deadly Ernest
Deadly Ernest

real show stopper for the communications system. I've always felt that the best encryption method was a multiple system - and I don't mean to use another encryption to re-encrypt what you've encrypted. If you use three encryption codes with each one being applied to every third character, any one character will have three different meanings, depending upon where it falls in the message. Thus, even if they break one cipher, the message won't make sense as it won't show a readable answer because they haven't broken the other two ciphers. To get a readable message, they need to break all three ciphers and apply them in the correct order. You can start the message with a semi-clear code that tells the order, say you break all the text up into eight character groups - so the first group will read something like 12056078 - which decodes to use cipher 12 on the first character, cipher 56 on the second character, and cipher 78 on the third character. The ciphers you use will, naturally, include a symbol that means end of word, and another for a full stop - they will be placed where required and coded as part of the text in the same manner. If you also incorporate the one time pad into such a system, using three pads, even if they get a copy of the message, it should stay unbreakable, or so hard to break they'll never work it out in time - unless they get hold of the pad by capturing you person - in which case all bets are off. I still feel the only sure and absolutely secure message transmission system that they can't decode is the old split the message and send it by multiple couriers, and all parts have to be safely received before it can be reconstituted. This does mean the loss or any one part means the whole message is lost, but it also means the enemy can't work it out if you get one part through or one of the couriers manages to destroy his part at time of capture. Naturally, this can be a bit hard on the couriers. Of course, the only way to really ensure something is kept absolutely secret is to totally restrict the information to be memorised by just one person.

apotheon
apotheon

Actually, you're basically using "truly random" numbers even the way you described using a PRNG -- because you're only using the PRNG to apply a transformation to actually random data, rather than using the PRNG to generate your "random" numbers in the first place. You introduce entropy to the system when you wave the mouse around to feed seeds into the PRNG. As for Cryptonomicon -- yes, it's an excellent book, with lots of subject matter to keep the crypto-geeks happy. I strongly recommend it.

apotheon
apotheon

For actually important purposes, I'd prefer to use a source for random numbers that is entirely under my own control. That way, nobody else would have a record of the particular sequence of random numbers I'm using. After all, the problems of nonrandom numbers are reproducibility and patterns, and protecting oneself against reproducibility doesn't do much good if others have access to the exact set of numbers that were produced the first time.

seanferd
seanferd

Bad example: Like claiming a simple XOR is somehow highly secure encryption? If I recall, you had some comments on an encryption scheme (for hard drives?) something like that. I can't remember the product. A more obvious way to get it wrong, though.

apotheon
apotheon

The random key is generated in advance, and one copy each given to the eventual sender of a message and the eventual recipient of the message. Then, when there's a message to send, the sender uses the key to encrypt it, then sends it; when the recipient receives the encrypted message, the recipient's copy of the key can be used to decrypt the message.

Deadly Ernest
Deadly Ernest

just that a split message was more secure than a single message - sorry if I didn't make that clear enough. Anyway, if they get all your couriers, the jig is up anyway as your network is probably all gone and you're in smelly brown stuff up to the neck .

mathew.gauvin
mathew.gauvin

What if your couriers are intercepted? As long as just one piece remains uncompromised, the message is secure, but if all of the couriers are intercepted, then the jig is up. Splitting really only works if each party has a stake in decrypting/protecting the message.

Deadly Ernest
Deadly Ernest

not smoothing out the inside properly. Then glaze and fire said cup, and you got some major irregularities - it's damned hard to get that inside smooth by hand, until AFTER you gate many, many hours of practice at it.

apotheon
apotheon

. . . if cosmic radiation is deterministic, we're pretty well screwed for sources of randomness anyway. Of course, at that point, we're done -- because all outcomes are set in stone. It's time to lay down and die. If you argue otherwise, it's only because you're programmed to do so. Ultimately, though, right or wrong, there's not much point in worrying about it. Pretend we know it's non-deterministic, and move on.

santeewelding
santeewelding

How are the bumps arranged -- by a previous shake of the cup without bumps?

Deadly Ernest
Deadly Ernest

bumps, shake for a variable amount of time, and roll. for a data set of 6 x 6 items, that will get you a very good randomisation that's going to be next to impossible to analyse.

apotheon
apotheon

Of course, if you sample whatever with a known technology or device that may introduce its own patterned noise, this too would be susceptible to some analysis. This is why you need a filter that doesn't regularize the random data. There are deterministic filters that do not, at least in theory, compromise randomness when they transform data from something unusable to something usable. If there weren't, it would be unreasonably difficult to generate random keys most of the time anyway. After all, cosmic radiation (for instance) doesn't come preformatted as neatly readable numbers.

seanferd
seanferd

That is just an example. My idea was that you would sample some natural random occurrence. Of course, if you sample whatever with a known technology or device that may introduce its own patterned noise, this too would be susceptible to some analysis.

apotheon
apotheon

Like claiming a simple XOR is somehow highly secure encryption? Coincidentally, I just finished writing an article about that today, complete with a (very) little bit of source code for a naive implementation of an XOR stream cipher. I hope my readers like this stuff, because I love it, and rather enjoy writing about it. If I recall, you had some comments on an encryption scheme (for hard drives?) something like that. I can't remember the product. I'm afraid I don't recall those comments off the top of my head, but it wouldn't surprise me if I did have something to say about something like that.

Editor's Picks