1 // Copyright (c) 2017, 2021 Pieter Wuille
2 // Copyright (c) 2021-2022 The Limenka developers
3 // Distributed under the MIT software license, see the accompanying
4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
5 6 #include <bech32.h>
7 #include <codex32.h>
8 #include <util/vector.h>
9 10 #include <array>
11 #include <assert.h>
12 #include <numeric>
13 #include <optional>
14 15 namespace codex32
16 {
17 18 namespace
19 {
20 21 typedef bech32::internal::data data;
22 23 // Build multiplication and logarithm tables for GF(32).
24 //
25 // We represent GF(32) as an extension of GF(2) by appending a root, alpha, of the
26 // polynomial x^5 + x^3 + 1. All elements of GF(32) can be represented as degree-4
27 // polynomials in alpha. So e.g. 1 is represented by 1, alpha by 2, alpha^2 by 4,
28 // and so on.
29 //
30 // alpha is also a generator of the multiplicative group of the field. So every nonzero
31 // element in GF(32) can be represented as alpha^i, for some i in {0, 1, ..., 31}.
32 // This representation makes multiplication and division very easy, since it is just
33 // addition and subtraction in the exponent.
34 //
35 // These tables allow converting from the normal binary representation of GF(32) elements
36 // to the power-of-alpha one.
37 constexpr std::pair<std::array<int8_t, 31>, std::array<int8_t, 32>> GenerateGF32Tables() {
38 // We use these tables to perform arithmetic in GF(32) below, when constructing the
39 // tables for GF(1024).
40 std::array<int8_t, 31> GF32_EXP{};
41 std::array<int8_t, 32> GF32_LOG{};
42 43 // fmod encodes the defining polynomial of GF(32) over GF(2), x^5 + x^3 + 1.
44 // Because coefficients in GF(2) are binary digits, the coefficients are packed as 101001.
45 const int fmod = 41;
46 47 // Elements of GF(32) are encoded as vectors of length 5 over GF(2), that is,
48 // 5 binary digits. Each element (b_4, b_3, b_2, b_1, b_0) encodes a polynomial
49 // b_4*x^4 + b_3*x^3 + b_2*x^2 + b_1*x^1 + b_0 (modulo fmod).
50 // For example, 00001 = 1 is the multiplicative identity.
51 GF32_EXP[0] = 1;
52 GF32_LOG[0] = -1;
53 GF32_LOG[1] = 0;
54 int v = 1;
55 for (int i = 1; i < 31; ++i) {
56 // Multiplication by x is the same as shifting left by 1, as
57 // every coefficient of the polynomial is moved up one place.
58 v = v << 1;
59 // If the polynomial now has an x^5 term, we subtract fmod from it
60 // to remain working modulo fmod. Subtraction is the same as XOR in characteristic
61 // 2 fields.
62 if (v & 32) v ^= fmod;
63 GF32_EXP[i] = v;
64 GF32_LOG[v] = i;
65 }
66 67 return std::make_pair(GF32_EXP, GF32_LOG);
68 }
69 70 constexpr auto tables32 = GenerateGF32Tables();
71 constexpr const std::array<int8_t, 31>& GF32_EXP = tables32.first;
72 constexpr const std::array<int8_t, 32>& GF32_LOG = tables32.second;
73 74 uint8_t gf32_mul(uint8_t x, uint8_t y) {
75 if (x == 0 || y == 0) {
76 return 0;
77 }
78 return GF32_EXP[(GF32_LOG[x] + GF32_LOG[y]) % 31];
79 }
80 81 uint8_t gf32_div(uint8_t x, uint8_t y) {
82 assert(y != 0);
83 if (x == 0) {
84 return 0;
85 }
86 return GF32_EXP[(GF32_LOG[x] + 31 - GF32_LOG[y]) % 31];
87 }
88 89 // The bech32 string "secretshare32"
90 constexpr const std::array<uint8_t, 13> CODEX32_M = {
91 16, 25, 24, 3, 25, 11, 16, 23, 29, 3, 25, 17, 10
92 };
93 94 // The bech32 string "secretshare32ex"
95 constexpr const std::array<uint8_t, 15> CODEX32_LONG_M = {
96 16, 25, 24, 3, 25, 11, 16, 23, 29, 3, 25, 17, 10, 25, 6,
97 };
98 99 // The generator for the codex32 checksum, not including the leading x^13 term
100 constexpr const std::array<uint8_t, 13> CODEX32_GEN = {
101 25, 27, 17, 8, 0, 25, 25, 25, 31, 27, 24, 16, 16,
102 };
103 104 // The generator for the long codex32 checksum, not including the leading x^15 term
105 constexpr const std::array<uint8_t, 15> CODEX32_LONG_GEN = {
106 15, 10, 25, 26, 9, 25, 21, 6, 23, 21, 6, 5, 22, 4, 23,
107 };
108 109 /** This function will compute what 5-bit values to XOR into the last <checksum length>
110 * input values, in order to make the checksum 0. These values are returned in an array
111 * whose length is implied by the type of the generator polynomial (`CODEX32_GEN` or
112 * `CODEX32_LONG_GEN`) that is passed in. The result should be xored with the target
113 * residue ("secretshare32" or "secretshare32ex". */
114 template <typename Residue>
115 Residue PolyMod(const data& v, const Residue& gen)
116 {
117 // The input is interpreted as a list of coefficients of a polynomial over F = GF(32),
118 // in the same way as in bech32. The block comment in bech32::<anonymous>::PolyMod
119 // provides more details.
120 //
121 // Unlike bech32, the output consists of 13 5-bit values, rather than 6, so they cannot
122 // be packed into a uint32_t, or even a uint64_t.
123 //
124 // Like bech32 we have a generator polynomial which defines the BCH code. For "short"
125 // strings, whose data part is 93 characters or less, we use
126 // g(x) = x^13 + {25}x^12 + {27}x^11 + {17}x^10 + {8}x^9 + {0}x^8 + {25}x^7
127 // + {25}x^6 + {25}x^5 + {31}x^4 + {27}x^3 + {24}x^2 + {16}x + {16}
128 //
129 // For long strings, whose data part is more than 93 characters, we use
130 // g(x) = x^15 + {15}x^14 + {10}x^13 + {25}x^12 + {26}x^11 + {9}x^10
131 // + {25}x^9 + {21}x^8 + {6}x^7 + {23}x^6 + {21}x^5 + {6}x^4
132 // + {5}x^3 + {22}x^2 + {4}x^1 + {23}
133 //
134 // In both cases g is chosen in such a way that the resulting code is a BCH code which
135 // can detect up to 8 errors in a window of 93 characters. Unlike bech32, no further
136 // optimization was done to achieve more detection capability than the design parameters.
137 //
138 // For information about the {n} encoding of GF32 elements, see the block comment in
139 // bech32::<anonymous>::PolyMod.
140 Residue res{};
141 res[gen.size() - 1] = 1;
142 for (const auto v_i : v) {
143 // We want to update `res` to correspond to a polynomial with one extra term. That is,
144 // we first multiply it by x and add the next character, which is done by left-shifting
145 // the entire array and adding the next character to the open slot.
146 //
147 // We then reduce it module g, which involves taking the shifted-off character, multiplying
148 // it by g, and adding it to the result of the previous step. This makes sense because after
149 // multiplying by x, `res` has the same degree as g, so reduction by g simply requires
150 // dividing the most significant coefficient of `res` by the most significant coefficient of
151 // g (which is 1), then subtracting that multiple of g.
152 //
153 // Recall that we are working in a characteristic-2 field, so that subtraction is the same
154 // thing as addition.
155 156 // Multiply by x
157 uint8_t shift = res[0];
158 for (size_t i = 1; i < res.size(); ++i) {
159 res[i - 1] = res[i];
160 }
161 // Add the next value
162 res[res.size() - 1] = v_i;
163 // Reduce
164 if (shift != 0) {
165 for(size_t i = 0; i < res.size(); ++i) {
166 if (gen[i] != 0) {
167 res[i] ^= gf32_mul(gen[i], shift);
168 }
169 }
170 }
171 }
172 return res;
173 }
174 175 /** Verify a checksum. */
176 template <typename Residue>
177 bool VerifyChecksum(const std::string& hrp, const data& values, const Residue& gen, const Residue& target)
178 {
179 auto enc = bech32::internal::PreparePolynomialCoefficients(hrp, values);
180 auto res = PolyMod(enc, gen);
181 for (size_t i = 0; i < res.size(); ++i) {
182 if (res[i] != target[i]) {
183 return 0;
184 }
185 }
186 return 1;
187 }
188 189 /** Create a checksum. */
190 template <typename Residue>
191 data CreateChecksum(const std::string& hrp, const data& values, const Residue& gen, const Residue& target)
192 {
193 data enc = bech32::internal::PreparePolynomialCoefficients(hrp, values);
194 enc.resize(enc.size() + gen.size());
195 const auto checksum = PolyMod(enc, gen);
196 data ret(gen.size());
197 for (size_t i = 0; i < checksum.size(); ++i) {
198 ret[i] = checksum[i] ^ target[i];
199 }
200 return ret;
201 }
202 203 // Given a set of share indices and a target index `idx`, which must be in the set,
204 // compute the Lagrange basis polynomial for `idx` evaluated at the point `eval`.
205 //
206 // All inputs are GF32 elements, rather than array indices or anything else.
207 uint8_t lagrange_coefficient(std::vector<uint8_t>& indices, uint8_t idx, uint8_t eval) {
208 uint8_t num = 1;
209 uint8_t den = 1;
210 for (const auto idx_i : indices) {
211 if (idx_i != idx) {
212 num = gf32_mul(num, idx_i ^ eval);
213 den = gf32_mul(den, idx_i ^ idx);
214 }
215 }
216 217 // return num / den
218 return gf32_div(num, den);
219 }
220 221 } // namespace
222 223 std::string ErrorString(Error e) {
224 switch (e) {
225 case OK: return "ok";
226 case BAD_CHECKSUM: return "bad checksum";
227 case BECH32_DECODE: return "bech32 decode failure (invalid character, no HRP, or inconsistent case)";
228 case INVALID_HRP: return "hrp differed from 'ms'";
229 case INVALID_ID_LEN: return "seed ID was not 4 characters";
230 case INVALID_ID_CHAR: return "seed ID used a non-bech32 character";
231 case INVALID_LENGTH: return "invalid length";
232 case INVALID_K: return "invalid threshold (k) value";
233 case INVALID_SHARE_IDX: return "invalid share index";
234 case TOO_FEW_SHARES: return "tried to derive a share but did not have enough input shares";
235 case DUPLICATE_SHARE: return "tried to derive a share but two input shares had the same index";
236 case MISMATCH_K: return "tried to derive a share but input shares had inconsistent threshold (k) values";
237 case MISMATCH_ID: return "tried to derive a share but input shares had inconsistent seed IDs";
238 case MISMATCH_LENGTH: return "tried to derive a share but input shares had inconsistent lengths";
239 }
240 assert(0);
241 }
242 243 /** Encode a codex32 string. */
244 std::string Result::Encode() const {
245 assert(IsValid());
246 247 const data checksum = m_data.size() <= 80
248 ? CreateChecksum(m_hrp, m_data, CODEX32_GEN, CODEX32_M)
249 : CreateChecksum(m_hrp, m_data, CODEX32_LONG_GEN, CODEX32_LONG_M);
250 return bech32::internal::Encode(m_hrp, m_data, checksum);
251 }
252 253 /** Decode a codex32 string */
254 Result::Result(const std::string& str) {
255 m_valid = OK;
256 257 auto res = bech32::internal::Decode(str, bech32::CharLimit::CODEX32, bech32::CHECKSUM_SIZE);
258 259 if (str.size() > bech32::CharLimit::CODEX32) {
260 m_valid = INVALID_LENGTH;
261 // Early return since if we failed the max size check, Decode did not give us any data.
262 return;
263 } else if (res.first.empty() && res.second.empty()) {
264 m_valid = BECH32_DECODE;
265 return;
266 } else if (res.first != "ms") {
267 m_valid = INVALID_HRP;
268 // Early return since if the HRP is wrong, all bets are off and no point continuing
269 return;
270 }
271 m_hrp = std::move(res.first);
272 273 if (res.second.size() >= 45 && res.second.size() <= 90) {
274 // If, after converting back to base-256, we have 5 or more bits of data
275 // remaining, it means that we had an entire character of useless data,
276 // which shouldn't have been included.
277 if (((res.second.size() - 6 - 13) * 5) % 8 > 4) {
278 m_valid = INVALID_LENGTH;
279 } else if (VerifyChecksum(m_hrp, res.second, CODEX32_GEN, CODEX32_M)) {
280 m_data = data(res.second.begin(), res.second.end() - 13);
281 } else {
282 m_valid = BAD_CHECKSUM;
283 }
284 } else if (res.second.size() >= 96 && res.second.size() <= 124) {
285 if (((res.second.size() - 6 - 15) * 5) % 8 > 4) {
286 m_valid = INVALID_LENGTH;
287 } else if (VerifyChecksum(m_hrp, res.second, CODEX32_LONG_GEN, CODEX32_LONG_M)) {
288 m_data = data(res.second.begin(), res.second.end() - 15);
289 } else {
290 m_valid = BAD_CHECKSUM;
291 }
292 } else {
293 m_valid = INVALID_LENGTH;
294 }
295 296 if (m_valid == OK) {
297 auto k = bech32::internal::CHARSET[res.second[0]];
298 if (k < '0' || k == '1' || k > '9') {
299 m_valid = INVALID_K;
300 }
301 if (k == '0' && m_data[5] != 16) {
302 // If the threshold is 0, the only allowable share is S
303 m_valid = INVALID_SHARE_IDX;
304 }
305 }
306 }
307 308 Result::Result(std::string&& hrp, size_t k, const std::string& id, char share_idx, const std::vector<unsigned char>& data) {
309 m_valid = OK;
310 if (hrp != "ms") {
311 m_valid = INVALID_HRP;
312 }
313 m_hrp = hrp;
314 if (k == 1 || k > 9) {
315 m_valid = INVALID_K;
316 }
317 if (id.size() != 4) {
318 m_valid = INVALID_ID_LEN;
319 }
320 int8_t sidx = bech32::internal::CHARSET_REV[(unsigned char) share_idx];
321 if (sidx == -1) {
322 m_valid = INVALID_SHARE_IDX;
323 }
324 if (k == 0 && sidx != 16) {
325 // If the threshold is 0, the only allowable share is S
326 m_valid = INVALID_SHARE_IDX;
327 }
328 for (size_t i = 0; i < id.size(); ++i) {
329 if (bech32::internal::CHARSET_REV[(unsigned char) id[i]] == -1) {
330 m_valid = INVALID_ID_CHAR;
331 }
332 }
333 334 if (m_valid != OK) {
335 // early bail before allocating memory
336 return;
337 }
338 339 m_data.reserve(6 + ((data.size() * 8) + 4) / 5);
340 m_data.push_back(bech32::internal::CHARSET_REV['0' + k]);
341 m_data.push_back(bech32::internal::CHARSET_REV[(unsigned char) id[0]]);
342 m_data.push_back(bech32::internal::CHARSET_REV[(unsigned char) id[1]]);
343 m_data.push_back(bech32::internal::CHARSET_REV[(unsigned char) id[2]]);
344 m_data.push_back(bech32::internal::CHARSET_REV[(unsigned char) id[3]]);
345 m_data.push_back(sidx);
346 ConvertBits<8, 5, true>([&](unsigned char c) { m_data.push_back(c); }, data.begin(), data.end());
347 }
348 349 Result::Result(const std::vector<Result>& shares, char output_idx) {
350 m_valid = OK;
351 352 int8_t oidx = bech32::internal::CHARSET_REV[(unsigned char) output_idx];
353 if (oidx == -1) {
354 m_valid = INVALID_SHARE_IDX;
355 }
356 if (shares.empty()) {
357 m_valid = TOO_FEW_SHARES;
358 return;
359 }
360 size_t k = shares[0].GetK();
361 if (k > shares.size()) {
362 m_valid = TOO_FEW_SHARES;
363 }
364 if (m_valid != OK) {
365 return;
366 }
367 368 std::vector<uint8_t> indices;
369 indices.reserve(shares.size());
370 for (size_t i = 0; i < shares.size(); ++i) {
371 // Currently the only supported hrp is "ms" so it is impossible to violate this
372 assert (shares[0].m_hrp == shares[i].m_hrp);
373 if (shares[0].m_data[0] != shares[i].m_data[0]) {
374 m_valid = MISMATCH_K;
375 }
376 for (size_t j = 1; j < 5; ++j) {
377 if (shares[0].m_data[j] != shares[i].m_data[j]) {
378 m_valid = MISMATCH_ID;
379 }
380 }
381 if (shares[i].m_data.size() != shares[0].m_data.size()) {
382 m_valid = MISMATCH_LENGTH;
383 }
384 385 indices.push_back(shares[i].m_data[5]);
386 for (size_t j = i + 1; j < shares.size(); ++j) {
387 if (shares[i].m_data[5] == shares[j].m_data[5]) {
388 m_valid = DUPLICATE_SHARE;
389 }
390 }
391 }
392 393 if (m_valid != OK) return;
394 395 m_hrp = shares[0].m_hrp;
396 m_data.reserve(shares[0].m_data.size());
397 for (size_t j = 0; j < shares[0].m_data.size(); ++j) {
398 m_data.push_back(0);
399 }
400 401 for (size_t i = 0; i < shares.size(); ++i) {
402 uint8_t lagrange_coeff = lagrange_coefficient(indices, shares[i].m_data[5], oidx);
403 for (size_t j = 0; j < m_data.size(); ++j) {
404 m_data[j] ^= gf32_mul(lagrange_coeff, shares[i].m_data[j]);
405 }
406 }
407 }
408 409 std::string Result::GetIdString() const {
410 assert(IsValid());
411 412 std::string ret;
413 ret.reserve(4);
414 ret.push_back(bech32::internal::CHARSET[m_data[1]]);
415 ret.push_back(bech32::internal::CHARSET[m_data[2]]);
416 ret.push_back(bech32::internal::CHARSET[m_data[3]]);
417 ret.push_back(bech32::internal::CHARSET[m_data[4]]);
418 return ret;
419 }
420 421 size_t Result::GetK() const {
422 assert(IsValid());
423 return bech32::internal::CHARSET[m_data[0]] - '0';
424 }
425 426 } // namespace codex32
427