A Response to "Perfect Encryption - Old Style!"
by Phil
I enjoyed Cliff's article "Perfect Encryption - Old Style!" in 28:4; it's great to see someone bringing it back to the old-school pen-and-paper One-Time Pad (OTP) methods of history.
However, the article doesn't cover why/how it is possible for OTP encrypted messages to be truly unbreakable. Suppose I had infinite computing power. Couldn't I figure it out eventually, even if it took a long time? It's not exactly intuitive, so I'd like to try demonstrating how OTP works and why it's unbreakable.
To demonstrate, I'll introduce an OTP-based encryption method that I developed.
It's more complicated than [plaintext + key] in order to give it flexibility: If the key meets the OTP requirements, it is perfectly secure; however, a less secure key can be used and it will still be very difficult to crack, due to the property of diffusion. To achieve this, my particular algorithm employs transposition with fractionation and substitution (in the form of combining the plaintext with key material via modular arithmetic).
For our example, we'll encrypt the following message: MEET AT DAWN with the key 38 62 69 73.
This algorithm converts letters into two-digit number equivalents, diffuses the digits, and then adds a numerical key to each digit to produce the ciphertext. As you follow along, note that this entire process can be completed without a computer at all.
First, we create a numerical alphabet so we can work with our plaintext, which is a string of numbers (the total length of which is divisible by two).
The underscore represents a space (yes, even spaces are encrypted), and the numbers 0-9 are treated as two-digit letters as well.
So, A becomes 01, B becomes 02, Z becomes 26, a space becomes 27, and the numbers 0 to 9 are represented by 28 to 37.
Hence, MEET AT DAWN becomes 13 05 05 20 27 01 20 27 04 01 23 14 - that's our plaintext.
Now that we have a workable plaintext, we can begin with the first step of the two-step procedure: Diffusion.
To do this, we take the plaintext and split it into groups of four-digits, stacked on top of each other to generate a matrix of four columns and ((message length) / 4) rows.
You might be wondering about messages that aren't divisible by four; you'd simply add a space (27) to the end of the message to make it divisible by four.
Our example message is already divisible by four, so we can continue generating the matrix:
To diffuse this plaintext, we will work with the two columns on the left and the two columns on the right separately.
Start with the top-left digit and move down in a zig-zag fashion:
So far we have: 152003
Now, take the remaining numbers from the left-side columns:
Now we have: 152003307242
Continue the same process on the right-side columns, starting at the upper-left digit:
And we get the last half of our message: 000704521211
So, we took our plaintext 13 05 05 20 27 01 20 27 04 01 23 14 and scrambled it into 15 20 03 30 72 42 00 07 04 52 12 11.
Now, we apply our key using modular arithmetic:
MEET AT DAWN (13 05 05 20 27 01 20 27 04 01 23 14) encrypted with 38 62 69 73 yields our ciphertext: 4382-6203-0004-6970-3214-7184
(I like to split the message into groups of four to make it easier to read.)
We can already tell that this particular encrypted message isn't perfectly secure, because the key isn't at least the length of the message. Hence, it repeats itself and makes the message vulnerable to cryptanalysis.
So, how do we achieve OTP security? The guidelines are simple in concept, but very difficult in implementation (hence the reason that OTP systems aren't widely used today - it just isn't practical).
To achieve OTP security, the key must be:
- Totally, truly random (pseudorandom numbers generated by computers do not count as truly random; numbers "randomly" chosen in someone's head or by randomly typing on a keyboard are also not truly random).
- Never ever reused, in whole or in part - the same key must never, ever be reused for any other message.
- As large as (or greater than) the length of the message. Since my algorithm converts characters into two-digit equivalents, the key length requirement would be ((message length) * 2). Hence, our example message MEET AT DAWN would need a key of at least 24 digits.
- And, of course, the key must be kept totally secret.
(Real-life implementations of OTP algorithms have demonstrated one-time pads printed on super-flammable paper for immediate destruction of the key, or very tiny paper that can be easily consumed or otherwise destroyed if necessary. The only limit is the cleverness of the user.) This requirement is arguably the hardest part of successful OTP implementation, as both the sender and receiver need to be able to have the same key for each message; securely sending the pads is very difficult in real life.
Now that we know how to make our message perfectly secure, let's analyze how unbreakable encryption is possible in the face of a theoretical "perfect" cryptanalysis machine: a cracking computer with infinite computing power. Such a machine could simply brute-force keys, and, with infinite power, it would always find the right key. So how could any encrypted message be truly secure?
Let's encrypt MEET AT DAWN again, but we'll use a key that meets our OTP requirements. We need a 24-digit keystream made up of truly random numbers.
Whenever I want some high-entropy random numbers, I go to www.random.org, which generates its random integers using atmospheric noise - a very high-quality source of randomness, to be sure. (For those of you keeping up with the "you don't need a computer" theme, you can get high-quality random numbers from rolling a ten-sided die.)
For our example, we'll use this key: 62 90 73 45 11 25 37 80 63 84 89 98
We complete our zig-zag diffusion method, and then add the key:
MEET AT DAWN encrypted with our random, 24-digit key gives us our ciphertext: 7710-7675-8367-3787-6736-9109
Now let's go back to the controls of our infinite-power cracking machine.
Hark, an encrypted message! Let's crack it!
We feed our ciphertext 7710-7675-8367-3787-6736-9109 into the cracking machine, and we program it to find all plaintexts that form a coherent message.
Soon enough, we see our actual plaintext, MEET AT DAWN on the list of cracked messages, corresponding to the key 629073451125378063848998.
If you think about it, perfect security doesn't necessarily mean the machine couldn't figure out that the actual plaintext is a possible solution.
Shannon security comes into play when we look at the rest of the list of cracked messages: "MEET AT EVE " (with a space on the end) appears with the key 629071451117378040848987.
That key is very similar to our actual key, but the plaintext has the opposite meaning - which key is the correct one? We also find MEET IN BACK with the key 629673451247378066840998; DO NOT MEET with the key 700376333115236460859057; and even FAKE MESSAGE with the key 769569141377327862266099.
With no other information, we have no way of knowing the correct key. OTP's unbreakable nature lies in the sea of keys through which the attacker is forced to swim. This also explains why key security is so vital in successful OTP implementation: It must be truly random (a key with a pattern in it will be easily picked as the most likely valid key); it must never be used again (if our key matches a previous known key, we can safely discard the other solved keys); it must never be revealed to anyone else (obviously, any clues to the correct key reveals our message).
Even though OTP ciphers can achieve unbreakable security in theory, the practical application of such a system has proven to be a challenge.
The security requirements of the key are such that, in practice, an OTP ciphertext may only be as secure as, say, a computer encryption method used to hide the keystream, or the physical security of a safe in which the keys are stored. While the OTP system is theoretically unbreakable, the practical application of OTP encryption opens up vulnerabilities.
For example, let's suppose I'm sending messages encrypted with my cipher to someone via mail. Both sides of communication have notebooks full of perfectly random numbers. The two notebooks are the only existing record of the numbers. As messages are sent back-and-forth, numbers are taken from the notebooks in order as needed and used only once. If I keep my notebook in a desk drawer in my house, then I can't claim that my messages are perfectly secure; cracking my messages would only be as difficult as breaking into my house and taking the notepad. That's just one example of many - OTP keys could be compromised at the origin, in transit, and at the destination.
Furthermore, the physical security of these random pads is just one factor. Authentication is a challenge that isn't addressed by OTP, and the existence of that countless number of decryption keys means that an adversary could easily calculate a key that would decrypt a ciphertext into any message of the same length. Thus, an adversary doesn't need to know the secret key in order to use your own cryptosystem to launch an attack. There are ways to address this, but it only highlights the relative difficulty of successfully implementing OTP communication.
Even if we could remove the implementation problems associated with the physical security of the key material - e.g., both communicating parties are savants who can perfectly memorize the key material, and hence never have it written down - the threat of rubber-hose cryptanalysis means that an inherent risk would still exist, keeping us from that elusive perfect security in practice.
This points to a bigger problem with information security in general: the humans are the weakest link in security, but an information system's need for usability means there will always be a human in the mix. We can't rely on theory alone if we want to secure our information.
Thanks for reading.