Cryptography for Dummies — Part 4: The One-Time Pad

Check out part 3 here.

So far in this series, we’ve covered a few key concepts as they relate to cryptography:

1. Cryptography is about being able to send secret messages
2. It uses mathematical operations or patterns to scramble messages
3. The more random a pattern, the more difficult it becomes for code breakers decode the message, making it more secure
4. The more random a pattern, the more difficult it becomes to effectively share the message, making it less scalable

As we’ve said before, the complexity in cryptography comes out of this tug-of-war between scalability and security. As you become more familiar with blockchains, you’ll find that this central problem persists there as well, which is why we’re spending a good amount of time trying to understand it. How can we maintain maximum security and maximum scalability, when increasing security reduces scalability, and vice versa?

To reiterate, security in this context means how difficult it is for a code breaker to decode a message, and scalability means how easily a secret message and its key can be shared with the intended parties. The perfect cipher is one that has an easily shareable key, yet does not leak any information that code breakers can use against it.

When we think about ciphers, we often overlook the importance of scalability. Theoretically speaking, a perfect cipher is one that is unbreakable. But what good is an unbreakable cipher if no one can use it? At the end of the day, cryptography, or blockchains, or any technology for that matter, has to be practical enough to be used by real people.

We can see this dilemma in action when we look at the One-Time Pad, a cipher designed in the 19th century that was able to achieve perfect secrecy. To this day, it is the most secure cipher in existence, beating out the algorithms used in modern cryptography, and yet it is largely obsolete because it’s too difficult to use, and too difficult to share.

The One-Time Pad implements the perfect cipher we described in our last post. If you remember, we said that the perfect cipher which leaks no information about its pattern to code breakers uses a never-ending sequence of shifts as its key. The One-Time Pad achieves this by generating a random number-sequence key that is exactly as long as the message being sent. This ensures that the letter-shifts never fall into a repetitive pattern that can be reverse-engineered, and that the resulting ciphertext has a uniform frequency distribution.

These two properties allow the One-Time Pad to attain perfect secrecy. This means that any ciphertext created from a One-Time Pad reveals absolutely no information about the original message, so that even if code breakers had infinite time and resources to try all possible keys, they still wouldn’t be able to decrypt the message.

Let’s look at an example to drive this point home. Imagine you want to send the secret message “HELLO” to your friend, using the One-Time Pad.

Remember that just like the previous ciphers we’ve looked at, the One-Time Pad takes a number sequence and shifts the each letter of the message forward by the numbers in the sequence. So if the key sequence was 1–2–3–4–5, you would move the letter H forward, by 1, the letter E forward by 2 etc., to get the resulting message “IGOPT”.

You roll a 26-sided die five times to generate a random key-sequence that’s as long as your message. We use 26 because the English alphabet has 26 letters; any number greater than 26 will just loop back to the beginning of the alphabet. For example, if you generate the random number 27, you will move through 26 positions in the alphabet to get back to the same letter, and then add 1 to shift the letter forward by 1 position. Therefore, generating any number greater than 26 will translate into the expression 26+x, where x is the actual number of shifts needed.

So you roll the 26-sided die to generate the following random sequence: 23–12–2–10–11. You share this key securely with your friend, and use it to encrypt your message:

Your friend can use the key you’ve provided to easily decrypt this message. For a code breaker, however, things aren’t so simple. The only thing a code breaker knows about your message is that it’s 5 letters long. Because you use a different shift for every letter, there are no patterns or hints the code breaker can use to guess the correct key.

Their only option is to use trial-and-error to test every five-number combination between 1 and 26, which, in itself, is a practically impossible feat. Each number in our key-sequence can be between 1 and 26. This means that there are 26 possibilities for the first number, 26 possibilities for the second number, and so on. To find the total number of possibilities for our key-sequence, we would have to multiply 26 by itself 5 times. That is nearly 12 million combinations we’d have to try!

To give you a sense of what that means, if you wrote each possible combination on a blank sheet of paper and stacked the papers on top of each other, the stack of papers would be over 1 kilometer high.

Let’s imagine, however, that our code breaker could test 12 million combinations in a timely manner. What would happen then?

At some point, the code breaker would arrive at the combination 23–12–2–10–11, and would decrypt the ciphertext to reveal the message “HELLO”. But that would mean that he’s broken our cipher, right?

Not quite, because before the code breaker can get too happy about his accomplishment, he arrives at another possible combination, 19–16–20–17–8, that translates into an equally valid message:

The point here is that since the only thing we know about the message we’re trying to decode is that it’s five letters long, the original text is equally likely to be any five-letter word. Our ciphertext can mix with many different key combinations to produce different words. In other words, we don’t have enough information about this message to be able to reach a reasonable conclusion.

This is what we mean by perfect secrecy. A cipher that maintains perfect secrecy is not only practically impossible to break, but theoretically impossible to break as well. Even with infinite time and infinite computational power, a code breaker would end up with a long list of five-letter words, any one of which could be the original message.

Attaining perfect secrecy is the goal of any cipher. But, as we said earlier, ciphers are meant to allow people to share messages secretly and efficiently, and as secure as the One-Time Pad was, it was highly impractical to use. As you can imagine, sharing a unique key securely with every message that is exactly as long as that message defeats the purpose of the cipher; if you’re going to go through the trouble of sharing a key that’s just as long as your message securely, you might as well just use that method to send your message.

One way implementations of the One-Time-Pad got around this issue was by creating notepads where each page had a different random sequence, and distributing that in person. Each sequence was very long, to ensure that messages being sent were always shorter than the key-sequence. The parties would also predefine a system for using the keys, so everyone knew when each key-sequence was being used. This could be a simple date system, where each page is dated, and you know that on November 27th, for example, everyone uses page 50 etc. Or it could be a simpler system, where you use the first page for your first message, and rip it off and destroy it, and the second page for the second message etc.

Despite these workarounds, however, the One-Time Pad still proved to be largely impractical, to the point where modern cryptography has opted to sacrifice perfect secrecy for usability and scalability. This means that modern ciphers are only practically unbreakable, so that with infinite computing power and infinite time, they can be broken.

This is one of the main concerns when it comes to the cryptographic security of blockchains. With things like quantum computing on the horizon, which will drastically increase computation speed, operations that were once infeasible, may become practical enough to solve. As far as cryptography is concerned, this means that testing every possible key for a cipher, or in other words, conducting a brute force attack, no longer requires infinite amounts of time. Operations that would have taken decades to complete, can be done in as little as a few hours or days.

That’s a scary thought, and it’s enough to make us reconsider theoretically secure algorithms. What is the difference between true randomness and the pseudo-randomness of our modern ciphers? What is it that makes pseudo-random ciphers ultimately breakable? And most importantly, is it possible at all for a cipher to achieve perfect secrecy without losing its usability? We’ll explore these questions and more in our next post, as we dive deeper into the mechanics of randomness and the central role it plays in cryptography.