Shannon Ciphers and Perfect Security

In: Technology

Cyphers are a way of turning a regular message into an encoded one, then back to the original form. It involves some secret, which is used in the encoding and decoding step. That secret is called a key.

The simplest cypher is the Caesar Cypher, where you can imagine A = 1, B = 2, C = 3, etc. You pick a number between 1 and 26 and add that number to each letter, wrapping around from Z to A (e.g. Y + 4 is C). With this scheme you can turn a message into its coded form and it will look unintelligible, but then by going through and subtracting that number from each letter you get back to the original.

This cypher is good enough for kids playing spy, but it quickly fails when put up against casual analysis–you only have 26 possible keys to check and with one of those keys you’ll find the message is plainly readable.

You could improve this cypher by choosing two numbers, Add the first number to all the even digits and the other number to all the odd ones. This means that instead of having 26 combinations to check you now have to check 26*26 = 676 combinations. This is much stronger, though of course a computer could crack this code in an instant.

You can keep going from there. Perhaps you get three or four or a dozen or a hundred numbers, cycling through them for every third, fourth, twelfth, or hundredth number. As you add more numbers to your cycle the number of combinations you have to check grows at an incredible rate. With 12 numbers there are about 10^17 combinations to check–enough that even a modern computer will struggle. With 100 numbers there are so many possibilities that it is physically impossible for a computer to go through them all.

However, even the 100-number key is insecure for a longer message because an analyst can look at what letters are most common in the English language and see what letter is most common in every 100th character. They can compare those two distributions and find that only one number makes the distributions line up.

That approach gets weaker as the key gets bigger relative to the message, since each number in the key gets used fewer and fewer times. The analyst is able to break the key by looking at patterns and abusing the fact that each digit of the key is used multiple times. The fewer times each number from the key gets used the less they have to go on, and eventually you get the key so large that each number in the key is used only once.

At this point there is no information to be gleaned from a single character from the encoded text–if the encoded character is an F we don’t know if that’s because the original character was an A and the number was 5, the original was B and the number was 4, etc for all 26 possibilities. You can’t look to other uses of this same digit from the key to get more information, so you’re just stuck there. Someone who has just the encoded message has no way of turning it back into the original message.

That encryption method is known as a “one-time pad.” It has the practical challenge that the key is as big as the message and the key itself must be transmitted securely, but sometimes this setup is practical (e.g. a spy in the field could be sent with a code book that contains the very long key, then messages could be sent to them encoded according to that key).

The one-time pad was invented a few times in the late 19th and early 20th century (eventually it stayed invented as cryptography became a proper field of study). Claude Shannon is credited with formalizing the notion of perfect secrecy and proving that a one-time pad is perfectly secure. He also proved that all encryption methods that offer this kind of guarantee face the same struggles regarding the size of the key.

Note that “perfect security” doesn’t mean that there’s no way to try to get at the underlying data. For example, a one-time pad reveals how large the message is. I recall hearing of a system where an internet-based phone would compress the audio before sending it over an encrypted link (it wasn’t a link that used perfect security, but that doesn’t matter here). It turns out that some sounds compress much better than others, so a cryptographer was able to look at just the data transmission speeds and figure out the words that were being said from there. This is known as a “side channel attack” because it doesn’t attack the cryptography directly, instead looking for data elsewhere. Even perfectly secure cryptosystems like a one-time pad are vulnerable to this kind of attack.

A Shannon Cipher is one where the message (the “plaintext”) is encrypted with a secret key, and the same secret key is used to decrypt the encrypted file and turn it back into plaintext. Obviously, you must have a way for the sender and receiver to securely share that secret key. Anyone who has the secret key can encrypt/decrypt messages, assuming that they know the process used.

“Perfect Security” refers to an encrypted message that provides no information about the original plaintext unless you have the secret key.