Botan 3.14.1
Crypto and TLS for C&
base58.cpp
Go to the documentation of this file.
1/*
2* (C) 2018,2020,2026 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/base58.h>
8
9#include <botan/exceptn.h>
10#include <botan/hash.h>
11#include <botan/mem_ops.h>
12#include <botan/secmem.h>
13#include <botan/internal/ct_utils.h>
14#include <botan/internal/int_utils.h>
15#include <botan/internal/loadstor.h>
16#include <botan/internal/mem_utils.h>
17#include <botan/internal/mp_core.h>
18#include <algorithm>
19#include <bit>
20#include <optional>
21
22namespace Botan {
23
24namespace {
25
26uint32_t sha256_d_checksum(const uint8_t input[], size_t input_length) {
27 auto sha256 = HashFunction::create_or_throw("SHA-256");
28
29 std::vector<uint8_t> checksum(32);
30
31 sha256->update(input, input_length);
32 sha256->final(checksum);
33
34 sha256->update(checksum);
35 sha256->final(checksum);
36
37 return load_be<uint32_t>(checksum.data(), 0);
38}
39
40char lookup_base58_char(uint8_t x) {
41 // "123456789 ABCDEFGH JKLMN PQRSTUVWXYZ abcdefghijk mnopqrstuvwxyz"
42 BOTAN_DEBUG_ASSERT(x < 58);
43
44 // This works by computing offset(x) such that x + offset(x) is equal to the
45 // desired character
46
47 size_t offset = 49;
48
49 offset += CT::Mask<uint8_t>::is_gt(x, 8).if_set_return(7);
50 offset += CT::Mask<uint8_t>::is_gt(x, 16).if_set_return(1);
51 offset += CT::Mask<uint8_t>::is_gt(x, 21).if_set_return(1);
52 offset += CT::Mask<uint8_t>::is_gt(x, 32).if_set_return(6);
53 offset += CT::Mask<uint8_t>::is_gt(x, 43).if_set_return(1);
54 return static_cast<char>(x + offset);
55}
56
57consteval word base58_conversion_radix() {
58 if constexpr(sizeof(word) == 8) {
59 // 58^10 largest that fits into a 64 bit word
60 return 430804206899405824U;
61 } else {
62 // 58^5 largest that fits into a 32 bit word
63 return 656356768U;
64 }
65}
66
67consteval size_t base58_conversion_radix_digits() {
68 if constexpr(sizeof(word) == 8) {
69 return 10;
70 } else {
71 return 5;
72 }
73}
74
75/*
76* In-place constant time division of a little-endian word vector by the
77* base58 conversion radix, returning the remainder
78*/
79word ct_divmod_base58radix(std::span<word> x) {
80 constexpr auto radix58_div = divide_precomp<word>::setup(base58_conversion_radix());
81
82 word rem = 0;
83
84 for(size_t i = x.size(); i > 0; --i) {
85 const auto [q, r] = radix58_div.divmod_2to1_ct(rem, x[i - 1]);
86 x[i - 1] = q;
87 rem = r;
88 }
89
90 return rem;
91}
92
93// v = v * mul + add; requires that the result fits in v
94void ct_mul_add_word(std::span<word> v, word mul, word add) {
95 word carry = add;
96
97 for(word& w : v) {
98 w = word_madd2(w, mul, &carry);
99 }
100
101 // The final carry is provably zero for in-range inputs
102 CT::unpoison(carry);
103 BOTAN_DEBUG_ASSERT(carry == 0);
104}
105
106// Count of leading bytes equal to c, without leaking which bytes matched
107size_t ct_count_leading_eq(std::span<const uint8_t> input, uint8_t c) {
108 constexpr uint64_t lo1 = 0x0101010101010101;
109 constexpr uint64_t hi1 = lo1 << 7;
110 constexpr uint64_t lo7 = ~hi1;
111
112 size_t count = 0;
113 auto all_eq = CT::Mask<uint64_t>::set();
114
115 while(input.size() >= 8) {
116 const uint64_t x = load_le<uint64_t>(input.first<8>()) ^ (lo1 * c);
117 // 0x80 in each byte of x which is zero
118 const uint64_t z = ~(((x & lo7) + lo7) | x) & hi1;
119 // 0x80 in each byte where it and all preceding bytes are zero
120 uint64_t p = z & ((z << 8) | 0x80);
121 p &= (p << 16) | 0x8080;
122 p &= (p << 32) | 0x80808080;
123 // Number of set bytes in p
124 const uint64_t n = ((p >> 7) * lo1) >> 56;
125 count += static_cast<size_t>(all_eq.if_set_return(n));
126 all_eq &= CT::Mask<uint64_t>::is_equal(p, hi1);
127 input = input.subspan(8);
128 }
129
130 for(const uint8_t b : input) {
131 all_eq &= CT::Mask<uint64_t>::is_equal(b, c);
132 count += static_cast<size_t>(all_eq.if_set_return(1));
133 }
134
135 return count;
136}
137
138size_t ct_count_trailing_zeros(std::span<const uint8_t> input) {
139 size_t count = 0;
140 auto all_zero = CT::Mask<uint8_t>::set();
141
142 for(size_t i = input.size(); i > 0; --i) {
143 all_zero &= CT::Mask<uint8_t>::is_zero(input[i - 1]);
144 count += all_zero.if_set_return(1);
145 }
146
147 return count;
148}
149
150// Load a big-endian byte string into a little-endian word vector
151secure_vector<word> to_le_words(std::span<const uint8_t> input) {
152 secure_vector<word> v((input.size() + sizeof(word) - 1) / sizeof(word));
153
154 for(size_t i = 0; i != input.size(); ++i) {
155 const uint8_t b = input[input.size() - 1 - i];
156 v[i / sizeof(word)] |= static_cast<word>(b) << (8 * (i % sizeof(word)));
157 }
158
159 return v;
160}
161
162std::string base58_encode(std::span<word> v, size_t leading_zeros) {
163 constexpr size_t radix_digits = base58_conversion_radix_digits();
164
165 // Each division removes at least radix_bits bits, so after chunks
166 // divisions v is zero regardless of its value
167 constexpr size_t radix_bits = std::bit_width(base58_conversion_radix()) - 1;
168 const size_t chunks = (v.size() * WordInfo<word>::bits + radix_bits - 1) / radix_bits;
169
171 digits.reserve(chunks * radix_digits);
172
173 constexpr auto div_58 = divide_precomp<word>::setup(58);
174
175 for(size_t c = 0; c != chunks; ++c) {
176 word r = ct_divmod_base58radix(v);
177
178 for(size_t i = 0; i != radix_digits; ++i) {
179 const auto [q58, r58] = div_58.divmod_2to1_ct(0, r);
180 digits.push_back(static_cast<uint8_t>(r58));
181 r = q58;
182 }
183 }
184
185 // Render all digits; leading zero digits become '1', same as leading zero bytes
186 std::string result(leading_zeros + digits.size(), '1');
187
188 for(size_t i = 0; i != digits.size(); ++i) {
189 result[result.size() - 1 - i] = lookup_base58_char(digits[i]);
190 }
191
192 // Remove leading zero digits; this reveals only the output length
193 const size_t zero_digits = ct_count_trailing_zeros(digits);
194 CT::unpoison(zero_digits);
195 CT::unpoison(result);
196 result.erase(0, zero_digits);
197 return result;
198}
199
200uint8_t base58_value_of(char input) {
201 /*
202 * Alphabet: "123456789 ABCDEFGH JKLMN PQRSTUVWXYZ abcdefghijk mnopqrstuvwxyz"
203 *
204 * Valid input ranges are:
205 *
206 * '1'-'9' (length 9)
207 * 'A'-'H' (length 8)
208 * 'J'-'N' (length 5)
209 * 'P'-'Z' (length 11)
210 * 'a'-'k' (length 11)
211 * 'm'-'z' (length 14)
212 */
213 constexpr uint64_t v_lo = make_uint64(0, '1', 'A', 'J', 'P', 'a', 'm', 0);
214 constexpr uint64_t v_range = make_uint64(0, 9, 8, 5, 11, 11, 14, 0);
215
216 constexpr uint64_t expand8 = 0x0101010101010101;
217
218 const uint8_t x = static_cast<uint8_t>(input);
219 const uint64_t x8 = x * expand8; // replicate x to each byte
220
221 // is x8 in any of the ranges?
222 const uint64_t v_mask = swar_in_range<uint64_t>(x8, v_lo, v_range) ^ 0x8000000000000000;
223
224 /*
225 * Offsets mapping from the character code x to the base58 value of x in each range
226 *
227 * For example '2' (50) + 0xCF == 1
228 *
229 * Fallback byte 7 is set to 0xFF - x so that if used it results in 0xFF to indicate invalid.
230 */
231 constexpr uint64_t val_v_const = make_uint64(0, 0xCF, 0xC8, 0xC7, 0xC6, 0xC0, 0xBF, 0);
232 const uint64_t val_v = val_v_const ^ (static_cast<uint64_t>(0xFF - x) << 56);
233
234 return x + static_cast<uint8_t>(val_v >> (8 * index_of_first_set_byte(v_mask)));
235}
236
237/*
238* Decode 8 base58 characters at once
239*
240* Returns the digit value of each byte of @p w, in the same byte position, or
241* nullopt if any byte is not a valid base58 character.
242*/
243std::optional<uint64_t> base58_values_of_8(uint64_t w) {
244 constexpr uint64_t lo1 = 0x0101010101010101;
245 constexpr uint64_t hi1 = 0x8080808080808080;
246
247 // For each byte v (assumed < 0x80), 0x80 if v > c else 0x00
248 const uint64_t w80 = w | hi1;
249 const auto gt = [w80](char c) { return (w80 - lo1 * static_cast<uint8_t>(c + 1)) & hi1; };
250
251 /*
252 * Alphabet: "123456789 ABCDEFGH JKLMN PQRSTUVWXYZ abcdefghijk mnopqrstuvwxyz"
253 *
254 * This is ASCII '1' through 'z' with gaps ':'-'@', 'I', 'O', '['-'`' and
255 * 'l'. The value of a character is its ASCII code minus '1' minus the total
256 * size of the gaps below it.
257 */
258 // NOLINTBEGIN(*-confusable-identifiers)
259 const uint64_t gt_0 = gt('0');
260 const uint64_t gt_9 = gt('9');
261 const uint64_t gt_at = gt('@');
262 const uint64_t gt_H = gt('H');
263 const uint64_t gt_I = gt('I');
264 const uint64_t gt_N = gt('N');
265 const uint64_t gt_O = gt('O');
266 const uint64_t gt_Z = gt('Z');
267 const uint64_t gt_bt = gt('`');
268 const uint64_t gt_k = gt('k');
269 const uint64_t gt_l = gt('l');
270 const uint64_t gt_z = gt('z');
271 // NOLINTEND(*-confusable-identifiers)
272
273 const uint64_t in_gap = (gt_9 & ~gt_at) | (gt_H & ~gt_I) | (gt_N & ~gt_O) | (gt_Z & ~gt_bt) | (gt_k & ~gt_l);
274 const uint64_t invalid = (w & hi1) | (~gt_0 & hi1) | gt_z | in_gap;
275
276 if(invalid != 0) {
277 return std::nullopt;
278 }
279
280 // Each byte is at most 65 and for valid input no byte of w is less than its
281 // offset, so neither the sum nor the subtraction carries between bytes
282 const uint64_t offsets = lo1 * 49 + 7 * (gt_at >> 7) + (gt_I >> 7) + (gt_O >> 7) + 6 * (gt_Z >> 7) + (gt_l >> 7);
283 return w - offsets;
284}
285
286} // namespace
287
288std::string base58_encode(const uint8_t input[], size_t input_length) {
289 const auto in = std::span{input, input_length};
290 const auto poison_guard = CT::scoped_poison(in);
291
292 const size_t leading_zeros = ct_count_leading_eq(in, 0);
293 CT::unpoison(leading_zeros);
294
295 auto v = to_le_words(in);
296 return base58_encode(v, leading_zeros);
297}
298
299std::string base58_check_encode(const uint8_t input[], size_t input_length) {
300 const auto in = std::span{input, input_length};
301 const auto poison_guard = CT::scoped_poison(in);
302
303 const size_t leading_zeros = ct_count_leading_eq(in, 0);
304 CT::unpoison(leading_zeros);
305
306 secure_vector<uint8_t> buf(input_length + 4);
307 copy_mem(buf.data(), input, input_length);
308 store_be(sha256_d_checksum(input, input_length), buf.data() + input_length);
309
310 auto v = to_le_words(buf);
311 return base58_encode(v, leading_zeros);
312}
313
314std::vector<uint8_t> base58_decode(const char input[], size_t input_length) {
315 const auto in = as_span_of_bytes(input, input_length);
316
317 const size_t leading_zeros = ct_count_leading_eq(in, static_cast<uint8_t>('1'));
318
319 secure_vector<uint8_t> digits(input_length - leading_zeros);
320 size_t digit_count = 0;
321
322 auto chars = in.subspan(leading_zeros);
323
324 while(!chars.empty()) {
325 if(chars.size() >= 8) {
326 if(auto values = base58_values_of_8(load_le<uint64_t>(chars.first<8>()))) {
327 store_le(std::span{digits}.subspan(digit_count).first<8>(), *values);
328 digit_count += 8;
329 chars = chars.subspan(8);
330 continue;
331 }
332 }
333
334 // Fewer than 8 characters remain, or the block contains whitespace or an invalid character
335 const size_t n = std::min<size_t>(chars.size(), 8);
336 for(size_t i = 0; i != n; ++i) {
337 const char c = static_cast<char>(chars[i]);
338
339 if(c == ' ' || c == '\n') {
340 continue;
341 }
342
343 const uint8_t idx = base58_value_of(c);
344
345 if(idx == 0xFF) {
346 throw Decoding_Error("Invalid base58");
347 }
348
349 digits[digit_count++] = idx;
350 }
351 chars = chars.subspan(n);
352 }
353
354 digits.resize(digit_count);
355
356 // From here on the digit values are secret; only lengths are revealed
357 const auto poison_guard = CT::scoped_poison(digits);
358
359 constexpr size_t radix_digits = base58_conversion_radix_digits();
360
361 // Since 58 < 2^6, any value of digits.size() base58 digits fits in
362 // 6 bits per digit
364
365 // Combine up to radix_digits digits into a single word
366 const auto accum_digits = [](std::span<const uint8_t> chunk) {
367 BOTAN_DEBUG_ASSERT(chunk.size() <= radix_digits);
368 word accum = 0;
369 for(const uint8_t d : chunk) {
370 accum = accum * 58 + d;
371 }
372 return accum;
373 };
374
375 std::span<const uint8_t> remaining{digits};
376
377 // Consume a leading partial chunk so that all remaining chunks are full;
378 // since v is zero at this point no multiplication is needed
379 if(const size_t partial = remaining.size() % radix_digits; partial > 0) {
380 v[0] = accum_digits(remaining.first(partial));
381 remaining = remaining.subspan(partial);
382 }
383
384 while(!remaining.empty()) {
385 ct_mul_add_word(v, base58_conversion_radix(), accum_digits(remaining.first(radix_digits)));
386 remaining = remaining.subspan(radix_digits);
387 }
388
389 secure_vector<uint8_t> vbytes(v.size() * sizeof(word));
390 for(size_t i = 0; i != v.size(); ++i) {
391 store_be(v[v.size() - 1 - i], vbytes.data() + i * sizeof(word));
392 }
393
394 const size_t sig_bytes = vbytes.size() - ct_count_leading_eq(vbytes, 0);
395 CT::unpoison(sig_bytes);
396
397 std::vector<uint8_t> output(leading_zeros + sig_bytes);
398 copy_mem(output.data() + leading_zeros, vbytes.data() + vbytes.size() - sig_bytes, sig_bytes);
399 CT::unpoison(output);
400 return output;
401}
402
403std::vector<uint8_t> base58_check_decode(const char input[], size_t input_length) {
404 std::vector<uint8_t> dec = base58_decode(input, input_length);
405
406 if(dec.size() < 4) {
407 throw Decoding_Error("Invalid base58 too short for checksum");
408 }
409
410 const uint32_t computed_checksum = sha256_d_checksum(dec.data(), dec.size() - 4);
411 const uint32_t checksum = load_be<uint32_t>(&dec[dec.size() - 4], 0);
412
413 if(checksum != computed_checksum) {
414 throw Decoding_Error("Invalid base58 checksum");
415 }
416
417 dec.resize(dec.size() - 4);
418
419 return dec;
420}
421
422} // namespace Botan
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
static constexpr Mask< T > set()
Definition ct_utils.h:387
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:447
static constexpr Mask< T > is_gt(T x, T y)
Definition ct_utils.h:463
static constexpr Mask< T > is_zero(T x)
Definition ct_utils.h:442
static std::unique_ptr< HashFunction > create_or_throw(std::string_view algo_spec, std::string_view provider="")
Definition hash.cpp:311
static constexpr divide_precomp setup(W divisor)
Definition mp_core.h:695
constexpr auto scoped_poison(const Ts &... xs)
Definition ct_utils.h:222
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67
std::span< const uint8_t > as_span_of_bytes(const char *s, size_t len)
Definition mem_utils.h:59
constexpr uint64_t make_uint64(uint8_t i0, uint8_t i1, uint8_t i2, uint8_t i3, uint8_t i4, uint8_t i5, uint8_t i6, uint8_t i7)
Definition loadstor.h:121
std::vector< uint8_t > base58_check_decode(const char input[], size_t input_length)
Definition base58.cpp:403
constexpr T swar_in_range(T v, T lower, T upper)
Definition int_utils.h:144
constexpr auto word_madd2(W a, W b, W *c) -> W
Definition mp_asmi.h:111
std::string base58_encode(const uint8_t input[], size_t input_length)
Definition base58.cpp:288
constexpr size_t index_of_first_set_byte(T v)
Definition int_utils.h:160
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736
std::string base58_check_encode(const uint8_t input[], size_t input_length)
Definition base58.cpp:299
std::vector< uint8_t > base58_decode(const char input[], size_t input_length)
Definition base58.cpp:314
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:745
constexpr auto load_be(ParamTs &&... params)
Definition loadstor.h:504