23402451516

Committed 22 Mar 2026 11:51AM UTC coverage: 89.401%. Remained the same

Build # 23402451516

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5470 from randombit/jack/tss-avoid-tables

Avoid tables for GF(2^8) arithmetic in TSS

Coverage Stats

104481 of 116868 relevant lines covered (89.4%)

11689998.77 hits per line

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

85.23

/src/lib/misc/tss/tss.cpp

/*
* RTSS (threshold secret sharing)
* (C) 2009,2018,2026 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/tss.h>

#include <botan/exceptn.h>
#include <botan/hash.h>
#include <botan/hex.h>
#include <botan/rng.h>
#include <botan/internal/ct_utils.h>
#include <botan/internal/loadstor.h>

namespace Botan {

namespace {

const size_t RTSS_HEADER_SIZE = 20;

/**
* Constant-time multiplication in GF(2^8) mod 0x11B
*/
uint8_t tss_gf_mul(uint8_t x, uint8_t y) {
   uint8_t r = 0;
   for(size_t i = 0; i != 8; ++i) {
      r ^= CT::Mask<uint8_t>::expand(y & 1).if_set_return(x);
      x = (x << 1) ^ CT::Mask<uint8_t>::expand_top_bit(x).if_set_return(0x1B);
      y >>= 1;
   }
   return r;
}

/**
* Inversion in GF(2^8) via Fermat's little theorem.
*
* Returns 0 for input 0 - a case which should not occur in our usage.
*
* Really this does not need to be constant-time - we only use inversion when
* computing the Lagrange coefficients, which is derived entirely from public data.
*/
uint8_t tss_gf_inv(uint8_t x) {
   const uint8_t x2 = tss_gf_mul(x, x);
   const uint8_t x3 = tss_gf_mul(x2, x);
   const uint8_t x6 = tss_gf_mul(x3, x3);
   const uint8_t x12 = tss_gf_mul(x6, x6);
   const uint8_t x15 = tss_gf_mul(x12, x3);
   const uint8_t x30 = tss_gf_mul(x15, x15);
   const uint8_t x60 = tss_gf_mul(x30, x30);
   const uint8_t x120 = tss_gf_mul(x60, x60);
   const uint8_t x126 = tss_gf_mul(x120, x6);
   const uint8_t x127 = tss_gf_mul(x126, x);
   return tss_gf_mul(x127, x127);
}

uint8_t rtss_hash_id(std::string_view hash_name) {
   if(hash_name == "None") {
      return 0;
   } else if(hash_name == "SHA-1") {
      return 1;
   } else if(hash_name == "SHA-256") {
      return 2;
   } else {
      throw Invalid_Argument("RTSS only supports SHA-1 and SHA-256");
   }
}

std::unique_ptr<HashFunction> get_rtss_hash_by_id(uint8_t id) {
   if(id == 0) {
      return std::unique_ptr<HashFunction>();
   }
   if(id == 1) {
      return HashFunction::create_or_throw("SHA-1");
   } else if(id == 2) {
      return HashFunction::create_or_throw("SHA-256");
   } else {
      throw Decoding_Error("Unknown RTSS hash identifier");
   }
}

}  // namespace

RTSS_Share::RTSS_Share(std::string_view hex_input) {
   m_contents = hex_decode_locked(hex_input);
}

RTSS_Share::RTSS_Share(const uint8_t bin[], size_t len) {
   m_contents.assign(bin, bin + len);
}

uint8_t RTSS_Share::share_id() const {
   if(!initialized()) {
      throw Invalid_State("RTSS_Share::share_id not initialized");
   }

   if(m_contents.size() < RTSS_HEADER_SIZE + 1) {
      throw Decoding_Error("RTSS_Share::share_id invalid share data");
   }

   return m_contents[20];
}

std::string RTSS_Share::to_string() const {
   return hex_encode(m_contents.data(), m_contents.size());
}

std::vector<RTSS_Share> RTSS_Share::split(
   uint8_t M, uint8_t N, const uint8_t S[], uint16_t S_len, const uint8_t identifier[16], RandomNumberGenerator& rng) {
   return RTSS_Share::split(M, N, S, S_len, std::vector<uint8_t>(identifier, identifier + 16), "SHA-256", rng);
}

