An ENIGMA machine at the Computer History Museum and FPE

Enigma 

The Computer History Museum is close to Voltage's headquarters. We're in Cupertino and museum's in nearby Mountain View. On a recent visit to this museum I noticed that they had an ENIGMA cipher machine, the machine that the Germans used to encrypt lots of their military communications in World War II. The Allied cryptographers were eventually able to break the ENIGMA cipher, and this let them decrypt and read lots of German military communications.

Part of the reason that the Alllies were able to do this was due to the way that the ENIGMA cipher was designed so that it would never encrypt a symbol to itself. So a plaintext "A" would never get encrypted to a ciphertext "A," even though you'd expect this to happen about 1 time in 26 (if a 26-letter keyboard was used). The fact that it never did proved very useful in the cryptanalysis of the ENIGMA cipher.

Now skip ahead a few decades and you get to the present day.

Instead of using cipher machines like the ENIGMA, people are commonly using AES to encrypt sensitive information. One way that's getting very popular to do this is by using a format-preserving mode of AES, like the FFX mode that NIST is now considering.

But many people who want to use FPE to encrypt sensitive data also want a version that makes sure that patterns never get encrypted to themselves. So if they're encrypting the last four digits of a credit card number, they want to make sure that the plaintext four digits never get encrypted to the same four ciphertext digits.

From the more theoretical point of view, this seems to make such a format preserving approach non-secure. One definition for the security of a deterministic block cipher is that it's indistinguishable from a random permutation, and ensuring that certain patterns never get mapped to themselves seems to violate this.

On a more practical level, this seems to introduce the same flaw that let the Allies break the ENIGMA back in World War II, so it's probably not a good idea.

A better approach is just to accept the fact that the plaintext and the ciphertext are going to agree by chance a certain fraction of the time. Doing that doesn't intentionally introduce a weakness like forcing the plaintext and ciphertext to never agree does.

Leave a Reply

Your email address will not be published. Required fields are marked *