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

1 files changed, 20 insertions, 17 deletions

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());
    }