std::vector<RTSS_Share> RTSS_Share::split(uint8_t M,
                                          uint8_t N,
                                          const uint8_t S[],
                                          uint16_t S_len,
                                          const std::vector<uint8_t>& identifier,
                                          std::string_view hash_fn,
                                          RandomNumberGenerator& rng) {
   if(M <= 1 || N <= 1 || M > N || N >= 255) {
      throw Invalid_Argument("RTSS_Share::split: Invalid N or M");
   }

   if(identifier.size() > 16) {
      throw Invalid_Argument("RTSS_Share::split Invalid identifier size");
   }

   const uint8_t hash_id = rtss_hash_id(hash_fn);

   std::unique_ptr<HashFunction> hash;
   if(hash_id > 0) {
      hash = HashFunction::create_or_throw(hash_fn);
   }

   // secret = S || H(S)
   secure_vector<uint8_t> secret(S, S + S_len);
   if(hash) {
      secret += hash->process(S, S_len);
   }

   if(secret.size() >= 0xFFFE) {
      throw Encoding_Error("RTSS_Share::split secret too large for TSS format");
   }

   // +1 byte for the share ID
   const uint16_t share_len = static_cast<uint16_t>(secret.size() + 1);

   secure_vector<uint8_t> share_header(RTSS_HEADER_SIZE);
   copy_mem(share_header.data(), identifier.data(), identifier.size());
   share_header[16] = hash_id;
   share_header[17] = M;
   share_header[18] = get_byte<0>(share_len);
   share_header[19] = get_byte<1>(share_len);

   // Create RTSS header in each share
   std::vector<RTSS_Share> shares(N);

   for(uint8_t i = 0; i != N; ++i) {
      shares[i].m_contents.reserve(share_header.size() + share_len);
      shares[i].m_contents = share_header;
   }

   // Choose sequential values for X starting from 1
   for(uint8_t i = 0; i != N; ++i) {
      shares[i].m_contents.push_back(i + 1);
   }

   for(const uint8_t secret_byte : secret) {
      std::vector<uint8_t> coefficients(M - 1);
      rng.randomize(coefficients.data(), coefficients.size());

      for(uint8_t j = 0; j != N; ++j) {
         const uint8_t X = j + 1;

         uint8_t sum = secret_byte;
         uint8_t X_i = X;

         for(const uint8_t cb : coefficients) {
            sum ^= tss_gf_mul(X_i, cb);
            X_i = tss_gf_mul(X_i, X);
         }

         shares[j].m_contents.push_back(sum);
      }
   }

   return shares;
}

