Botan 2.19.1
Crypto and TLS for C&
fpe_fe1.cpp
Go to the documentation of this file.
1/*
2* Format Preserving Encryption (FE1 scheme)
3* (C) 2009,2018 Jack Lloyd
4*
5* Botan is released under the Simplified BSD License (see license.txt)
6*/
7
8#include <botan/fpe_fe1.h>
9#include <botan/loadstor.h>
10#include <botan/numthry.h>
11#include <botan/divide.h>
12#include <botan/reducer.h>
13#include <botan/mac.h>
14
15namespace Botan {
16
17namespace {
18
19// Normally FPE is for SSNs, CC#s, etc, nothing too big
20const size_t MAX_N_BYTES = 128/8;
21
22/*
23* Factor n into a and b which are as close together as possible.
24* Assumes n is composed mostly of small factors which is the case for
25* typical uses of FPE (typically, n is a power of 10)
26*/
27void factor(BigInt n, BigInt& a, BigInt& b)
28 {
29 a = 1;
30 b = 1;
31
32 size_t n_low_zero = low_zero_bits(n);
33
34 a <<= (n_low_zero / 2);
35 b <<= n_low_zero - (n_low_zero / 2);
36 n >>= n_low_zero;
37
38 for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)
39 {
40 while(n % PRIMES[i] == 0)
41 {
42 a *= PRIMES[i];
43 if(a > b)
44 std::swap(a, b);
45 n /= PRIMES[i];
46 }
47 }
48
49 if(a > b)
50 std::swap(a, b);
51 a *= n;
52
53 if(a <= 1 || b <= 1)
54 throw Internal_Error("Could not factor n for use in FPE");
55 }
56
57}
58
60 size_t rounds,
61 bool compat_mode,
62 const std::string& mac_algo) :
63 m_rounds(rounds)
64 {
65 if(m_rounds < 3)
66 throw Invalid_Argument("FPE_FE1 rounds too small");
67
69
70 m_n_bytes = BigInt::encode(n);
71
72 if(m_n_bytes.size() > MAX_N_BYTES)
73 throw Invalid_Argument("N is too large for FPE encryption");
74
75 factor(n, m_a, m_b);
76
77 if(compat_mode)
78 {
79 if(m_a < m_b)
80 std::swap(m_a, m_b);
81 }
82 else
83 {
84 if(m_a > m_b)
85 std::swap(m_a, m_b);
86 }
87
88 mod_a.reset(new Modular_Reducer(m_a));
89 }
90
92 {
93 // for ~unique_ptr
94 }
95
97 {
98 m_mac->clear();
99 }
100
101std::string FPE_FE1::name() const
102 {
103 return "FPE_FE1(" + m_mac->name() + "," + std::to_string(m_rounds) + ")";
104 }
105
107 {
108 return m_mac->key_spec();
109 }
110
111void FPE_FE1::key_schedule(const uint8_t key[], size_t length)
112 {
113 m_mac->set_key(key, length);
114 }
115
116BigInt FPE_FE1::F(const BigInt& R, size_t round,
117 const secure_vector<uint8_t>& tweak_mac,
118 secure_vector<uint8_t>& tmp) const
119 {
120 tmp = BigInt::encode_locked(R);
121
122 m_mac->update(tweak_mac);
123 m_mac->update_be(static_cast<uint32_t>(round));
124
125 m_mac->update_be(static_cast<uint32_t>(tmp.size()));
126 m_mac->update(tmp.data(), tmp.size());
127
128 tmp = m_mac->final();
129 return BigInt(tmp.data(), tmp.size());
130 }
131
132secure_vector<uint8_t> FPE_FE1::compute_tweak_mac(const uint8_t tweak[], size_t tweak_len) const
133 {
134 m_mac->update_be(static_cast<uint32_t>(m_n_bytes.size()));
135 m_mac->update(m_n_bytes.data(), m_n_bytes.size());
136
137 m_mac->update_be(static_cast<uint32_t>(tweak_len));
138 if(tweak_len > 0)
139 m_mac->update(tweak, tweak_len);
140
141 return m_mac->final();
142 }
143
144BigInt FPE_FE1::encrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const
145 {
146 const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);
147
148 BigInt X = input;
149
151
152 BigInt L, R, Fi;
153 for(size_t i = 0; i != m_rounds; ++i)
154 {
155 ct_divide(X, m_b, L, R);
156 Fi = F(R, i, tweak_mac, tmp);
157 X = m_a * R + mod_a->reduce(L + Fi);
158 }
159
160 return X;
161 }
162
163BigInt FPE_FE1::decrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const
164 {
165 const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);
166
167 BigInt X = input;
169
170 BigInt W, R, Fi;
171 for(size_t i = 0; i != m_rounds; ++i)
172 {
173 ct_divide(X, m_a, R, W);
174
175 Fi = F(R, m_rounds-i-1, tweak_mac, tmp);
176 X = m_b * mod_a->reduce(W - Fi) + R;
177 }
178
179 return X;
180 }
181
182BigInt FPE_FE1::encrypt(const BigInt& x, uint64_t tweak) const
183 {
184 uint8_t tweak8[8];
185 store_be(tweak, tweak8);
186 return encrypt(x, tweak8, sizeof(tweak8));
187 }
188
189BigInt FPE_FE1::decrypt(const BigInt& x, uint64_t tweak) const
190 {
191 uint8_t tweak8[8];
192 store_be(tweak, tweak8);
193 return decrypt(x, tweak8, sizeof(tweak8));
194 }
195
196namespace FPE {
197
199 const SymmetricKey& key,
200 const std::vector<uint8_t>& tweak)
201 {
202 FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
203 fpe.set_key(key);
204 return fpe.encrypt(X, tweak.data(), tweak.size());
205 }
206
208 const SymmetricKey& key,
209 const std::vector<uint8_t>& tweak)
210 {
211 FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
212 fpe.set_key(key);
213 return fpe.decrypt(X, tweak.data(), tweak.size());
214 }
215
216}
217
218}
static secure_vector< uint8_t > encode_locked(const BigInt &n)
Definition: bigint.h:782
static std::vector< uint8_t > encode(const BigInt &n)
Definition: bigint.h:770
BigInt encrypt(const BigInt &x, const uint8_t tweak[], size_t tweak_len) const
Definition: fpe_fe1.cpp:144
void clear() override
Definition: fpe_fe1.cpp:96
FPE_FE1(const BigInt &n, size_t rounds=5, bool compat_mode=false, const std::string &mac_algo="HMAC(SHA-256)")
Definition: fpe_fe1.cpp:59
std::string name() const override
Definition: fpe_fe1.cpp:101
Key_Length_Specification key_spec() const override
Definition: fpe_fe1.cpp:106
BigInt decrypt(const BigInt &x, const uint8_t tweak[], size_t tweak_len) const
Definition: fpe_fe1.cpp:163
static std::unique_ptr< MessageAuthenticationCode > create_or_throw(const std::string &algo_spec, const std::string &provider="")
Definition: mac.cpp:141
void set_key(const SymmetricKey &key)
Definition: sym_algo.h:147
fe X
Definition: ge.cpp:27
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213
BigInt fe1_decrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition: fpe_fe1.cpp:207
BigInt fe1_encrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition: fpe_fe1.cpp:198
Definition: alg_id.cpp:13
void store_be(uint16_t in, uint8_t out[2])
Definition: loadstor.h:438
const uint16_t PRIMES[]
Definition: primes.cpp:12
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:39
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:287
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
Definition: divide.cpp:52
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65