2bb8192d64dc2a1e37834cf63fdd8df0241469af
1 /*
2 * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files (the
6 * "Software"), to deal in the Software without restriction, including
7 * without limitation the rights to use, copy, modify, merge, publish,
8 * distribute, sublicense, and/or sell copies of the Software, and to
9 * permit persons to whom the Software is furnished to do so, subject to
10 * the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
25 #ifndef INNER_H__
26 #define INNER_H__
28 #include <string.h>
29 #include <limits.h>
31 #include "config.h"
34 /*
35 * On MSVC, disable the warning about applying unary minus on an
36 * unsigned type: it is standard, we do it all the time, and for
37 * good reasons.
38 */
39 #if _MSC_VER
40 #pragma warning( disable : 4146 )
41 #endif
43 /*
44 * Maximum size for a RSA modulus (in bits). Allocated stack buffers
45 * depend on that size, so this value should be kept small. Currently,
46 * 2048-bit RSA keys offer adequate security, and should still do so for
47 * the next few decades; however, a number of widespread PKI have
48 * already set their root keys to RSA-4096, so we should be able to
49 * process such keys.
50 *
51 * This value MUST be a multiple of 64.
52 */
53 #define BR_MAX_RSA_SIZE 4096
55 /*
56 * Maximum size for a RSA factor (in bits). This is for RSA private-key
57 * operations. Default is to support factors up to a bit more than half
58 * the maximum modulus size.
59 *
60 * This value MUST be a multiple of 32.
61 */
62 #define BR_MAX_RSA_FACTOR ((BR_MAX_RSA_SIZE + 64) >> 1)
64 /*
65 * Maximum size for an EC curve (modulus or order), in bits. Size of
66 * stack buffers depends on that parameter. This size MUST be a multiple
67 * of 8 (so that decoding an integer with that many bytes does not
68 * overflow).
69 */
70 #define BR_MAX_EC_SIZE 528
72 /*
73 * Some macros to recognize the current architecture. Right now, we are
74 * interested into automatically recognizing architecture with efficient
75 * 64-bit types so that we may automatically use implementations that
76 * use 64-bit registers in that case. Future versions may detect, e.g.,
77 * availability of SSE2 intrinsics.
78 *
79 * If 'unsigned long' is a 64-bit type, then we assume that 64-bit types
80 * are efficient. Otherwise, we rely on macros that depend on compiler,
81 * OS and architecture. In any case, failure to detect the architecture
82 * as 64-bit means that the 32-bit code will be used, and that code
83 * works also on 64-bit architectures (the 64-bit code may simply be
84 * more efficient).
85 *
86 * The test on 'unsigned long' should already catch most cases, the one
87 * notable exception being Windows code where 'unsigned long' is kept to
88 * 32-bit for compatbility with all the legacy code that liberally uses
89 * the 'DWORD' type for 32-bit values.
90 *
91 * Macro names are taken from: http://nadeausoftware.com/articles/2012/02/c_c_tip_how_detect_processor_type_using_compiler_predefined_macros
92 */
93 #ifndef BR_64
94 #if ((ULONG_MAX >> 31) >> 31) == 3
95 #define BR_64 1
96 #elif defined(__ia64) || defined(__itanium__) || defined(_M_IA64)
97 #define BR_64 1
98 #elif defined(__powerpc64__) || defined(__ppc64__) || defined(__PPC64__) \
99 || defined(__64BIT__) || defined(_LP64) || defined(__LP64__)
100 #define BR_64 1
101 #elif defined(__sparc64__)
102 #define BR_64 1
103 #elif defined(__x86_64__) || defined(_M_X64)
104 #define BR_64 1
105 #endif
106 #endif
108 /* ==================================================================== */
109 /*
110 * Encoding/decoding functions.
111 *
112 * 32-bit and 64-bit decoding, both little-endian and big-endian, is
113 * implemented with the inline functions below. These functions are
114 * generic: they don't depend on the architecture natural endianness,
115 * and they can handle unaligned accesses. Optimized versions for some
116 * specific architectures may be implemented at a later time.
117 */
119 static inline void
120 br_enc16le(void *dst, unsigned x)
121 {
122 unsigned char *buf;
124 buf = dst;
125 buf = (unsigned char)x;
126 buf = (unsigned char)(x >> 8);
127 }
129 static inline void
130 br_enc16be(void *dst, unsigned x)
131 {
132 unsigned char *buf;
134 buf = dst;
135 buf = (unsigned char)(x >> 8);
136 buf = (unsigned char)x;
137 }
139 static inline unsigned
140 br_dec16le(const void *src)
141 {
142 const unsigned char *buf;
144 buf = src;
145 return (unsigned)buf | ((unsigned)buf << 8);
146 }
148 static inline unsigned
149 br_dec16be(const void *src)
150 {
151 const unsigned char *buf;
153 buf = src;
154 return ((unsigned)buf << 8) | (unsigned)buf;
155 }
157 static inline void
158 br_enc32le(void *dst, uint32_t x)
159 {
160 unsigned char *buf;
162 buf = dst;
163 buf = (unsigned char)x;
164 buf = (unsigned char)(x >> 8);
165 buf = (unsigned char)(x >> 16);
166 buf = (unsigned char)(x >> 24);
167 }
169 static inline void
170 br_enc32be(void *dst, uint32_t x)
171 {
172 unsigned char *buf;
174 buf = dst;
175 buf = (unsigned char)(x >> 24);
176 buf = (unsigned char)(x >> 16);
177 buf = (unsigned char)(x >> 8);
178 buf = (unsigned char)x;
179 }
181 static inline uint32_t
182 br_dec32le(const void *src)
183 {
184 const unsigned char *buf;
186 buf = src;
187 return (uint32_t)buf
188 | ((uint32_t)buf << 8)
189 | ((uint32_t)buf << 16)
190 | ((uint32_t)buf << 24);
191 }
193 static inline uint32_t
194 br_dec32be(const void *src)
195 {
196 const unsigned char *buf;
198 buf = src;
199 return ((uint32_t)buf << 24)
200 | ((uint32_t)buf << 16)
201 | ((uint32_t)buf << 8)
202 | (uint32_t)buf;
203 }
205 static inline void
206 br_enc64le(void *dst, uint64_t x)
207 {
208 unsigned char *buf;
210 buf = dst;
211 br_enc32le(buf, (uint32_t)x);
212 br_enc32le(buf + 4, (uint32_t)(x >> 32));
213 }
215 static inline void
216 br_enc64be(void *dst, uint64_t x)
217 {
218 unsigned char *buf;
220 buf = dst;
221 br_enc32be(buf, (uint32_t)(x >> 32));
222 br_enc32be(buf + 4, (uint32_t)x);
223 }
225 static inline uint64_t
226 br_dec64le(const void *src)
227 {
228 const unsigned char *buf;
230 buf = src;
231 return (uint64_t)br_dec32le(buf)
232 | ((uint64_t)br_dec32le(buf + 4) << 32);
233 }
235 static inline uint64_t
236 br_dec64be(const void *src)
237 {
238 const unsigned char *buf;
240 buf = src;
241 return ((uint64_t)br_dec32be(buf) << 32)
242 | (uint64_t)br_dec32be(buf + 4);
243 }
245 /*
246 * Range decoding and encoding (for several successive values).
247 */
248 void br_range_dec16le(uint16_t *v, size_t num, const void *src);
249 void br_range_dec16be(uint16_t *v, size_t num, const void *src);
250 void br_range_enc16le(void *dst, const uint16_t *v, size_t num);
251 void br_range_enc16be(void *dst, const uint16_t *v, size_t num);
253 void br_range_dec32le(uint32_t *v, size_t num, const void *src);
254 void br_range_dec32be(uint32_t *v, size_t num, const void *src);
255 void br_range_enc32le(void *dst, const uint32_t *v, size_t num);
256 void br_range_enc32be(void *dst, const uint32_t *v, size_t num);
258 void br_range_dec64le(uint64_t *v, size_t num, const void *src);
259 void br_range_dec64be(uint64_t *v, size_t num, const void *src);
260 void br_range_enc64le(void *dst, const uint64_t *v, size_t num);
261 void br_range_enc64be(void *dst, const uint64_t *v, size_t num);
263 /*
264 * Byte-swap a 32-bit integer.
265 */
266 static inline uint32_t
267 br_swap32(uint32_t x)
268 {
269 x = ((x & (uint32_t)0x00FF00FF) << 8)
270 | ((x >> 8) & (uint32_t)0x00FF00FF);
271 return (x << 16) | (x >> 16);
272 }
274 /* ==================================================================== */
275 /*
276 * Support code for hash functions.
277 */
279 /*
280 * IV for MD5, SHA-1, SHA-224 and SHA-256.
281 */
282 extern const uint32_t br_md5_IV[];
283 extern const uint32_t br_sha1_IV[];
284 extern const uint32_t br_sha224_IV[];
285 extern const uint32_t br_sha256_IV[];
287 /*
288 * Round functions for MD5, SHA-1, SHA-224 and SHA-256 (SHA-224 and
289 * SHA-256 use the same round function).
290 */
291 void br_md5_round(const unsigned char *buf, uint32_t *val);
292 void br_sha1_round(const unsigned char *buf, uint32_t *val);
293 void br_sha2small_round(const unsigned char *buf, uint32_t *val);
295 /*
296 * The core function for the TLS PRF. It computes
297 * P_hash(secret, label + seed), and XORs the result into the dst buffer.
298 */
299 void br_tls_phash(void *dst, size_t len,
300 const br_hash_class *dig,
301 const void *secret, size_t secret_len,
302 const char *label, const void *seed, size_t seed_len);
304 /*
305 * Copy all configured hash implementations from a multihash context
306 * to another.
307 */
308 static inline void
309 br_multihash_copyimpl(br_multihash_context *dst,
310 const br_multihash_context *src)
311 {
312 memcpy((void *)dst->impl, src->impl, sizeof src->impl);
313 }
315 /* ==================================================================== */
316 /*
317 * Constant-time primitives. These functions manipulate 32-bit values in
318 * order to provide constant-time comparisons and multiplexers.
319 *
320 * Boolean values (the "ctl" bits) MUST have value 0 or 1.
321 *
322 * Implementation notes:
323 * =====================
324 *
325 * The uintN_t types are unsigned and with width exactly N bits; the C
326 * standard guarantees that computations are performed modulo 2^N, and
327 * there can be no overflow. Negation (unary '-') works on unsigned types
328 * as well.
329 *
330 * The intN_t types are guaranteed to have width exactly N bits, with no
331 * padding bit, and using two's complement representation. Casting
332 * intN_t to uintN_t really is conversion modulo 2^N. Beware that intN_t
333 * types, being signed, trigger implementation-defined behaviour on
334 * overflow (including raising some signal): with GCC, while modular
335 * arithmetics are usually applied, the optimizer may assume that
336 * overflows don't occur (unless the -fwrapv command-line option is
337 * added); Clang has the additional -ftrapv option to explicitly trap on
338 * integer overflow or underflow.
339 */
341 /*
342 * Negate a boolean.
343 */
344 static inline uint32_t
345 NOT(uint32_t ctl)
346 {
347 return ctl ^ 1;
348 }
350 /*
351 * Multiplexer: returns x if ctl == 1, y if ctl == 0.
352 */
353 static inline uint32_t
354 MUX(uint32_t ctl, uint32_t x, uint32_t y)
355 {
356 return y ^ (-ctl & (x ^ y));
357 }
359 /*
360 * Equality check: returns 1 if x == y, 0 otherwise.
361 */
362 static inline uint32_t
363 EQ(uint32_t x, uint32_t y)
364 {
365 uint32_t q;
367 q = x ^ y;
368 return NOT((q | -q) >> 31);
369 }
371 /*
372 * Inequality check: returns 1 if x != y, 0 otherwise.
373 */
374 static inline uint32_t
375 NEQ(uint32_t x, uint32_t y)
376 {
377 uint32_t q;
379 q = x ^ y;
380 return (q | -q) >> 31;
381 }
383 /*
384 * Comparison: returns 1 if x > y, 0 otherwise.
385 */
386 static inline uint32_t
387 GT(uint32_t x, uint32_t y)
388 {
389 /*
390 * If both x < 2^31 and x < 2^31, then y-x will have its high
391 * bit set if x > y, cleared otherwise.
392 *
393 * If either x >= 2^31 or y >= 2^31 (but not both), then the
394 * result is the high bit of x.
395 *
396 * If both x >= 2^31 and y >= 2^31, then we can virtually
397 * subtract 2^31 from both, and we are back to the first case.
398 * Since (y-2^31)-(x-2^31) = y-x, the subtraction is already
399 * fine.
400 */
401 uint32_t z;
403 z = y - x;
404 return (z ^ ((x ^ y) & (x ^ z))) >> 31;
405 }
407 /*
408 * Other comparisons (greater-or-equal, lower-than, lower-or-equal).
409 */
410 #define GE(x, y) NOT(GT(y, x))
411 #define LT(x, y) GT(y, x)
412 #define LE(x, y) NOT(GT(x, y))
414 /*
415 * General comparison: returned value is -1, 0 or 1, depending on
416 * whether x is lower than, equal to, or greater than y.
417 */
418 static inline int32_t
419 CMP(uint32_t x, uint32_t y)
420 {
421 return (int32_t)GT(x, y) | -(int32_t)GT(y, x);
422 }
424 /*
425 * Returns 1 if x == 0, 0 otherwise. Take care that the operand is signed.
426 */
427 static inline uint32_t
428 EQ0(int32_t x)
429 {
430 uint32_t q;
432 q = (uint32_t)x;
433 return ~(q | -q) >> 31;
434 }
436 /*
437 * Returns 1 if x > 0, 0 otherwise. Take care that the operand is signed.
438 */
439 static inline uint32_t
440 GT0(int32_t x)
441 {
442 /*
443 * High bit of -x is 0 if x == 0, but 1 if x > 0.
444 */
445 uint32_t q;
447 q = (uint32_t)x;
448 return (~q & -q) >> 31;
449 }
451 /*
452 * Returns 1 if x >= 0, 0 otherwise. Take care that the operand is signed.
453 */
454 static inline uint32_t
455 GE0(int32_t x)
456 {
457 return ~(uint32_t)x >> 31;
458 }
460 /*
461 * Returns 1 if x < 0, 0 otherwise. Take care that the operand is signed.
462 */
463 static inline uint32_t
464 LT0(int32_t x)
465 {
466 return (uint32_t)x >> 31;
467 }
469 /*
470 * Returns 1 if x <= 0, 0 otherwise. Take care that the operand is signed.
471 */
472 static inline uint32_t
473 LE0(int32_t x)
474 {
475 uint32_t q;
477 /*
478 * ~-x has its high bit set if and only if -x is nonnegative (as
479 * a signed int), i.e. x is in the -(2^31-1) to 0 range. We must
480 * do an OR with x itself to account for x = -2^31.
481 */
482 q = (uint32_t)x;
483 return (q | ~-q) >> 31;
484 }
486 /*
487 * Conditional copy: src[] is copied into dst[] if and only if ctl is 1.
488 * dst[] and src[] may overlap completely (but not partially).
489 */
490 void br_ccopy(uint32_t ctl, void *dst, const void *src, size_t len);
492 #define CCOPY br_ccopy
494 /*
495 * Compute the bit length of a 32-bit integer. Returned value is between 0
496 * and 32 (inclusive).
497 */
498 static inline uint32_t
499 BIT_LENGTH(uint32_t x)
500 {
501 uint32_t k, c;
503 k = NEQ(x, 0);
504 c = GT(x, 0xFFFF); x = MUX(c, x >> 16, x); k += c << 4;
505 c = GT(x, 0x00FF); x = MUX(c, x >> 8, x); k += c << 3;
506 c = GT(x, 0x000F); x = MUX(c, x >> 4, x); k += c << 2;
507 c = GT(x, 0x0003); x = MUX(c, x >> 2, x); k += c << 1;
508 k += GT(x, 0x0001);
509 return k;
510 }
512 /*
513 * Compute the minimum of x and y.
514 */
515 static inline uint32_t
516 MIN(uint32_t x, uint32_t y)
517 {
518 return MUX(GT(x, y), y, x);
519 }
521 /*
522 * Compute the maximum of x and y.
523 */
524 static inline uint32_t
525 MAX(uint32_t x, uint32_t y)
526 {
527 return MUX(GT(x, y), x, y);
528 }
530 /*
531 * Multiply two 32-bit integers, with a 64-bit result. This default
532 * implementation assumes that the basic multiplication operator
533 * yields constant-time code.
534 */
535 #define MUL(x, y) ((uint64_t)(x) * (uint64_t)(y))
537 #if BR_CT_MUL31
539 /*
540 * Alternate implementation of MUL31, that will be constant-time on some
541 * (old) platforms where the default MUL31 is not. Unfortunately, it is
542 * also substantially slower, and yields larger code, on more modern
543 * platforms, which is why it is deactivated by default.
544 *
545 * MUL31_lo() must do some extra work because on some platforms, the
546 * _signed_ multiplication may return early if the top bits are 1.
547 * Simply truncating (casting) the output of MUL31() would not be
548 * sufficient, because the compiler may notice that we keep only the low
549 * word, and then replace automatically the unsigned multiplication with
550 * a signed multiplication opcode.
551 */
552 #define MUL31(x, y) ((uint64_t)((x) | (uint32_t)0x80000000) \
553 * (uint64_t)((y) | (uint32_t)0x80000000) \
554 - ((uint64_t)(x) << 31) - ((uint64_t)(y) << 31) \
555 - ((uint64_t)1 << 62))
556 static inline uint32_t
557 MUL31_lo(uint32_t x, uint32_t y)
558 {
559 uint32_t xl, xh;
560 uint32_t yl, yh;
562 xl = (x & 0xFFFF) | (uint32_t)0x80000000;
563 xh = (x >> 16) | (uint32_t)0x80000000;
564 yl = (y & 0xFFFF) | (uint32_t)0x80000000;
565 yh = (y >> 16) | (uint32_t)0x80000000;
566 return (xl * yl + ((xl * yh + xh * yl) << 16)) & (uint32_t)0x7FFFFFFF;
567 }
569 #else
571 /*
572 * Multiply two 31-bit integers, with a 62-bit result. This default
573 * implementation assumes that the basic multiplication operator
574 * yields constant-time code.
575 * The MUL31_lo() macro returns only the low 31 bits of the product.
576 */
577 #define MUL31(x, y) ((uint64_t)(x) * (uint64_t)(y))
578 #define MUL31_lo(x, y) (((uint32_t)(x) * (uint32_t)(y)) & (uint32_t)0x7FFFFFFF)
580 #endif
582 /*
583 * Multiply two words together; the sum of the lengths of the two
584 * operands must not exceed 31 (for instance, one operand may use 16
585 * bits if the other fits on 15). If BR_CT_MUL15 is non-zero, then the
586 * macro will contain some extra operations that help in making the
587 * operation constant-time on some platforms, where the basic 32-bit
588 * multiplication is not constant-time.
589 */
590 #if BR_CT_MUL15
591 #define MUL15(x, y) (((uint32_t)(x) | (uint32_t)0x80000000) \
592 * ((uint32_t)(y) | (uint32_t)0x80000000) \
593 & (uint32_t)0x7FFFFFFF)
594 #else
595 #define MUL15(x, y) ((uint32_t)(x) * (uint32_t)(y))
596 #endif
598 /*
599 * Arithmetic right shift (sign bit is copied). What happens when
600 * right-shifting a negative value is _implementation-defined_, so it
601 * does not trigger undefined behaviour, but it is still up to each
602 * compiler to define (and document) what it does. Most/all compilers
603 * will do an arithmetic shift, the sign bit being used to fill the
604 * holes; this is a native operation on the underlying CPU, and it would
605 * make little sense for the compiler to do otherwise. GCC explicitly
606 * documents that it follows that convention.
607 *
608 * Still, if BR_NO_ARITH_SHIFT is defined (and non-zero), then an
609 * alternate version will be used, that does not rely on such
610 * implementation-defined behaviour. Unfortunately, it is also slower
611 * and yields bigger code, which is why it is deactivated by default.
612 */
613 #if BR_NO_ARITH_SHIFT
614 #define ARSH(x, n) (((uint32_t)(x) >> (n)) \
615 | ((-((uint32_t)(x) >> 31)) << (32 - (n))))
616 #else
617 #define ARSH(x, n) ((*(int32_t *)&(x)) >> (n))
618 #endif
620 /*
621 * Constant-time division. The dividend hi:lo is divided by the
622 * divisor d; the quotient is returned and the remainder is written
623 * in *r. If hi == d, then the quotient does not fit on 32 bits;
624 * returned value is thus truncated. If hi > d, returned values are
625 * indeterminate.
626 */
627 uint32_t br_divrem(uint32_t hi, uint32_t lo, uint32_t d, uint32_t *r);
629 /*
630 * Wrapper for br_divrem(); the remainder is returned, and the quotient
632 */
633 static inline uint32_t
634 br_rem(uint32_t hi, uint32_t lo, uint32_t d)
635 {
636 uint32_t r;
638 br_divrem(hi, lo, d, &r);
639 return r;
640 }
642 /*
643 * Wrapper for br_divrem(); the quotient is returned, and the remainder
645 */
646 static inline uint32_t
647 br_div(uint32_t hi, uint32_t lo, uint32_t d)
648 {
649 uint32_t r;
651 return br_divrem(hi, lo, d, &r);
652 }
654 /* ==================================================================== */
656 /*
657 * Integers 'i32'
658 * --------------
659 *
660 * The 'i32' functions implement computations on big integers using
661 * an internal representation as an array of 32-bit integers. For
662 * an array x[]:
663 * -- x contains the "announced bit length" of the integer
664 * -- x, x... contain the value in little-endian order (x
665 * contains the least significant 32 bits)
666 *
667 * Multiplications rely on the elementary 32x32->64 multiplication.
668 *
669 * The announced bit length specifies the number of bits that are
670 * significant in the subsequent 32-bit words. Unused bits in the
671 * last (most significant) word are set to 0; subsequent words are
672 * uninitialized and need not exist at all.
673 *
674 * The execution time and memory access patterns of all computations
675 * depend on the announced bit length, but not on the actual word
676 * values. For modular integers, the announced bit length of any integer
677 * modulo n is equal to the actual bit length of n; thus, computations
678 * on modular integers are "constant-time" (only the modulus length may
679 * leak).
680 */
682 /*
683 * Compute the actual bit length of an integer. The argument x should
684 * point to the first (least significant) value word of the integer.
685 * The len 'xlen' contains the number of 32-bit words to access.
686 *
687 * CT: value or length of x does not leak.
688 */
689 uint32_t br_i32_bit_length(uint32_t *x, size_t xlen);
691 /*
692 * Decode an integer from its big-endian unsigned representation. The
693 * "true" bit length of the integer is computed, but all words of x[]
694 * corresponding to the full 'len' bytes of the source are set.
695 *
696 * CT: value or length of x does not leak.
697 */
698 void br_i32_decode(uint32_t *x, const void *src, size_t len);
700 /*
701 * Decode an integer from its big-endian unsigned representation. The
702 * integer MUST be lower than m[]; the announced bit length written in
703 * x[] will be equal to that of m[]. All 'len' bytes from the source are
705 *
706 * Returned value is 1 if the decode value fits within the modulus, 0
707 * otherwise. In the latter case, the x[] buffer will be set to 0 (but
708 * still with the announced bit length of m[]).
709 *
710 * CT: value or length of x does not leak. Memory access pattern depends
711 * only of 'len' and the announced bit length of m. Whether x fits or
712 * not does not leak either.
713 */
714 uint32_t br_i32_decode_mod(uint32_t *x,
715 const void *src, size_t len, const uint32_t *m);
717 /*
718 * Reduce an integer (a[]) modulo another (m[]). The result is written
719 * in x[] and its announced bit length is set to be equal to that of m[].
720 *
721 * x[] MUST be distinct from a[] and m[].
722 *
723 * CT: only announced bit lengths leak, not values of x, a or m.
724 */
725 void br_i32_reduce(uint32_t *x, const uint32_t *a, const uint32_t *m);
727 /*
728 * Decode an integer from its big-endian unsigned representation, and
729 * reduce it modulo the provided modulus m[]. The announced bit length
730 * of the result is set to be equal to that of the modulus.
731 *
732 * x[] MUST be distinct from m[].
733 */
734 void br_i32_decode_reduce(uint32_t *x,
735 const void *src, size_t len, const uint32_t *m);
737 /*
738 * Encode an integer into its big-endian unsigned representation. The
739 * output length in bytes is provided (parameter 'len'); if the length
740 * is too short then the integer is appropriately truncated; if it is
741 * too long then the extra bytes are set to 0.
742 */
743 void br_i32_encode(void *dst, size_t len, const uint32_t *x);
745 /*
746 * Multiply x[] by 2^32 and then add integer z, modulo m[]. This
747 * function assumes that x[] and m[] have the same announced bit
748 * length, and the announced bit length of m[] matches its true
749 * bit length.
750 *
751 * x[] and m[] MUST be distinct arrays.
752 *
753 * CT: only the common announced bit length of x and m leaks, not
754 * the values of x, z or m.
755 */
756 void br_i32_muladd_small(uint32_t *x, uint32_t z, const uint32_t *m);
758 /*
759 * Extract one word from an integer. The offset is counted in bits.
760 * The word MUST entirely fit within the word elements corresponding
761 * to the announced bit length of a[].
762 */
763 static inline uint32_t
764 br_i32_word(const uint32_t *a, uint32_t off)
765 {
766 size_t u;
767 unsigned j;
769 u = (size_t)(off >> 5) + 1;
770 j = (unsigned)off & 31;
771 if (j == 0) {
772 return a[u];
773 } else {
774 return (a[u] >> j) | (a[u + 1] << (32 - j));
775 }
776 }
778 /*
779 * Test whether an integer is zero.
780 */
781 uint32_t br_i32_iszero(const uint32_t *x);
783 /*
784 * Add b[] to a[] and return the carry (0 or 1). If ctl is 0, then a[]
785 * is unmodified, but the carry is still computed and returned. The
786 * arrays a[] and b[] MUST have the same announced bit length.
787 *
788 * a[] and b[] MAY be the same array, but partial overlap is not allowed.
789 */
790 uint32_t br_i32_add(uint32_t *a, const uint32_t *b, uint32_t ctl);
792 /*
793 * Subtract b[] from a[] and return the carry (0 or 1). If ctl is 0,
794 * then a[] is unmodified, but the carry is still computed and returned.
795 * The arrays a[] and b[] MUST have the same announced bit length.
796 *
797 * a[] and b[] MAY be the same array, but partial overlap is not allowed.
798 */
799 uint32_t br_i32_sub(uint32_t *a, const uint32_t *b, uint32_t ctl);
801 /*
802 * Compute d+a*b, result in d. The initial announced bit length of d[]
803 * MUST match that of a[]. The d[] array MUST be large enough to
804 * accommodate the full result, plus (possibly) an extra word. The
805 * resulting announced bit length of d[] will be the sum of the announced
806 * bit lengths of a[] and b[] (therefore, it may be larger than the actual
807 * bit length of the numerical result).
808 *
809 * a[] and b[] may be the same array. d[] must be disjoint from both a[]
810 * and b[].
811 */
812 void br_i32_mulacc(uint32_t *d, const uint32_t *a, const uint32_t *b);
814 /*
815 * Zeroize an integer. The announced bit length is set to the provided
816 * value, and the corresponding words are set to 0.
817 */
818 static inline void
819 br_i32_zero(uint32_t *x, uint32_t bit_len)
820 {
821 *x ++ = bit_len;
822 memset(x, 0, ((bit_len + 31) >> 5) * sizeof *x);
823 }
825 /*
826 * Compute -(1/x) mod 2^32. If x is even, then this function returns 0.
827 */
828 uint32_t br_i32_ninv32(uint32_t x);
830 /*
831 * Convert a modular integer to Montgomery representation. The integer x[]
832 * MUST be lower than m[], but with the same announced bit length.
833 */
834 void br_i32_to_monty(uint32_t *x, const uint32_t *m);
836 /*
837 * Convert a modular integer back from Montgomery representation. The
838 * integer x[] MUST be lower than m[], but with the same announced bit
839 * length. The "m0i" parameter is equal to -(1/m0) mod 2^32, where m0 is
840 * the least significant value word of m[] (this works only if m[] is
841 * an odd integer).
842 */
843 void br_i32_from_monty(uint32_t *x, const uint32_t *m, uint32_t m0i);
845 /*
846 * Compute a modular Montgomery multiplication. d[] is filled with the
847 * value of x*y/R modulo m[] (where R is the Montgomery factor). The
848 * array d[] MUST be distinct from x[], y[] and m[]. x[] and y[] MUST be
849 * numerically lower than m[]. x[] and y[] MAY be the same array. The
850 * "m0i" parameter is equal to -(1/m0) mod 2^32, where m0 is the least
851 * significant value word of m[] (this works only if m[] is an odd
852 * integer).
853 */
854 void br_i32_montymul(uint32_t *d, const uint32_t *x, const uint32_t *y,
855 const uint32_t *m, uint32_t m0i);
857 /*
858 * Compute a modular exponentiation. x[] MUST be an integer modulo m[]
859 * (same announced bit length, lower value). m[] MUST be odd. The
860 * exponent is in big-endian unsigned notation, over 'elen' bytes. The
861 * "m0i" parameter is equal to -(1/m0) mod 2^32, where m0 is the least
862 * significant value word of m[] (this works only if m[] is an odd
863 * integer). The t1[] and t2[] parameters must be temporary arrays,
864 * each large enough to accommodate an integer with the same size as m[].
865 */
866 void br_i32_modpow(uint32_t *x, const unsigned char *e, size_t elen,
867 const uint32_t *m, uint32_t m0i, uint32_t *t1, uint32_t *t2);
869 /* ==================================================================== */
871 /*
872 * Integers 'i31'
873 * --------------
874 *
875 * The 'i31' functions implement computations on big integers using
876 * an internal representation as an array of 32-bit integers. For
877 * an array x[]:
878 * -- x encodes the array length and the "announced bit length"
879 * of the integer: namely, if the announced bit length is k,
880 * then x = ((k / 31) << 5) + (k % 31).
881 * -- x, x... contain the value in little-endian order, 31
882 * bits per word (x contains the least significant 31 bits).
883 * The upper bit of each word is 0.
884 *
885 * Multiplications rely on the elementary 32x32->64 multiplication.
886 *
887 * The announced bit length specifies the number of bits that are
888 * significant in the subsequent 32-bit words. Unused bits in the
889 * last (most significant) word are set to 0; subsequent words are
890 * uninitialized and need not exist at all.
891 *
892 * The execution time and memory access patterns of all computations
893 * depend on the announced bit length, but not on the actual word
894 * values. For modular integers, the announced bit length of any integer
895 * modulo n is equal to the actual bit length of n; thus, computations
896 * on modular integers are "constant-time" (only the modulus length may
897 * leak).
898 */
900 /*
901 * Test whether an integer is zero.
902 */
903 uint32_t br_i31_iszero(const uint32_t *x);
905 /*
906 * Add b[] to a[] and return the carry (0 or 1). If ctl is 0, then a[]
907 * is unmodified, but the carry is still computed and returned. The
908 * arrays a[] and b[] MUST have the same announced bit length.
909 *
910 * a[] and b[] MAY be the same array, but partial overlap is not allowed.
911 */
912 uint32_t br_i31_add(uint32_t *a, const uint32_t *b, uint32_t ctl);
914 /*
915 * Subtract b[] from a[] and return the carry (0 or 1). If ctl is 0,
916 * then a[] is unmodified, but the carry is still computed and returned.
917 * The arrays a[] and b[] MUST have the same announced bit length.
918 *
919 * a[] and b[] MAY be the same array, but partial overlap is not allowed.
920 */
921 uint32_t br_i31_sub(uint32_t *a, const uint32_t *b, uint32_t ctl);
923 /*
924 * Compute the ENCODED actual bit length of an integer. The argument x
925 * should point to the first (least significant) value word of the
926 * integer. The len 'xlen' contains the number of 32-bit words to
927 * access. The upper bit of each value word MUST be 0.
928 * Returned value is ((k / 31) << 5) + (k % 31) if the bit length is k.
929 *
930 * CT: value or length of x does not leak.
931 */
932 uint32_t br_i31_bit_length(uint32_t *x, size_t xlen);
934 /*
935 * Decode an integer from its big-endian unsigned representation. The
936 * "true" bit length of the integer is computed and set in the encoded
937 * announced bit length (x), but all words of x[] corresponding to
938 * the full 'len' bytes of the source are set.
939 *
940 * CT: value or length of x does not leak.
941 */
942 void br_i31_decode(uint32_t *x, const void *src, size_t len);
944 /*
945 * Decode an integer from its big-endian unsigned representation. The
946 * integer MUST be lower than m[]; the (encoded) announced bit length
947 * written in x[] will be equal to that of m[]. All 'len' bytes from the
949 *
950 * Returned value is 1 if the decode value fits within the modulus, 0
951 * otherwise. In the latter case, the x[] buffer will be set to 0 (but
952 * still with the announced bit length of m[]).
953 *
954 * CT: value or length of x does not leak. Memory access pattern depends
955 * only of 'len' and the announced bit length of m. Whether x fits or
956 * not does not leak either.
957 */
958 uint32_t br_i31_decode_mod(uint32_t *x,
959 const void *src, size_t len, const uint32_t *m);
961 /*
962 * Zeroize an integer. The announced bit length is set to the provided
963 * value, and the corresponding words are set to 0. The ENCODED bit length
964 * is expected here.
965 */
966 static inline void
967 br_i31_zero(uint32_t *x, uint32_t bit_len)
968 {
969 *x ++ = bit_len;
970 memset(x, 0, ((bit_len + 31) >> 5) * sizeof *x);
971 }
973 /*
974 * Right-shift an integer. The shift amount must be lower than 31
975 * bits.
976 */
977 void br_i31_rshift(uint32_t *x, int count);
979 /*
980 * Reduce an integer (a[]) modulo another (m[]). The result is written
981 * in x[] and its announced bit length is set to be equal to that of m[].
982 *
983 * x[] MUST be distinct from a[] and m[].
984 *
985 * CT: only announced bit lengths leak, not values of x, a or m.
986 */
987 void br_i31_reduce(uint32_t *x, const uint32_t *a, const uint32_t *m);
989 /*
990 * Decode an integer from its big-endian unsigned representation, and
991 * reduce it modulo the provided modulus m[]. The announced bit length
992 * of the result is set to be equal to that of the modulus.
993 *
994 * x[] MUST be distinct from m[].
995 */
996 void br_i31_decode_reduce(uint32_t *x,
997 const void *src, size_t len, const uint32_t *m);
999 /*
1000 * Multiply x[] by 2^31 and then add integer z, modulo m[]. This
1001 * function assumes that x[] and m[] have the same announced bit
1002 * length, the announced bit length of m[] matches its true
1003 * bit length.
1004 *
1005 * x[] and m[] MUST be distinct arrays. z MUST fit in 31 bits (upper
1006 * bit set to 0).
1007 *
1008 * CT: only the common announced bit length of x and m leaks, not
1009 * the values of x, z or m.
1010 */
1011 void br_i31_muladd_small(uint32_t *x, uint32_t z, const uint32_t *m);
1013 /*
1014 * Encode an integer into its big-endian unsigned representation. The
1015 * output length in bytes is provided (parameter 'len'); if the length
1016 * is too short then the integer is appropriately truncated; if it is
1017 * too long then the extra bytes are set to 0.
1018 */
1019 void br_i31_encode(void *dst, size_t len, const uint32_t *x);
1021 /*
1022 * Compute -(1/x) mod 2^31. If x is even, then this function returns 0.
1023 */
1024 uint32_t br_i31_ninv31(uint32_t x);
1026 /*
1027 * Compute a modular Montgomery multiplication. d[] is filled with the
1028 * value of x*y/R modulo m[] (where R is the Montgomery factor). The
1029 * array d[] MUST be distinct from x[], y[] and m[]. x[] and y[] MUST be
1030 * numerically lower than m[]. x[] and y[] MAY be the same array. The
1031 * "m0i" parameter is equal to -(1/m0) mod 2^31, where m0 is the least
1032 * significant value word of m[] (this works only if m[] is an odd
1033 * integer).
1034 */
1035 void br_i31_montymul(uint32_t *d, const uint32_t *x, const uint32_t *y,
1036 const uint32_t *m, uint32_t m0i);
1038 /*
1039 * Convert a modular integer to Montgomery representation. The integer x[]
1040 * MUST be lower than m[], but with the same announced bit length.
1041 */
1042 void br_i31_to_monty(uint32_t *x, const uint32_t *m);
1044 /*
1045 * Convert a modular integer back from Montgomery representation. The
1046 * integer x[] MUST be lower than m[], but with the same announced bit
1047 * length. The "m0i" parameter is equal to -(1/m0) mod 2^32, where m0 is
1048 * the least significant value word of m[] (this works only if m[] is
1049 * an odd integer).
1050 */
1051 void br_i31_from_monty(uint32_t *x, const uint32_t *m, uint32_t m0i);
1053 /*
1054 * Compute a modular exponentiation. x[] MUST be an integer modulo m[]
1055 * (same announced bit length, lower value). m[] MUST be odd. The
1056 * exponent is in big-endian unsigned notation, over 'elen' bytes. The
1057 * "m0i" parameter is equal to -(1/m0) mod 2^31, where m0 is the least
1058 * significant value word of m[] (this works only if m[] is an odd
1059 * integer). The t1[] and t2[] parameters must be temporary arrays,
1060 * each large enough to accommodate an integer with the same size as m[].
1061 */
1062 void br_i31_modpow(uint32_t *x, const unsigned char *e, size_t elen,
1063 const uint32_t *m, uint32_t m0i, uint32_t *t1, uint32_t *t2);
1065 /*
1066 * Compute d+a*b, result in d. The initial announced bit length of d[]
1067 * MUST match that of a[]. The d[] array MUST be large enough to
1068 * accommodate the full result, plus (possibly) an extra word. The
1069 * resulting announced bit length of d[] will be the sum of the announced
1070 * bit lengths of a[] and b[] (therefore, it may be larger than the actual
1071 * bit length of the numerical result).
1072 *
1073 * a[] and b[] may be the same array. d[] must be disjoint from both a[]
1074 * and b[].
1075 */
1076 void br_i31_mulacc(uint32_t *d, const uint32_t *a, const uint32_t *b);
1078 /* ==================================================================== */
1080 static inline void
1081 br_i15_zero(uint16_t *x, uint16_t bit_len)
1082 {
1083 *x ++ = bit_len;
1084 memset(x, 0, ((bit_len + 15) >> 4) * sizeof *x);
1085 }
1087 uint32_t br_i15_iszero(const uint16_t *x);
1089 uint16_t br_i15_ninv15(uint16_t x);
1091 uint32_t br_i15_add(uint16_t *a, const uint16_t *b, uint32_t ctl);
1093 uint32_t br_i15_sub(uint16_t *a, const uint16_t *b, uint32_t ctl);
1095 void br_i15_muladd_small(uint16_t *x, uint16_t z, const uint16_t *m);
1097 void br_i15_montymul(uint16_t *d, const uint16_t *x, const uint16_t *y,
1098 const uint16_t *m, uint16_t m0i);
1100 void br_i15_to_monty(uint16_t *x, const uint16_t *m);
1102 void br_i15_modpow(uint16_t *x, const unsigned char *e, size_t elen,
1103 const uint16_t *m, uint16_t m0i, uint16_t *t1, uint16_t *t2);
1105 uint32_t br_i15_modpow_opt(uint16_t *x, const unsigned char *e, size_t elen,
1106 const uint16_t *m, uint16_t m0i, uint16_t *tmp, size_t twlen);
1108 void br_i15_encode(void *dst, size_t len, const uint16_t *x);
1110 uint32_t br_i15_decode_mod(uint16_t *x,
1111 const void *src, size_t len, const uint16_t *m);
1113 void br_i15_rshift(uint16_t *x, int count);
1115 uint32_t br_i15_bit_length(uint16_t *x, size_t xlen);
1117 void br_i15_decode(uint16_t *x, const void *src, size_t len);
1119 void br_i15_from_monty(uint16_t *x, const uint16_t *m, uint16_t m0i);
1121 void br_i15_decode_reduce(uint16_t *x,
1122 const void *src, size_t len, const uint16_t *m);
1124 void br_i15_reduce(uint16_t *x, const uint16_t *a, const uint16_t *m);
1126 void br_i15_mulacc(uint16_t *d, const uint16_t *a, const uint16_t *b);
1128 /* ==================================================================== */
1130 static inline size_t
1131 br_digest_size(const br_hash_class *digest_class)
1132 {
1133 return (size_t)(digest_class->desc >> BR_HASHDESC_OUT_OFF)
1135 }
1137 /*
1138 * Get the output size (in bytes) of a hash function.
1139 */
1140 size_t br_digest_size_by_ID(int digest_id);
1142 /*
1143 * Get the OID (encoded OBJECT IDENTIFIER value, without tag and length)
1144 * for a hash function. If digest_id is not a supported digest identifier
1145 * (in particular if it is equal to 0, i.e. br_md5sha1_ID), then NULL is
1146 * returned and *len is set to 0.
1147 */
1148 const unsigned char *br_digest_OID(int digest_id, size_t *len);
1150 /* ==================================================================== */
1151 /*
1152 * DES support functions.
1153 */
1155 /*
1156 * Apply DES Initial Permutation.
1157 */
1158 void br_des_do_IP(uint32_t *xl, uint32_t *xr);
1160 /*
1161 * Apply DES Final Permutation (inverse of IP).
1162 */
1163 void br_des_do_invIP(uint32_t *xl, uint32_t *xr);
1165 /*
1166 * Key schedule unit: for a DES key (8 bytes), compute 16 subkeys. Each
1167 * subkey is two 28-bit words represented as two 32-bit words; the PC-2
1168 * bit extration is NOT applied.
1169 */
1170 void br_des_keysched_unit(uint32_t *skey, const void *key);
1172 /*
1173 * Reversal of 16 DES sub-keys (for decryption).
1174 */
1175 void br_des_rev_skey(uint32_t *skey);
1177 /*
1178 * DES/3DES key schedule for 'des_tab' (encryption direction). Returned
1179 * value is the number of rounds.
1180 */
1181 unsigned br_des_tab_keysched(uint32_t *skey, const void *key, size_t key_len);
1183 /*
1184 * DES/3DES key schedule for 'des_ct' (encryption direction). Returned
1185 * value is the number of rounds.
1186 */
1187 unsigned br_des_ct_keysched(uint32_t *skey, const void *key, size_t key_len);
1189 /*
1190 * DES/3DES subkey decompression (from the compressed bitsliced subkeys).
1191 */
1192 void br_des_ct_skey_expand(uint32_t *sk_exp,
1193 unsigned num_rounds, const uint32_t *skey);
1195 /*
1196 * DES/3DES block encryption/decryption ('des_tab').
1197 */
1198 void br_des_tab_process_block(unsigned num_rounds,
1199 const uint32_t *skey, void *block);
1201 /*
1202 * DES/3DES block encryption/decryption ('des_ct').
1203 */
1204 void br_des_ct_process_block(unsigned num_rounds,
1205 const uint32_t *skey, void *block);
1207 /* ==================================================================== */
1208 /*
1209 * AES support functions.
1210 */
1212 /*
1213 * The AES S-box (256-byte table).
1214 */
1215 extern const unsigned char br_aes_S[];
1217 /*
1218 * AES key schedule. skey[] is filled with n+1 128-bit subkeys, where n
1219 * is the number of rounds (10 to 14, depending on key size). The number
1220 * of rounds is returned. If the key size is invalid (not 16, 24 or 32),
1221 * then 0 is returned.
1222 *
1223 * This implementation uses a 256-byte table and is NOT constant-time.
1224 */
1225 unsigned br_aes_keysched(uint32_t *skey, const void *key, size_t key_len);
1227 /*
1228 * AES key schedule for decryption ('aes_big' implementation).
1229 */
1230 unsigned br_aes_big_keysched_inv(uint32_t *skey,
1231 const void *key, size_t key_len);
1233 /*
1234 * AES block encryption with the 'aes_big' implementation (fast, but
1235 * not constant-time). This function encrypts a single block "in place".
1236 */
1237 void br_aes_big_encrypt(unsigned num_rounds, const uint32_t *skey, void *data);
1239 /*
1240 * AES block decryption with the 'aes_big' implementation (fast, but
1241 * not constant-time). This function decrypts a single block "in place".
1242 */
1243 void br_aes_big_decrypt(unsigned num_rounds, const uint32_t *skey, void *data);
1245 /*
1246 * AES block encryption with the 'aes_small' implementation (small, but
1247 * slow and not constant-time). This function encrypts a single block
1248 * "in place".
1249 */
1250 void br_aes_small_encrypt(unsigned num_rounds,
1251 const uint32_t *skey, void *data);
1253 /*
1254 * AES block decryption with the 'aes_small' implementation (small, but
1255 * slow and not constant-time). This function decrypts a single block
1256 * "in place".
1257 */
1258 void br_aes_small_decrypt(unsigned num_rounds,
1259 const uint32_t *skey, void *data);
1261 /*
1262 * The constant-time implementation is "bitsliced": the 128-bit state is
1263 * split over eight 32-bit words q* in the following way:
1264 *
1265 * -- Input block consists in 16 bytes:
1266 * a00 a10 a20 a30 a01 a11 a21 a31 a02 a12 a22 a32 a03 a13 a23 a33
1267 * In the terminology of FIPS 197, this is a 4x4 matrix which is read
1268 * column by column.
1269 *
1270 * -- Each byte is split into eight bits which are distributed over the
1271 * eight words, at the same rank. Thus, for a byte x at rank k, bit 0
1272 * (least significant) of x will be at rank k in q0 (if that bit is b,
1273 * then it contributes "b << k" to the value of q0), bit 1 of x will be
1274 * at rank k in q1, and so on.
1275 *
1276 * -- Ranks given to bits are in "row order" and are either all even, or
1277 * all odd. Two independent AES states are thus interleaved, one using
1278 * the even ranks, the other the odd ranks. Row order means:
1279 * a00 a01 a02 a03 a10 a11 a12 a13 a20 a21 a22 a23 a30 a31 a32 a33
1280 *
1281 * Converting input bytes from two AES blocks to bitslice representation
1282 * is done in the following way:
1283 * -- Decode first block into the four words q0 q2 q4 q6, in that order,
1284 * using little-endian convention.
1285 * -- Decode second block into the four words q1 q3 q5 q7, in that order,
1286 * using little-endian convention.
1287 * -- Call br_aes_ct_ortho().
1288 *
1289 * Converting back to bytes is done by using the reverse operations. Note
1290 * that br_aes_ct_ortho() is its own inverse.
1291 */
1293 /*
1294 * Perform bytewise orthogonalization of eight 32-bit words. Bytes
1295 * of q0..q7 are spread over all words: for a byte x that occurs
1296 * at rank i in q[j] (byte x uses bits 8*i to 8*i+7 in q[j]), the bit
1297 * of rank k in x (0 <= k <= 7) goes to q[k] at rank 8*i+j.
1298 *
1299 * This operation is an involution.
1300 */
1301 void br_aes_ct_ortho(uint32_t *q);
1303 /*
1304 * The AES S-box, as a bitsliced constant-time version. The input array
1305 * consists in eight 32-bit words; 32 S-box instances are computed in
1306 * parallel. Bits 0 to 7 of each S-box input (bit 0 is least significant)
1307 * are spread over the words 0 to 7, at the same rank.
1308 */
1309 void br_aes_ct_bitslice_Sbox(uint32_t *q);
1311 /*
1312 * Like br_aes_bitslice_Sbox(), but for the inverse S-box.
1313 */
1314 void br_aes_ct_bitslice_invSbox(uint32_t *q);
1316 /*
1317 * Compute AES encryption on bitsliced data. Since input is stored on
1318 * eight 32-bit words, two block encryptions are actually performed
1319 * in parallel.
1320 */
1321 void br_aes_ct_bitslice_encrypt(unsigned num_rounds,
1322 const uint32_t *skey, uint32_t *q);
1324 /*
1325 * Compute AES decryption on bitsliced data. Since input is stored on
1326 * eight 32-bit words, two block decryptions are actually performed
1327 * in parallel.
1328 */
1329 void br_aes_ct_bitslice_decrypt(unsigned num_rounds,
1330 const uint32_t *skey, uint32_t *q);
1332 /*
1333 * AES key schedule, constant-time version. skey[] is filled with n+1
1334 * 128-bit subkeys, where n is the number of rounds (10 to 14, depending
1335 * on key size). The number of rounds is returned. If the key size is
1336 * invalid (not 16, 24 or 32), then 0 is returned.
1337 */
1338 unsigned br_aes_ct_keysched(uint32_t *comp_skey,
1339 const void *key, size_t key_len);
1341 /*
1342 * Expand AES subkeys as produced by br_aes_ct_keysched(), into
1343 * a larger array suitable for br_aes_ct_bitslice_encrypt() and
1344 * br_aes_ct_bitslice_decrypt().
1345 */
1346 void br_aes_ct_skey_expand(uint32_t *skey,
1347 unsigned num_rounds, const uint32_t *comp_skey);
1349 /*
1350 * For the ct64 implementation, the same bitslicing technique is used,
1351 * but four instances are interleaved. First instance uses bits 0, 4,
1352 * 8, 12,... of each word; second instance uses bits 1, 5, 9, 13,...
1353 * and so on.
1354 */
1356 /*
1357 * Perform bytewise orthogonalization of eight 64-bit words. Bytes
1358 * of q0..q7 are spread over all words: for a byte x that occurs
1359 * at rank i in q[j] (byte x uses bits 8*i to 8*i+7 in q[j]), the bit
1360 * of rank k in x (0 <= k <= 7) goes to q[k] at rank 8*i+j.
1361 *
1362 * This operation is an involution.
1363 */
1364 void br_aes_ct64_ortho(uint64_t *q);
1366 /*
1367 * Interleave bytes for an AES input block. If input bytes are
1368 * denoted 0123456789ABCDEF, and have been decoded with little-endian
1369 * convention (w contains 0123, with '3' being most significant;
1370 * w contains 4567, and so on), then output word q0 will be
1371 * set to 08192A3B (again little-endian convention) and q1 will
1372 * be set to 4C5D6E7F.
1373 */
1374 void br_aes_ct64_interleave_in(uint64_t *q0, uint64_t *q1, const uint32_t *w);
1376 /*
1377 * Perform the opposite of br_aes_ct64_interleave_in().
1378 */
1379 void br_aes_ct64_interleave_out(uint32_t *w, uint64_t q0, uint64_t q1);
1381 /*
1382 * The AES S-box, as a bitsliced constant-time version. The input array
1383 * consists in eight 64-bit words; 64 S-box instances are computed in
1384 * parallel. Bits 0 to 7 of each S-box input (bit 0 is least significant)
1385 * are spread over the words 0 to 7, at the same rank.
1386 */
1387 void br_aes_ct64_bitslice_Sbox(uint64_t *q);
1389 /*
1390 * Like br_aes_bitslice_Sbox(), but for the inverse S-box.
1391 */
1392 void br_aes_ct64_bitslice_invSbox(uint64_t *q);
1394 /*
1395 * Compute AES encryption on bitsliced data. Since input is stored on
1396 * eight 64-bit words, four block encryptions are actually performed
1397 * in parallel.
1398 */
1399 void br_aes_ct64_bitslice_encrypt(unsigned num_rounds,
1400 const uint64_t *skey, uint64_t *q);
1402 /*
1403 * Compute AES decryption on bitsliced data. Since input is stored on
1404 * eight 64-bit words, four block decryptions are actually performed
1405 * in parallel.
1406 */
1407 void br_aes_ct64_bitslice_decrypt(unsigned num_rounds,
1408 const uint64_t *skey, uint64_t *q);
1410 /*
1411 * AES key schedule, constant-time version. skey[] is filled with n+1
1412 * 128-bit subkeys, where n is the number of rounds (10 to 14, depending
1413 * on key size). The number of rounds is returned. If the key size is
1414 * invalid (not 16, 24 or 32), then 0 is returned.
1415 */
1416 unsigned br_aes_ct64_keysched(uint64_t *comp_skey,
1417 const void *key, size_t key_len);
1419 /*
1420 * Expand AES subkeys as produced by br_aes_ct64_keysched(), into
1421 * a larger array suitable for br_aes_ct64_bitslice_encrypt() and
1422 * br_aes_ct64_bitslice_decrypt().
1423 */
1424 void br_aes_ct64_skey_expand(uint64_t *skey,
1425 unsigned num_rounds, const uint64_t *comp_skey);
1427 /* ==================================================================== */
1428 /*
1429 * RSA.
1430 */
1432 /*
1433 * Apply proper PKCS#1 v1.5 padding (for signatures). 'hash_oid' is
1434 * the encoded hash function OID, or NULL.
1435 */
1436 uint32_t br_rsa_pkcs1_sig_pad(const unsigned char *hash_oid,
1437 const unsigned char *hash, size_t hash_len,
1438 uint32_t n_bitlen, unsigned char *x);
1440 /*
1441 * Check PKCS#1 v1.5 padding (for signatures). 'hash_oid' is the encoded
1442 * hash function OID, or NULL. The provided 'sig' value is _after_ the
1443 * modular exponentiation, i.e. it should be the padded hash. On
1444 * success, the hashed message is extracted.
1445 */
1446 uint32_t br_rsa_pkcs1_sig_unpad(const unsigned char *sig, size_t sig_len,
1447 const unsigned char *hash_oid, size_t hash_len,
1448 unsigned char *hash_out);
1450 /* ==================================================================== */
1451 /*
1452 * Elliptic curves.
1453 */
1455 /*
1456 * Type for generic EC parameters: curve order (unsigned big-endian
1457 * encoding) and encoded conventional generator.
1458 */
1459 typedef struct {
1460 int curve;
1461 const unsigned char *order;
1462 size_t order_len;
1463 const unsigned char *generator;
1464 size_t generator_len;
1465 } br_ec_curve_def;
1467 extern const br_ec_curve_def br_secp256r1;
1468 extern const br_ec_curve_def br_secp384r1;
1469 extern const br_ec_curve_def br_secp521r1;
1471 /*
1472 * For Curve25519, the advertised "order" really is 2^255-1, since the
1473 * point multipliction function really works over arbitrary 255-bit
1474 * scalars. This value is only meant as a hint for ECDH key generation;
1475 * only ECDSA uses the exact curve order, and ECDSA is not used with
1476 * that specific curve.
1477 */
1478 extern const br_ec_curve_def br_curve25519;
1480 /*
1481 * Decode some bytes as an i31 integer, with truncation (corresponding
1482 * to the 'bits2int' operation in RFC 6979). The target ENCODED bit
1483 * length is provided as last parameter. The resulting value will have
1484 * this declared bit length, and consists the big-endian unsigned decoding
1485 * of exactly that many bits in the source (capped at the source length).
1486 */
1487 void br_ecdsa_i31_bits2int(uint32_t *x,
1488 const void *src, size_t len, uint32_t ebitlen);
1490 /*
1491 * Decode some bytes as an i15 integer, with truncation (corresponding
1492 * to the 'bits2int' operation in RFC 6979). The target ENCODED bit
1493 * length is provided as last parameter. The resulting value will have
1494 * this declared bit length, and consists the big-endian unsigned decoding
1495 * of exactly that many bits in the source (capped at the source length).
1496 */
1497 void br_ecdsa_i15_bits2int(uint16_t *x,
1498 const void *src, size_t len, uint32_t ebitlen);
1500 /* ==================================================================== */
1501 /*
1502 * SSL/TLS support functions.
1503 */
1505 /*
1506 * Record types.
1507 */
1508 #define BR_SSL_CHANGE_CIPHER_SPEC 20
1510 #define BR_SSL_HANDSHAKE 22
1511 #define BR_SSL_APPLICATION_DATA 23
1513 /*
1514 * Handshake message types.
1515 */
1516 #define BR_SSL_HELLO_REQUEST 0
1517 #define BR_SSL_CLIENT_HELLO 1
1518 #define BR_SSL_SERVER_HELLO 2
1519 #define BR_SSL_CERTIFICATE 11
1520 #define BR_SSL_SERVER_KEY_EXCHANGE 12
1521 #define BR_SSL_CERTIFICATE_REQUEST 13
1522 #define BR_SSL_SERVER_HELLO_DONE 14
1523 #define BR_SSL_CERTIFICATE_VERIFY 15
1524 #define BR_SSL_CLIENT_KEY_EXCHANGE 16
1525 #define BR_SSL_FINISHED 20
1527 /*
1529 */
1530 #define BR_LEVEL_WARNING 1
1531 #define BR_LEVEL_FATAL 2
1533 /*
1534 * Low-level I/O state.
1535 */
1536 #define BR_IO_FAILED 0
1537 #define BR_IO_IN 1
1538 #define BR_IO_OUT 2
1539 #define BR_IO_INOUT 3
1541 /*
1542 * Mark a SSL engine as failed. The provided error code is recorded if
1543 * the engine was not already marked as failed. If 'err' is 0, then the
1544 * engine is marked as closed (without error).
1545 */
1546 void br_ssl_engine_fail(br_ssl_engine_context *cc, int err);
1548 /*
1549 * Test whether the engine is closed (normally or as a failure).
1550 */
1551 static inline int
1552 br_ssl_engine_closed(const br_ssl_engine_context *cc)
1553 {
1554 return cc->iomode == BR_IO_FAILED;
1555 }
1557 /*
1558 * Configure a new maximum fragment length. If possible, the maximum
1559 * length for outgoing records is immediately adjusted (if there are
1560 * not already too many buffered bytes for that).
1561 */
1562 void br_ssl_engine_new_max_frag_len(
1563 br_ssl_engine_context *rc, unsigned max_frag_len);
1565 /*
1566 * Test whether the current incoming record has been fully received
1567 * or not. This functions returns 0 only if a complete record header
1568 * has been received, but some of the (possibly encrypted) payload
1569 * has not yet been obtained.
1570 */
1571 int br_ssl_engine_recvrec_finished(const br_ssl_engine_context *rc);
1573 /*
1574 * Flush the current record (if not empty). This is meant to be called
1575 * from the handshake processor only.
1576 */
1577 void br_ssl_engine_flush_record(br_ssl_engine_context *cc);
1579 /*
1580 * Test whether there is some accumulated payload to send.
1581 */
1582 static inline int
1583 br_ssl_engine_has_pld_to_send(const br_ssl_engine_context *rc)
1584 {
1585 return rc->oxa != rc->oxb && rc->oxa != rc->oxc;
1586 }
1588 /*
1589 * Initialize RNG in engine. Returned value is 1 on success, 0 on error.
1590 * This function will try to use the OS-provided RNG, if available. If
1591 * there is no OS-provided RNG, or if it failed, and no entropy was
1592 * injected by the caller, then a failure will be reported. On error,
1593 * the context error code is set.
1594 */
1595 int br_ssl_engine_init_rand(br_ssl_engine_context *cc);
1597 /*
1598 * Reset the handshake-related parts of the engine.
1599 */
1600 void br_ssl_engine_hs_reset(br_ssl_engine_context *cc,
1601 void (*hsinit)(void *), void (*hsrun)(void *));
1603 /*
1604 * Get the PRF to use for this context, for the provided PRF hash
1605 * function ID.
1606 */
1607 br_tls_prf_impl br_ssl_engine_get_PRF(br_ssl_engine_context *cc, int prf_id);
1609 /*
1610 * Consume the provided pre-master secret and compute the corresponding
1611 * master secret. The 'prf_id' is the ID of the hash function to use
1612 * with the TLS 1.2 PRF (ignored if the version is TLS 1.0 or 1.1).
1613 */
1614 void br_ssl_engine_compute_master(br_ssl_engine_context *cc,
1615 int prf_id, const void *pms, size_t len);
1617 /*
1618 * Switch to CBC decryption for incoming records.
1619 * cc the engine context
1620 * is_client non-zero for a client, zero for a server
1621 * prf_id id of hash function for PRF (ignored if not TLS 1.2+)
1622 * mac_id id of hash function for HMAC
1623 * bc_impl block cipher implementation (CBC decryption)
1624 * cipher_key_len block cipher key length (in bytes)
1625 */
1626 void br_ssl_engine_switch_cbc_in(br_ssl_engine_context *cc,
1627 int is_client, int prf_id, int mac_id,
1628 const br_block_cbcdec_class *bc_impl, size_t cipher_key_len);
1630 /*
1631 * Switch to CBC encryption for outgoing records.
1632 * cc the engine context
1633 * is_client non-zero for a client, zero for a server
1634 * prf_id id of hash function for PRF (ignored if not TLS 1.2+)
1635 * mac_id id of hash function for HMAC
1636 * bc_impl block cipher implementation (CBC encryption)
1637 * cipher_key_len block cipher key length (in bytes)
1638 */
1639 void br_ssl_engine_switch_cbc_out(br_ssl_engine_context *cc,
1640 int is_client, int prf_id, int mac_id,
1641 const br_block_cbcenc_class *bc_impl, size_t cipher_key_len);
1643 /*
1644 * Switch to GCM decryption for incoming records.
1645 * cc the engine context
1646 * is_client non-zero for a client, zero for a server
1647 * prf_id id of hash function for PRF
1648 * bc_impl block cipher implementation (CTR)
1649 * cipher_key_len block cipher key length (in bytes)
1650 */
1651 void br_ssl_engine_switch_gcm_in(br_ssl_engine_context *cc,
1652 int is_client, int prf_id,
1653 const br_block_ctr_class *bc_impl, size_t cipher_key_len);
1655 /*
1656 * Switch to GCM encryption for outgoing records.
1657 * cc the engine context
1658 * is_client non-zero for a client, zero for a server
1659 * prf_id id of hash function for PRF
1660 * bc_impl block cipher implementation (CTR)
1661 * cipher_key_len block cipher key length (in bytes)
1662 */
1663 void br_ssl_engine_switch_gcm_out(br_ssl_engine_context *cc,
1664 int is_client, int prf_id,
1665 const br_block_ctr_class *bc_impl, size_t cipher_key_len);
1667 /*
1668 * Switch to ChaCha20+Poly1305 decryption for incoming records.
1669 * cc the engine context
1670 * is_client non-zero for a client, zero for a server
1671 * prf_id id of hash function for PRF
1672 */
1673 void br_ssl_engine_switch_chapol_in(br_ssl_engine_context *cc,
1674 int is_client, int prf_id);
1676 /*
1677 * Switch to ChaCha20+Poly1305 encryption for outgoing records.
1678 * cc the engine context
1679 * is_client non-zero for a client, zero for a server
1680 * prf_id id of hash function for PRF
1681 */
1682 void br_ssl_engine_switch_chapol_out(br_ssl_engine_context *cc,
1683 int is_client, int prf_id);
1685 /*
1686 * Calls to T0-generated code.
1687 */
1688 void br_ssl_hs_client_init_main(void *ctx);
1689 void br_ssl_hs_client_run(void *ctx);
1690 void br_ssl_hs_server_init_main(void *ctx);
1691 void br_ssl_hs_server_run(void *ctx);
1693 /*
1694 * Get the hash function to use for signatures, given a bit mask of
1695 * supported hash functions. This implements a strict choice order
1696 * (namely SHA-256, SHA-384, SHA-512, SHA-224, SHA-1). If the mask
1697 * does not document support of any of these hash functions, then this
1698 * functions returns 0.
1699 */
1700 int br_ssl_choose_hash(unsigned bf);
1702 /* ==================================================================== */
1704 #endif
{"ft_lang_label":"__label__en","ft_lang_prob":0.67170477,"math_prob":0.9465274,"size":53786,"snap":"2023-14-2023-23","text_gpt3_token_len":15484,"char_repetition_ratio":0.18119445,"word_repetition_ratio":0.2554259,"special_character_ratio":0.3829249,"punctuation_ratio":0.12581833,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9510135,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-06-09T10:47:08Z\",\"WARC-Record-ID\":\"<urn:uuid:e64e6207-f831-4e70-ab67-2f16d483ef7c>\",\"Content-Length\":\"426148\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:2a5570b4-7baa-4d1f-8ae8-f05c28f9fe12>\",\"WARC-Concurrent-To\":\"<urn:uuid:820881cb-b0da-439d-b5f2-c8c8a6bdcd71>\",\"WARC-IP-Address\":\"158.69.204.153\",\"WARC-Target-URI\":\"https://bearssl.org/gitweb/?p=BearSSL;a=blob;f=src/inner.h;h=2bb8192d64dc2a1e37834cf63fdd8df0241469af\",\"WARC-Payload-Digest\":\"sha1:YBZPWEXXXMNSHZ4WPJBJ6MMIEMOGY7KA\",\"WARC-Block-Digest\":\"sha1:OTLNKKYCRUEHEERTOIRC4JMCICD2TAJW\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224656675.90_warc_CC-MAIN-20230609100535-20230609130535-00037.warc.gz\"}"}