secure_vector<uint8_t> RTSS_Share::reconstruct(const std::vector<RTSS_Share>& shares) {
   if(shares.size() <= 1) {
      throw Decoding_Error("Insufficient shares to do TSS reconstruction");
   }

   for(size_t i = 0; i != shares.size(); ++i) {
      if(shares[i].size() < RTSS_HEADER_SIZE + 1) {
         throw Decoding_Error("Missing or malformed RTSS header");
      }

      if(shares[i].share_id() == 0) {
         throw Decoding_Error("Invalid (id = 0) RTSS share detected");
      }

      if(i > 0) {
         if(shares[i].size() != shares[0].size()) {
            throw Decoding_Error("Different sized RTSS shares detected");
         }

         if(!CT::is_equal(shares[0].m_contents.data(), shares[i].m_contents.data(), RTSS_HEADER_SIZE).as_bool()) {
            throw Decoding_Error("Different RTSS headers detected");
         }
      }
   }

   const uint8_t N = shares[0].m_contents[17];

   if(shares.size() < N) {
      throw Decoding_Error("Insufficient shares to do TSS reconstruction");
   }

   const uint16_t share_len = make_uint16(shares[0].m_contents[18], shares[0].m_contents[19]);

   const uint8_t hash_id = shares[0].m_contents[16];
   auto hash = get_rtss_hash_by_id(hash_id);
   const size_t hash_len = (hash ? hash->output_length() : 0);

   if(shares[0].size() != RTSS_HEADER_SIZE + share_len) {
      /*
      * This second (laxer) check accommodates a bug in TSS that was
      * fixed in 2.9.0 - previous versions used the length of the
      * *secret* here, instead of the length of the *share*, which is
      * precisely 1 + hash_len longer.
      */
      if(shares[0].size() <= RTSS_HEADER_SIZE + 1 + hash_len) {
         throw Decoding_Error("Bad RTSS length field in header");
      }
   }

   std::vector<uint8_t> V(shares.size());
   secure_vector<uint8_t> recovered;

   // Compute the Lagrange coefficients
   std::vector<uint8_t> lagrange_coeffs(shares.size());
   for(size_t k = 0; k != shares.size(); ++k) {
      uint8_t coeff = 1;
      for(size_t l = 0; l != shares.size(); ++l) {
         if(k == l) {
            continue;
         }
         const uint8_t share_k = shares[k].share_id();
         const uint8_t share_l = shares[l].share_id();
         if(share_k == share_l) {
            throw Decoding_Error("Duplicate shares found in RTSS recovery");
         }
         // We already verified this earlier in the function
         BOTAN_ASSERT_NOMSG(share_k > 0 && share_l > 0);
         const uint8_t div = tss_gf_mul(share_l, tss_gf_inv(share_k ^ share_l));
         coeff = tss_gf_mul(coeff, div);
      }
      lagrange_coeffs[k] = coeff;
   }

   for(size_t i = RTSS_HEADER_SIZE + 1; i != shares[0].size(); ++i) {
      for(size_t j = 0; j != V.size(); ++j) {
         V[j] = shares[j].m_contents[i];
      }

      /*
      * Interpolation step
      *
      * This is effectively a multi-scalar multiplication (aka sum-of-products)
      * where one of the inputs, namely the Lagrange coefficients, are public.
      * If optimizing this function further was useful, this would be the place
      * to start, for example by using Pippeneger's algorithm.
      */
      uint8_t r = 0;
      for(size_t k = 0; k != shares.size(); ++k) {
         r ^= tss_gf_mul(V[k], lagrange_coeffs[k]);
      }
      recovered.push_back(r);
   }

   if(hash) {
      if(recovered.size() < hash->output_length()) {
         throw Decoding_Error("RTSS recovered value too short to be valid");
      }

      const size_t secret_len = recovered.size() - hash->output_length();

      hash->update(recovered.data(), secret_len);
      secure_vector<uint8_t> hash_check = hash->final();

      if(!CT::is_equal(hash_check.data(), &recovered[secret_len], hash->output_length()).as_bool()) {
         throw Decoding_Error("RTSS hash check failed");
      }

      // remove the trailing hash value
      recovered.resize(secret_len);
   }

   return recovered;
}

}  // namespace Botan

