If you have more than a few bank cards, door-entry keycodes, or other small numeric passwords to remember, it eventually gets to be a hassle. The worst, for me, is a bank card for a business account that I use once in a blue moon. I probably used it eight times in five years, and then they gave me a new card with a new PIN. Sigh.
How would a normal person cope with a proliferation of PINs? They’d write down the numbers on a piece of paper and keep it in their wallet. We all know how that ends, right? A lost wallet and multiple empty bank accounts. How would a hacker handle it? Write each number down on the card itself, but encrypted, naturally, with the only unbreakable encryption scheme there is out there: the one-time pad (OTP).
The OTP is an odd duck among encryption methods. They’re meant to be decrypted in your head, but as long as the secret key remains safe, they’re rock solid. If you’ve ever tried to code up the s-boxes and all that adding, shifting, and mixing that goes on with a normal encryption method, OTPs are refreshingly simple. The tradeoff is a “long” key, but an OTP is absolutely perfect for encrypting your PINs.
The first part of this article appears to be the friendly “life-hack” pablum that you’ll get elsewhere, but don’t despair, it’s also a back-door introduction to the OTP. The second half dives into the one-time pad with some deep crypto intuition, some friendly math, and hopefully a convincing argument that writing down your encrypted PINs is the right thing to do. Along the way, I list the three things you can do wrong when implementing an OTP. (And none of them will shock you!) But in the end, my PIN encryption solution will break one of the three, and remain nonetheless sound. Curious yet? Read on.
The OTP is an odd duck among encryption methods. They’re meant to be decrypted in your head, but as long as the secret key remains safe, they’re rock solid. If you’ve ever tried to code up the s-boxes and all that adding, shifting, and mixing that goes on with a normal encryption method, OTPs are refreshingly simple. The tradeoff is a “long” key, but an OTP is absolutely perfect for encrypting your PINs.
The first part of this article appears to be the friendly “life-hack” pablum that you’ll get elsewhere, but don’t despair, it’s also a back-door introduction to the OTP. The second half dives into the one-time pad with some deep crypto intuition, some friendly math, and hopefully a convincing argument that writing down your encrypted PINs is the right thing to do. Along the way, I list the three things you can do wrong when implementing an OTP. (And none of them will shock you!) But in the end, my PIN encryption solution will break one of the three, and remain nonetheless sound. Curious yet? Read on.
THE PIN SOLUTION
So first the solution to the bank card problem: write your PIN encrypted with a secret that only you know. Instead of needing to remember a four-digit number for each new card, you’ll just need one four-digit number forever. The key is to choose an encryption scheme that’s easy enough to undo so that you won’t look too strange when asked to type the PIN in at the bank teller’s window. This is the classic use of the OTP — an encryption that you can undo in your head.
First, randomly select a secret four-digit number. Then, subtract that number from your PIN and write the result on your card. To get your PIN, when standing in front of the bank teller, simply look down at the card and add the secret number back. The teller will think that you’ve written your PIN on the card. Feel free to feel smug, because you’ve used an unbreakable encryption scheme.
So first the solution to the bank card problem: write your PIN encrypted with a secret that only you know. Instead of needing to remember a four-digit number for each new card, you’ll just need one four-digit number forever. The key is to choose an encryption scheme that’s easy enough to undo so that you won’t look too strange when asked to type the PIN in at the bank teller’s window. This is the classic use of the OTP — an encryption that you can undo in your head.
First, randomly select a secret four-digit number. Then, subtract that number from your PIN and write the result on your card. To get your PIN, when standing in front of the bank teller, simply look down at the card and add the secret number back. The teller will think that you’ve written your PIN on the card. Feel free to feel smug, because you’ve used an unbreakable encryption scheme.
Instead of normal addition and subtraction, with the carrying and borrowing across digits, you will want to use modulo-10 math — adding or subtracting ten from the result any time it gets outside the range 0-9. We’ll talk about why below, but for now, here’s a working example.
Suppose the PIN is 1234 — it has to happen so someone, right? — and my random secret number is 1337, naturally. Let’s encrypt. Subtracting 1 from 1 gives a zero, so I write that down. Subtracting 3 from 2 gives -1, which is where the modulo-10 arithmetic comes in. In this case, -1 turns into 9 by adding ten. 3 – 3 = 0, and 4 – 7 = 7, mod-10. My card now has 0907 written on it. Now let’s decrypt. Looking down at the card, I see a 0 and add 1. 9 + 3 = 12, however, so we’ll need to subtract ten to get 2. (That’s the reason to choose addition for the decryption stage, it’s easy to just drop any leading 1s.) 0 + 3 = 3 and 7 + 7 = 14 -> 4<. I type in 1234, and the money is mine! Once you get the hang of adding your secret number to any other number, digit-wise mod-10, you’ll be surprised how quickly it will work. Try it out and see if you get good at it within ten minutes. |
ONE-TIME PADS
A one-time pad is both the simplest symmetric encryption scheme and also completely unbreakable. It has three crucial features, two of which were demonstrated above, and getting any of them wrong can be catastrophic.
The most important feature of an OTP is that the password needs to be random, and the same length as the text that it encrypts — hence the four-digit secret for the PIN. In an OTP, everything revolves around the secret, which is also its Achilles’ heel. For a four-digit number, keeping a four-digit secret is no problem. But imagine that you want to send gigabytes of encrypted photos of your vacation to a friend. That’s a lot of key material to keep on-hand and secret.
A one-time pad is both the simplest symmetric encryption scheme and also completely unbreakable. It has three crucial features, two of which were demonstrated above, and getting any of them wrong can be catastrophic.
The most important feature of an OTP is that the password needs to be random, and the same length as the text that it encrypts — hence the four-digit secret for the PIN. In an OTP, everything revolves around the secret, which is also its Achilles’ heel. For a four-digit number, keeping a four-digit secret is no problem. But imagine that you want to send gigabytes of encrypted photos of your vacation to a friend. That’s a lot of key material to keep on-hand and secret.
Second, the method of combining the message with the secret has to be similar to the modulo arithmetic, in that the set of encrypted characters and the set of plaintext characters — the PIN in our example — have to map one-to-one. Mod-10 ensures this easily: both are in the range 0-9. Maybe you’re familiar with using the XOR operator on binary data, which is the same thing as either addition or subtraction, mod-2. ( 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 2 -> 0. QED.) You can also use letters and wrap the alphabet around at “z” like the Caesar cipher or ROT13, which is just mapping the alphabet into numbers and doing math mod-26.
Third, and maybe this is a corollary of the first, you shouldn’t re-use the secret in a one-time pad. You’d think that this was obvious, since it’s even in the name of the encryption method, but it’s hard to do in practice. And in fact, my PIN-encryption scheme breaks this rule by using the same secret across multiple keys. We’ll get into that soon.
MESSING UP THE PERFECT ENCRYPTION
Why is a OTP unbreakable? Breaking most encryption schemes often boils down to probability and statistics. For instance, if you encrypt a text with the Caesar cipher above, each letter in the plaintext is mapped to another single letter every time it occurs in the ciphertext. If you know that the original text is in English, where the most commonly used letter is “e”, it’s a good bet that if “q” is the most common letter in the ciphertext, it stands for “e”. That is, we find statistical similarities between the plaintext and the ciphertext, and use them to make a bridge between the two.
Using a secret key that is as long as the plaintext, and randomly chosen, breaks any statistical relationship with the ciphertext. Given a specific ciphertext written down on my card, every PIN from 0000 to 9999 is possible, and if the key was chosen randomly, is equally likely. There is no information about the plaintext in the ciphertext — that’s essentially Claude Shannon’s proof (absolutely classic PDF) in a nutshell. And that’s why an OTP is unbreakable.
Third, and maybe this is a corollary of the first, you shouldn’t re-use the secret in a one-time pad. You’d think that this was obvious, since it’s even in the name of the encryption method, but it’s hard to do in practice. And in fact, my PIN-encryption scheme breaks this rule by using the same secret across multiple keys. We’ll get into that soon.
MESSING UP THE PERFECT ENCRYPTION
Why is a OTP unbreakable? Breaking most encryption schemes often boils down to probability and statistics. For instance, if you encrypt a text with the Caesar cipher above, each letter in the plaintext is mapped to another single letter every time it occurs in the ciphertext. If you know that the original text is in English, where the most commonly used letter is “e”, it’s a good bet that if “q” is the most common letter in the ciphertext, it stands for “e”. That is, we find statistical similarities between the plaintext and the ciphertext, and use them to make a bridge between the two.
Using a secret key that is as long as the plaintext, and randomly chosen, breaks any statistical relationship with the ciphertext. Given a specific ciphertext written down on my card, every PIN from 0000 to 9999 is possible, and if the key was chosen randomly, is equally likely. There is no information about the plaintext in the ciphertext — that’s essentially Claude Shannon’s proof (absolutely classic PDF) in a nutshell. And that’s why an OTP is unbreakable.
This is actually the key to understanding the field of cryptography: it is an attempt to scramble up the information about the plaintext during the encryption process so that even though a shorter key is used, no statistically relevant traces of the plaintext remain. This desire for short keys isn’t just a matter of convenience either: imagine that you and Hackaday had to previously exchange 500 KiB of random data just to download this article and read it. Imagine the length of the WiFi password that you’d have to write down for guests! This is the sense in which the OTP is trivial and uninteresting — it may be unbreakable, but the secrets are just too long for most applications. Real crypto is about finding algorithms that break the statistical relationship with a minimum of key material.
With that in mind, you can screw up an OTP implementation by using a short or non-random password. Imagine using 1 as your password and repeating it as necessary; our ciphertext would read 2345, and the PIN would be guessed on the second try. You also want to use a random password; picking 0000 because it makes the math easy is the only thing worse than the above. (Although, strictly speaking, I’d re-roll if I got 0000, 1111, 9999, 1234, 4321, or similar.) Anyway, don’t use your birthday. Old phone numbers of childhood friends might be acceptable. |
The role of modulo arithmetic is a little more subtle. Whatever function is used, the set of possible characters in the plaintext has to map one-to-one with the ciphertext. Why? Imagine that you used simple addition instead of mod-10 addition. To get the last digit of our PIN ciphertext, we used 4 – 7 = -3 -> 7 and decrypted with 7 + 7 = 14 -> 4. If we wrote down -3 instead, an attacker would know that our last digit couldn’t be greater than 6 because adding 9, the maximum value, gives only 6. We’ve leaked information by having a larger set in the ciphertext than in the plaintext.
And that leaves the last way to mess up: re-using the “one-time” pad. Obvious, right? Wrong.
And that leaves the last way to mess up: re-using the “one-time” pad. Obvious, right? Wrong.
On one hand, reuse is a definite liability. Re-using a password in a very similar encryption scheme broke “Tunny”, an important code during WWII. A 4,000 character encrypted message was sent but not received correctly. The sender re-sent the message, with the same secret but made small changes in the text, using different abbreviations and so on. This gave the Allies enough to break Tunny and reverse engineer the machine that encrypted it. Game over.
Here’s the math that made the Tunny decrypt work, and should convince you to almost never reuse a key. If we encode the messages A and B with the secret key C, and someone overhears both, they can just mod them together to get (A mod C) mod (B mod C) = (A mod B) mod C mod C = A mod B, where mod is the bitwise or number-wise modulo operator that we’re now used to. Since taking the binary modulo is its own reverse, the result is something that’s related to both plaintexts, and independent of the secret key.
From here, comparing smart guesses for A and B and comparing them with the A mod B result can break the code. So if you’re pretty sure that “attack” appears in both texts (crypto types always encrypt “attack at dawn”), then you can try modding “attack” together in different positions until you get a match with A mod B.
A SURPRISE ENDING
But here’s the final twist! We can get away with reusing the secret key across all of our bank cards, even despite the above math. Why? Because the PINs themselves are random. In contrast to the natural-language messages sent during wartime, A mod B is just as random as A mod C if both A and B are random PINs.
So this is how a hacker remembers PINs: by learning a lot about the one-time pad, how to break it, and how it’s nonetheless useful if the message it needs to protect is short. And how, for particular messages, you can even break the rules.
Here’s the math that made the Tunny decrypt work, and should convince you to almost never reuse a key. If we encode the messages A and B with the secret key C, and someone overhears both, they can just mod them together to get (A mod C) mod (B mod C) = (A mod B) mod C mod C = A mod B, where mod is the bitwise or number-wise modulo operator that we’re now used to. Since taking the binary modulo is its own reverse, the result is something that’s related to both plaintexts, and independent of the secret key.
From here, comparing smart guesses for A and B and comparing them with the A mod B result can break the code. So if you’re pretty sure that “attack” appears in both texts (crypto types always encrypt “attack at dawn”), then you can try modding “attack” together in different positions until you get a match with A mod B.
A SURPRISE ENDING
But here’s the final twist! We can get away with reusing the secret key across all of our bank cards, even despite the above math. Why? Because the PINs themselves are random. In contrast to the natural-language messages sent during wartime, A mod B is just as random as A mod C if both A and B are random PINs.
So this is how a hacker remembers PINs: by learning a lot about the one-time pad, how to break it, and how it’s nonetheless useful if the message it needs to protect is short. And how, for particular messages, you can even break the rules.