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