1	/*
2	* RTSS (threshold secret sharing)
3	* (C) 2009,2018,2026 Jack Lloyd
4	*
5	* Botan is released under the Simplified BSD License (see license.txt)
6	*/
7
8	#include <botan/tss.h>
9
10	#include <botan/exceptn.h>
11	#include <botan/hash.h>
12	#include <botan/hex.h>
13	#include <botan/rng.h>
14	#include <botan/internal/ct_utils.h>
15	#include <botan/internal/loadstor.h>
16
17	namespace Botan {
18
19	namespace {
20
21	const size_t RTSS_HEADER_SIZE = 20;
22
23	/**
24	* Constant-time multiplication in GF(2^8) mod 0x11B
25	*/
26	uint8_t tss_gf_mul(uint8_t x, uint8_t y) {	31,411✔
27	uint8_t r = 0;	31,411✔
28	for(size_t i = 0; i != 8; ++i) {	282,699✔
29	r ^= CT::Mask<uint8_t>::expand(y & 1).if_set_return(x);	251,288✔
30	x = (x << 1) ^ CT::Mask<uint8_t>::expand_top_bit(x).if_set_return(0x1B);	251,288✔
31	y >>= 1;	251,288✔
32	}
33	return r;	31,411✔
34	}
35
36	/**
37	* Inversion in GF(2^8) via Fermat's little theorem.
38	*
39	* Returns 0 for input 0 - a case which should not occur in our usage.
40	*
41	* Really this does not need to be constant-time - we only use inversion when
42	* computing the Lagrange coefficients, which is derived entirely from public data.
43	*/
44	uint8_t tss_gf_inv(uint8_t x) {	1,800✔
45	const uint8_t x2 = tss_gf_mul(x, x);	1,800✔
46	const uint8_t x3 = tss_gf_mul(x2, x);	1,800✔
47	const uint8_t x6 = tss_gf_mul(x3, x3);	1,800✔
48	const uint8_t x12 = tss_gf_mul(x6, x6);	1,800✔
49	const uint8_t x15 = tss_gf_mul(x12, x3);	1,800✔
50	const uint8_t x30 = tss_gf_mul(x15, x15);	1,800✔
51	const uint8_t x60 = tss_gf_mul(x30, x30);	1,800✔
52	const uint8_t x120 = tss_gf_mul(x60, x60);	1,800✔
53	const uint8_t x126 = tss_gf_mul(x120, x6);	1,800✔
54	const uint8_t x127 = tss_gf_mul(x126, x);	1,800✔
55	return tss_gf_mul(x127, x127);	1,800✔
56	}
57
58	uint8_t rtss_hash_id(std::string_view hash_name) {	7✔
59	if(hash_name == "None") {	7✔
60	return 0;	4✔
61	} else if(hash_name == "SHA-1") {	3✔
62	return 1;	1✔
63	} else if(hash_name == "SHA-256") {	2✔
64	return 2;	2✔
65	} else {
66	throw Invalid_Argument("RTSS only supports SHA-1 and SHA-256");	×
67	}
68	}
69
70	std::unique_ptr<HashFunction> get_rtss_hash_by_id(uint8_t id) {	34✔
71	if(id == 0) {	34✔
72	return std::unique_ptr<HashFunction>();	22✔
73	}
74	if(id == 1) {	12✔
75	return HashFunction::create_or_throw("SHA-1");	3✔
76	} else if(id == 2) {	9✔
77	return HashFunction::create_or_throw("SHA-256");	9✔
78	} else {
79	throw Decoding_Error("Unknown RTSS hash identifier");	×
80	}
81	}
82
83	} // namespace
84
85	RTSS_Share::RTSS_Share(std::string_view hex_input) {	×
86	m_contents = hex_decode_locked(hex_input);	×
87	}	×
88
89	RTSS_Share::RTSS_Share(const uint8_t bin[], size_t len) {	27✔
90	m_contents.assign(bin, bin + len);	27✔
91	}	27✔
92
93	uint8_t RTSS_Share::share_id() const {	3,815✔
94	if(!initialized()) {	3,815✔
95	throw Invalid_State("RTSS_Share::share_id not initialized");	×
96	}
97
98	if(m_contents.size() < RTSS_HEADER_SIZE + 1) {	3,815✔
99	throw Decoding_Error("RTSS_Share::share_id invalid share data");	×
100	}
101
102	return m_contents[20];	3,815✔
103	}
104
105	std::string RTSS_Share::to_string() const {	×
106	return hex_encode(m_contents.data(), m_contents.size());	×
107	}
108
109	std::vector<RTSS_Share> RTSS_Share::split(	×
110	uint8_t M, uint8_t N, const uint8_t S[], uint16_t S_len, const uint8_t identifier[16], RandomNumberGenerator& rng) {
111	return RTSS_Share::split(M, N, S, S_len, std::vector<uint8_t>(identifier, identifier + 16), "SHA-256", rng);	×
112	}
113
114	std::vector<RTSS_Share> RTSS_Share::split(uint8_t M,	7✔
115	uint8_t N,
116	const uint8_t S[],
117	uint16_t S_len,
118	const std::vector<uint8_t>& identifier,
119	std::string_view hash_fn,
120	RandomNumberGenerator& rng) {
121	if(M <= 1 \|\| N <= 1 \|\| M > N \|\| N >= 255) {	7✔
122	throw Invalid_Argument("RTSS_Share::split: Invalid N or M");	×
123	}
124
125	if(identifier.size() > 16) {	7✔
126	throw Invalid_Argument("RTSS_Share::split Invalid identifier size");	×
127	}
128
129	const uint8_t hash_id = rtss_hash_id(hash_fn);	7✔
130
131	std::unique_ptr<HashFunction> hash;	7✔
132	if(hash_id > 0) {	7✔
133	hash = HashFunction::create_or_throw(hash_fn);	3✔
134	}
135
136	// secret = S \|\| H(S)
137	secure_vector<uint8_t> secret(S, S + S_len);	7✔
138	if(hash) {	7✔
139	secret += hash->process(S, S_len);	9✔
140	}
141
142	if(secret.size() >= 0xFFFE) {	7✔
143	throw Encoding_Error("RTSS_Share::split secret too large for TSS format");	×
144	}
145
146	// +1 byte for the share ID
147	const uint16_t share_len = static_cast<uint16_t>(secret.size() + 1);	7✔
148
149	secure_vector<uint8_t> share_header(RTSS_HEADER_SIZE);	7✔
150	copy_mem(share_header.data(), identifier.data(), identifier.size());	7✔
151	share_header[16] = hash_id;	7✔
152	share_header[17] = M;	7✔
153	share_header[18] = get_byte<0>(share_len);	7✔
154	share_header[19] = get_byte<1>(share_len);	7✔
155
156	// Create RTSS header in each share
157	std::vector<RTSS_Share> shares(N);	7✔
158
159	for(uint8_t i = 0; i != N; ++i) {	46✔
160	shares[i].m_contents.reserve(share_header.size() + share_len);	39✔
161	shares[i].m_contents = share_header;	39✔
162	}
163
164	// Choose sequential values for X starting from 1
165	for(uint8_t i = 0; i != N; ++i) {	46✔
166	shares[i].m_contents.push_back(i + 1);	39✔
167	}
168
169	for(const uint8_t secret_byte : secret) {	210✔
170	std::vector<uint8_t> coefficients(M - 1);	203✔
171	rng.randomize(coefficients.data(), coefficients.size());	203✔
172
173	for(uint8_t j = 0; j != N; ++j) {	1,158✔
174	const uint8_t X = j + 1;	955✔
175
176	uint8_t sum = secret_byte;	955✔
177	uint8_t X_i = X;	955✔
178
179	for(const uint8_t cb : coefficients) {	3,044✔
180	sum ^= tss_gf_mul(X_i, cb);	2,089✔
181	X_i = tss_gf_mul(X_i, X);	2,089✔
182	}
183
184	shares[j].m_contents.push_back(sum);	955✔
185	}
186	}	203✔
187
188	return shares;	7✔
189	}	17✔
190
191	secure_vector<uint8_t> RTSS_Share::reconstruct(const std::vector<RTSS_Share>& shares) {	35✔
192	if(shares.size() <= 1) {	35✔
193	throw Decoding_Error("Insufficient shares to do TSS reconstruction");	×
194	}
195
196	for(size_t i = 0; i != shares.size(); ++i) {	250✔
197	if(shares[i].size() < RTSS_HEADER_SIZE + 1) {	215✔
198	throw Decoding_Error("Missing or malformed RTSS header");	×
199	}
200
201	if(shares[i].share_id() == 0) {	215✔
202	throw Decoding_Error("Invalid (id = 0) RTSS share detected");	×
203	}
204
205	if(i > 0) {	215✔
206	if(shares[i].size() != shares[0].size()) {	180✔
207	throw Decoding_Error("Different sized RTSS shares detected");	×
208	}
209
210	if(!CT::is_equal(shares[0].m_contents.data(), shares[i].m_contents.data(), RTSS_HEADER_SIZE).as_bool()) {	180✔
211	throw Decoding_Error("Different RTSS headers detected");	×
212	}
213	}
214	}
215
216	const uint8_t N = shares[0].m_contents[17];	35✔
217
218	if(shares.size() < N) {	35✔
219	throw Decoding_Error("Insufficient shares to do TSS reconstruction");	1✔
220	}
221
222	const uint16_t share_len = make_uint16(shares[0].m_contents[18], shares[0].m_contents[19]);	34✔
223
224	const uint8_t hash_id = shares[0].m_contents[16];	34✔
225	auto hash = get_rtss_hash_by_id(hash_id);	34✔
226	const size_t hash_len = (hash ? hash->output_length() : 0);	34✔
227
228	if(shares[0].size() != RTSS_HEADER_SIZE + share_len) {	34✔
229	/*
230	* This second (laxer) check accommodates a bug in TSS that was
231	* fixed in 2.9.0 - previous versions used the length of the
232	* secret here, instead of the length of the share, which is
233	* precisely 1 + hash_len longer.
234	*/
235	if(shares[0].size() <= RTSS_HEADER_SIZE + 1 + hash_len) {	3✔
236	throw Decoding_Error("Bad RTSS length field in header");	×
237	}
238	}
239
240	std::vector<uint8_t> V(shares.size());	35✔
241	secure_vector<uint8_t> recovered;	34✔
242
243	// Compute the Lagrange coefficients
244	std::vector<uint8_t> lagrange_coeffs(shares.size());	35✔
245	for(size_t k = 0; k != shares.size(); ++k) {	247✔
246	uint8_t coeff = 1;
247	for(size_t l = 0; l != shares.size(); ++l) {	2,226✔
248	if(k == l) {	2,013✔
249	continue;	213✔
250	}
251	const uint8_t share_k = shares[k].share_id();	1,800✔
252	const uint8_t share_l = shares[l].share_id();	1,800✔
253	if(share_k == share_l) {	1,800✔
254	throw Decoding_Error("Duplicate shares found in RTSS recovery");	×
255	}
256	// We already verified this earlier in the function
257	BOTAN_ASSERT_NOMSG(share_k > 0 && share_l > 0);	1,800✔
258	const uint8_t div = tss_gf_mul(share_l, tss_gf_inv(share_k ^ share_l));	1,800✔
259	coeff = tss_gf_mul(coeff, div);	1,800✔
260	}
261	lagrange_coeffs[k] = coeff;	213✔
262	}
263
264	for(size_t i = RTSS_HEADER_SIZE + 1; i != shares[0].size(); ++i) {	887✔
265	for(size_t j = 0; j != V.size(); ++j) {	4,686✔
266	V[j] = shares[j].m_contents[i];	3,833✔
267	}
268
269	/*
270	* Interpolation step
271	*
272	* This is effectively a multi-scalar multiplication (aka sum-of-products)
273	* where one of the inputs, namely the Lagrange coefficients, are public.
274	* If optimizing this function further was useful, this would be the place
275	* to start, for example by using Pippeneger's algorithm.
276	*/
277	uint8_t r = 0;	853✔
278	for(size_t k = 0; k != shares.size(); ++k) {	4,686✔
279	r ^= tss_gf_mul(V[k], lagrange_coeffs[k]);	3,833✔
280	}
281	recovered.push_back(r);	853✔
282	}
283
284	if(hash) {	34✔
285	if(recovered.size() < hash->output_length()) {	12✔
286	throw Decoding_Error("RTSS recovered value too short to be valid");	×
287	}
288
289	const size_t secret_len = recovered.size() - hash->output_length();	12✔
290
291	hash->update(recovered.data(), secret_len);	12✔
292	secure_vector<uint8_t> hash_check = hash->final();	12✔
293
294	if(!CT::is_equal(hash_check.data(), &recovered[secret_len], hash->output_length()).as_bool()) {	13✔
295	throw Decoding_Error("RTSS hash check failed");	1✔
296	}
297
298	// remove the trailing hash value
299	recovered.resize(secret_len);	11✔
300	}	12✔
301
302	return recovered;	33✔
303	}	80✔
304
305	} // namespace Botan

randombit / botan / 23402451516

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