# Encryption of small messages

Some time ago, I asked how to encrypt small messages like e.g., four decimal digit numbers (banking PINs). I've got my answer, but also a warning like it makes no sense as it's easy to guess: Even having no information at all and bad luck implies 10000 trials only, which is nothing in crypto.

However, at an ATM you have three trials only, and a PIN encryption scheme not leaking any information makes a lot sense to me. What does the theory say?

### Clarification:

I'm looking for something telling apart bad and good system for this encryption.

• A bad system could be "add a constant to the PIN modulo $$10^4$$. The attacker with a single plaintext-ciphertext pair could decrypt any other ciphertext.
• A perfect system would be "generate a permutation table with $$10^4$$ elements using a true RNG and a proper algorithm". Now the attacker with any number of plaintext-ciphertext pairs given an unseen-yet ciphertext knows nothing except that the corresponding plaintext is not in his collection.

You want to talk about format-preserving encryption. One of the main motivations for FPE is the ability to encrypt messages which lie in a short space, with an output which is in the same space.

The ideal encryption model on a space of size $S$ (e.g. $S = 10000$ for four-digit PIN codes) is that the encryption systems implements a permutation chosen randomly and uniformly among the set of $S!$ possible permutations. Or at least that the cipher is indistinguishable from such a randomly chosen permutation.

An extreme security model is then the following: assume that the attacker is given a black box which implements the encryption (and decryption) algorithms. He can ask for the encryption or decryption of the almost complete code book, i.e. $S-2$ requests. The attacker gets to choose the contents of each request, adaptatively. So at that point, the attacker can simulate the complete encryption function, except for two input values: he knows the two inputs (let's call them $p_0$ and $p_1$) and the two corresponding outputs ($s_0$ and $s_1$), but he does not know whether $p_0$ encrypts to $s_0$ or to $s_1$. His goal is to predict the encryption of $p_0$ with probability substantially better than pure luck (i.e. $1/2$).

A commonly quoted solution for FPE is the Thorp shuffle. It is an unbalanced Feistel cipher, with enough rounds to make it secure. The good part of it is that it is possible to prove security while keeping the number of rounds low enough to be practical (say 100 rounds or so). The bad part is that it does not realize the extreme model explained above. You have to relax a bit the model, because a Feistel scheme always implements an even permutation; so if you know all the code book except the encryptions of $p_0$ and $p_1$, then you can decide whether $p_0$ goes to $s_0$ or $s_1$ with 100% success rate, because only one of the two choices leads to an even permutation. However, the relaxation is not a big deal: if you give to the attacker only $S-3$ requests, then you can have the best possible under these conditions (attacker cannot predict the mapping of the three remaining inputs, except that they will have to comply to the "even permutation" rule).

To reach the "ideal" model with $S-2$ requests, you have to do heavier thing, like generating the complete permutation in a big array (this is certainly doable with only 10000 entries; for bigger spaces, memory-conscious solutions exist, but the CPU price is quite high). For a practical solution, use the Thorp shuffle.

For verifying PIN codes, encryption is probably not the right tool anyway. Indeed, as you notice, the space of PIN codes is so small that there must be a locking mechanism somewhere, which blocks the attempt after three wrong tries. You cannot have that from cryptography alone. In fact, you will get locking by using dedicated hardware: either a smart card (the smart card is tamper-resistant and locks itself after three wrong PIN codes) or a remote server (that enforces the locking policy).

FPE is used to realize other features, e.g. serial numbers with verifiable validity: you define an 8-digit number which embeds a 5-digit counter value, and you want to have a tool which can verify whether a given sequence of 8 digits is one of the 100000 sequences that you have issued; but you don't want anybody else to be able to generate random "valid" sequences with success probability higher than 1/1000. Solution is to encode the 5-digit counter as 8 digits by appending three zeros, then encrypting the whole lot with FPE. To verify, decrypt, and see if the three zeros are there.

• How is FPE relevant? I don't see how the question calls for treating a PIN as anything more than an element of a set with no structure. – Gilles 'SO- stop being evil' Oct 17 '13 at 18:41
• That's what FPE is about: encrypted an element from a set of 10000 values into another element of the same set. – Thomas Pornin Oct 17 '13 at 18:56
• I think swap-or-not is a much better practical solution than the Thorp shuffle. $\hspace{1.75 in}$ – user991 Oct 17 '13 at 20:12
• @Thomas Pornin: I didn't say that I wanted a length preserving encryption, but you understood it well. Thanks for the perfect answer. – maaartinus Oct 18 '13 at 12:14

PIN encryption today is performed using two techniques to protect against attack.

First, the PIN is combined with the account number using XOR before 3DES encryption is performed. This ensures the plaintext being encrypted differs between two people with unique accounts but the same PIN.

Next, a protocol called DUKPT is used to create a Derived Unique Key Per Transaction for the 3DES operation. A counter in the PIN pad is used to generate a new key every time a PIN is encrypted. This key is derived from a "super secret" key using an algorithm that prevents computing prior keys given only the knowledge of the current state. (Future keys can always be derived.) The PIN pad generates keys in batches of 21 at a time, then recycles, destroying prior state including the destruction of the previous keys. Implementations must also be certified to destroy their current key state (and render themselves inoperative) in self-defense in many conditions: if the container is opened, if the screen is removed, if the mag stripe read head is tampered with, and once the algorithm has generated one million keys.

• I was actually interested in a length preserving encyption, but I failed to state it, and your answer is interesting, too. Thanks. – maaartinus Oct 18 '13 at 12:15