Optimize FE1 format preserving encryption

Expose the state as the FPE_FE1 class which allows most values
to be precomputed. Approx 6-8 times faster.

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