100% Unbreakable Encryption is Achievable!

There were two common cryptography misconceptions that we unlearned in school, and this post is about the first one we learned about. (And Cryptonomicon helped with this one too.)

We hear a lot about how “strong” encryption is. That our files would take bazillion years to decrypt via brute force or that our Bitcoin account would take the fastest supercomputer a gajillion years to break into. But what about an encryption scheme that an adversary could never, ever brute force? Sounds pretty useful, doesn’t it?

You may be surprised to learn that yes, we can do it! And we’ve been doing perfectly unbreakable encryption in the military since before WWII.

Let’s say we have a plain-text message:

A T T A C K A T O N E O C L O C K

And we encrypted it with a random key that’s the same length as the message, where each character of the key is just added to the corresponding plain-text letter of the English alphabet (A = 0, so B + C = D, Y + B = Z and so on…).

plaintext  A T T A C K A T O N E O C L O C K
key        X R Y B B A W V U E W Y R C M X T
ciphertext X K R B D K W O I R A M T N A Z D

There are two insights that can help you see why this is unbreakable. The first is that every letter is encrypted independently with its own letter from the key. The encryption of each letter is totally unrelated to the encryption of any other letter, and by changing one letter in the key, you only change one letter in the ciphertext.

Building on that, the more important insight is that any message of the same length can be produced given the appropriate key. If we took the same ciphertext that we got above and used a different key, we could decrypt it as a completely different, yet valid message:

ciphertext X K R B D K W O I R A M T N A Z D
key        U T J O T M I U R D F M I U S M Z
plaintext  D R I N K Y O U R O V A L T I N E

You could try every single possible key, but the problem is not how fast you can try the keys, rather that you can’t tell if you’ve found the answer or not!

This method of encryption is called the One-Time Pad, not to be confused with the One-Time Passwords that your bank sends you. It was used by militaries and espionage agencies starting sometime before WWII and worked roughly like this:

• Headquarters would produce pages and pages of random letters, and would make two copies of each page. These pages would be assembled into one-time pads.
• One copy was kept at HQ, while the other copy was given to whichever unit or asset needed to communicate securely.
• When a message was sent, HQ would encrypt the message with a fresh page from their one-time pad, send the message, and destroy the page.
• When the remote unit received the message, they would decrypt the message using the corresponding page from their copy of the one-time pad and then destroy the OTP page that they used. This works the same in the other direction as well.

Why don’t we use this more?

There are some obvious drawbacks here, primarily that you needed as much key as you had message. If you wanted to send 1 million characters of encrypted data, you’d need 1 million characters of one-time pad (a huge amount back in the day!).

Once you ran out, you had to somehow securely get more from HQ. If HQ could securely send you more one-time pads, why wouldn’t they just securely send you the message? Getting more one-time pads wasn’t something you could do after you were already in the field and thus, the OTP was used sparingly.

And if you ever made the mistake of reusing any part of your one-time pad, making it a two-time pad, you’d instantly lose your unbreakability guarantee. If the adversary intercepted different messages that used the same two-time pad, they could figure out what key produced valid plaintexts out of both ciphertexts, like the USA did to Soviet communications.

Try it out yourself

You can find the Python code used to generate the above examples here: https://gist.github.com/erjiang/5ba01d43922fdf8c62818ce23e2e2b86