More ancient format-preserving encryption

In addition to the way of doing format-preserving encryption that FIPS 74 describes, there's another way that has been around for quite a while. This the technique that Michael Brightwell and Harry Smith describe in their paper "Using Datatype-Preserving Encryption to Enhance Data Warehouse Security," which they originally presented at the 1997 National Information Systems Security Conference. You can get their presentation here and a more carefully written paper here. Here's how their scheme works (ignoring an initial permutation).

Suppose that we want to encrypt a sequence of digits i₁, i₂, …, i_n in a way that maps each digit to another digit. We use the DES algorithm with a key K to do this. We first hash K to get the bytes A = (a₁,…,a₈) and use this value as shown in this diagram to produce the ciphertext z₁ from the plaintext i₁. In this diagram, the addition is done modulo 10 to ensure that we get another digit when we encrypt.

 

To get the next ciphertext digit, we shift the inputs into the DES encryption function, shifting in the plaintext i₁ as we do this. This diagram shows how to get the ciphertext z₂ from the plaintext input i₂.

   

To get the next ciphertext digit, we again shift the input into the DES encryption function, this time shifting in i₂. Here's how this step works when we get  the ciphertext z₃ from the plaintext i₃.

 

We repeat this process as many times as we need to encrypt the entire sequence of plaintext digits, shifting in a new plaintext digit at each step.

Brightwell and Smith claim that their scheme is as secure as DES, but that's probably not really true. This is because adding the output of a DES encryption to a plaintext digit and then reducing the sum modulo 10 produces a bias in the ciphertext. If we're adding a random number from 0 through 255 and reducing the sum modulo 10, we'll be adding each of 0 through 5 26/256 of the time, and adding each of 6 through 9 only 25/256 of the time. Because of this, the ciphertext that we get from encrypting the digit 0 will have a different distribution than that that we get from encrypting a 1, for example.  This means that it's easy to distinguish encryption using the Brightwell-Smith scheme from a random permutation so the scheme doesn't really meet the definition of a secure one, at least by today's standards. It's still interesting, however, at least from a historical perspective.