aboutsummaryrefslogtreecommitdiffstats
path: root/src/constructs/fpe
diff options
context:
space:
mode:
Diffstat (limited to 'src/constructs/fpe')
-rw-r--r--src/constructs/fpe/fpe.cpp195
-rw-r--r--src/constructs/fpe/fpe.h32
-rw-r--r--src/constructs/fpe/info.txt13
3 files changed, 240 insertions, 0 deletions
diff --git a/src/constructs/fpe/fpe.cpp b/src/constructs/fpe/fpe.cpp
new file mode 100644
index 000000000..86e56625d
--- /dev/null
+++ b/src/constructs/fpe/fpe.cpp
@@ -0,0 +1,195 @@
+/*
+* 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 <botan/fpe.h>
+#include <botan/numthry.h>
+#include <botan/hmac.h>
+#include <botan/sha2_32.h>
+#include <botan/loadstor.h>
+#include <stdexcept>
+
+namespace Botan {
+
+namespace {
+
+// Normally FPE is for SSNs, CC#s, etc, nothing too big
+const u32bit 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;
+
+ u32bit 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(u32bit 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.
+*/
+u32bit 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<byte>& tweak);
+
+ ~FPE_Encryptor() { delete mac; }
+
+ BigInt operator()(u32bit i, const BigInt& R);
+
+ private:
+ MessageAuthenticationCode* mac;
+ SecureVector<byte> mac_n_t;
+ };
+
+FPE_Encryptor::FPE_Encryptor(const SymmetricKey& key,
+ const BigInt& n,
+ const MemoryRegion<byte>& tweak)
+ {
+ mac = new HMAC(new SHA_256);
+ mac->set_key(key);
+
+ SecureVector<byte> n_bin = BigInt::encode(n);
+
+ if(n_bin.size() > MAX_N_BYTES)
+ throw std::runtime_error("N is too large for FPE encryption");
+
+ for(u32bit i = 0; i != 4; ++i)
+ mac->update(get_byte(i, n_bin.size()));
+ mac->update(&n_bin[0], n_bin.size());
+
+ for(u32bit i = 0; i != 4; ++i)
+ mac->update(get_byte(i, tweak.size()));
+ mac->update(&tweak[0], tweak.size());
+
+ mac_n_t = mac->final();
+ }
+
+BigInt FPE_Encryptor::operator()(u32bit round_no, const BigInt& R)
+ {
+ mac->update(mac_n_t);
+
+ for(u32bit i = 0; i != 4; ++i)
+ mac->update(get_byte(i, round_no));
+
+ SecureVector<byte> r_bin = BigInt::encode(R);
+
+ for(u32bit i = 0; i != 4; ++i)
+ mac->update(get_byte(i, r_bin.size()));
+ mac->update(&r_bin[0], r_bin.size());
+
+ SecureVector<byte> 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<byte>& tweak)
+ {
+ FPE_Encryptor F(key, n, tweak);
+
+ BigInt a, b;
+ factor(n, a, b);
+
+ const u32bit r = rounds(a, b);
+
+ BigInt X = X0;
+
+ for(u32bit 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<byte>& tweak)
+ {
+ FPE_Encryptor F(key, n, tweak);
+
+ BigInt a, b;
+ factor(n, a, b);
+
+ const u32bit r = rounds(a, b);
+
+ BigInt X = X0;
+
+ for(u32bit 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
new file mode 100644
index 000000000..fba1652d3
--- /dev/null
+++ b/src/constructs/fpe/fpe.h
@@ -0,0 +1,32 @@
+/*
+* 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 <botan/bigint.h>
+#include <botan/symkey.h>
+
+namespace Botan {
+
+/*
+* Encrypt X from and onto the group Z_n using key and tweak
+*/
+BigInt fpe_encrypt(const BigInt& n, const BigInt& X,
+ const SymmetricKey& key,
+ const MemoryRegion<byte>& tweak);
+
+/*
+* Decrypt X from and onto the group Z_n using key and tweak
+*/
+BigInt fpe_decrypt(const BigInt& n, const BigInt& X,
+ const SymmetricKey& key,
+ const MemoryRegion<byte>& tweak);
+
+}
+
+#endif
diff --git a/src/constructs/fpe/info.txt b/src/constructs/fpe/info.txt
new file mode 100644
index 000000000..f7a8c4ae4
--- /dev/null
+++ b/src/constructs/fpe/info.txt
@@ -0,0 +1,13 @@
+define FORMAT_PRESERVING_ENCRYPTION
+
+load_on auto
+
+<add>
+fpe.cpp
+fpe.h
+</add>
+
+<requires>
+cbc_mac
+bigint
+</requires>