Botan 3.3.0
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/reducer.h>
13#include <botan/internal/divide.h>
14#include <botan/internal/fmt.h>
15#include <botan/internal/loadstor.h>
16
17namespace Botan {
18
19namespace {
20
21// Normally FPE is for SSNs, CC#s, etc, nothing too big
22const size_t MAX_N_BYTES = 128 / 8;
23
24/*
25* Factor n into a and b which are as close together as possible.
26* Assumes n is composed mostly of small factors which is the case for
27* typical uses of FPE (typically, n is a power of 10)
28*/
29void factor(BigInt n, BigInt& a, BigInt& b) {
30 a = BigInt::one();
31 b = BigInt::one();
32
33 size_t n_low_zero = low_zero_bits(n);
34
35 a <<= (n_low_zero / 2);
36 b <<= n_low_zero - (n_low_zero / 2);
37 n >>= n_low_zero;
38
39 for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i) {
40 while(n % PRIMES[i] == 0) {
41 a *= PRIMES[i];
42 if(a > b) {
43 std::swap(a, b);
44 }
46 }
47 }
48
49 if(a > b) {
50 std::swap(a, b);
51 }
52 a *= n;
53
54 if(a <= 1 || b <= 1) {
55 throw Internal_Error("Could not factor n for use in FPE");
56 }
57}
58
59} // namespace
60
61FPE_FE1::FPE_FE1(const BigInt& n, size_t rounds, bool compat_mode, std::string_view mac_algo) : m_rounds(rounds) {
62 if(m_rounds < 3) {
63 throw Invalid_Argument("FPE_FE1 rounds too small");
64 }
65
67
68 m_n_bytes = BigInt::encode(n);
69
70 if(m_n_bytes.size() > MAX_N_BYTES) {
71 throw Invalid_Argument("N is too large for FPE encryption");
72 }
73
74 factor(n, m_a, m_b);
75
76 if(compat_mode) {
77 if(m_a < m_b) {
78 std::swap(m_a, m_b);
79 }
80 } else {
81 if(m_a > m_b) {
82 std::swap(m_a, m_b);
83 }
84 }
85
86 mod_a = std::make_unique<Modular_Reducer>(m_a);
87}
88
89FPE_FE1::~FPE_FE1() = default;
90
92 m_mac->clear();
93}
94
95std::string FPE_FE1::name() const {
96 return fmt("FPE_FE1({},{})", m_mac->name(), m_rounds);
97}
98
100 return m_mac->key_spec();
101}
102
104 return m_mac->has_keying_material();
105}
106
107void FPE_FE1::key_schedule(std::span<const uint8_t> key) {
108 m_mac->set_key(key);
109}
110
111BigInt FPE_FE1::F(const BigInt& R,
112 size_t round,
113 const secure_vector<uint8_t>& tweak_mac,
114 secure_vector<uint8_t>& tmp) const {
115 tmp = BigInt::encode_locked(R);
116
117 m_mac->update(tweak_mac);
118 m_mac->update_be(static_cast<uint32_t>(round));
119
120 m_mac->update_be(static_cast<uint32_t>(tmp.size()));
121 m_mac->update(tmp.data(), tmp.size());
122
123 tmp = m_mac->final();
124 return BigInt(tmp.data(), tmp.size());
125}
126
127secure_vector<uint8_t> FPE_FE1::compute_tweak_mac(const uint8_t tweak[], size_t tweak_len) const {
128 m_mac->update_be(static_cast<uint32_t>(m_n_bytes.size()));
129 m_mac->update(m_n_bytes.data(), m_n_bytes.size());
130
131 m_mac->update_be(static_cast<uint32_t>(tweak_len));
132 if(tweak_len > 0) {
133 m_mac->update(tweak, tweak_len);
134 }
135
136 return m_mac->final();
137}
138
139BigInt FPE_FE1::encrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const {
140 const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);
141
142 BigInt X = input;
143
145
146 BigInt L, R, Fi;
147 for(size_t i = 0; i != m_rounds; ++i) {
148 ct_divide(X, m_b, L, R);
149 Fi = F(R, i, tweak_mac, tmp);
150 X = m_a * R + mod_a->reduce(L + Fi);
151 }
152
153 return X;
154}
155
156BigInt FPE_FE1::decrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const {
157 const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);
158
159 BigInt X = input;
161
162 BigInt W, R, Fi;
163 for(size_t i = 0; i != m_rounds; ++i) {
164 ct_divide(X, m_a, R, W);
165
166 Fi = F(R, m_rounds - i - 1, tweak_mac, tmp);
167 X = m_b * mod_a->reduce(W - Fi) + R;
168 }
169
170 return X;
171}
172
173BigInt FPE_FE1::encrypt(const BigInt& x, uint64_t tweak) const {
174 uint8_t tweak8[8];
175 store_be(tweak, tweak8);
176 return encrypt(x, tweak8, sizeof(tweak8));
177}
178
179BigInt FPE_FE1::decrypt(const BigInt& x, uint64_t tweak) const {
180 uint8_t tweak8[8];
181 store_be(tweak, tweak8);
182 return decrypt(x, tweak8, sizeof(tweak8));
183}
184
185namespace FPE {
186
187BigInt fe1_encrypt(const BigInt& n, const BigInt& X, const SymmetricKey& key, const std::vector<uint8_t>& tweak) {
188 FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
189 fpe.set_key(key);
190 return fpe.encrypt(X, tweak.data(), tweak.size());
191}
192
193BigInt fe1_decrypt(const BigInt& n, const BigInt& X, const SymmetricKey& key, const std::vector<uint8_t>& tweak) {
194 FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
195 fpe.set_key(key);
196 return fpe.decrypt(X, tweak.data(), tweak.size());
197}
198
199} // namespace FPE
200
201} // namespace Botan
static secure_vector< uint8_t > encode_locked(const BigInt &n)
Definition bigint.h:760
static BigInt one()
Definition bigint.h:50
static std::vector< uint8_t > encode(const BigInt &n)
Definition bigint.h:749
static BigInt from_word(word n)
Definition bigint.cpp:42
BigInt encrypt(const BigInt &x, const uint8_t tweak[], size_t tweak_len) const
Definition fpe_fe1.cpp:139
void clear() override
Definition fpe_fe1.cpp:91
std::string name() const override
Definition fpe_fe1.cpp:95
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:61
bool has_keying_material() const override
Definition fpe_fe1.cpp:103
~FPE_FE1() override
Key_Length_Specification key_spec() const override
Definition fpe_fe1.cpp:99
BigInt decrypt(const BigInt &x, const uint8_t tweak[], size_t tweak_len) const
Definition fpe_fe1.cpp:156
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 SymmetricKey &key)
Definition sym_algo.h:113
FE_25519 X
Definition ge.cpp:25
BigInt fe1_decrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition fpe_fe1.cpp:193
BigInt fe1_encrypt(const BigInt &n, const BigInt &X, const SymmetricKey &key, const std::vector< uint8_t > &tweak)
Definition fpe_fe1.cpp:187
constexpr void store_be(T in, OutR &&out_range)
Definition loadstor.h:358
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:167
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:48
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61