25650639339

Committed 10 May 2026 07:03PM UTC coverage: 89.326% (-0.002%) from 89.328%

Build # 25650639339

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5592 from randombit/jack/bn-hardening

Various BigInt/mp related hardenings and bug fixes

Coverage Stats

107853 of 120741 relevant lines covered (89.33%)

11294230.95 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

80.91

/src/lib/misc/fpe_fe1/fpe_fe1.cpp

/*
* Format Preserving Encryption (FE1 scheme)
* (C) 2009,2018 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/fpe_fe1.h>

#include <botan/exceptn.h>
#include <botan/mac.h>
#include <botan/numthry.h>
#include <botan/internal/divide.h>
#include <botan/internal/fmt.h>
#include <botan/internal/loadstor.h>

namespace Botan {

namespace {

// Normally FPE is for SSNs, CC#s, etc, nothing too big
const size_t MAX_N_BYTES = 128 / 8;

/*
* Factor n into a and b which are as close together as possible.
* Assumes n is composed mostly of small factors which is the case for
* typical uses of FPE (typically, n is a power of 10)
*/
void factor(BigInt n, BigInt& a, BigInt& b) {
   BOTAN_ARG_CHECK(n >= 2, "Invalid FPE modulus");

   a = BigInt::one();
   b = BigInt::one();

   /*
   * This algorithm was poorly designed. It should have fully factored n (to the
   * extent possible) and then built a/b starting from the largest factor first.
   *
   * This can't be fixed now without breaking existing users but if some
   * incompatible change (or new flag, etc) is added in the future, consider
   * fixing the factoring for those users.
   */

   const size_t n_low_zero = low_zero_bits(n);

   a <<= (n_low_zero / 2);
   b <<= n_low_zero - (n_low_zero / 2);
   n >>= n_low_zero;

   for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i) {
      while(n % PRIMES[i] == 0) {
         a *= PRIMES[i];
         if(a > b) {
            std::swap(a, b);
         }
         n /= BigInt::from_word(PRIMES[i]);
      }
   }

   if(a > b) {
      std::swap(a, b);
   }
   a *= n;

   if(a <= 1 || b <= 1) {
      throw Invalid_Argument("FPE_FE1 modulus must be composite with at least one prime factor under 65521");
   }
}

}  // namespace

FPE_FE1::FPE_FE1(const BigInt& n, size_t rounds, bool compat_mode, std::string_view mac_algo) :
      m_n(n), m_rounds(rounds) {
   if(m_rounds < 3) {
      throw Invalid_Argument("FPE_FE1 rounds too small");
   }

   m_mac = MessageAuthenticationCode::create_or_throw(mac_algo);

   m_n_bytes = m_n.serialize();

   if(m_n_bytes.size() > MAX_N_BYTES) {
      throw Invalid_Argument("N is too large for FPE encryption");
   }

   factor(m_n, m_a, m_b);

   if(compat_mode) {
      if(m_a < m_b) {
         std::swap(m_a, m_b);
      }
   } else {
      if(m_a > m_b) {
         std::swap(m_a, m_b);
      }
   }
}

FPE_FE1::FPE_FE1(FPE_FE1&& other) noexcept = default;

FPE_FE1::~FPE_FE1() = default;

void FPE_FE1::clear() {
   m_mac->clear();
}

std::string FPE_FE1::name() const {
   return fmt("FPE_FE1({},{})", m_mac->name(), m_rounds);
}

Key_Length_Specification FPE_FE1::key_spec() const {
   return m_mac->key_spec();
}

bool FPE_FE1::has_keying_material() const {
   return m_mac->has_keying_material();
}

void FPE_FE1::key_schedule(std::span<const uint8_t> key) {
   m_mac->set_key(key);
}

BigInt FPE_FE1::F(const BigInt& R,
                  size_t round,
                  const secure_vector<uint8_t>& tweak_mac,
                  secure_vector<uint8_t>& tmp) const {
   tmp = R.serialize<secure_vector<uint8_t>>();

   m_mac->update(tweak_mac);
   m_mac->update_be(static_cast<uint32_t>(round));

   m_mac->update_be(static_cast<uint32_t>(tmp.size()));
   m_mac->update(tmp.data(), tmp.size());

   tmp = m_mac->final();
   return BigInt::from_bytes(tmp);
}

secure_vector<uint8_t> FPE_FE1::compute_tweak_mac(const uint8_t tweak[], size_t tweak_len) const {
   m_mac->update_be(static_cast<uint32_t>(m_n_bytes.size()));
   m_mac->update(m_n_bytes.data(), m_n_bytes.size());

   m_mac->update_be(static_cast<uint32_t>(tweak_len));
   if(tweak_len > 0) {
      m_mac->update(tweak, tweak_len);
   }

   return m_mac->final();
}

BigInt FPE_FE1::encrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const {
   BOTAN_ARG_CHECK(input.signum() >= 0 && input < m_n, "Invalid FPE_FE1 input");

   const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);

   BigInt X = input;

   secure_vector<uint8_t> tmp;

   BigInt L;
   BigInt R;
   BigInt Fi;
   for(size_t i = 0; i != m_rounds; ++i) {
      ct_divide(X, m_b, L, R);
      Fi = F(R, i, tweak_mac, tmp);
      X = m_a * R + ct_modulo(L + Fi, m_a);
   }

   return X;
}

BigInt FPE_FE1::decrypt(const BigInt& input, const uint8_t tweak[], size_t tweak_len) const {
   BOTAN_ARG_CHECK(input.signum() >= 0 && input < m_n, "Invalid FPE_FE1 input");

   const secure_vector<uint8_t> tweak_mac = compute_tweak_mac(tweak, tweak_len);

   BigInt X = input;
   secure_vector<uint8_t> tmp;

   BigInt W;
   BigInt R;
   BigInt Fi;
   for(size_t i = 0; i != m_rounds; ++i) {
      ct_divide(X, m_a, R, W);

      Fi = F(R, m_rounds - i - 1, tweak_mac, tmp);
      X = m_b * ct_modulo(W - Fi, m_a) + R;
   }

   return X;
}

BigInt FPE_FE1::encrypt(const BigInt& x, uint64_t tweak) const {
   uint8_t tweak8[8];
   store_be(tweak, tweak8);
   return encrypt(x, tweak8, sizeof(tweak8));
}

BigInt FPE_FE1::decrypt(const BigInt& x, uint64_t tweak) const {
   uint8_t tweak8[8];
   store_be(tweak, tweak8);
   return decrypt(x, tweak8, sizeof(tweak8));
}

namespace FPE {

BigInt fe1_encrypt(const BigInt& n, const BigInt& X, const SymmetricKey& key, const std::vector<uint8_t>& tweak) {
   FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
   fpe.set_key(key);
   return fpe.encrypt(X, tweak.data(), tweak.size());
}

BigInt fe1_decrypt(const BigInt& n, const BigInt& X, const SymmetricKey& key, const std::vector<uint8_t>& tweak) {
   FPE_FE1 fpe(n, 3, true, "HMAC(SHA-256)");
   fpe.set_key(key);
   return fpe.decrypt(X, tweak.data(), tweak.size());
}

}  // namespace FPE

}  // namespace Botan

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

randombit / botan / 25650639339

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous