Format Preserving Encryption¶

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 similarly 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 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 10¹⁵, and then calculate what the checksum is for the new (ciphertext) number. Or, if you were encrypting words in a dictionary, you could rank the words by their lexicographical order, and choose the modulus to be the number of words in the dictionary.

The interfaces for FE1 are defined in the header fpe_fe1.h:

Added in version 2.5.0.

class FPE_FE1¶

FPE_FE1(const BigInt &n, size_t rounds = 5, bool compat_mode = false, std::string mac_algo = "HMAC(SHA-256)")¶

Initialize an FPE operation to encrypt/decrypt integers less than n. It is expected that n is trivially factorable into small integers. Common usage would be n to be a power of 10.

Note that the default parameters to this constructor are incompatible with the fe1_encrypt and fe1_decrypt function originally added in 1.9.17. For compatibility, use 3 rounds and set compat_mode to true.

BigInt encrypt(const BigInt &x, const uint8_t tweak[], size_t tweak_len) const¶: 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. The same tweak value must be used during decryption.

BigInt decrypt(const BigInt &x, const uint8_t tweak[], size_t tweak_len) const¶

Decrypts an FE1 ciphertext. The tweak must be the same as that provided to the encryption function. Returns the plaintext integer.

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

BigInt encrypt(const BigInt &x, uint64_t tweak)¶: Convenience version of encrypt taking an integer tweak.

BigInt decrypt(const BigInt &x, uint64_t tweak)¶: Convenience version of decrypt taking an integer tweak.

There are two functions that handle the entire FE1 encrypt/decrypt operation. These are the original interface to FE1, first added in 1.9.17. However because they do the entire setup cost for each operation, they are significantly slower than the class-based API presented above.

Warning

These functions are hardcoded to use 3 rounds, which may be insufficient depending on the chosen modulus.

BigInt FPE::fe1_encrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector<uint8_t> &tweak)¶: This creates an FPE_FE1 object, sets the key, and encrypts X using the provided tweak.

BigInt FPE::fe1_decrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector<uint8_t> &tweak)¶: This creates an FPE_FE1 object, sets the key, and decrypts X using the provided tweak.

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

/*
* (C) 2014,2015 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include "cli.h"
#include <botan/hex.h>

#if defined(BOTAN_HAS_FPE_FE1) && defined(BOTAN_HAS_PBKDF)

   #include <botan/fpe_fe1.h>
   #include <botan/pbkdf.h>

namespace Botan_CLI {

namespace {

uint8_t luhn_checksum(uint64_t cc_number) {
   uint8_t sum = 0;

   bool alt = false;
   while(cc_number) {
      uint8_t 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(uint64_t cc_number) {
   return (luhn_checksum(cc_number) == 0);
}

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

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

   return 0;
}

uint64_t encrypt_cc_number(uint64_t cc_number, const Botan::SymmetricKey& key, const std::vector<uint8_t>& tweak) {
   const Botan::BigInt n = 1000000000000000;

   const uint64_t cc_ranked = cc_rank(cc_number);

   const Botan::BigInt c = Botan::FPE::fe1_encrypt(n, cc_ranked, key, tweak);

   if(c.bits() > 50) {
      throw Botan::Internal_Error("FPE produced a number too large");
   }

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

uint64_t decrypt_cc_number(uint64_t enc_cc, const Botan::SymmetricKey& key, const std::vector<uint8_t>& tweak) {
   const Botan::BigInt n = 1000000000000000;

   const uint64_t cc_ranked = cc_rank(enc_cc);

   const Botan::BigInt c = Botan::FPE::fe1_decrypt(n, cc_ranked, key, tweak);

   if(c.bits() > 50) {
      throw CLI_Error("FPE produced a number too large");
   }

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

}  // namespace

class CC_Encrypt final : public Command {
   public:
      CC_Encrypt() : Command("cc_encrypt CC passphrase --tweak=") {}

      std::string group() const override { return "misc"; }

      std::string description() const override {
         return "Encrypt the passed valid credit card number using FPE encryption";
      }

      void go() override {
         const uint64_t cc_number = std::stoull(get_arg("CC"));
         const std::vector<uint8_t> tweak = Botan::hex_decode(get_arg("tweak"));
         const std::string pass = get_arg("passphrase");

         auto pbkdf = Botan::PBKDF::create("PBKDF2(SHA-256)");
         if(!pbkdf) {
            throw CLI_Error_Unsupported("PBKDF", "PBKDF2(SHA-256)");
         }

         auto key = Botan::SymmetricKey(pbkdf->pbkdf_iterations(32, pass, tweak.data(), tweak.size(), 100000));

         output() << encrypt_cc_number(cc_number, key, tweak) << "\n";
      }
};

BOTAN_REGISTER_COMMAND("cc_encrypt", CC_Encrypt);

class CC_Decrypt final : public Command {
   public:
      CC_Decrypt() : Command("cc_decrypt CC passphrase --tweak=") {}

      std::string group() const override { return "misc"; }

      std::string description() const override {
         return "Decrypt the passed valid ciphertext credit card number using FPE decryption";
      }

      void go() override {
         const uint64_t cc_number = std::stoull(get_arg("CC"));
         const std::vector<uint8_t> tweak = Botan::hex_decode(get_arg("tweak"));
         const std::string pass = get_arg("passphrase");

         auto pbkdf = Botan::PBKDF::create("PBKDF2(SHA-256)");
         if(!pbkdf) {
            throw CLI_Error_Unsupported("PBKDF", "PBKDF2(SHA-256)");
         }

         auto key = Botan::SymmetricKey(pbkdf->pbkdf_iterations(32, pass, tweak.data(), tweak.size(), 100000));

         output() << decrypt_cc_number(cc_number, key, tweak) << "\n";
      }
};

BOTAN_REGISTER_COMMAND("cc_decrypt", CC_Decrypt);

}  // namespace Botan_CLI

#endif  // FPE && PBKDF

Botan

Format Preserving Encryption¶

Table of Contents

Search