Botan 3.14.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
10#include <botan/exceptn.h>
11#include <botan/mac.h>
12#include <botan/numthry.h>
13#include <botan/internal/ct_utils.h>
14#include <botan/internal/divide.h>
15#include <botan/internal/fmt.h>
16#include <botan/internal/loadstor.h>
17
18namespace Botan {
19
20namespace {
21
22// Normally FPE is for SSNs, CC#s, etc, nothing too big
23const size_t MAX_N_BYTES = 128 / 8;
24
25/*
26* Factor n into a and b which are as close together as possible.
27* Assumes n is composed mostly of small factors which is the case for
28* typical uses of FPE (typically, n is a power of 10)
29*/
30void factor(BigInt n, BigInt& a, BigInt& b) {
31 BOTAN_ARG_CHECK(n >= 2, "Invalid FPE modulus");
32
33 a = BigInt::one();
34 b = BigInt::one();
35
36 /*
37 * This algorithm was poorly designed. It should have fully factored n (to the
38 * extent possible) and then built a/b starting from the largest factor first.
39 *
40 * This can't be fixed now without breaking existing users but if some
41 * incompatible change (or new flag, etc) is added in the future, consider
42 * fixing the factoring for those users.
43 */
44
45 const size_t n_low_zero = low_zero_bits(n);
46
47 a <<= (n_low_zero / 2);
48 b <<= n_low_zero - (n_low_zero / 2);
49 n >>= n_low_zero;
50
51 for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i) {
52 while(n % PRIMES[i] == 0) {
53 a *= PRIMES[i];
54 if(a > b) {
55 std::swap(a, b);
56 }
58 }
59 }
60
61 if(a > b) {
62 std::swap(a, b);
63 }
64 a *= n;
65
66 if(a <= 1 || b <= 1) {
67 throw Invalid_Argument("FPE_FE1 modulus must be composite with at least one prime factor under 65521");
68 }
69}
70
71} // namespace
72
73FPE_FE1::FPE_FE1(const BigInt& n, size_t rounds, bool compat_mode, std::string_view mac_algo) :
74 m_n(n), m_rounds(rounds) {
75 if(m_rounds < 3) {
76 throw Invalid_Argument("FPE_FE1 rounds too small");
77 }
78
80
81 m_n_bytes = m_n.serialize();
82
83 if(m_n_bytes.size() > MAX_N_BYTES) {
84 throw Invalid_Argument("N is too large for FPE encryption");
85 }
86
87 factor(m_n, m_a, m_b);
88
89 if(compat_mode) {
90 if(m_a < m_b) {
91 std::swap(m_a, m_b);
92 }
93 } else {
94 if(m_a > m_b) {
95 std::swap(m_a, m_b);
96 }
97 }
98}
99
100FPE_FE1::FPE_FE1(FPE_FE1&& other) noexcept = default;
101
102FPE_FE1::~FPE_FE1() = default;
103
105 m_mac->clear();
106}
107
108std::string FPE_FE1::name() const {
109 return fmt("FPE_FE1({},{})", m_mac->name(), m_rounds);
110}
111
113 return m_mac->key_spec();
114}
115
117 return m_mac->has_keying_material();
118}
119
120void FPE_FE1::key_schedule(std::span<const uint8_t> key) {
121 m_mac->set_key(key);
122}
123
124BigInt FPE_FE1::F(const BigInt& R,
125 size_t round,
126 const secure_vector<uint8_t>& tweak_mac,
127 secure_vector<uint8_t>& tmp) const {
128 tmp = R.serialize<secure_vector<uint8_t>>();
129
130 m_mac->update(tweak_mac);
131 m_mac->update_be(static_cast<uint32_t>(round));
132
133 m_mac->update_be(static_cast<uint32_t>(tmp.size()));
134 m_mac->update(tmp.data(), tmp.size());
135
136 tmp = m_mac->final();
137 return BigInt::from_bytes(tmp);
138}
139
140secure_vector<uint8_t> FPE_FE1::compute_tweak_mac(const uint8_t tweak[], size_t tweak_len) const {
141 m_mac->update_be(static_cast<uint32_t>(m_n_bytes.size()));
142 m_mac->update(m_n_bytes.data(), m_n_bytes.size());
143
144 m_mac->update_be(static_cast<uint32_t>(tweak_len));
145 if(tweak_len > 0) {
146 m_mac->update(tweak, tweak_len);
147 }
148
149 return m_mac->final();
150}
151
152BigInt FPE_FE1::encrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const {
153 BOTAN_ARG_CHECK(input.signum() >= 0 && input < m_n, "Invalid FPE_FE1 input");
154
155 const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);
156
157 BigInt X = input;
158 CT::poison(X);
159
161
162 BigInt L;
163 BigInt R;
164 BigInt Fi;
165 for(size_t i = 0; i != m_rounds; ++i) {
166 ct_divide(X, m_b, L, R);
167 Fi = F(R, i, tweak_mac, tmp);
168 X = m_a * R + ct_modulo(L + Fi, m_a);
169 }
170
171 CT::unpoison(X);
172 return X;
173}
174
175BigInt FPE_FE1::decrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const {
176 BOTAN_ARG_CHECK(input.signum() >= 0 && input < m_n, "Invalid FPE_FE1 input");
177
178 const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);
179
180 BigInt X = input;
181 CT::poison(X);
183
184 BigInt W;
185 BigInt R;
186 BigInt Fi;
187 for(size_t i = 0; i != m_rounds; ++i) {
188 ct_divide(X, m_a, R, W);
189
190 Fi = F(R, m_rounds - i - 1, tweak_mac, tmp);
191 X = m_b * ct_modulo(W - Fi, m_a) + R;
192 }
193
194 CT::unpoison(X);
195 return X;
196}
197
198BigInt FPE_FE1::encrypt(const BigInt& x, uint64_t tweak) const {
199 uint8_t tweak8[8];
200 store_be(tweak, tweak8);
201 return encrypt(x, tweak8, sizeof(tweak8));
202}
203
204BigInt FPE_FE1::decrypt(const BigInt& x, uint64_t tweak) const {
205 uint8_t tweak8[8];
206 store_be(tweak, tweak8);
207 return decrypt(x, tweak8, sizeof(tweak8));
208}
209
210namespace FPE {
211
212BigInt fe1_encrypt(const BigInt& n, const BigInt& X, const SymmetricKey& key, const std::vector<uint8_t>& tweak) {
213 FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
214 fpe.set_key(key);
215 return fpe.encrypt(X, tweak.data(), tweak.size());
216}
217
218BigInt fe1_decrypt(const BigInt& n, const BigInt& X, const SymmetricKey& key, const std::vector<uint8_t>& tweak) {
219 FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
220 fpe.set_key(key);
221 return fpe.decrypt(X, tweak.data(), tweak.size());
222}
223
224} // namespace FPE
225
226} // namespace Botan
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
const word * data() const
Definition bigint.h:718
int signum() const
Definition bigint.h:493
static BigInt one()
Definition bigint.h:55
static BigInt from_bytes(std::span< const uint8_t > bytes)
Definition bigint.cpp:84
static BigInt from_word(word n)
Definition bigint.cpp:36
BigInt encrypt(const BigInt &x, const uint8_t tweak[], size_t tweak_len) const
Definition fpe_fe1.cpp:152
void clear() override
Definition fpe_fe1.cpp:104
std::string name() const override
Definition fpe_fe1.cpp:108
BOTAN_FUTURE_EXPLICIT FPE_FE1(const BigInt &n, size_t rounds=5, bool compat_mode=false, std::string_view mac_algo="HMAC(SHA-256)")
Definition fpe_fe1.cpp:73
bool has_keying_material() const override
Definition fpe_fe1.cpp:116
~FPE_FE1() override
Key_Length_Specification key_spec() const override
Definition fpe_fe1.cpp:112
BigInt decrypt(const BigInt &x, const uint8_t tweak[], size_t tweak_len) const
Definition fpe_fe1.cpp:175
static std::unique_ptr< MessageAuthenticationCode > create_or_throw(std::string_view algo_spec, std::string_view provider="")
Definition mac.cpp:142
void set_key(const OctetString &key)
Definition sym_algo.cpp:14
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56
BigInt fe1_decrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition fpe_fe1.cpp:218
BigInt fe1_encrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition fpe_fe1.cpp:212
OctetString SymmetricKey
Definition symkey.h:153
std::string fmt(std::string_view format, const T &... args)
Definition fmt.h:53
size_t low_zero_bits(const BigInt &n)
Definition numthry.cpp:194
const size_t PRIME_TABLE_SIZE
Definition numthry.h:177
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition divide.cpp:262
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:180
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
const uint16_t PRIMES[]
Definition primes.cpp:17
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:745