1 /**
2 * Format Preserving Encryption (FE1 scheme)
3 * 
4 * Copyright:
5 * (C) 2009 Jack Lloyd
6 * (C) 2014-2015 Etienne Cimon
7 *
8 * License:
9 * Botan is released under the Simplified BSD License (see LICENSE.md)
10 */
11 module botan.constructs.fpe_fe1;
12 
13 import botan.constants;
14 static if (BOTAN_HAS_FPE_FE1):
15 
16 import botan.math.bigint.bigint;
17 import botan.algo_base.symkey;
18 import botan.math.numbertheory.numthry;
19 import botan.mac.hmac;
20 import botan.hash.sha2_32;
21 import botan.mac.mac;
22 import botan.utils.exceptn;
23 import botan.utils.types;
24 import botan.utils.mem_ops;
25 import std.exception;
26 import std.algorithm : swap;
27 
28 struct FPE {
29 
30     /**
31     * Format Preserving Encryption using the scheme FE1 from the paper
32     * "Format-Preserving Encryption" by Bellare, Rogaway, et al
33     * (http://eprint.iacr.org/2009/251)
34     *
35     * Encrypt X from and onto the group Z_n using key and tweak
36     * 
37     * Params:
38     *  n = the modulus
39     *  X = the plaintext as a BigInt
40     *  key = a random key
41     *  tweak = will modify the ciphertext (think of as an IV)
42     */
43     static BigInt fe1Encrypt(const ref BigInt n0, const ref BigInt X0,
44                              in SymmetricKey key,
45                              const ref Vector!ubyte tweak)
46     {
47         Unique!FPEEncryptor F = new FPEEncryptor(key, n0, tweak);
48         
49         BigInt a, b;
50         factor(n0.dup, a, b);
51         
52         const size_t r = rounds(a, b);
53         
54         BigInt X = X0.dup;
55         
56         foreach (size_t i; 0 .. r)
57         {
58             BigInt L = X / b;
59             BigInt R = X % b;
60             
61             BigInt W = (L + (*F)(i, R)) % a;
62             X = a * R + W;
63         }
64         
65         return X;
66     }
67 
68 
69     /**
70     * Decrypt X from and onto the group Z_n using key and tweak
71     * Params:
72     *  n = the modulus
73     *  X = the ciphertext as a BigInt
74     *  key = is the key used for encryption
75     *  tweak = the same tweak used for encryption
76     */
77     static BigInt fe1Decrypt(const ref BigInt n0, const ref BigInt X0, in SymmetricKey key, const ref Vector!ubyte tweak)
78     {
79         auto F = scoped!FPEEncryptor(key, n0, tweak);
80         
81         BigInt a, b;
82         factor(n0.dup, a, b);
83         
84         const size_t r = rounds(a, b);
85         
86         BigInt X = X0.dup;
87         
88         foreach (size_t i; 0 .. r)
89         {
90             BigInt W = X % a;
91             BigInt R = X / a;
92             
93             BigInt L = (W - F(r-i-1, R)) % a;
94             X = b * L + R;
95         }
96         
97         return X;
98     }
99 
100 
101 }
102 
103 private:
104 
105 // Normally FPE is for SSNs, CC#s, etc, nothing too big
106 __gshared immutable size_t MAX_N_BYTES = 128/8;
107 
108 /*
109 * Factor n into a and b which are as close together as possible.
110 * Assumes n is composed mostly of small factors which is the case for
111 * typical uses of FPE (typically, n is a power of 10)
112 *
113 * Want a >= b since the safe number of rounds is 2+log_a(b); if a >= b
114 * then this is always 3
115 */
116 void factor(BigInt n, ref BigInt a, ref BigInt b)
117 {
118     a = 1;
119     b = 1;
120     
121     size_t n_low_zero = lowZeroBits(n);
122     
123     a <<= (n_low_zero / 2);
124     b <<= n_low_zero - (n_low_zero / 2);
125     n >>= n_low_zero;
126     
127     foreach (size_t i; 0 .. PRIME_TABLE_SIZE)
128     {
129         while (n % PRIMES[i] == 0)
130         {
131             a *= PRIMES[i];
132             if (a > b)
133                 swap(a, b);
134             n /= PRIMES[i];
135         }
136     }
137     
138     if (a > b)
139         swap(a, b);
140     a *= n;
141     if (a < b)
142         swap(a, b);
143     
144     if (a <= 1 || b <= 1)
145         throw new Exception("Could not factor n for use in FPE");
146 }
147 
148 /*
149 * According to a paper by Rogaway, Bellare, etc, the min safe number
150 * of rounds to use for FPE is 2+log_a(b). If a >= b then log_a(b) <= 1
151 * so 3 rounds is safe. The FPE factorization routine should always
152 * return a >= b, so just confirm that and return 3.
153 */
154 size_t rounds(const ref BigInt a, const ref BigInt b)
155 {
156     if (a < b)
157         throw new LogicError("FPE rounds: a < b");
158     return 3;
159 }
160 
161 /*
162 * A simple round function based on HMAC(SHA-256)
163 */
164 final class FPEEncryptor
165 {
166 public:
167     this()(in SymmetricKey key, auto const ref BigInt n, const ref Vector!ubyte tweak)
168     {
169 
170         m_mac = new HMAC(new SHA256);
171         m_mac.setKey(key);
172         
173         Vector!ubyte n_bin = BigInt.encode(n);
174         
175         if (n_bin.length > MAX_N_BYTES)
176             throw new Exception("N is too large for FPE encryption");
177         
178         m_mac.updateBigEndian(cast(uint)(n_bin.length));
179         m_mac.update(n_bin.ptr, n_bin.length);
180         
181         m_mac.updateBigEndian(cast(uint)(tweak.length));
182         m_mac.update(tweak.ptr, tweak.length);
183         
184         m_mac_n_t = unlock(m_mac.finished());
185     }
186 
187     
188     BigInt opCall(size_t round_no, const ref BigInt R)
189     {
190         SecureVector!ubyte r_bin = BigInt.encodeLocked(R);
191 
192         m_mac.update(m_mac_n_t);
193         m_mac.updateBigEndian(cast(uint)(round_no));
194         
195         m_mac.updateBigEndian(cast(uint)(r_bin.length));
196         m_mac.update(r_bin.ptr, r_bin.length);
197         
198         SecureVector!ubyte X = m_mac.finished();
199         return BigInt(X.ptr, X.length);
200     }
201     
202 private:
203     Unique!MessageAuthenticationCode m_mac;
204     Vector!ubyte m_mac_n_t;
205 }