Cycle walking

Consider the following problem statement. We have a legacy database whose schema cannot be changed, and it is currently storing unencrypted card numbers. We want to encrypt the card numbers without changing the schema. Clearly, we need to come up with a mode of encryption that maps card numbers to other card numbers in a way that is computationally indistinguishable from true randomness. One such way to achieve this is through the use of a small-width secure pseudorandom permutation (SPRP) and cycle walking.

Pseudorandom permutations

Because we need a mapping that is format-preserving, pseudorandom permutations are top of mind. Unfortunately, plugging a card number directly into a standard-issue block cipher such as AES is not helpful. This is because the block size is far too big: there is a high probability that the output will not be a valid card number. Instead, we must craft a block cipher that has just the right width.

There are 1016 possible card numbers. Because we like to design modes that operate in base 2, we need to calculate the number of bits we need to represent any card number. We simply need to solve the inequality 2b ≥ 1016 for integer b. Taking the integer constraint into account, we obtain b = 54. Therefore, we need to use a 54-bit pseudorandom permutation. One way of achieving this is by constructing a Feistel network with a sufficient number of rounds.

Unfortunately, it is not as simple as plugging the plaintext card number into the 54-bit SPRP. The problem is that occasionally, the SPRP will map the input to a card number that is not valid, because 254 > 1016. Thankfully, there is an elegant solution: if the encryption operation outputs an out-of-range card number, we simply take the invalid output and encrypt it. We iterate this process until we land on a valid number. This is known as cycle walking. In the example visualized below, the entire area within the square represents the domain and range of the 54-bit SPRP. The white portion represents the space of all valid card numbers, and the gray portion represents out-of-range card numbers.

Cycle walking

Decryption follows the same process but in reverse order: we start at C and stop when we arrive at a valid P. The probability of having to perform > i steps decays approximately geometrically:

Steps Probability
> 0 100%
> 1 44.5%
> 2 19.8%
> 3 8.8%
> 4 3.9%
> 5 1.7%
> 6 0.8%
> 7 0.3%