2 * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
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:
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
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
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
40 #pragma warning( disable : 4146 )
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
51 * This value MUST be a multiple of 64.
53 #define BR_MAX_RSA_SIZE 4096
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.
60 * This value MUST be a multiple of 32.
62 #define BR_MAX_RSA_FACTOR ((BR_MAX_RSA_SIZE + 64) >> 1)
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
70 #define BR_MAX_EC_SIZE 528
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.
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
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.
91 * Macro names are taken from: http://nadeausoftware.com/articles/2012/02/c_c_tip_how_detect_processor_type_using_compiler_predefined_macros
94 #if ((ULONG_MAX >> 31) >> 31) == 3
96 #elif defined(__ia64) || defined(__itanium__) || defined(_M_IA64)
98 #elif defined(__powerpc64__) || defined(__ppc64__) || defined(__PPC64__) \
99 || defined(__64BIT__) || defined(_LP64) || defined(__LP64__)
101 #elif defined(__sparc64__)
103 #elif defined(__x86_64__) || defined(_M_X64)
109 * Set BR_LOMUL on platforms where it makes sense.
112 #if BR_ARMEL_CORTEX_GCC
118 * Determine whether x86 AES instructions are understood by the compiler.
121 #if (__i386__ || __x86_64__) \
122 && ((__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)) \
123 || (__clang_major__ > 3 \
124 || (__clang_major__ == 3 && __clang_minor__ >= 7)))
125 #define BR_AES_X86NI 1
126 #elif (_M_IX86 || _M_X64) && (_MSC_VER >= 1700)
127 #define BR_AES_X86NI 1
132 * If we use x86 AES instruction, determine the compiler brand.
135 #ifndef BR_AES_X86NI_GCC
137 #define BR_AES_X86NI_GCC 1
140 #ifndef BR_AES_X86NI_MSC
142 #define BR_AES_X86NI_MSC 1
148 * Determine whether SSE2 intrinsics are understood by the compiler.
149 * Right now, we restrict ourselves to compiler versions where things
150 * are documented to work well:
151 * -- GCC 4.4+ and Clang 3.7+ understand the function attribute "target"
152 * -- MS Visual Studio 2005 documents the existence of <emmintrin.h>
153 * SSE2-powered code _might_ work with older versions, but there is no
154 * pressing need to do so right now.
157 #if (__i386__ || __x86_64__) \
158 && ((__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 4)) \
159 || (__clang_major__ > 3 \
160 || (__clang_major__ == 3 && __clang_minor__ >= 7)))
162 #elif (_M_IX86 || _M_X64) && (_MSC_VER >= 1400)
168 * If we use SSE2 intrinsics, determine the compiler brand.
173 #define BR_SSE2_GCC 1
178 #define BR_SSE2_MSC 1
184 * A macro to tag a function with a "target" attribute (for GCC and Clang).
186 #if BR_AES_X86NI_GCC || BR_SSE2_GCC
187 #define BR_TARGET(x) __attribute__((target(x)))
193 * GCC versions from 4.4 to 4.8 (inclusive) must use a special #pragma
194 * to activate extra opcodes before including the relevant intrinsic
195 * AES-NI headers. But these don't work with Clang (which does not need
196 * them either). We also need that #pragma for GCC 4.9 in order to work
197 * around a compiler bug (it tends to blow up on ghash_pclmul code
200 #if BR_AES_X86NI_GCC && !defined BR_AES_X86NI_GCC_OLD
201 #if __GNUC__ == 4 && __GNUC_MINOR__ >= 4 && __GNUC_MINOR__ <= 9 && !__clang__
202 #define BR_AES_X86NI_GCC_OLD 1
207 * POWER8 crypto support. We rely on compiler macros for the
208 * architecture, since we do not have a reliable, simple way to detect
209 * the required support at runtime (we could try running an opcode, and
210 * trapping the exception or signal on illegal instruction, but this
211 * induces some non-trivial OS dependencies that we would prefer to
212 * avoid if possible).
215 #if __GNUC__ && ((_ARCH_PWR8 || _ARCH_PPC) && __CRYPTO__)
221 * Detect endinanness on POWER8.
224 #if defined BR_POWER8_LE
227 #define BR_POWER8_BE 0
229 #define BR_POWER8_BE 1
231 #elif defined BR_POWER8_BE
234 #define BR_POWER8_LE 0
236 #define BR_POWER8_LE 1
239 #if __LITTLE_ENDIAN__
240 #define BR_POWER8_LE 1
241 #define BR_POWER8_BE 0
243 #define BR_POWER8_LE 0
244 #define BR_POWER8_BE 1
250 * Detect support for 128-bit integers.
252 #if !defined BR_INT128 && !defined BR_UMUL128
253 #ifdef __SIZEOF_INT128__
261 * Detect support for unaligned accesses with known endianness.
263 * x86 (both 32-bit and 64-bit) is little-endian and allows unaligned
266 * POWER/PowerPC allows unaligned accesses when big-endian. POWER8 and
267 * later also allow unaligned accesses when little-endian.
269 #if !defined BR_LE_UNALIGNED && !defined BR_BE_UNALIGNED
271 #if __i386 || __i386__ || __x86_64__ || _M_IX86 || _M_X64
272 #define BR_LE_UNALIGNED 1
274 #define BR_BE_UNALIGNED 1
276 #define BR_LE_UNALIGNED 1
277 #elif (__powerpc__ || __powerpc64__ || _M_PPC || _ARCH_PPC || _ARCH_PPC64) \
279 #define BR_BE_UNALIGNED 1
284 /* ==================================================================== */
286 * Encoding/decoding functions.
288 * 32-bit and 64-bit decoding, both little-endian and big-endian, is
289 * implemented with the inline functions below.
291 * When allowed by some compile-time options (autodetected or provided),
292 * optimised code is used, to perform direct memory access when the
293 * underlying architecture supports it, both for endianness and
294 * alignment. This, however, may trigger strict aliasing issues; the
295 * code below uses unions to perform (supposedly) safe type punning.
296 * Since the C aliasing rules are relatively complex and were amended,
297 * or at least re-explained with different phrasing, in all successive
298 * versions of the C standard, it is always a bit risky to bet that any
299 * specific version of a C compiler got it right, for some notion of
305 unsigned char b
[sizeof(uint16_t)];
310 unsigned char b
[sizeof(uint32_t)];
315 unsigned char b
[sizeof(uint64_t)];
319 br_enc16le(void *dst
, unsigned x
)
322 ((br_union_u16
*)dst
)->u
= x
;
327 buf
[0] = (unsigned char)x
;
328 buf
[1] = (unsigned char)(x
>> 8);
333 br_enc16be(void *dst
, unsigned x
)
336 ((br_union_u16
*)dst
)->u
= x
;
341 buf
[0] = (unsigned char)(x
>> 8);
342 buf
[1] = (unsigned char)x
;
346 static inline unsigned
347 br_dec16le(const void *src
)
350 return ((const br_union_u16
*)src
)->u
;
352 const unsigned char *buf
;
355 return (unsigned)buf
[0] | ((unsigned)buf
[1] << 8);
359 static inline unsigned
360 br_dec16be(const void *src
)
363 return ((const br_union_u16
*)src
)->u
;
365 const unsigned char *buf
;
368 return ((unsigned)buf
[0] << 8) | (unsigned)buf
[1];
373 br_enc32le(void *dst
, uint32_t x
)
376 ((br_union_u32
*)dst
)->u
= x
;
381 buf
[0] = (unsigned char)x
;
382 buf
[1] = (unsigned char)(x
>> 8);
383 buf
[2] = (unsigned char)(x
>> 16);
384 buf
[3] = (unsigned char)(x
>> 24);
389 br_enc32be(void *dst
, uint32_t x
)
392 ((br_union_u32
*)dst
)->u
= x
;
397 buf
[0] = (unsigned char)(x
>> 24);
398 buf
[1] = (unsigned char)(x
>> 16);
399 buf
[2] = (unsigned char)(x
>> 8);
400 buf
[3] = (unsigned char)x
;
404 static inline uint32_t
405 br_dec32le(const void *src
)
408 return ((const br_union_u32
*)src
)->u
;
410 const unsigned char *buf
;
413 return (uint32_t)buf
[0]
414 | ((uint32_t)buf
[1] << 8)
415 | ((uint32_t)buf
[2] << 16)
416 | ((uint32_t)buf
[3] << 24);
420 static inline uint32_t
421 br_dec32be(const void *src
)
424 return ((const br_union_u32
*)src
)->u
;
426 const unsigned char *buf
;
429 return ((uint32_t)buf
[0] << 24)
430 | ((uint32_t)buf
[1] << 16)
431 | ((uint32_t)buf
[2] << 8)
437 br_enc64le(void *dst
, uint64_t x
)
440 ((br_union_u64
*)dst
)->u
= x
;
445 br_enc32le(buf
, (uint32_t)x
);
446 br_enc32le(buf
+ 4, (uint32_t)(x
>> 32));
451 br_enc64be(void *dst
, uint64_t x
)
454 ((br_union_u64
*)dst
)->u
= x
;
459 br_enc32be(buf
, (uint32_t)(x
>> 32));
460 br_enc32be(buf
+ 4, (uint32_t)x
);
464 static inline uint64_t
465 br_dec64le(const void *src
)
468 return ((const br_union_u64
*)src
)->u
;
470 const unsigned char *buf
;
473 return (uint64_t)br_dec32le(buf
)
474 | ((uint64_t)br_dec32le(buf
+ 4) << 32);
478 static inline uint64_t
479 br_dec64be(const void *src
)
482 return ((const br_union_u64
*)src
)->u
;
484 const unsigned char *buf
;
487 return ((uint64_t)br_dec32be(buf
) << 32)
488 | (uint64_t)br_dec32be(buf
+ 4);
493 * Range decoding and encoding (for several successive values).
495 void br_range_dec16le(uint16_t *v
, size_t num
, const void *src
);
496 void br_range_dec16be(uint16_t *v
, size_t num
, const void *src
);
497 void br_range_enc16le(void *dst
, const uint16_t *v
, size_t num
);
498 void br_range_enc16be(void *dst
, const uint16_t *v
, size_t num
);
500 void br_range_dec32le(uint32_t *v
, size_t num
, const void *src
);
501 void br_range_dec32be(uint32_t *v
, size_t num
, const void *src
);
502 void br_range_enc32le(void *dst
, const uint32_t *v
, size_t num
);
503 void br_range_enc32be(void *dst
, const uint32_t *v
, size_t num
);
505 void br_range_dec64le(uint64_t *v
, size_t num
, const void *src
);
506 void br_range_dec64be(uint64_t *v
, size_t num
, const void *src
);
507 void br_range_enc64le(void *dst
, const uint64_t *v
, size_t num
);
508 void br_range_enc64be(void *dst
, const uint64_t *v
, size_t num
);
511 * Byte-swap a 32-bit integer.
513 static inline uint32_t
514 br_swap32(uint32_t x
)
516 x
= ((x
& (uint32_t)0x00FF00FF) << 8)
517 | ((x
>> 8) & (uint32_t)0x00FF00FF);
518 return (x
<< 16) | (x
>> 16);
521 /* ==================================================================== */
523 * Support code for hash functions.
527 * IV for MD5, SHA-1, SHA-224 and SHA-256.
529 extern const uint32_t br_md5_IV
[];
530 extern const uint32_t br_sha1_IV
[];
531 extern const uint32_t br_sha224_IV
[];
532 extern const uint32_t br_sha256_IV
[];
535 * Round functions for MD5, SHA-1, SHA-224 and SHA-256 (SHA-224 and
536 * SHA-256 use the same round function).
538 void br_md5_round(const unsigned char *buf
, uint32_t *val
);
539 void br_sha1_round(const unsigned char *buf
, uint32_t *val
);
540 void br_sha2small_round(const unsigned char *buf
, uint32_t *val
);
543 * The core function for the TLS PRF. It computes
544 * P_hash(secret, label + seed), and XORs the result into the dst buffer.
546 void br_tls_phash(void *dst
, size_t len
,
547 const br_hash_class
*dig
,
548 const void *secret
, size_t secret_len
, const char *label
,
549 size_t seed_num
, const br_tls_prf_seed_chunk
*seed
);
552 * Copy all configured hash implementations from a multihash context
556 br_multihash_copyimpl(br_multihash_context
*dst
,
557 const br_multihash_context
*src
)
559 memcpy((void *)dst
->impl
, src
->impl
, sizeof src
->impl
);
562 /* ==================================================================== */
564 * Constant-time primitives. These functions manipulate 32-bit values in
565 * order to provide constant-time comparisons and multiplexers.
567 * Boolean values (the "ctl" bits) MUST have value 0 or 1.
569 * Implementation notes:
570 * =====================
572 * The uintN_t types are unsigned and with width exactly N bits; the C
573 * standard guarantees that computations are performed modulo 2^N, and
574 * there can be no overflow. Negation (unary '-') works on unsigned types
577 * The intN_t types are guaranteed to have width exactly N bits, with no
578 * padding bit, and using two's complement representation. Casting
579 * intN_t to uintN_t really is conversion modulo 2^N. Beware that intN_t
580 * types, being signed, trigger implementation-defined behaviour on
581 * overflow (including raising some signal): with GCC, while modular
582 * arithmetics are usually applied, the optimizer may assume that
583 * overflows don't occur (unless the -fwrapv command-line option is
584 * added); Clang has the additional -ftrapv option to explicitly trap on
585 * integer overflow or underflow.
591 static inline uint32_t
598 * Multiplexer: returns x if ctl == 1, y if ctl == 0.
600 static inline uint32_t
601 MUX(uint32_t ctl
, uint32_t x
, uint32_t y
)
603 return y
^ (-ctl
& (x
^ y
));
607 * Equality check: returns 1 if x == y, 0 otherwise.
609 static inline uint32_t
610 EQ(uint32_t x
, uint32_t y
)
615 return NOT((q
| -q
) >> 31);
619 * Inequality check: returns 1 if x != y, 0 otherwise.
621 static inline uint32_t
622 NEQ(uint32_t x
, uint32_t y
)
627 return (q
| -q
) >> 31;
631 * Comparison: returns 1 if x > y, 0 otherwise.
633 static inline uint32_t
634 GT(uint32_t x
, uint32_t y
)
637 * If both x < 2^31 and x < 2^31, then y-x will have its high
638 * bit set if x > y, cleared otherwise.
640 * If either x >= 2^31 or y >= 2^31 (but not both), then the
641 * result is the high bit of x.
643 * If both x >= 2^31 and y >= 2^31, then we can virtually
644 * subtract 2^31 from both, and we are back to the first case.
645 * Since (y-2^31)-(x-2^31) = y-x, the subtraction is already
651 return (z
^ ((x
^ y
) & (x
^ z
))) >> 31;
655 * Other comparisons (greater-or-equal, lower-than, lower-or-equal).
657 #define GE(x, y) NOT(GT(y, x))
658 #define LT(x, y) GT(y, x)
659 #define LE(x, y) NOT(GT(x, y))
662 * General comparison: returned value is -1, 0 or 1, depending on
663 * whether x is lower than, equal to, or greater than y.
665 static inline int32_t
666 CMP(uint32_t x
, uint32_t y
)
668 return (int32_t)GT(x
, y
) | -(int32_t)GT(y
, x
);
672 * Returns 1 if x == 0, 0 otherwise. Take care that the operand is signed.
674 static inline uint32_t
680 return ~(q
| -q
) >> 31;
684 * Returns 1 if x > 0, 0 otherwise. Take care that the operand is signed.
686 static inline uint32_t
690 * High bit of -x is 0 if x == 0, but 1 if x > 0.
695 return (~q
& -q
) >> 31;
699 * Returns 1 if x >= 0, 0 otherwise. Take care that the operand is signed.
701 static inline uint32_t
704 return ~(uint32_t)x
>> 31;
708 * Returns 1 if x < 0, 0 otherwise. Take care that the operand is signed.
710 static inline uint32_t
713 return (uint32_t)x
>> 31;
717 * Returns 1 if x <= 0, 0 otherwise. Take care that the operand is signed.
719 static inline uint32_t
725 * ~-x has its high bit set if and only if -x is nonnegative (as
726 * a signed int), i.e. x is in the -(2^31-1) to 0 range. We must
727 * do an OR with x itself to account for x = -2^31.
730 return (q
| ~-q
) >> 31;
734 * Conditional copy: src[] is copied into dst[] if and only if ctl is 1.
735 * dst[] and src[] may overlap completely (but not partially).
737 void br_ccopy(uint32_t ctl
, void *dst
, const void *src
, size_t len
);
739 #define CCOPY br_ccopy
742 * Compute the bit length of a 32-bit integer. Returned value is between 0
743 * and 32 (inclusive).
745 static inline uint32_t
746 BIT_LENGTH(uint32_t x
)
751 c
= GT(x
, 0xFFFF); x
= MUX(c
, x
>> 16, x
); k
+= c
<< 4;
752 c
= GT(x
, 0x00FF); x
= MUX(c
, x
>> 8, x
); k
+= c
<< 3;
753 c
= GT(x
, 0x000F); x
= MUX(c
, x
>> 4, x
); k
+= c
<< 2;
754 c
= GT(x
, 0x0003); x
= MUX(c
, x
>> 2, x
); k
+= c
<< 1;
760 * Compute the minimum of x and y.
762 static inline uint32_t
763 MIN(uint32_t x
, uint32_t y
)
765 return MUX(GT(x
, y
), y
, x
);
769 * Compute the maximum of x and y.
771 static inline uint32_t
772 MAX(uint32_t x
, uint32_t y
)
774 return MUX(GT(x
, y
), x
, y
);
778 * Multiply two 32-bit integers, with a 64-bit result. This default
779 * implementation assumes that the basic multiplication operator
780 * yields constant-time code.
782 #define MUL(x, y) ((uint64_t)(x) * (uint64_t)(y))
787 * Alternate implementation of MUL31, that will be constant-time on some
788 * (old) platforms where the default MUL31 is not. Unfortunately, it is
789 * also substantially slower, and yields larger code, on more modern
790 * platforms, which is why it is deactivated by default.
792 * MUL31_lo() must do some extra work because on some platforms, the
793 * _signed_ multiplication may return early if the top bits are 1.
794 * Simply truncating (casting) the output of MUL31() would not be
795 * sufficient, because the compiler may notice that we keep only the low
796 * word, and then replace automatically the unsigned multiplication with
797 * a signed multiplication opcode.
799 #define MUL31(x, y) ((uint64_t)((x) | (uint32_t)0x80000000) \
800 * (uint64_t)((y) | (uint32_t)0x80000000) \
801 - ((uint64_t)(x) << 31) - ((uint64_t)(y) << 31) \
802 - ((uint64_t)1 << 62))
803 static inline uint32_t
804 MUL31_lo(uint32_t x
, uint32_t y
)
809 xl
= (x
& 0xFFFF) | (uint32_t)0x80000000;
810 xh
= (x
>> 16) | (uint32_t)0x80000000;
811 yl
= (y
& 0xFFFF) | (uint32_t)0x80000000;
812 yh
= (y
>> 16) | (uint32_t)0x80000000;
813 return (xl
* yl
+ ((xl
* yh
+ xh
* yl
) << 16)) & (uint32_t)0x7FFFFFFF;
819 * Multiply two 31-bit integers, with a 62-bit result. This default
820 * implementation assumes that the basic multiplication operator
821 * yields constant-time code.
822 * The MUL31_lo() macro returns only the low 31 bits of the product.
824 #define MUL31(x, y) ((uint64_t)(x) * (uint64_t)(y))
825 #define MUL31_lo(x, y) (((uint32_t)(x) * (uint32_t)(y)) & (uint32_t)0x7FFFFFFF)
830 * Multiply two words together; the sum of the lengths of the two
831 * operands must not exceed 31 (for instance, one operand may use 16
832 * bits if the other fits on 15). If BR_CT_MUL15 is non-zero, then the
833 * macro will contain some extra operations that help in making the
834 * operation constant-time on some platforms, where the basic 32-bit
835 * multiplication is not constant-time.
838 #define MUL15(x, y) (((uint32_t)(x) | (uint32_t)0x80000000) \
839 * ((uint32_t)(y) | (uint32_t)0x80000000) \
840 & (uint32_t)0x7FFFFFFF)
842 #define MUL15(x, y) ((uint32_t)(x) * (uint32_t)(y))
846 * Arithmetic right shift (sign bit is copied). What happens when
847 * right-shifting a negative value is _implementation-defined_, so it
848 * does not trigger undefined behaviour, but it is still up to each
849 * compiler to define (and document) what it does. Most/all compilers
850 * will do an arithmetic shift, the sign bit being used to fill the
851 * holes; this is a native operation on the underlying CPU, and it would
852 * make little sense for the compiler to do otherwise. GCC explicitly
853 * documents that it follows that convention.
855 * Still, if BR_NO_ARITH_SHIFT is defined (and non-zero), then an
856 * alternate version will be used, that does not rely on such
857 * implementation-defined behaviour. Unfortunately, it is also slower
858 * and yields bigger code, which is why it is deactivated by default.
860 #if BR_NO_ARITH_SHIFT
861 #define ARSH(x, n) (((uint32_t)(x) >> (n)) \
862 | ((-((uint32_t)(x) >> 31)) << (32 - (n))))
864 #define ARSH(x, n) ((*(int32_t *)&(x)) >> (n))
868 * Constant-time division. The dividend hi:lo is divided by the
869 * divisor d; the quotient is returned and the remainder is written
870 * in *r. If hi == d, then the quotient does not fit on 32 bits;
871 * returned value is thus truncated. If hi > d, returned values are
874 uint32_t br_divrem(uint32_t hi
, uint32_t lo
, uint32_t d
, uint32_t *r
);
877 * Wrapper for br_divrem(); the remainder is returned, and the quotient
880 static inline uint32_t
881 br_rem(uint32_t hi
, uint32_t lo
, uint32_t d
)
885 br_divrem(hi
, lo
, d
, &r
);
890 * Wrapper for br_divrem(); the quotient is returned, and the remainder
893 static inline uint32_t
894 br_div(uint32_t hi
, uint32_t lo
, uint32_t d
)
898 return br_divrem(hi
, lo
, d
, &r
);
901 /* ==================================================================== */
907 * The 'i32' functions implement computations on big integers using
908 * an internal representation as an array of 32-bit integers. For
910 * -- x[0] contains the "announced bit length" of the integer
911 * -- x[1], x[2]... contain the value in little-endian order (x[1]
912 * contains the least significant 32 bits)
914 * Multiplications rely on the elementary 32x32->64 multiplication.
916 * The announced bit length specifies the number of bits that are
917 * significant in the subsequent 32-bit words. Unused bits in the
918 * last (most significant) word are set to 0; subsequent words are
919 * uninitialized and need not exist at all.
921 * The execution time and memory access patterns of all computations
922 * depend on the announced bit length, but not on the actual word
923 * values. For modular integers, the announced bit length of any integer
924 * modulo n is equal to the actual bit length of n; thus, computations
925 * on modular integers are "constant-time" (only the modulus length may
930 * Compute the actual bit length of an integer. The argument x should
931 * point to the first (least significant) value word of the integer.
932 * The len 'xlen' contains the number of 32-bit words to access.
934 * CT: value or length of x does not leak.
936 uint32_t br_i32_bit_length(uint32_t *x
, size_t xlen
);
939 * Decode an integer from its big-endian unsigned representation. The
940 * "true" bit length of the integer is computed, but all words of x[]
941 * corresponding to the full 'len' bytes of the source are set.
943 * CT: value or length of x does not leak.
945 void br_i32_decode(uint32_t *x
, const void *src
, size_t len
);
948 * Decode an integer from its big-endian unsigned representation. The
949 * integer MUST be lower than m[]; the announced bit length written in
950 * x[] will be equal to that of m[]. All 'len' bytes from the source are
953 * Returned value is 1 if the decode value fits within the modulus, 0
954 * otherwise. In the latter case, the x[] buffer will be set to 0 (but
955 * still with the announced bit length of m[]).
957 * CT: value or length of x does not leak. Memory access pattern depends
958 * only of 'len' and the announced bit length of m. Whether x fits or
959 * not does not leak either.
961 uint32_t br_i32_decode_mod(uint32_t *x
,
962 const void *src
, size_t len
, const uint32_t *m
);
965 * Reduce an integer (a[]) modulo another (m[]). The result is written
966 * in x[] and its announced bit length is set to be equal to that of m[].
968 * x[] MUST be distinct from a[] and m[].
970 * CT: only announced bit lengths leak, not values of x, a or m.
972 void br_i32_reduce(uint32_t *x
, const uint32_t *a
, const uint32_t *m
);
975 * Decode an integer from its big-endian unsigned representation, and
976 * reduce it modulo the provided modulus m[]. The announced bit length
977 * of the result is set to be equal to that of the modulus.
979 * x[] MUST be distinct from m[].
981 void br_i32_decode_reduce(uint32_t *x
,
982 const void *src
, size_t len
, const uint32_t *m
);
985 * Encode an integer into its big-endian unsigned representation. The
986 * output length in bytes is provided (parameter 'len'); if the length
987 * is too short then the integer is appropriately truncated; if it is
988 * too long then the extra bytes are set to 0.
990 void br_i32_encode(void *dst
, size_t len
, const uint32_t *x
);
993 * Multiply x[] by 2^32 and then add integer z, modulo m[]. This
994 * function assumes that x[] and m[] have the same announced bit
995 * length, and the announced bit length of m[] matches its true
998 * x[] and m[] MUST be distinct arrays.
1000 * CT: only the common announced bit length of x and m leaks, not
1001 * the values of x, z or m.
1003 void br_i32_muladd_small(uint32_t *x
, uint32_t z
, const uint32_t *m
);
1006 * Extract one word from an integer. The offset is counted in bits.
1007 * The word MUST entirely fit within the word elements corresponding
1008 * to the announced bit length of a[].
1010 static inline uint32_t
1011 br_i32_word(const uint32_t *a
, uint32_t off
)
1016 u
= (size_t)(off
>> 5) + 1;
1017 j
= (unsigned)off
& 31;
1021 return (a
[u
] >> j
) | (a
[u
+ 1] << (32 - j
));
1026 * Test whether an integer is zero.
1028 uint32_t br_i32_iszero(const uint32_t *x
);
1031 * Add b[] to a[] and return the carry (0 or 1). If ctl is 0, then a[]
1032 * is unmodified, but the carry is still computed and returned. The
1033 * arrays a[] and b[] MUST have the same announced bit length.
1035 * a[] and b[] MAY be the same array, but partial overlap is not allowed.
1037 uint32_t br_i32_add(uint32_t *a
, const uint32_t *b
, uint32_t ctl
);
1040 * Subtract b[] from a[] and return the carry (0 or 1). If ctl is 0,
1041 * then a[] is unmodified, but the carry is still computed and returned.
1042 * The arrays a[] and b[] MUST have the same announced bit length.
1044 * a[] and b[] MAY be the same array, but partial overlap is not allowed.
1046 uint32_t br_i32_sub(uint32_t *a
, const uint32_t *b
, uint32_t ctl
);
1049 * Compute d+a*b, result in d. The initial announced bit length of d[]
1050 * MUST match that of a[]. The d[] array MUST be large enough to
1051 * accommodate the full result, plus (possibly) an extra word. The
1052 * resulting announced bit length of d[] will be the sum of the announced
1053 * bit lengths of a[] and b[] (therefore, it may be larger than the actual
1054 * bit length of the numerical result).
1056 * a[] and b[] may be the same array. d[] must be disjoint from both a[]
1059 void br_i32_mulacc(uint32_t *d
, const uint32_t *a
, const uint32_t *b
);
1062 * Zeroize an integer. The announced bit length is set to the provided
1063 * value, and the corresponding words are set to 0.
1066 br_i32_zero(uint32_t *x
, uint32_t bit_len
)
1069 memset(x
, 0, ((bit_len
+ 31) >> 5) * sizeof *x
);
1073 * Compute -(1/x) mod 2^32. If x is even, then this function returns 0.
1075 uint32_t br_i32_ninv32(uint32_t x
);
1078 * Convert a modular integer to Montgomery representation. The integer x[]
1079 * MUST be lower than m[], but with the same announced bit length.
1081 void br_i32_to_monty(uint32_t *x
, const uint32_t *m
);
1084 * Convert a modular integer back from Montgomery representation. The
1085 * integer x[] MUST be lower than m[], but with the same announced bit
1086 * length. The "m0i" parameter is equal to -(1/m0) mod 2^32, where m0 is
1087 * the least significant value word of m[] (this works only if m[] is
1090 void br_i32_from_monty(uint32_t *x
, const uint32_t *m
, uint32_t m0i
);
1093 * Compute a modular Montgomery multiplication. d[] is filled with the
1094 * value of x*y/R modulo m[] (where R is the Montgomery factor). The
1095 * array d[] MUST be distinct from x[], y[] and m[]. x[] and y[] MUST be
1096 * numerically lower than m[]. x[] and y[] MAY be the same array. The
1097 * "m0i" parameter is equal to -(1/m0) mod 2^32, where m0 is the least
1098 * significant value word of m[] (this works only if m[] is an odd
1101 void br_i32_montymul(uint32_t *d
, const uint32_t *x
, const uint32_t *y
,
1102 const uint32_t *m
, uint32_t m0i
);
1105 * Compute a modular exponentiation. x[] MUST be an integer modulo m[]
1106 * (same announced bit length, lower value). m[] MUST be odd. The
1107 * exponent is in big-endian unsigned notation, over 'elen' bytes. The
1108 * "m0i" parameter is equal to -(1/m0) mod 2^32, where m0 is the least
1109 * significant value word of m[] (this works only if m[] is an odd
1110 * integer). The t1[] and t2[] parameters must be temporary arrays,
1111 * each large enough to accommodate an integer with the same size as m[].
1113 void br_i32_modpow(uint32_t *x
, const unsigned char *e
, size_t elen
,
1114 const uint32_t *m
, uint32_t m0i
, uint32_t *t1
, uint32_t *t2
);
1116 /* ==================================================================== */
1122 * The 'i31' functions implement computations on big integers using
1123 * an internal representation as an array of 32-bit integers. For
1125 * -- x[0] encodes the array length and the "announced bit length"
1126 * of the integer: namely, if the announced bit length is k,
1127 * then x[0] = ((k / 31) << 5) + (k % 31).
1128 * -- x[1], x[2]... contain the value in little-endian order, 31
1129 * bits per word (x[1] contains the least significant 31 bits).
1130 * The upper bit of each word is 0.
1132 * Multiplications rely on the elementary 32x32->64 multiplication.
1134 * The announced bit length specifies the number of bits that are
1135 * significant in the subsequent 32-bit words. Unused bits in the
1136 * last (most significant) word are set to 0; subsequent words are
1137 * uninitialized and need not exist at all.
1139 * The execution time and memory access patterns of all computations
1140 * depend on the announced bit length, but not on the actual word
1141 * values. For modular integers, the announced bit length of any integer
1142 * modulo n is equal to the actual bit length of n; thus, computations
1143 * on modular integers are "constant-time" (only the modulus length may
1148 * Test whether an integer is zero.
1150 uint32_t br_i31_iszero(const uint32_t *x
);
1153 * Add b[] to a[] and return the carry (0 or 1). If ctl is 0, then a[]
1154 * is unmodified, but the carry is still computed and returned. The
1155 * arrays a[] and b[] MUST have the same announced bit length.
1157 * a[] and b[] MAY be the same array, but partial overlap is not allowed.
1159 uint32_t br_i31_add(uint32_t *a
, const uint32_t *b
, uint32_t ctl
);
1162 * Subtract b[] from a[] and return the carry (0 or 1). If ctl is 0,
1163 * then a[] is unmodified, but the carry is still computed and returned.
1164 * The arrays a[] and b[] MUST have the same announced bit length.
1166 * a[] and b[] MAY be the same array, but partial overlap is not allowed.
1168 uint32_t br_i31_sub(uint32_t *a
, const uint32_t *b
, uint32_t ctl
);
1171 * Compute the ENCODED actual bit length of an integer. The argument x
1172 * should point to the first (least significant) value word of the
1173 * integer. The len 'xlen' contains the number of 32-bit words to
1174 * access. The upper bit of each value word MUST be 0.
1175 * Returned value is ((k / 31) << 5) + (k % 31) if the bit length is k.
1177 * CT: value or length of x does not leak.
1179 uint32_t br_i31_bit_length(uint32_t *x
, size_t xlen
);
1182 * Decode an integer from its big-endian unsigned representation. The
1183 * "true" bit length of the integer is computed and set in the encoded
1184 * announced bit length (x[0]), but all words of x[] corresponding to
1185 * the full 'len' bytes of the source are set.
1187 * CT: value or length of x does not leak.
1189 void br_i31_decode(uint32_t *x
, const void *src
, size_t len
);
1192 * Decode an integer from its big-endian unsigned representation. The
1193 * integer MUST be lower than m[]; the (encoded) announced bit length
1194 * written in x[] will be equal to that of m[]. All 'len' bytes from the
1197 * Returned value is 1 if the decode value fits within the modulus, 0
1198 * otherwise. In the latter case, the x[] buffer will be set to 0 (but
1199 * still with the announced bit length of m[]).
1201 * CT: value or length of x does not leak. Memory access pattern depends
1202 * only of 'len' and the announced bit length of m. Whether x fits or
1203 * not does not leak either.
1205 uint32_t br_i31_decode_mod(uint32_t *x
,
1206 const void *src
, size_t len
, const uint32_t *m
);
1209 * Zeroize an integer. The announced bit length is set to the provided
1210 * value, and the corresponding words are set to 0. The ENCODED bit length
1214 br_i31_zero(uint32_t *x
, uint32_t bit_len
)
1217 memset(x
, 0, ((bit_len
+ 31) >> 5) * sizeof *x
);
1221 * Right-shift an integer. The shift amount must be lower than 31
1224 void br_i31_rshift(uint32_t *x
, int count
);
1227 * Reduce an integer (a[]) modulo another (m[]). The result is written
1228 * in x[] and its announced bit length is set to be equal to that of m[].
1230 * x[] MUST be distinct from a[] and m[].
1232 * CT: only announced bit lengths leak, not values of x, a or m.
1234 void br_i31_reduce(uint32_t *x
, const uint32_t *a
, const uint32_t *m
);
1237 * Decode an integer from its big-endian unsigned representation, and
1238 * reduce it modulo the provided modulus m[]. The announced bit length
1239 * of the result is set to be equal to that of the modulus.
1241 * x[] MUST be distinct from m[].
1243 void br_i31_decode_reduce(uint32_t *x
,
1244 const void *src
, size_t len
, const uint32_t *m
);
1247 * Multiply x[] by 2^31 and then add integer z, modulo m[]. This
1248 * function assumes that x[] and m[] have the same announced bit
1249 * length, the announced bit length of m[] matches its true
1252 * x[] and m[] MUST be distinct arrays. z MUST fit in 31 bits (upper
1255 * CT: only the common announced bit length of x and m leaks, not
1256 * the values of x, z or m.
1258 void br_i31_muladd_small(uint32_t *x
, uint32_t z
, const uint32_t *m
);
1261 * Encode an integer into its big-endian unsigned representation. The
1262 * output length in bytes is provided (parameter 'len'); if the length
1263 * is too short then the integer is appropriately truncated; if it is
1264 * too long then the extra bytes are set to 0.
1266 void br_i31_encode(void *dst
, size_t len
, const uint32_t *x
);
1269 * Compute -(1/x) mod 2^31. If x is even, then this function returns 0.
1271 uint32_t br_i31_ninv31(uint32_t x
);
1274 * Compute a modular Montgomery multiplication. d[] is filled with the
1275 * value of x*y/R modulo m[] (where R is the Montgomery factor). The
1276 * array d[] MUST be distinct from x[], y[] and m[]. x[] and y[] MUST be
1277 * numerically lower than m[]. x[] and y[] MAY be the same array. The
1278 * "m0i" parameter is equal to -(1/m0) mod 2^31, where m0 is the least
1279 * significant value word of m[] (this works only if m[] is an odd
1282 void br_i31_montymul(uint32_t *d
, const uint32_t *x
, const uint32_t *y
,
1283 const uint32_t *m
, uint32_t m0i
);
1286 * Convert a modular integer to Montgomery representation. The integer x[]
1287 * MUST be lower than m[], but with the same announced bit length.
1289 void br_i31_to_monty(uint32_t *x
, const uint32_t *m
);
1292 * Convert a modular integer back from Montgomery representation. The
1293 * integer x[] MUST be lower than m[], but with the same announced bit
1294 * length. The "m0i" parameter is equal to -(1/m0) mod 2^32, where m0 is
1295 * the least significant value word of m[] (this works only if m[] is
1298 void br_i31_from_monty(uint32_t *x
, const uint32_t *m
, uint32_t m0i
);
1301 * Compute a modular exponentiation. x[] MUST be an integer modulo m[]
1302 * (same announced bit length, lower value). m[] MUST be odd. The
1303 * exponent is in big-endian unsigned notation, over 'elen' bytes. The
1304 * "m0i" parameter is equal to -(1/m0) mod 2^31, where m0 is the least
1305 * significant value word of m[] (this works only if m[] is an odd
1306 * integer). The t1[] and t2[] parameters must be temporary arrays,
1307 * each large enough to accommodate an integer with the same size as m[].
1309 void br_i31_modpow(uint32_t *x
, const unsigned char *e
, size_t elen
,
1310 const uint32_t *m
, uint32_t m0i
, uint32_t *t1
, uint32_t *t2
);
1313 * Compute a modular exponentiation. x[] MUST be an integer modulo m[]
1314 * (same announced bit length, lower value). m[] MUST be odd. The
1315 * exponent is in big-endian unsigned notation, over 'elen' bytes. The
1316 * "m0i" parameter is equal to -(1/m0) mod 2^31, where m0 is the least
1317 * significant value word of m[] (this works only if m[] is an odd
1318 * integer). The tmp[] array is used for temporaries, and has size
1319 * 'twlen' words; it must be large enough to accommodate at least two
1320 * temporary values with the same size as m[] (including the leading
1321 * "bit length" word). If there is room for more temporaries, then this
1322 * function may use the extra room for window-based optimisation,
1323 * resulting in faster computations.
1325 * Returned value is 1 on success, 0 on error. An error is reported if
1326 * the provided tmp[] array is too short.
1328 uint32_t br_i31_modpow_opt(uint32_t *x
, const unsigned char *e
, size_t elen
,
1329 const uint32_t *m
, uint32_t m0i
, uint32_t *tmp
, size_t twlen
);
1332 * Compute d+a*b, result in d. The initial announced bit length of d[]
1333 * MUST match that of a[]. The d[] array MUST be large enough to
1334 * accommodate the full result, plus (possibly) an extra word. The
1335 * resulting announced bit length of d[] will be the sum of the announced
1336 * bit lengths of a[] and b[] (therefore, it may be larger than the actual
1337 * bit length of the numerical result).
1339 * a[] and b[] may be the same array. d[] must be disjoint from both a[]
1342 void br_i31_mulacc(uint32_t *d
, const uint32_t *a
, const uint32_t *b
);
1344 /* ==================================================================== */
1347 * FIXME: document "i15" functions.
1351 br_i15_zero(uint16_t *x
, uint16_t bit_len
)
1354 memset(x
, 0, ((bit_len
+ 15) >> 4) * sizeof *x
);
1357 uint32_t br_i15_iszero(const uint16_t *x
);
1359 uint16_t br_i15_ninv15(uint16_t x
);
1361 uint32_t br_i15_add(uint16_t *a
, const uint16_t *b
, uint32_t ctl
);
1363 uint32_t br_i15_sub(uint16_t *a
, const uint16_t *b
, uint32_t ctl
);
1365 void br_i15_muladd_small(uint16_t *x
, uint16_t z
, const uint16_t *m
);
1367 void br_i15_montymul(uint16_t *d
, const uint16_t *x
, const uint16_t *y
,
1368 const uint16_t *m
, uint16_t m0i
);
1370 void br_i15_to_monty(uint16_t *x
, const uint16_t *m
);
1372 void br_i15_modpow(uint16_t *x
, const unsigned char *e
, size_t elen
,
1373 const uint16_t *m
, uint16_t m0i
, uint16_t *t1
, uint16_t *t2
);
1375 uint32_t br_i15_modpow_opt(uint16_t *x
, const unsigned char *e
, size_t elen
,
1376 const uint16_t *m
, uint16_t m0i
, uint16_t *tmp
, size_t twlen
);
1378 void br_i15_encode(void *dst
, size_t len
, const uint16_t *x
);
1380 uint32_t br_i15_decode_mod(uint16_t *x
,
1381 const void *src
, size_t len
, const uint16_t *m
);
1383 void br_i15_rshift(uint16_t *x
, int count
);
1385 uint32_t br_i15_bit_length(uint16_t *x
, size_t xlen
);
1387 void br_i15_decode(uint16_t *x
, const void *src
, size_t len
);
1389 void br_i15_from_monty(uint16_t *x
, const uint16_t *m
, uint16_t m0i
);
1391 void br_i15_decode_reduce(uint16_t *x
,
1392 const void *src
, size_t len
, const uint16_t *m
);
1394 void br_i15_reduce(uint16_t *x
, const uint16_t *a
, const uint16_t *m
);
1396 void br_i15_mulacc(uint16_t *d
, const uint16_t *a
, const uint16_t *b
);
1398 uint32_t br_i62_modpow_opt(uint32_t *x31
, const unsigned char *e
, size_t elen
,
1399 const uint32_t *m31
, uint32_t m0i31
, uint64_t *tmp
, size_t twlen
);
1401 /* ==================================================================== */
1403 static inline size_t
1404 br_digest_size(const br_hash_class
*digest_class
)
1406 return (size_t)(digest_class
->desc
>> BR_HASHDESC_OUT_OFF
)
1407 & BR_HASHDESC_OUT_MASK
;
1411 * Get the output size (in bytes) of a hash function.
1413 size_t br_digest_size_by_ID(int digest_id
);
1416 * Get the OID (encoded OBJECT IDENTIFIER value, without tag and length)
1417 * for a hash function. If digest_id is not a supported digest identifier
1418 * (in particular if it is equal to 0, i.e. br_md5sha1_ID), then NULL is
1419 * returned and *len is set to 0.
1421 const unsigned char *br_digest_OID(int digest_id
, size_t *len
);
1423 /* ==================================================================== */
1425 * DES support functions.
1429 * Apply DES Initial Permutation.
1431 void br_des_do_IP(uint32_t *xl
, uint32_t *xr
);
1434 * Apply DES Final Permutation (inverse of IP).
1436 void br_des_do_invIP(uint32_t *xl
, uint32_t *xr
);
1439 * Key schedule unit: for a DES key (8 bytes), compute 16 subkeys. Each
1440 * subkey is two 28-bit words represented as two 32-bit words; the PC-2
1441 * bit extration is NOT applied.
1443 void br_des_keysched_unit(uint32_t *skey
, const void *key
);
1446 * Reversal of 16 DES sub-keys (for decryption).
1448 void br_des_rev_skey(uint32_t *skey
);
1451 * DES/3DES key schedule for 'des_tab' (encryption direction). Returned
1452 * value is the number of rounds.
1454 unsigned br_des_tab_keysched(uint32_t *skey
, const void *key
, size_t key_len
);
1457 * DES/3DES key schedule for 'des_ct' (encryption direction). Returned
1458 * value is the number of rounds.
1460 unsigned br_des_ct_keysched(uint32_t *skey
, const void *key
, size_t key_len
);
1463 * DES/3DES subkey decompression (from the compressed bitsliced subkeys).
1465 void br_des_ct_skey_expand(uint32_t *sk_exp
,
1466 unsigned num_rounds
, const uint32_t *skey
);
1469 * DES/3DES block encryption/decryption ('des_tab').
1471 void br_des_tab_process_block(unsigned num_rounds
,
1472 const uint32_t *skey
, void *block
);
1475 * DES/3DES block encryption/decryption ('des_ct').
1477 void br_des_ct_process_block(unsigned num_rounds
,
1478 const uint32_t *skey
, void *block
);
1480 /* ==================================================================== */
1482 * AES support functions.
1486 * The AES S-box (256-byte table).
1488 extern const unsigned char br_aes_S
[];
1491 * AES key schedule. skey[] is filled with n+1 128-bit subkeys, where n
1492 * is the number of rounds (10 to 14, depending on key size). The number
1493 * of rounds is returned. If the key size is invalid (not 16, 24 or 32),
1494 * then 0 is returned.
1496 * This implementation uses a 256-byte table and is NOT constant-time.
1498 unsigned br_aes_keysched(uint32_t *skey
, const void *key
, size_t key_len
);
1501 * AES key schedule for decryption ('aes_big' implementation).
1503 unsigned br_aes_big_keysched_inv(uint32_t *skey
,
1504 const void *key
, size_t key_len
);
1507 * AES block encryption with the 'aes_big' implementation (fast, but
1508 * not constant-time). This function encrypts a single block "in place".
1510 void br_aes_big_encrypt(unsigned num_rounds
, const uint32_t *skey
, void *data
);
1513 * AES block decryption with the 'aes_big' implementation (fast, but
1514 * not constant-time). This function decrypts a single block "in place".
1516 void br_aes_big_decrypt(unsigned num_rounds
, const uint32_t *skey
, void *data
);
1519 * AES block encryption with the 'aes_small' implementation (small, but
1520 * slow and not constant-time). This function encrypts a single block
1523 void br_aes_small_encrypt(unsigned num_rounds
,
1524 const uint32_t *skey
, void *data
);
1527 * AES block decryption with the 'aes_small' implementation (small, but
1528 * slow and not constant-time). This function decrypts a single block
1531 void br_aes_small_decrypt(unsigned num_rounds
,
1532 const uint32_t *skey
, void *data
);
1535 * The constant-time implementation is "bitsliced": the 128-bit state is
1536 * split over eight 32-bit words q* in the following way:
1538 * -- Input block consists in 16 bytes:
1539 * a00 a10 a20 a30 a01 a11 a21 a31 a02 a12 a22 a32 a03 a13 a23 a33
1540 * In the terminology of FIPS 197, this is a 4x4 matrix which is read
1543 * -- Each byte is split into eight bits which are distributed over the
1544 * eight words, at the same rank. Thus, for a byte x at rank k, bit 0
1545 * (least significant) of x will be at rank k in q0 (if that bit is b,
1546 * then it contributes "b << k" to the value of q0), bit 1 of x will be
1547 * at rank k in q1, and so on.
1549 * -- Ranks given to bits are in "row order" and are either all even, or
1550 * all odd. Two independent AES states are thus interleaved, one using
1551 * the even ranks, the other the odd ranks. Row order means:
1552 * a00 a01 a02 a03 a10 a11 a12 a13 a20 a21 a22 a23 a30 a31 a32 a33
1554 * Converting input bytes from two AES blocks to bitslice representation
1555 * is done in the following way:
1556 * -- Decode first block into the four words q0 q2 q4 q6, in that order,
1557 * using little-endian convention.
1558 * -- Decode second block into the four words q1 q3 q5 q7, in that order,
1559 * using little-endian convention.
1560 * -- Call br_aes_ct_ortho().
1562 * Converting back to bytes is done by using the reverse operations. Note
1563 * that br_aes_ct_ortho() is its own inverse.
1567 * Perform bytewise orthogonalization of eight 32-bit words. Bytes
1568 * of q0..q7 are spread over all words: for a byte x that occurs
1569 * at rank i in q[j] (byte x uses bits 8*i to 8*i+7 in q[j]), the bit
1570 * of rank k in x (0 <= k <= 7) goes to q[k] at rank 8*i+j.
1572 * This operation is an involution.
1574 void br_aes_ct_ortho(uint32_t *q
);
1577 * The AES S-box, as a bitsliced constant-time version. The input array
1578 * consists in eight 32-bit words; 32 S-box instances are computed in
1579 * parallel. Bits 0 to 7 of each S-box input (bit 0 is least significant)
1580 * are spread over the words 0 to 7, at the same rank.
1582 void br_aes_ct_bitslice_Sbox(uint32_t *q
);
1585 * Like br_aes_bitslice_Sbox(), but for the inverse S-box.
1587 void br_aes_ct_bitslice_invSbox(uint32_t *q
);
1590 * Compute AES encryption on bitsliced data. Since input is stored on
1591 * eight 32-bit words, two block encryptions are actually performed
1594 void br_aes_ct_bitslice_encrypt(unsigned num_rounds
,
1595 const uint32_t *skey
, uint32_t *q
);
1598 * Compute AES decryption on bitsliced data. Since input is stored on
1599 * eight 32-bit words, two block decryptions are actually performed
1602 void br_aes_ct_bitslice_decrypt(unsigned num_rounds
,
1603 const uint32_t *skey
, uint32_t *q
);
1606 * AES key schedule, constant-time version. skey[] is filled with n+1
1607 * 128-bit subkeys, where n is the number of rounds (10 to 14, depending
1608 * on key size). The number of rounds is returned. If the key size is
1609 * invalid (not 16, 24 or 32), then 0 is returned.
1611 unsigned br_aes_ct_keysched(uint32_t *comp_skey
,
1612 const void *key
, size_t key_len
);
1615 * Expand AES subkeys as produced by br_aes_ct_keysched(), into
1616 * a larger array suitable for br_aes_ct_bitslice_encrypt() and
1617 * br_aes_ct_bitslice_decrypt().
1619 void br_aes_ct_skey_expand(uint32_t *skey
,
1620 unsigned num_rounds
, const uint32_t *comp_skey
);
1623 * For the ct64 implementation, the same bitslicing technique is used,
1624 * but four instances are interleaved. First instance uses bits 0, 4,
1625 * 8, 12,... of each word; second instance uses bits 1, 5, 9, 13,...
1630 * Perform bytewise orthogonalization of eight 64-bit words. Bytes
1631 * of q0..q7 are spread over all words: for a byte x that occurs
1632 * at rank i in q[j] (byte x uses bits 8*i to 8*i+7 in q[j]), the bit
1633 * of rank k in x (0 <= k <= 7) goes to q[k] at rank 8*i+j.
1635 * This operation is an involution.
1637 void br_aes_ct64_ortho(uint64_t *q
);
1640 * Interleave bytes for an AES input block. If input bytes are
1641 * denoted 0123456789ABCDEF, and have been decoded with little-endian
1642 * convention (w[0] contains 0123, with '3' being most significant;
1643 * w[1] contains 4567, and so on), then output word q0 will be
1644 * set to 08192A3B (again little-endian convention) and q1 will
1645 * be set to 4C5D6E7F.
1647 void br_aes_ct64_interleave_in(uint64_t *q0
, uint64_t *q1
, const uint32_t *w
);
1650 * Perform the opposite of br_aes_ct64_interleave_in().
1652 void br_aes_ct64_interleave_out(uint32_t *w
, uint64_t q0
, uint64_t q1
);
1655 * The AES S-box, as a bitsliced constant-time version. The input array
1656 * consists in eight 64-bit words; 64 S-box instances are computed in
1657 * parallel. Bits 0 to 7 of each S-box input (bit 0 is least significant)
1658 * are spread over the words 0 to 7, at the same rank.
1660 void br_aes_ct64_bitslice_Sbox(uint64_t *q
);
1663 * Like br_aes_bitslice_Sbox(), but for the inverse S-box.
1665 void br_aes_ct64_bitslice_invSbox(uint64_t *q
);
1668 * Compute AES encryption on bitsliced data. Since input is stored on
1669 * eight 64-bit words, four block encryptions are actually performed
1672 void br_aes_ct64_bitslice_encrypt(unsigned num_rounds
,
1673 const uint64_t *skey
, uint64_t *q
);
1676 * Compute AES decryption on bitsliced data. Since input is stored on
1677 * eight 64-bit words, four block decryptions are actually performed
1680 void br_aes_ct64_bitslice_decrypt(unsigned num_rounds
,
1681 const uint64_t *skey
, uint64_t *q
);
1684 * AES key schedule, constant-time version. skey[] is filled with n+1
1685 * 128-bit subkeys, where n is the number of rounds (10 to 14, depending
1686 * on key size). The number of rounds is returned. If the key size is
1687 * invalid (not 16, 24 or 32), then 0 is returned.
1689 unsigned br_aes_ct64_keysched(uint64_t *comp_skey
,
1690 const void *key
, size_t key_len
);
1693 * Expand AES subkeys as produced by br_aes_ct64_keysched(), into
1694 * a larger array suitable for br_aes_ct64_bitslice_encrypt() and
1695 * br_aes_ct64_bitslice_decrypt().
1697 void br_aes_ct64_skey_expand(uint64_t *skey
,
1698 unsigned num_rounds
, const uint64_t *comp_skey
);
1701 * Test support for AES-NI opcodes.
1703 int br_aes_x86ni_supported(void);
1706 * AES key schedule, using x86 AES-NI instructions. This yields the
1707 * subkeys in the encryption direction. Number of rounds is returned.
1708 * Key size MUST be 16, 24 or 32 bytes; otherwise, 0 is returned.
1710 unsigned br_aes_x86ni_keysched_enc(unsigned char *skni
,
1711 const void *key
, size_t len
);
1714 * AES key schedule, using x86 AES-NI instructions. This yields the
1715 * subkeys in the decryption direction. Number of rounds is returned.
1716 * Key size MUST be 16, 24 or 32 bytes; otherwise, 0 is returned.
1718 unsigned br_aes_x86ni_keysched_dec(unsigned char *skni
,
1719 const void *key
, size_t len
);
1722 * Test support for AES POWER8 opcodes.
1724 int br_aes_pwr8_supported(void);
1727 * AES key schedule, using POWER8 instructions. This yields the
1728 * subkeys in the encryption direction. Number of rounds is returned.
1729 * Key size MUST be 16, 24 or 32 bytes; otherwise, 0 is returned.
1731 unsigned br_aes_pwr8_keysched(unsigned char *skni
,
1732 const void *key
, size_t len
);
1734 /* ==================================================================== */
1740 * Apply proper PKCS#1 v1.5 padding (for signatures). 'hash_oid' is
1741 * the encoded hash function OID, or NULL.
1743 uint32_t br_rsa_pkcs1_sig_pad(const unsigned char *hash_oid
,
1744 const unsigned char *hash
, size_t hash_len
,
1745 uint32_t n_bitlen
, unsigned char *x
);
1748 * Check PKCS#1 v1.5 padding (for signatures). 'hash_oid' is the encoded
1749 * hash function OID, or NULL. The provided 'sig' value is _after_ the
1750 * modular exponentiation, i.e. it should be the padded hash. On
1751 * success, the hashed message is extracted.
1753 uint32_t br_rsa_pkcs1_sig_unpad(const unsigned char *sig
, size_t sig_len
,
1754 const unsigned char *hash_oid
, size_t hash_len
,
1755 unsigned char *hash_out
);
1757 /* ==================================================================== */
1763 * Type for generic EC parameters: curve order (unsigned big-endian
1764 * encoding) and encoded conventional generator.
1768 const unsigned char *order
;
1770 const unsigned char *generator
;
1771 size_t generator_len
;
1774 extern const br_ec_curve_def br_secp256r1
;
1775 extern const br_ec_curve_def br_secp384r1
;
1776 extern const br_ec_curve_def br_secp521r1
;
1779 * For Curve25519, the advertised "order" really is 2^255-1, since the
1780 * point multipliction function really works over arbitrary 255-bit
1781 * scalars. This value is only meant as a hint for ECDH key generation;
1782 * only ECDSA uses the exact curve order, and ECDSA is not used with
1783 * that specific curve.
1785 extern const br_ec_curve_def br_curve25519
;
1788 * Decode some bytes as an i31 integer, with truncation (corresponding
1789 * to the 'bits2int' operation in RFC 6979). The target ENCODED bit
1790 * length is provided as last parameter. The resulting value will have
1791 * this declared bit length, and consists the big-endian unsigned decoding
1792 * of exactly that many bits in the source (capped at the source length).
1794 void br_ecdsa_i31_bits2int(uint32_t *x
,
1795 const void *src
, size_t len
, uint32_t ebitlen
);
1798 * Decode some bytes as an i15 integer, with truncation (corresponding
1799 * to the 'bits2int' operation in RFC 6979). The target ENCODED bit
1800 * length is provided as last parameter. The resulting value will have
1801 * this declared bit length, and consists the big-endian unsigned decoding
1802 * of exactly that many bits in the source (capped at the source length).
1804 void br_ecdsa_i15_bits2int(uint16_t *x
,
1805 const void *src
, size_t len
, uint32_t ebitlen
);
1807 /* ==================================================================== */
1809 * SSL/TLS support functions.
1815 #define BR_SSL_CHANGE_CIPHER_SPEC 20
1816 #define BR_SSL_ALERT 21
1817 #define BR_SSL_HANDSHAKE 22
1818 #define BR_SSL_APPLICATION_DATA 23
1821 * Handshake message types.
1823 #define BR_SSL_HELLO_REQUEST 0
1824 #define BR_SSL_CLIENT_HELLO 1
1825 #define BR_SSL_SERVER_HELLO 2
1826 #define BR_SSL_CERTIFICATE 11
1827 #define BR_SSL_SERVER_KEY_EXCHANGE 12
1828 #define BR_SSL_CERTIFICATE_REQUEST 13
1829 #define BR_SSL_SERVER_HELLO_DONE 14
1830 #define BR_SSL_CERTIFICATE_VERIFY 15
1831 #define BR_SSL_CLIENT_KEY_EXCHANGE 16
1832 #define BR_SSL_FINISHED 20
1837 #define BR_LEVEL_WARNING 1
1838 #define BR_LEVEL_FATAL 2
1841 * Low-level I/O state.
1843 #define BR_IO_FAILED 0
1846 #define BR_IO_INOUT 3
1849 * Mark a SSL engine as failed. The provided error code is recorded if
1850 * the engine was not already marked as failed. If 'err' is 0, then the
1851 * engine is marked as closed (without error).
1853 void br_ssl_engine_fail(br_ssl_engine_context
*cc
, int err
);
1856 * Test whether the engine is closed (normally or as a failure).
1859 br_ssl_engine_closed(const br_ssl_engine_context
*cc
)
1861 return cc
->iomode
== BR_IO_FAILED
;
1865 * Configure a new maximum fragment length. If possible, the maximum
1866 * length for outgoing records is immediately adjusted (if there are
1867 * not already too many buffered bytes for that).
1869 void br_ssl_engine_new_max_frag_len(
1870 br_ssl_engine_context
*rc
, unsigned max_frag_len
);
1873 * Test whether the current incoming record has been fully received
1874 * or not. This functions returns 0 only if a complete record header
1875 * has been received, but some of the (possibly encrypted) payload
1876 * has not yet been obtained.
1878 int br_ssl_engine_recvrec_finished(const br_ssl_engine_context
*rc
);
1881 * Flush the current record (if not empty). This is meant to be called
1882 * from the handshake processor only.
1884 void br_ssl_engine_flush_record(br_ssl_engine_context
*cc
);
1887 * Test whether there is some accumulated payload to send.
1890 br_ssl_engine_has_pld_to_send(const br_ssl_engine_context
*rc
)
1892 return rc
->oxa
!= rc
->oxb
&& rc
->oxa
!= rc
->oxc
;
1896 * Initialize RNG in engine. Returned value is 1 on success, 0 on error.
1897 * This function will try to use the OS-provided RNG, if available. If
1898 * there is no OS-provided RNG, or if it failed, and no entropy was
1899 * injected by the caller, then a failure will be reported. On error,
1900 * the context error code is set.
1902 int br_ssl_engine_init_rand(br_ssl_engine_context
*cc
);
1905 * Reset the handshake-related parts of the engine.
1907 void br_ssl_engine_hs_reset(br_ssl_engine_context
*cc
,
1908 void (*hsinit
)(void *), void (*hsrun
)(void *));
1911 * Get the PRF to use for this context, for the provided PRF hash
1914 br_tls_prf_impl
br_ssl_engine_get_PRF(br_ssl_engine_context
*cc
, int prf_id
);
1917 * Consume the provided pre-master secret and compute the corresponding
1918 * master secret. The 'prf_id' is the ID of the hash function to use
1919 * with the TLS 1.2 PRF (ignored if the version is TLS 1.0 or 1.1).
1921 void br_ssl_engine_compute_master(br_ssl_engine_context
*cc
,
1922 int prf_id
, const void *pms
, size_t len
);
1925 * Switch to CBC decryption for incoming records.
1926 * cc the engine context
1927 * is_client non-zero for a client, zero for a server
1928 * prf_id id of hash function for PRF (ignored if not TLS 1.2+)
1929 * mac_id id of hash function for HMAC
1930 * bc_impl block cipher implementation (CBC decryption)
1931 * cipher_key_len block cipher key length (in bytes)
1933 void br_ssl_engine_switch_cbc_in(br_ssl_engine_context
*cc
,
1934 int is_client
, int prf_id
, int mac_id
,
1935 const br_block_cbcdec_class
*bc_impl
, size_t cipher_key_len
);
1938 * Switch to CBC encryption for outgoing records.
1939 * cc the engine context
1940 * is_client non-zero for a client, zero for a server
1941 * prf_id id of hash function for PRF (ignored if not TLS 1.2+)
1942 * mac_id id of hash function for HMAC
1943 * bc_impl block cipher implementation (CBC encryption)
1944 * cipher_key_len block cipher key length (in bytes)
1946 void br_ssl_engine_switch_cbc_out(br_ssl_engine_context
*cc
,
1947 int is_client
, int prf_id
, int mac_id
,
1948 const br_block_cbcenc_class
*bc_impl
, size_t cipher_key_len
);
1951 * Switch to GCM decryption for incoming records.
1952 * cc the engine context
1953 * is_client non-zero for a client, zero for a server
1954 * prf_id id of hash function for PRF
1955 * bc_impl block cipher implementation (CTR)
1956 * cipher_key_len block cipher key length (in bytes)
1958 void br_ssl_engine_switch_gcm_in(br_ssl_engine_context
*cc
,
1959 int is_client
, int prf_id
,
1960 const br_block_ctr_class
*bc_impl
, size_t cipher_key_len
);
1963 * Switch to GCM encryption for outgoing records.
1964 * cc the engine context
1965 * is_client non-zero for a client, zero for a server
1966 * prf_id id of hash function for PRF
1967 * bc_impl block cipher implementation (CTR)
1968 * cipher_key_len block cipher key length (in bytes)
1970 void br_ssl_engine_switch_gcm_out(br_ssl_engine_context
*cc
,
1971 int is_client
, int prf_id
,
1972 const br_block_ctr_class
*bc_impl
, size_t cipher_key_len
);
1975 * Switch to ChaCha20+Poly1305 decryption for incoming records.
1976 * cc the engine context
1977 * is_client non-zero for a client, zero for a server
1978 * prf_id id of hash function for PRF
1980 void br_ssl_engine_switch_chapol_in(br_ssl_engine_context
*cc
,
1981 int is_client
, int prf_id
);
1984 * Switch to ChaCha20+Poly1305 encryption for outgoing records.
1985 * cc the engine context
1986 * is_client non-zero for a client, zero for a server
1987 * prf_id id of hash function for PRF
1989 void br_ssl_engine_switch_chapol_out(br_ssl_engine_context
*cc
,
1990 int is_client
, int prf_id
);
1993 * Calls to T0-generated code.
1995 void br_ssl_hs_client_init_main(void *ctx
);
1996 void br_ssl_hs_client_run(void *ctx
);
1997 void br_ssl_hs_server_init_main(void *ctx
);
1998 void br_ssl_hs_server_run(void *ctx
);
2001 * Get the hash function to use for signatures, given a bit mask of
2002 * supported hash functions. This implements a strict choice order
2003 * (namely SHA-256, SHA-384, SHA-512, SHA-224, SHA-1). If the mask
2004 * does not document support of any of these hash functions, then this
2005 * functions returns 0.
2007 int br_ssl_choose_hash(unsigned bf
);
2009 /* ==================================================================== */
2012 * PowerPC / POWER assembly stuff. The special BR_POWER_ASM_MACROS macro
2013 * must be defined before including this file; this is done by source
2014 * files that use some inline assembly for PowerPC / POWER machines.
2017 #if BR_POWER_ASM_MACROS
2019 #define lxvw4x(xt, ra, rb) lxvw4x_(xt, ra, rb)
2020 #define stxvw4x(xt, ra, rb) stxvw4x_(xt, ra, rb)
2022 #define bdnz(foo) bdnz_(foo)
2023 #define beq(foo) beq_(foo)
2025 #define li(rx, value) li_(rx, value)
2026 #define addi(rx, ra, imm) addi_(rx, ra, imm)
2027 #define cmpldi(rx, imm) cmpldi_(rx, imm)
2028 #define mtctr(rx) mtctr_(rx)
2029 #define vspltb(vrt, vrb, uim) vspltb_(vrt, vrb, uim)
2030 #define vspltw(vrt, vrb, uim) vspltw_(vrt, vrb, uim)
2031 #define vspltisb(vrt, imm) vspltisb_(vrt, imm)
2032 #define vspltisw(vrt, imm) vspltisw_(vrt, imm)
2033 #define vrlw(vrt, vra, vrb) vrlw_(vrt, vra, vrb)
2034 #define vsbox(vrt, vra) vsbox_(vrt, vra)
2035 #define vxor(vrt, vra, vrb) vxor_(vrt, vra, vrb)
2036 #define vand(vrt, vra, vrb) vand_(vrt, vra, vrb)
2037 #define vsro(vrt, vra, vrb) vsro_(vrt, vra, vrb)
2038 #define vsl(vrt, vra, vrb) vsl_(vrt, vra, vrb)
2039 #define vsldoi(vt, va, vb, sh) vsldoi_(vt, va, vb, sh)
2040 #define vsr(vrt, vra, vrb) vsr_(vrt, vra, vrb)
2041 #define vadduwm(vrt, vra, vrb) vadduwm_(vrt, vra, vrb)
2042 #define vsububm(vrt, vra, vrb) vsububm_(vrt, vra, vrb)
2043 #define vsubuwm(vrt, vra, vrb) vsubuwm_(vrt, vra, vrb)
2044 #define vsrw(vrt, vra, vrb) vsrw_(vrt, vra, vrb)
2045 #define vcipher(vt, va, vb) vcipher_(vt, va, vb)
2046 #define vcipherlast(vt, va, vb) vcipherlast_(vt, va, vb)
2047 #define vncipher(vt, va, vb) vncipher_(vt, va, vb)
2048 #define vncipherlast(vt, va, vb) vncipherlast_(vt, va, vb)
2049 #define vperm(vt, va, vb, vc) vperm_(vt, va, vb, vc)
2050 #define vpmsumd(vt, va, vb) vpmsumd_(vt, va, vb)
2051 #define xxpermdi(vt, va, vb, d) xxpermdi_(vt, va, vb, d)
2053 #define lxvw4x_(xt, ra, rb) "\tlxvw4x\t" #xt "," #ra "," #rb "\n"
2054 #define stxvw4x_(xt, ra, rb) "\tstxvw4x\t" #xt "," #ra "," #rb "\n"
2056 #define label(foo) #foo "%=:\n"
2057 #define bdnz_(foo) "\tbdnz\t" #foo "%=\n"
2058 #define beq_(foo) "\tbeq\t" #foo "%=\n"
2060 #define li_(rx, value) "\tli\t" #rx "," #value "\n"
2061 #define addi_(rx, ra, imm) "\taddi\t" #rx "," #ra "," #imm "\n"
2062 #define cmpldi_(rx, imm) "\tcmpldi\t" #rx "," #imm "\n"
2063 #define mtctr_(rx) "\tmtctr\t" #rx "\n"
2064 #define vspltb_(vrt, vrb, uim) "\tvspltb\t" #vrt "," #vrb "," #uim "\n"
2065 #define vspltw_(vrt, vrb, uim) "\tvspltw\t" #vrt "," #vrb "," #uim "\n"
2066 #define vspltisb_(vrt, imm) "\tvspltisb\t" #vrt "," #imm "\n"
2067 #define vspltisw_(vrt, imm) "\tvspltisw\t" #vrt "," #imm "\n"
2068 #define vrlw_(vrt, vra, vrb) "\tvrlw\t" #vrt "," #vra "," #vrb "\n"
2069 #define vsbox_(vrt, vra) "\tvsbox\t" #vrt "," #vra "\n"
2070 #define vxor_(vrt, vra, vrb) "\tvxor\t" #vrt "," #vra "," #vrb "\n"
2071 #define vand_(vrt, vra, vrb) "\tvand\t" #vrt "," #vra "," #vrb "\n"
2072 #define vsro_(vrt, vra, vrb) "\tvsro\t" #vrt "," #vra "," #vrb "\n"
2073 #define vsl_(vrt, vra, vrb) "\tvsl\t" #vrt "," #vra "," #vrb "\n"
2074 #define vsldoi_(vt, va, vb, sh) "\tvsldoi\t" #vt "," #va "," #vb "," #sh "\n"
2075 #define vsr_(vrt, vra, vrb) "\tvsr\t" #vrt "," #vra "," #vrb "\n"
2076 #define vadduwm_(vrt, vra, vrb) "\tvadduwm\t" #vrt "," #vra "," #vrb "\n"
2077 #define vsububm_(vrt, vra, vrb) "\tvsububm\t" #vrt "," #vra "," #vrb "\n"
2078 #define vsubuwm_(vrt, vra, vrb) "\tvsubuwm\t" #vrt "," #vra "," #vrb "\n"
2079 #define vsrw_(vrt, vra, vrb) "\tvsrw\t" #vrt "," #vra "," #vrb "\n"
2080 #define vcipher_(vt, va, vb) "\tvcipher\t" #vt "," #va "," #vb "\n"
2081 #define vcipherlast_(vt, va, vb) "\tvcipherlast\t" #vt "," #va "," #vb "\n"
2082 #define vncipher_(vt, va, vb) "\tvncipher\t" #vt "," #va "," #vb "\n"
2083 #define vncipherlast_(vt, va, vb) "\tvncipherlast\t" #vt "," #va "," #vb "\n"
2084 #define vperm_(vt, va, vb, vc) "\tvperm\t" #vt "," #va "," #vb "," #vc "\n"
2085 #define vpmsumd_(vt, va, vb) "\tvpmsumd\t" #vt "," #va "," #vb "\n"
2086 #define xxpermdi_(vt, va, vb, d) "\txxpermdi\t" #vt "," #va "," #vb "," #d "\n"
2090 /* ==================================================================== */