Unless you’re Grace Owen of Concord, New Hampshire (the woman who’s famous for having the lowest Social Security number of all – 001-01-0001), you probably want to keep your Social Security number private. Sometimes this is out of your control, and you rely on the banks and other businesses that need your Social Security number to treat it carefully so that it’s not exposed to identity thieves. Some of the businesses that have your Social Security number need to keep it around for a long time. If your college uses it as a unique identifier, for example, they need to keep it around for as long as you might need to access your college transcripts. Health care organizations also need to keep medical records for a long time. Banks also do.
Because each of these organizations need to keep your Social Security number for many years, they’re also the ones who will have to deal with the problems of keeping your records compatible with many generations of computing technology. This is a difficult problem, and it’s even more difficult if they want to protect your Social Security number by encrypting it. This is because both the size and the format of the Social Security number changes when it gets encrypted.
Let’s use Ms. Owen’s Social Security number as an example. It might be stored in a database as 001010001, which is nine decimal digits. This might get encrypted to ciphertext that looks like this:
This ciphertext is clearly not just nine decimal digits. It’s much longer and it’s no longer made up of just digits. If you have a computing environment that has been around for many years, there’s a very good chance that this ciphertext will cause a problem with some part of it because it’s expecting nine decimal digits instead of a longer alphanumeric string. One way around this problem is to AES in a way that keeps the format of the original plaintext. If we can do this, we can then encrypt a nine-digit Social Security number so that the ciphertext is also another nine-digit number. Or we can encrypt a sixteen-digit credit card number and get a ciphertext which is also a sixteen-digit number. Either of these will be much easier for legacy environments to handle.
A new mode that’s recently been proposed for AES, the so-called Feistel Finite Set Encryption Mode (FFSEM) does exactly this. You can see the full proposal on the NIST web site. If you’re interested in the details of why FFSEM is secure, you can look at the original paper by John Black and Philip Rogaway. They have a formal proof of why FFSEM is exactly as secure as the cipher that’s used to construct it. So if AES is this underlying cipher, the resulting FFSEM is exactly as secure as AES.
If you use FFSEM, things look much different. We might encrypt Ms. Owen’s Social Security number into the ciphertext 812493994. (Note that the 812 prefix ensures that that’s not a valid Social Security number, so we’re not accidentally giving away sensitive data here.) In this case, it’s very unlikely that any part of a legacy computing environment will have problems handling an encrypted Social Security number because encrypted data will look just like the unencrypted data. So FFSEM will let you protect sensitive information while minimizing the chances of fatal interactions with older systems. If you want to protect sensitive information using encryption but worry that encrypted data will cause problems in your computing envisonment, FFSEM may be just what you need.