Botan

Format Preserving Encryption

New in version 1.9.17.

Format preserving encryption (FPE) refers to a set of techniques for encrypting data such that the ciphertext has the same format as the plaintext. For instance, you can use FPE to encrypt credit card numbers with valid checksums such that the ciphertext is also an credit card number with a valid checksum, or similiarly for bank account numbers, US Social Security numbers, or even more general mappings like English words onto other English words.

The scheme currently implemented in botan is called FE1, and described in the paper Format Preserving Encryption by Mihir Bellare, Thomas Ristenpart, Phillip Rogaway, and Till Stegers. FPE is an area of ongoing standardization and it is likely that other schemes will be included in the future.

To use FE1, use these functions, from fpe_fe1.h:

BigInt FPE::fe1_encrypt(const BigInt& n, const BigInt& X, const SymmetricKey& key, const std::vector<byte>& tweak)

Encrypts the value X modulo the value n using the key and tweak specified. Returns an integer less than n. The tweak is a value that does not need to be secret that parameterizes the encryption function. For instance, if you were encrypting a database column with a single key, you could use a per-row-unique integer index value as the tweak.

To encrypt an arbitrary value using FE1, you need to use a ranking method. Basically, the idea is to assign an integer to every value you might encrypt. For instance, a 16 digit credit card number consists of a 15 digit code plus a 1 digit checksum. So to encrypt a credit card number, you first remove the checksum, encrypt the 15 digit value modulo 1015, and then calculate what the checksum is for the new (ciphertext) number.

BigInt FPE::fe1_decrypt(const BigInt& n, const BigInt& X, const SymmetricKey& key, const std::vector<byte>& tweak)

Decrypts an FE1 ciphertext produced by fe1_encrypt; the n, key and tweak should be the same as that provided to the encryption function. Returns the plaintext.

Note that there is not any implicit authentication or checking of data, so if you provide an incorrect key or tweak the result is simply a random integer.

This example encrypts a credit card number with a valid Luhn checksum to another number with the same format, including a correct checksum.

#include "apps.h"

#if defined(BOTAN_HAS_FPE_FE1)
#include <botan/fpe_fe1.h>
#include <botan/sha160.h>

using namespace Botan;

#include <iostream>
#include <stdexcept>

namespace {

byte luhn_checksum(u64bit cc_number)
   {
   byte sum = 0;

   bool alt = false;
   while(cc_number)
      {
      byte digit = cc_number % 10;
      if(alt)
         {
         digit *= 2;
         if(digit > 9)
            digit -= 9;
         }

      sum += digit;

      cc_number /= 10;
      alt = !alt;
      }

   return (sum % 10);
   }

bool luhn_check(u64bit cc_number)
   {
   return (luhn_checksum(cc_number) == 0);
   }

u64bit cc_rank(u64bit cc_number)
   {
   // Remove Luhn checksum
   return cc_number / 10;
   }

u64bit cc_derank(u64bit cc_number)
   {
   for(u32bit i = 0; i != 10; ++i)
      if(luhn_check(cc_number * 10 + i))
         return (cc_number * 10 + i);
   return 0;
   }

/*
* Use the SHA-1 hash of the account name or ID as a tweak
*/
std::vector<byte> sha1(const std::string& acct_name)
   {
   SHA_160 hash;
   hash.update(acct_name);
   return unlock(hash.final());
   }

u64bit encrypt_cc_number(u64bit cc_number,
                         const SymmetricKey& key,
                         const std::string& acct_name)
   {
   BigInt n = 1000000000000000;

   u64bit cc_ranked = cc_rank(cc_number);

   BigInt c = FPE::fe1_encrypt(n, cc_ranked, key, sha1(acct_name));

   if(c.bits() > 50)
      throw std::runtime_error("FPE produced a number too large");

   u64bit enc_cc = 0;
   for(u32bit i = 0; i != 7; ++i)
      enc_cc = (enc_cc << 8) | c.byte_at(6-i);
   return cc_derank(enc_cc);
   }

u64bit decrypt_cc_number(u64bit enc_cc,
                         const SymmetricKey& key,
                         const std::string& acct_name)
   {
   BigInt n = 1000000000000000;

   u64bit cc_ranked = cc_rank(enc_cc);

   BigInt c = FPE::fe1_decrypt(n, cc_ranked, key, sha1(acct_name));

   if(c.bits() > 50)
      throw std::runtime_error("FPE produced a number too large");

   u64bit dec_cc = 0;
   for(u32bit i = 0; i != 7; ++i)
      dec_cc = (dec_cc << 8) | c.byte_at(6-i);
   return cc_derank(dec_cc);
   }

}

int fpe_main(int argc, char* argv[])
   {
   if(argc != 4)
      {
      std::cout << "Usage: " << argv[0] << " cc-number acct-name passwd\n";
      return 1;
      }

   u64bit cc_number = atoll(argv[1]);
   std::string acct_name = argv[2];
   std::string passwd = argv[3];

   std::cout << "Input was: " << cc_number << ' '
             << luhn_check(cc_number) << '\n';

   /*
   * In practice something like PBKDF2 with a salt and high iteration
   * count would be a good idea.
   */
   SymmetricKey key(sha1(passwd));

   u64bit enc_cc = encrypt_cc_number(cc_number, key, acct_name);

   std::cout << "Encrypted: " << enc_cc
             << ' ' << luhn_check(enc_cc) << '\n';

   u64bit dec_cc = decrypt_cc_number(enc_cc, key, acct_name);

   std::cout << "Decrypted: " << dec_cc
             << ' ' << luhn_check(dec_cc) << '\n';

   if(dec_cc != cc_number)
      {
      std::cout << "Something went wrong :( Bad CC checksum?\n";
      return 2;
      }

   return 0;
   }
#else
UNIMPLEMENTED(fpe_main, "FPE");
#endif