From 162b5ca3c330af4b09823f286cd18cc21d3c2ac4 Mon Sep 17 00:00:00 2001 From: lloyd Date: Wed, 20 Apr 2011 19:10:32 +0000 Subject: It's likely that other FPE methods will be desirable once they are standardized by NIST; the FPE currently included is just a random one that was relatively easy to implement. Move the header to fpe_fe1.h, and rename the function. Update the example and add some documentation for it. --- doc/examples/fpe.cpp | 6 +- doc/fpe.txt | 58 +++++++++++ doc/log.txt | 7 ++ src/constructs/fpe/fpe.cpp | 189 ------------------------------------ src/constructs/fpe/fpe.h | 40 -------- src/constructs/fpe/info.txt | 7 -- src/constructs/fpe_fe1/fpe_fe1.cpp | 193 +++++++++++++++++++++++++++++++++++++ src/constructs/fpe_fe1/fpe_fe1.h | 44 +++++++++ src/constructs/fpe_fe1/info.txt | 7 ++ 9 files changed, 312 insertions(+), 239 deletions(-) create mode 100644 doc/fpe.txt delete mode 100644 src/constructs/fpe/fpe.cpp delete mode 100644 src/constructs/fpe/fpe.h delete mode 100644 src/constructs/fpe/info.txt create mode 100644 src/constructs/fpe_fe1/fpe_fe1.cpp create mode 100644 src/constructs/fpe_fe1/fpe_fe1.h create mode 100644 src/constructs/fpe_fe1/info.txt diff --git a/doc/examples/fpe.cpp b/doc/examples/fpe.cpp index a7a483d65..029a761e7 100644 --- a/doc/examples/fpe.cpp +++ b/doc/examples/fpe.cpp @@ -1,5 +1,5 @@ #include -#include +#include #include using namespace Botan; @@ -70,7 +70,7 @@ u64bit encrypt_cc_number(u64bit cc_number, u64bit cc_ranked = cc_rank(cc_number); - BigInt c = fpe_encrypt(n, cc_ranked, key, sha1(acct_name)); + 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"); @@ -89,7 +89,7 @@ u64bit decrypt_cc_number(u64bit enc_cc, u64bit cc_ranked = cc_rank(enc_cc); - BigInt c = fpe_decrypt(n, cc_ranked, key, sha1(acct_name)); + 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"); diff --git a/doc/fpe.txt b/doc/fpe.txt new file mode 100644 index 000000000..80a24a70e --- /dev/null +++ b/doc/fpe.txt @@ -0,0 +1,58 @@ + +.. _fpe: + +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 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``: + +.. cpp:function:: BigInt FPE::fe1_encrypt(const BigInt& n, const BigInt& X, \ + const SymmetricKey& key, const MemoryRegion& 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 10\ :sup:`15`, and then calculate what the + checksum is for the new (ciphertext) number. + +.. cpp:function:: BigInt FPE::fe1_decrypt(const BigInt& n, const BigInt& X, \ + const SymmetricKey& key, const MemoryRegion& tweak) + + Decrypts an FE1 ciphertext produced by :cpp:func:`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. + +.. literalinclude:: examples/fpe.cpp + diff --git a/doc/log.txt b/doc/log.txt index b8a23079b..f60086c7c 100644 --- a/doc/log.txt +++ b/doc/log.txt @@ -12,6 +12,13 @@ Version 1.10.0, Not Yet Released * Further updates to the documentation +* The format preserving encryption method currently available was + presented in the header ``fpe.h`` and the functions ``fpe_encrypt`` + and ``fpe_decrypt``. These were renamed as it is likely that other + FPE schemes will be included in the future. The header is now + ``fpe_fe1.h``, and the functions are named ``fe1_encrypt`` and + ``fe1_decrypt``. See :ref:`fpe` for more information. + * A bug in 1.9.16 effectively disabled support for runtime CPU feature detection on x86 under GCC in that release. diff --git a/src/constructs/fpe/fpe.cpp b/src/constructs/fpe/fpe.cpp deleted file mode 100644 index 5491af133..000000000 --- a/src/constructs/fpe/fpe.cpp +++ /dev/null @@ -1,189 +0,0 @@ -/* -* Format Preserving Encryption using the scheme FE1 from the paper -* "Format-Preserving Encryption" by Bellare, Rogaway, et al -* (http://eprint.iacr.org/2009/251) -* -* (C) 2009 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#include -#include -#include -#include -#include - -namespace Botan { - -namespace { - -// Normally FPE is for SSNs, CC#s, etc, nothing too big -const size_t MAX_N_BYTES = 128/8; - -/* -* Factor n into a and b which are as close together as possible. -* Assumes n is composed mostly of small factors which is the case for -* typical uses of FPE (typically, n is a power of 10) -* -* Want a >= b since the safe number of rounds is 2+log_a(b); if a >= b -* then this is always 3 -*/ -void factor(BigInt n, BigInt& a, BigInt& b) - { - a = 1; - b = 1; - - size_t n_low_zero = low_zero_bits(n); - - a <<= (n_low_zero / 2); - b <<= n_low_zero - (n_low_zero / 2); - n >>= n_low_zero; - - for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i) - { - while(n % PRIMES[i] == 0) - { - a *= PRIMES[i]; - if(a > b) - std::swap(a, b); - n /= PRIMES[i]; - } - } - - if(a > b) - std::swap(a, b); - a *= n; - if(a < b) - std::swap(a, b); - - if(a <= 1 || b <= 1) - throw std::runtime_error("Could not factor n for use in FPE"); - } - -/* -* According to a paper by Rogaway, Bellare, etc, the min safe number -* of rounds to use for FPE is 2+log_a(b). If a >= b then log_a(b) <= 1 -* so 3 rounds is safe. The FPE factorization routine should always -* return a >= b, so just confirm that and return 3. -*/ -size_t rounds(const BigInt& a, const BigInt& b) - { - if(a < b) - throw std::logic_error("FPE rounds: a < b"); - return 3; - } - -/* -* A simple round function based on HMAC(SHA-256) -*/ -class FPE_Encryptor - { - public: - FPE_Encryptor(const SymmetricKey& key, - const BigInt& n, - const MemoryRegion& tweak); - - ~FPE_Encryptor() { delete mac; } - - BigInt operator()(size_t i, const BigInt& R); - - private: - MessageAuthenticationCode* mac; - SecureVector mac_n_t; - }; - -FPE_Encryptor::FPE_Encryptor(const SymmetricKey& key, - const BigInt& n, - const MemoryRegion& tweak) - { - mac = new HMAC(new SHA_256); - mac->set_key(key); - - SecureVector n_bin = BigInt::encode(n); - - if(n_bin.size() > MAX_N_BYTES) - throw std::runtime_error("N is too large for FPE encryption"); - - mac->update_be(static_cast(n_bin.size())); - mac->update(&n_bin[0], n_bin.size()); - - mac->update_be(static_cast(tweak.size())); - mac->update(&tweak[0], tweak.size()); - - mac_n_t = mac->final(); - } - -BigInt FPE_Encryptor::operator()(size_t round_no, const BigInt& R) - { - SecureVector r_bin = BigInt::encode(R); - - mac->update(mac_n_t); - mac->update_be(static_cast(round_no)); - - mac->update_be(static_cast(r_bin.size())); - mac->update(&r_bin[0], r_bin.size()); - - SecureVector X = mac->final(); - return BigInt(&X[0], X.size()); - } - -} - -/* -* Generic Z_n FPE encryption, FE1 scheme -*/ -BigInt fpe_encrypt(const BigInt& n, const BigInt& X0, - const SymmetricKey& key, - const MemoryRegion& tweak) - { - FPE_Encryptor F(key, n, tweak); - - BigInt a, b; - factor(n, a, b); - - const size_t r = rounds(a, b); - - BigInt X = X0; - - for(size_t i = 0; i != r; ++i) - { - BigInt L = X / b; - BigInt R = X % b; - - BigInt W = (L + F(i, R)) % a; - X = a * R + W; - } - - return X; - } - -/* -* Generic Z_n FPE decryption, FD1 scheme -*/ -BigInt fpe_decrypt(const BigInt& n, const BigInt& X0, - const SymmetricKey& key, - const MemoryRegion& tweak) - { - FPE_Encryptor F(key, n, tweak); - - BigInt a, b; - factor(n, a, b); - - const size_t r = rounds(a, b); - - BigInt X = X0; - - for(size_t i = 0; i != r; ++i) - { - BigInt W = X % a; - BigInt R = X / a; - - BigInt L = (W - F(r-i-1, R)) % a; - X = b * L + R; - } - - return X; - } - -} diff --git a/src/constructs/fpe/fpe.h b/src/constructs/fpe/fpe.h deleted file mode 100644 index 7a4a7861a..000000000 --- a/src/constructs/fpe/fpe.h +++ /dev/null @@ -1,40 +0,0 @@ -/* -* Format Preserving Encryption -* (C) 2009 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#ifndef BOTAN_FORMAT_PRESERVING_ENCRYPTION_H__ -#define BOTAN_FORMAT_PRESERVING_ENCRYPTION_H__ - -#include -#include - -namespace Botan { - -/** -* Encrypt X from and onto the group Z_n using key and tweak -* @param n the modulus -* @param X the plaintext as a BigInt -* @param key a random key -* @param tweak will modify the ciphertext (think of as an IV) -*/ -BigInt BOTAN_DLL fpe_encrypt(const BigInt& n, const BigInt& X, - const SymmetricKey& key, - const MemoryRegion& tweak); - -/** -* Decrypt X from and onto the group Z_n using key and tweak -* @param n the modulus -* @param X the ciphertext as a BigInt -* @param key is the key used for encryption -* @param tweak the same tweak used for encryption -*/ -BigInt BOTAN_DLL fpe_decrypt(const BigInt& n, const BigInt& X, - const SymmetricKey& key, - const MemoryRegion& tweak); - -} - -#endif diff --git a/src/constructs/fpe/info.txt b/src/constructs/fpe/info.txt deleted file mode 100644 index 078eb2135..000000000 --- a/src/constructs/fpe/info.txt +++ /dev/null @@ -1,7 +0,0 @@ -define FORMAT_PRESERVING_ENCRYPTION - - -hmac -sha2_32 -bigint - diff --git a/src/constructs/fpe_fe1/fpe_fe1.cpp b/src/constructs/fpe_fe1/fpe_fe1.cpp new file mode 100644 index 000000000..91d328c17 --- /dev/null +++ b/src/constructs/fpe_fe1/fpe_fe1.cpp @@ -0,0 +1,193 @@ +/* +* Format Preserving Encryption using the scheme FE1 from the paper +* "Format-Preserving Encryption" by Bellare, Rogaway, et al +* (http://eprint.iacr.org/2009/251) +* +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include +#include +#include +#include +#include + +namespace Botan { + +namespace FPE { + +namespace { + +// Normally FPE is for SSNs, CC#s, etc, nothing too big +const size_t MAX_N_BYTES = 128/8; + +/* +* Factor n into a and b which are as close together as possible. +* Assumes n is composed mostly of small factors which is the case for +* typical uses of FPE (typically, n is a power of 10) +* +* Want a >= b since the safe number of rounds is 2+log_a(b); if a >= b +* then this is always 3 +*/ +void factor(BigInt n, BigInt& a, BigInt& b) + { + a = 1; + b = 1; + + size_t n_low_zero = low_zero_bits(n); + + a <<= (n_low_zero / 2); + b <<= n_low_zero - (n_low_zero / 2); + n >>= n_low_zero; + + for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i) + { + while(n % PRIMES[i] == 0) + { + a *= PRIMES[i]; + if(a > b) + std::swap(a, b); + n /= PRIMES[i]; + } + } + + if(a > b) + std::swap(a, b); + a *= n; + if(a < b) + std::swap(a, b); + + if(a <= 1 || b <= 1) + throw std::runtime_error("Could not factor n for use in FPE"); + } + +/* +* According to a paper by Rogaway, Bellare, etc, the min safe number +* of rounds to use for FPE is 2+log_a(b). If a >= b then log_a(b) <= 1 +* so 3 rounds is safe. The FPE factorization routine should always +* return a >= b, so just confirm that and return 3. +*/ +size_t rounds(const BigInt& a, const BigInt& b) + { + if(a < b) + throw std::logic_error("FPE rounds: a < b"); + return 3; + } + +/* +* A simple round function based on HMAC(SHA-256) +*/ +class FPE_Encryptor + { + public: + FPE_Encryptor(const SymmetricKey& key, + const BigInt& n, + const MemoryRegion& tweak); + + ~FPE_Encryptor() { delete mac; } + + BigInt operator()(size_t i, const BigInt& R); + + private: + MessageAuthenticationCode* mac; + SecureVector mac_n_t; + }; + +FPE_Encryptor::FPE_Encryptor(const SymmetricKey& key, + const BigInt& n, + const MemoryRegion& tweak) + { + mac = new HMAC(new SHA_256); + mac->set_key(key); + + SecureVector n_bin = BigInt::encode(n); + + if(n_bin.size() > MAX_N_BYTES) + throw std::runtime_error("N is too large for FPE encryption"); + + mac->update_be(static_cast(n_bin.size())); + mac->update(&n_bin[0], n_bin.size()); + + mac->update_be(static_cast(tweak.size())); + mac->update(&tweak[0], tweak.size()); + + mac_n_t = mac->final(); + } + +BigInt FPE_Encryptor::operator()(size_t round_no, const BigInt& R) + { + SecureVector r_bin = BigInt::encode(R); + + mac->update(mac_n_t); + mac->update_be(static_cast(round_no)); + + mac->update_be(static_cast(r_bin.size())); + mac->update(&r_bin[0], r_bin.size()); + + SecureVector X = mac->final(); + return BigInt(&X[0], X.size()); + } + +} + +/* +* Generic Z_n FPE encryption, FE1 scheme +*/ +BigInt fe1_encrypt(const BigInt& n, const BigInt& X0, + const SymmetricKey& key, + const MemoryRegion& tweak) + { + FPE_Encryptor F(key, n, tweak); + + BigInt a, b; + factor(n, a, b); + + const size_t r = rounds(a, b); + + BigInt X = X0; + + for(size_t i = 0; i != r; ++i) + { + BigInt L = X / b; + BigInt R = X % b; + + BigInt W = (L + F(i, R)) % a; + X = a * R + W; + } + + return X; + } + +/* +* Generic Z_n FPE decryption, FD1 scheme +*/ +BigInt fe1_decrypt(const BigInt& n, const BigInt& X0, + const SymmetricKey& key, + const MemoryRegion& tweak) + { + FPE_Encryptor F(key, n, tweak); + + BigInt a, b; + factor(n, a, b); + + const size_t r = rounds(a, b); + + BigInt X = X0; + + for(size_t i = 0; i != r; ++i) + { + BigInt W = X % a; + BigInt R = X / a; + + BigInt L = (W - F(r-i-1, R)) % a; + X = b * L + R; + } + + return X; + } + +} + +} diff --git a/src/constructs/fpe_fe1/fpe_fe1.h b/src/constructs/fpe_fe1/fpe_fe1.h new file mode 100644 index 000000000..da9a6bcb6 --- /dev/null +++ b/src/constructs/fpe_fe1/fpe_fe1.h @@ -0,0 +1,44 @@ +/* +* Format Preserving Encryption (FE1 scheme) +* (C) 2009 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_FPE_FE1_H__ +#define BOTAN_FPE_FE1_H__ + +#include +#include + +namespace Botan { + +namespace FPE { + +/** +* Encrypt X from and onto the group Z_n using key and tweak +* @param n the modulus +* @param X the plaintext as a BigInt +* @param key a random key +* @param tweak will modify the ciphertext (think of as an IV) +*/ +BigInt BOTAN_DLL fe1_encrypt(const BigInt& n, const BigInt& X, + const SymmetricKey& key, + const MemoryRegion& tweak); + +/** +* Decrypt X from and onto the group Z_n using key and tweak +* @param n the modulus +* @param X the ciphertext as a BigInt +* @param key is the key used for encryption +* @param tweak the same tweak used for encryption +*/ +BigInt BOTAN_DLL fe1_decrypt(const BigInt& n, const BigInt& X, + const SymmetricKey& key, + const MemoryRegion& tweak); + +} + +} + +#endif diff --git a/src/constructs/fpe_fe1/info.txt b/src/constructs/fpe_fe1/info.txt new file mode 100644 index 000000000..33b5a1c80 --- /dev/null +++ b/src/constructs/fpe_fe1/info.txt @@ -0,0 +1,7 @@ +define FPE_FE1 + + +hmac +sha2_32 +bigint + -- cgit v1.2.3