Fix error in FPE_FE1

An implementation mistake led to choosing a >= b when the original
paper assumes a <= b. Add a boolean to control which version is used.

Increase the default FE1 rounds to 5 for a safety factor.

GH #500

4 files changed, 59 insertions, 19 deletions

diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index fb47581eb..90ddafbdf 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -1372,7 +1372,7 @@ class Speed final : public Command
 
          Botan::BigInt x = 1;
 
-         Botan::FPE_FE1 fpe_fe1(n, 3, "HMAC(SHA-256)");
+         Botan::FPE_FE1 fpe_fe1(n);
          fpe_fe1.set_key(key);
 
          while(enc_timer->under(runtime))
diff --git a/src/lib/misc/fpe_fe1/fpe_fe1.cpp b/src/lib/misc/fpe_fe1/fpe_fe1.cpp
index d06264413..0ec36363f 100644
--- a/src/lib/misc/fpe_fe1/fpe_fe1.cpp
+++ b/src/lib/misc/fpe_fe1/fpe_fe1.cpp
@@ -51,8 +51,6 @@ void factor(BigInt n, BigInt& a, BigInt& b)
    if(a > b)
       std::swap(a, b);
    a *= n;
-   if(a < b)
-      std::swap(a, b);
 
    if(a <= 1 || b <= 1)
       throw Exception("Could not factor n for use in FPE");
@@ -60,9 +58,15 @@ void factor(BigInt n, BigInt& a, BigInt& b)
 
 }
 
-FPE_FE1::FPE_FE1(const BigInt& n, size_t rounds, const std::string& mac_algo) :
+FPE_FE1::FPE_FE1(const BigInt& n,
+                 size_t rounds,
+                 bool compat_mode,
+                 const std::string& mac_algo) :
    m_rounds(rounds)
    {
+   if(m_rounds < 3)
+      throw Invalid_Argument("FPE_FE1 rounds too small");
+
    m_mac = MessageAuthenticationCode::create_or_throw(mac_algo);
 
    m_n_bytes = BigInt::encode(n);
@@ -72,19 +76,18 @@ FPE_FE1::FPE_FE1(const BigInt& n, size_t rounds, const std::string& mac_algo) :
 
    factor(n, m_a, m_b);
 
-   mod_a.reset(new 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");
+   if(compat_mode)
+      {
+      if(m_a < m_b)
+         std::swap(m_a, m_b);
+      }
+   else
+      {
+      if(m_a > m_b)
+         std::swap(m_a, m_b);
+      }
 
-   if(m_rounds < 3)
-      throw Invalid_Argument("FPE_FE1 rounds too small");
+   mod_a.reset(new Modular_Reducer(m_a));
    }
 
 FPE_FE1::~FPE_FE1()
@@ -197,7 +200,7 @@ 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_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
    fpe.set_key(key);
    return fpe.encrypt(X, tweak.data(), tweak.size());
    }
@@ -206,7 +209,7 @@ 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_FE1 fpe(n, 3, true, "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 8f987fd65..e823a5d3c 100644
--- a/src/lib/misc/fpe_fe1/fpe_fe1.h
+++ b/src/lib/misc/fpe_fe1/fpe_fe1.h
@@ -16,11 +16,26 @@ namespace Botan {
 class Modular_Reducer;
 class MessageAuthenticationCode;
 
+/**
+* Format Preserving Encryption using the scheme FE1 from the paper
+* "Format-Preserving Encryption" by Bellare, Rogaway, et al
+* (https://eprint.iacr.org/2009/251)
+*/
 class BOTAN_PUBLIC_API(2,5) FPE_FE1 final : public SymmetricAlgorithm
    {
    public:
+
+      /**
+      * @param n the modulus. All plaintext and ciphertext values must be
+      *        less than this.
+      * @param rounds the number of rounds to use. Must be at least 3.
+      * @param compat_mode An error in versions before 2.5.0 chose incorrect
+      *        values for a and b. Set compat_mode to true to select this version.
+      * @param mac_algo the PRF to use as the encryption function
+      */
       FPE_FE1(const BigInt& n,
-              size_t rounds = 3,
+              size_t rounds = 5,
+              bool compat_mode = false,
               const std::string& mac_algo = "HMAC(SHA-256)");
 
       ~FPE_FE1();
@@ -31,8 +46,18 @@ class BOTAN_PUBLIC_API(2,5) FPE_FE1 final : public SymmetricAlgorithm
 
       void clear() override;
 
+      /**
+      * Encrypt X from and onto the group Z_n using key and tweak
+      * @param x the plaintext to encrypt <= n
+      * @param tweak will modify the ciphertext
+      */
       BigInt encrypt(const BigInt& x, const uint8_t tweak[], size_t tweak_len) const;
 
+      /**
+      * Decrypt X from and onto the group Z_n using key and tweak
+      * @param x the ciphertext to encrypt <= n
+      * @param tweak must match the value used to encrypt
+      */
       BigInt decrypt(const BigInt& x, const uint8_t tweak[], size_t tweak_len) const;
 
       BigInt encrypt(const BigInt& x, uint64_t tweak) const;
@@ -67,6 +92,9 @@ namespace FPE {
 * @param X the plaintext as a BigInt
 * @param key a random key
 * @param tweak will modify the ciphertext (think of as an IV)
+*
+* @warning This function is hardcoded to use only 3 rounds which
+* may be insecure for some values of n. Prefer FPE_FE1 class
 */
 BigInt BOTAN_PUBLIC_API(2,0) fe1_encrypt(const BigInt& n, const BigInt& X,
                                          const SymmetricKey& key,
@@ -78,6 +106,9 @@ BigInt BOTAN_PUBLIC_API(2,0) fe1_encrypt(const BigInt& n, const BigInt& X,
 * @param X the ciphertext as a BigInt
 * @param key is the key used for encryption
 * @param tweak the same tweak used for encryption
+*
+* @warning This function is hardcoded to use only 3 rounds which
+* may be insecure for some values of n. Prefer FPE_FE1 class
 */
 BigInt BOTAN_PUBLIC_API(2,0) fe1_decrypt(const BigInt& n, const BigInt& X,
                                          const SymmetricKey& key,
diff --git a/src/tests/data/fpe_fe1.vec b/src/tests/data/fpe_fe1.vec
index ba6720744..b431b9c68 100644
--- a/src/tests/data/fpe_fe1.vec
+++ b/src/tests/data/fpe_fe1.vec
@@ -19,6 +19,12 @@ Out = 935673214
 Key = 00112233445566778899AABBCCDDEEFF
 Tweak = 0123456789
 
+Mod = 1000000000
+In = 8765310
+Out = 258898741
+Key = 00112233445566778899AABBCCDDEEFF
+Tweak = 0123456789
+
 Mod = 100000000000
 In = 8765309
 Out = 1082083628