diff options
| -rw-r--r-- | doc/manual/fpe.rst | 92 | ||||
| -rw-r--r-- | src/cli/speed.cpp | 7 | ||||
| -rw-r--r-- | src/lib/misc/fpe_fe1/fpe_fe1.cpp | 196 | ||||
| -rw-r--r-- | src/lib/misc/fpe_fe1/fpe_fe1.h | 52 | ||||
| -rw-r--r-- | src/tests/data/fpe_fe1.vec | 12 |
5 files changed, 235 insertions, 124 deletions
diff --git a/doc/manual/fpe.rst b/doc/manual/fpe.rst index 283d6c1a7..56a839930 100644 --- a/doc/manual/fpe.rst +++ b/doc/manual/fpe.rst @@ -1,8 +1,6 @@ Format Preserving Encryption ======================================== -.. versionadded:: 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 @@ -18,39 +16,73 @@ 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``: +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. + +The interfaces for FE1 are defined in the header ``fpe_fe1.h``: + +.. versionadded:: 2.5.0 + +.. cpp:class:: FPE_FE1 + + .. cpp:function:: FPE_FE1(const BigInt& n, size_t rounds = 3, std::string mac_algo = "HMAC(SHA-256)") + + Initialize an FPE operation to encrypt/decrypt integers less than *n*. It + is expected that *n* is trially factorable into small integers. + + The default rounds and mac algorithm match the original FPE implementation + first available in version 1.9.17. + + .. cpp:function:: 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. + + .. cpp:function:: 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. + + .. cpp:function:: BigInt encrypt(const BigInt& x, uint64_t tweak) + + Convenience version of encrypt taking an integer tweak. + + .. cpp:function:: 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. .. cpp:function:: BigInt FPE::fe1_encrypt(const BigInt& n, const BigInt& X, \ - const SymmetricKey& key, const std::vector<uint8_t>& 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. + const SymmetricKey& key, const std::vector<uint8_t>& tweak) -.. cpp:function:: 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 encrypts *X* using + the provided 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. +.. cpp:function:: BigInt FPE::fe1_decrypt(const BigInt& n, const BigInt& X, \ + const SymmetricKey& key, const std::vector<uint8_t>& tweak) - 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 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 <https://en.wikipedia.org/wiki/Luhn_algorithm>`_ to -another number with the same format, including a correct checksum. +This example encrypts a credit card number with a valid `Luhn checksum +<https://en.wikipedia.org/wiki/Luhn_algorithm>`_ to another number with the same +format, including a correct checksum. .. literalinclude:: ../../src/cli/cc_enc.cpp diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp index 1e8c3135f..b29c8b9e9 100644 --- a/src/cli/speed.cpp +++ b/src/cli/speed.cpp @@ -1290,17 +1290,20 @@ class Speed final : public Command Botan::BigInt x = 1; + Botan::FPE_FE1 fpe_fe1(n, 3, "HMAC(SHA-256)"); + fpe_fe1.set_key(key); + while(enc_timer.under(runtime)) { enc_timer.start(); - x = Botan::FPE::fe1_encrypt(n, x, key, tweak); + x = fpe_fe1.encrypt(x, tweak.data(), tweak.size()); enc_timer.stop(); } for(size_t i = 0; i != enc_timer.events(); ++i) { dec_timer.start(); - x = Botan::FPE::fe1_decrypt(n, x, key, tweak); + x = fpe_fe1.decrypt(x, tweak.data(), tweak.size()); dec_timer.stop(); } diff --git a/src/lib/misc/fpe_fe1/fpe_fe1.cpp b/src/lib/misc/fpe_fe1/fpe_fe1.cpp index 04503125c..7166e480f 100644 --- a/src/lib/misc/fpe_fe1/fpe_fe1.cpp +++ b/src/lib/misc/fpe_fe1/fpe_fe1.cpp @@ -1,18 +1,17 @@ /* * Format Preserving Encryption (FE1 scheme) -* (C) 2009 Jack Lloyd +* (C) 2009,2018 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ #include <botan/fpe_fe1.h> #include <botan/numthry.h> +#include <botan/divide.h> #include <botan/mac.h> namespace Botan { -namespace FPE { - namespace { // Normally FPE is for SSNs, CC#s, etc, nothing too big @@ -58,129 +57,154 @@ void factor(BigInt n, BigInt& a, BigInt& b) throw Exception("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) +} + +FPE_FE1::FPE_FE1(const BigInt& n, size_t rounds, const std::string& mac_algo) : + m_rounds(rounds) { - if(a < b) + m_mac = MessageAuthenticationCode::create_or_throw(mac_algo); + + m_n_bytes = BigInt::encode(n); + + if(m_n_bytes.size() > MAX_N_BYTES) + throw Exception("N is too large for FPE encryption"); + + factor(n, m_a, m_b); + + mod_a = Modular_Reducer(m_a); + + /* + * 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. + */ + if(m_a < m_b) throw Internal_Error("FPE rounds: a < b"); - return 3; + + if(m_rounds < 3) + throw Invalid_Argument("FPE_FE1 rounds too small"); } -/* -* A simple round function based on HMAC(SHA-256) -*/ -class FPE_Encryptor final +void FPE_FE1::clear() { - public: - FPE_Encryptor(const SymmetricKey& key, - const BigInt& n, - const std::vector<uint8_t>& tweak); - - BigInt operator()(size_t i, const BigInt& R); + m_mac->clear(); + } - private: - std::unique_ptr<MessageAuthenticationCode> m_mac; - std::vector<uint8_t> m_mac_n_t; - }; +std::string FPE_FE1::name() const + { + return "FPE_FE1(" + m_mac->name() + "," + std::to_string(m_rounds) + ")"; + } -FPE_Encryptor::FPE_Encryptor(const SymmetricKey& key, - const BigInt& n, - const std::vector<uint8_t>& tweak) +Key_Length_Specification FPE_FE1::key_spec() const { - m_mac = MessageAuthenticationCode::create_or_throw("HMAC(SHA-256)"); - m_mac->set_key(key); + return m_mac->key_spec(); + } - std::vector<uint8_t> n_bin = BigInt::encode(n); +void FPE_FE1::key_schedule(const uint8_t key[], size_t length) + { + m_mac->set_key(key, length); + } - if(n_bin.size() > MAX_N_BYTES) - throw Exception("N is too large for FPE encryption"); +BigInt FPE_FE1::F(const BigInt& R, size_t round, + const secure_vector<uint8_t>& tweak_mac, + secure_vector<uint8_t>& tmp) const + { + tmp = BigInt::encode_locked(R); - m_mac->update_be(static_cast<uint32_t>(n_bin.size())); - m_mac->update(n_bin.data(), n_bin.size()); + m_mac->update(tweak_mac); + m_mac->update_be(static_cast<uint32_t>(round)); - m_mac->update_be(static_cast<uint32_t>(tweak.size())); - m_mac->update(tweak.data(), tweak.size()); + m_mac->update_be(static_cast<uint32_t>(tmp.size())); + m_mac->update(tmp.data(), tmp.size()); - m_mac_n_t = unlock(m_mac->final()); + tmp = m_mac->final(); + return BigInt(tmp.data(), tmp.size()); } -BigInt FPE_Encryptor::operator()(size_t round_no, const BigInt& R) +secure_vector<uint8_t> FPE_FE1::compute_tweak_mac(const uint8_t tweak[], size_t tweak_len) const { - secure_vector<uint8_t> r_bin = BigInt::encode_locked(R); - - m_mac->update(m_mac_n_t); - m_mac->update_be(static_cast<uint32_t>(round_no)); + m_mac->update_be(static_cast<uint32_t>(m_n_bytes.size())); + m_mac->update(m_n_bytes.data(), m_n_bytes.size()); - m_mac->update_be(static_cast<uint32_t>(r_bin.size())); - m_mac->update(r_bin.data(), r_bin.size()); + m_mac->update_be(static_cast<uint32_t>(tweak_len)); + m_mac->update(tweak, tweak_len); - secure_vector<uint8_t> X = m_mac->final(); - return BigInt(X.data(), X.size()); + return m_mac->final(); } -} - -/* -* Generic Z_n FPE encryption, FE1 scheme -*/ -BigInt fe1_encrypt(const BigInt& n, const BigInt& X0, - const SymmetricKey& key, - const std::vector<uint8_t>& tweak) +BigInt FPE_FE1::encrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const { - FPE_Encryptor F(key, n, tweak); - - BigInt a, b; - factor(n, a, b); + const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len); - const size_t r = rounds(a, b); + BigInt X = input; - BigInt X = X0; + secure_vector<uint8_t> tmp; - for(size_t i = 0; i != r; ++i) + BigInt L, R, Fi; + for(size_t i = 0; i != m_rounds; ++i) { - BigInt L = X / b; - BigInt R = X % b; - - BigInt W = (L + F(i, R)) % a; - X = a * R + W; + divide(X, m_b, L, R); + Fi = F(R, i, tweak_mac, tmp); + X = m_a * R + mod_a.reduce(L + Fi); } return X; } -/* -* Generic Z_n FPE decryption, FD1 scheme -*/ -BigInt fe1_decrypt(const BigInt& n, const BigInt& X0, - const SymmetricKey& key, - const std::vector<uint8_t>& tweak) +BigInt FPE_FE1::decrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const { - FPE_Encryptor F(key, n, tweak); - - BigInt a, b; - factor(n, a, b); + const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len); - const size_t r = rounds(a, b); + BigInt X = input; + secure_vector<uint8_t> tmp; - BigInt X = X0; - - for(size_t i = 0; i != r; ++i) + BigInt W, R, Fi; + for(size_t i = 0; i != m_rounds; ++i) { - BigInt W = X % a; - BigInt R = X / a; + divide(X, m_a, R, W); - BigInt L = (W - F(r-i-1, R)) % a; - X = b * L + R; + Fi = F(R, m_rounds-i-1, tweak_mac, tmp); + X = m_b * mod_a.reduce(W - Fi) + R; } return X; } +BigInt FPE_FE1::encrypt(const BigInt& x, uint64_t tweak) const + { + uint8_t tweak8[8]; + store_be(tweak, tweak8); + return encrypt(x, tweak8, sizeof(tweak8)); + } + +BigInt FPE_FE1::decrypt(const BigInt& x, uint64_t tweak) const + { + uint8_t tweak8[8]; + store_be(tweak, tweak8); + return decrypt(x, tweak8, sizeof(tweak8)); + } + +namespace FPE { + +BigInt fe1_encrypt(const BigInt& n, const BigInt& X, + const SymmetricKey& key, + const std::vector<uint8_t>& tweak) + { + FPE_FE1 fpe(n, 3, "HMAC(SHA-256)"); + fpe.set_key(key); + return fpe.encrypt(X, tweak.data(), tweak.size()); + } + +BigInt fe1_decrypt(const BigInt& n, const BigInt& X, + const SymmetricKey& key, + const std::vector<uint8_t>& tweak) + { + FPE_FE1 fpe(n, 3, "HMAC(SHA-256)"); + fpe.set_key(key); + return fpe.decrypt(X, tweak.data(), tweak.size()); + } + } } diff --git a/src/lib/misc/fpe_fe1/fpe_fe1.h b/src/lib/misc/fpe_fe1/fpe_fe1.h index 7f92f0601..a38231aa6 100644 --- a/src/lib/misc/fpe_fe1/fpe_fe1.h +++ b/src/lib/misc/fpe_fe1/fpe_fe1.h @@ -1,6 +1,6 @@ /* * Format Preserving Encryption (FE1 scheme) -* (C) 2009 Jack Lloyd +* (C) 2009,2018 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -8,11 +8,51 @@ #ifndef BOTAN_FPE_FE1_H_ #define BOTAN_FPE_FE1_H_ +#include <botan/sym_algo.h> #include <botan/bigint.h> -#include <botan/symkey.h> +#include <botan/reducer.h> namespace Botan { +class MessageAuthenticationCode; + +class BOTAN_PUBLIC_API(2,5) FPE_FE1 final : public SymmetricAlgorithm + { + public: + FPE_FE1(const BigInt& n, + size_t rounds = 3, + const std::string& mac_algo = "HMAC(SHA-256)"); + + Key_Length_Specification key_spec() const override; + + std::string name() const; + + void clear(); + + BigInt encrypt(const BigInt& x, const uint8_t tweak[], size_t tweak_len) const; + + BigInt decrypt(const BigInt& x, const uint8_t tweak[], size_t tweak_len) const; + + BigInt encrypt(const BigInt& x, uint64_t tweak) const; + + BigInt decrypt(const BigInt& x, uint64_t tweak) const; + private: + void key_schedule(const uint8_t key[], size_t length) override; + + BigInt F(const BigInt& R, size_t round, + const secure_vector<uint8_t>& tweak, + secure_vector<uint8_t>& tmp) const; + + secure_vector<uint8_t> compute_tweak_mac(const uint8_t tweak[], size_t tweak_len) const; + + std::unique_ptr<MessageAuthenticationCode> m_mac; + std::vector<uint8_t> m_n_bytes; + BigInt m_a; + BigInt m_b; + Modular_Reducer mod_a; + size_t m_rounds; + }; + namespace FPE { /** @@ -27,8 +67,8 @@ namespace FPE { * @param tweak will modify the ciphertext (think of as an IV) */ BigInt BOTAN_PUBLIC_API(2,0) fe1_encrypt(const BigInt& n, const BigInt& X, - const SymmetricKey& key, - const std::vector<uint8_t>& tweak); + const SymmetricKey& key, + const std::vector<uint8_t>& tweak); /** * Decrypt X from and onto the group Z_n using key and tweak @@ -38,8 +78,8 @@ BigInt BOTAN_PUBLIC_API(2,0) fe1_encrypt(const BigInt& n, const BigInt& X, * @param tweak the same tweak used for encryption */ BigInt BOTAN_PUBLIC_API(2,0) fe1_decrypt(const BigInt& n, const BigInt& X, - const SymmetricKey& key, - const std::vector<uint8_t>& tweak); + const SymmetricKey& key, + const std::vector<uint8_t>& tweak); } diff --git a/src/tests/data/fpe_fe1.vec b/src/tests/data/fpe_fe1.vec index 4108a56a2..ba6720744 100644 --- a/src/tests/data/fpe_fe1.vec +++ b/src/tests/data/fpe_fe1.vec @@ -12,3 +12,15 @@ In = 48166 Out = 69575 Key = AABB Tweak = CCDD + +Mod = 1000000000 +In = 8765309 +Out = 935673214 +Key = 00112233445566778899AABBCCDDEEFF +Tweak = 0123456789 + +Mod = 100000000000 +In = 8765309 +Out = 1082083628 +Key = 00112233445566778899AABBCCDDEEFF +Tweak = 0123456789 |