1/* Copyright (c) (2019,2021-2023) Apple Inc. All rights reserved.
2 *
3 * corecrypto is licensed under Apple Inc.’s Internal Use License Agreement (which
4 * is contained in the License.txt file distributed with corecrypto) and only to
5 * people who accept that license. IMPORTANT: Any license rights granted to you by
6 * Apple Inc. (if any) are limited to internal use within your organization only on
7 * devices and computers you own or control, for the sole purpose of verifying the
8 * security characteristics and correct functioning of the Apple Software. You may
9 * not, directly or indirectly, redistribute the Apple Software or any portions thereof.
10 *
11 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
12 *
13 * This file contains Original Code and/or Modifications of Original Code
14 * as defined in and that are subject to the Apple Public Source License
15 * Version 2.0 (the 'License'). You may not use this file except in
16 * compliance with the License. The rights granted to you under the License
17 * may not be used to create, or enable the creation or redistribution of,
18 * unlawful or unlicensed copies of an Apple operating system, or to
19 * circumvent, violate, or enable the circumvention or violation of, any
20 * terms of an Apple operating system software license agreement.
21 *
22 * Please obtain a copy of the License at
23 * http://www.opensource.apple.com/apsl/ and read it before using this file.
24 *
25 * The Original Code and all software distributed under the License are
26 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
27 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
28 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
29 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
30 * Please see the License for the specific language governing rights and
31 * limitations under the License.
32 *
33 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
34 */
35
36#ifndef _CORECRYPTO_CC_INTERNAL_H_
37#define _CORECRYPTO_CC_INTERNAL_H_
38
39#include <corecrypto/cc_priv.h>
40#include "cc_runtime_config.h"
41
42#if CC_XNU_KERNEL_PRIVATE
43#elif CC_EFI
44#elif CC_KERNEL
45#include <libkern/libkern.h>
46#else
47#include <stdlib.h>
48#include <stdio.h>
49#endif
50
51#include <stdarg.h>
52
53#include "cc_macros.h"
54
55#if CC_EFI
56#include "cc_efi_shim.h"
57int cc_memcmp(const void *buf1, const void *buf2, size_t len);
58#else
59 #define cc_memcmp(buf1, buf2, len) memcmp(buf1, buf2, len)
60#endif
61
62extern bool cc_rdrand(uint64_t *rand);
63
64#if CC_BUILT_FOR_TESTING
65extern bool (*cc_rdrand_mock)(uint64_t *rand);
66
67extern void (*cc_abort_mock)(const char *msg);
68#endif
69
70
71#if CC_DIT_MAYBE_SUPPORTED
72
73// Use the DIT register's encoded name to avoid assembler
74// complaints when compiling for ARM64 before v8.4.
75#define CC_DIT_REGISTER "s3_3_c4_c2_5"
76
77#define CC_DIT_BIT (1U << 24)
78
79CC_INLINE bool
80cc_is_dit_enabled(void)
81{
82 return __builtin_arm_rsr64(CC_DIT_REGISTER) & CC_DIT_BIT;
83}
84
85CC_INLINE bool
86cc_enable_dit(void)
87{
88 if (!CC_HAS_DIT()) {
89 return false;
90 }
91
92 // DIT might have already been enabled by another corecrypto function, in
93 // that case that function is responsible for disabling DIT when returning.
94 //
95 // This also covers when code _outside_ corecrypto enabled DIT before
96 // calling us. In that case we're not responsible for disabling it either.
97 if (cc_is_dit_enabled()) {
98 return false;
99 }
100
101 // Encoding of <msr dit, #1>.
102 __asm__ __volatile__ (".long 0xd503415f");
103
104#if CC_BUILT_FOR_TESTING
105 // Check that DIT was enabled.
106 cc_try_abort_if(!cc_is_dit_enabled(), "DIT not enabled");
107#endif
108
109 // To the cleanup function, indicate that we toggled DIT and
110 // that cc_disable_dit() should actually disable it again.
111 return true;
112}
113
114void cc_disable_dit(volatile bool *cc_unsafe_indexable dit_was_enabled);
115
116#define CC_ENSURE_DIT_ENABLED \
117 volatile bool _cc_dit_auto_disable \
118 __attribute__((cleanup(cc_disable_dit))) \
119 __attribute__((unused)) = cc_enable_dit();
120
121#else
122
123#define CC_ENSURE_DIT_ENABLED
124
125#endif // CC_DIT_MAYBE_SUPPORTED
126
127/*!
128 * @function cc_is_vmm_present
129 * @abstract Determine if corecrypto is running in a VM
130 *
131 * @return True iff running in a VM; false otherwise
132 *
133 * @discussion This function merely checks the relevant sysctl, which
134 * may not be accurate. Thus, it should not be used to make any
135 * security decisions.
136 */
137extern bool cc_is_vmm_present(void);
138
139/*!
140 * @function cc_current_arch
141 * @abstract The architecture loaded in the current process
142 *
143 * @return A string representation of the current architecture or
144 * "unknown"
145 */
146extern const char *cc_current_arch(void);
147
148// MARK: - popcount
149
150/// Count number of bits set
151CC_INLINE CC_CONST unsigned
152cc_popcount32_fallback(uint32_t v)
153{
154 v = v - ((v >> 1) & 0x55555555);
155 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
156 return ((v + (v >> 4) & 0xf0f0f0f) * 0x1010101) >> 24;
157}
158
159/// Count number of bits set
160CC_INLINE CC_CONST unsigned
161cc_popcount64_fallback(uint64_t v)
162{
163 v = v - ((v >> 1) & 0x5555555555555555);
164 v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
165 v = (v + (v >> 4)) & 0xf0f0f0f0f0f0f0f;
166 return (v * 0x101010101010101) >> 56;
167}
168
169/// Count number of bits set
170CC_INLINE CC_CONST unsigned
171cc_popcount32(uint32_t data)
172{
173#if __has_builtin(__builtin_popcount)
174 return (unsigned)__builtin_popcount(data);
175#else
176 return cc_popcount32_fallback(data);
177#endif
178}
179
180/// Count number of bits set
181CC_INLINE CC_CONST unsigned
182cc_popcount64(uint64_t data)
183{
184#if __has_builtin(__builtin_popcountll)
185 return (unsigned)__builtin_popcountll(data);
186#else
187 return cc_popcount64_fallback(data);
188#endif
189}
190
191// Use with volatile variables only.
192#define CC_MULTI_IF_AND(condition) \
193 ((condition) && (condition) && (condition))
194
195// MARK: - Byte Extraction
196#ifdef _MSC_VER
197#define cc_byte(x, n) ((unsigned char)((x) >> (8 * (n))))
198#else
199#define cc_byte(x, n) (((x) >> (8 * (n))) & 255)
200#endif
201
202// MARK: - 32-bit Rotates
203
204#if defined(_MSC_VER)
205// MARK: -- MSVC version
206
207#include <stdlib.h>
208#if !defined(__clang__)
209 #pragma intrinsic(_lrotr,_lrotl)
210#endif
211#define CC_ROR(x, n) _lrotr(x,n)
212#define CC_ROL(x, n) _lrotl(x,n)
213#define CC_RORc(x, n) _lrotr(x,n)
214#define CC_ROLc(x, n) _lrotl(x,n)
215
216#elif (defined(__i386__) || defined(__x86_64__))
217// MARK: -- intel asm version
218
219CC_INLINE uint32_t
220CC_ROL(uint32_t word, int i)
221{
222 __asm__ ("roll %%cl,%0"
223 :"=r" (word)
224 :"0" (word),"c" (i));
225 return word;
226}
227
228CC_INLINE uint32_t
229CC_ROR(uint32_t word, int i)
230{
231 __asm__ ("rorl %%cl,%0"
232 :"=r" (word)
233 :"0" (word),"c" (i));
234 return word;
235}
236
237/* Need to be a macro here, because 'i' is an immediate (constant) */
238#define CC_ROLc(word, i) \
239({ uint32_t _word=(word); \
240 __asm__ __volatile__ ("roll %2,%0" \
241 :"=r" (_word) \
242 :"0" (_word),"I" (i)); \
243 _word; \
244})
245
246
247#define CC_RORc(word, i) \
248({ uint32_t _word=(word); \
249 __asm__ __volatile__ ("rorl %2,%0" \
250 :"=r" (_word) \
251 :"0" (_word),"I" (i)); \
252 _word; \
253})
254
255#else
256
257// MARK: -- default version
258
259CC_INLINE uint32_t
260CC_ROL(uint32_t word, int i)
261{
262 return (word << (i & 31)) | (word >> ((32 - (i & 31)) & 31));
263}
264
265CC_INLINE uint32_t
266CC_ROR(uint32_t word, int i)
267{
268 return (word >> (i & 31)) | (word << ((32 - (i & 31)) & 31));
269}
270
271#define CC_ROLc(x, y) CC_ROL(x, y)
272#define CC_RORc(x, y) CC_ROR(x, y)
273
274#endif
275
276// MARK: - 64 bits rotates
277
278#if defined(__x86_64__) && !defined(_MSC_VER) //clang _MSVC doesn't support GNU-style inline assembly
279// MARK: -- intel 64 asm version
280
281CC_INLINE uint64_t
282CC_ROL64(uint64_t word, int i)
283{
284 __asm__("rolq %%cl,%0"
285 :"=r" (word)
286 :"0" (word),"c" (i));
287 return word;
288}
289
290CC_INLINE uint64_t
291CC_ROR64(uint64_t word, int i)
292{
293 __asm__("rorq %%cl,%0"
294 :"=r" (word)
295 :"0" (word),"c" (i));
296 return word;
297}
298
299/* Need to be a macro here, because 'i' is an immediate (constant) */
300#define CC_ROL64c(word, i) \
301({ \
302 uint64_t _word=(word); \
303 __asm__("rolq %2,%0" \
304 :"=r" (_word) \
305 :"0" (_word),"J" (i)); \
306 _word; \
307})
308
309#define CC_ROR64c(word, i) \
310({ \
311 uint64_t _word=(word); \
312 __asm__("rorq %2,%0" \
313 :"=r" (_word) \
314 :"0" (_word),"J" (i)); \
315 _word; \
316})
317
318
319#else /* Not x86_64 */
320
321// MARK: -- default C version
322
323CC_INLINE uint64_t
324CC_ROL64(uint64_t word, int i)
325{
326 return (word << (i & 63)) | (word >> ((64 - (i & 63)) & 63));
327}
328
329CC_INLINE uint64_t
330CC_ROR64(uint64_t word, int i)
331{
332 return (word >> (i & 63)) | (word << ((64 - (i & 63)) & 63));
333}
334
335#define CC_ROL64c(x, y) CC_ROL64(x, y)
336#define CC_ROR64c(x, y) CC_ROR64(x, y)
337
338#endif
339
340// MARK: -- Count Leading / Trailing Zeros
341/* Count leading zeros (for nonzero inputs) */
342
343/*
344 * On i386 and x86_64, we know clang and GCC will generate BSR for
345 * __builtin_clzl. This instruction IS NOT constant time on all micro-
346 * architectures, but it *is* constant time on all micro-architectures that
347 * have been used by Apple, and we expect that to continue to be the case.
348 *
349 * When building for x86_64h with clang, this produces LZCNT, which is exactly
350 * what we want.
351 *
352 * On arm and arm64, we know that clang and GCC generate the constant-time CLZ
353 * instruction from __builtin_clzl( ).
354 */
355
356#if defined(_WIN32)
357/* We use the Windows implementations below. */
358#elif defined(__x86_64__) || defined(__i386__) || defined(__arm64__) || defined(__arm__)
359/* We use a thought-to-be-good version of __builtin_clz. */
360#elif defined __GNUC__
361#warning Using __builtin_clz() on an unknown architecture; it may not be constant-time.
362/* If you find yourself seeing this warning, file a radar for someone to
363 * check whether or not __builtin_clz() generates a constant-time
364 * implementation on the architecture you are targeting. If it does, append
365 * the name of that architecture to the list of "safe" architectures above. */
366#endif
367
368CC_INLINE CC_CONST unsigned
369cc_clz32_fallback(uint32_t data)
370{
371 unsigned int b = 0;
372 unsigned int bit = 0;
373 // Work from LSB to MSB
374 for (int i = 0; i < 32; i++) {
375 bit = (data >> i) & 1;
376 // If the bit is 0, update the "leading bits are zero" counter "b".
377 b += (1 - bit);
378 /* If the bit is 0, (bit - 1) is 0xffff... therefore b is retained.
379 * If the bit is 1, (bit - 1) is 0 therefore b is set to 0.
380 */
381 b &= (bit - 1);
382 }
383 return b;
384}
385
386CC_INLINE CC_CONST unsigned
387cc_clz64_fallback(uint64_t data)
388{
389 unsigned int b = 0;
390 unsigned int bit = 0;
391 // Work from LSB to MSB
392 for (int i = 0; i < 64; i++) {
393 bit = (data >> i) & 1;
394 // If the bit is 0, update the "leading bits are zero" counter.
395 b += (1 - bit);
396 /* If the bit is 0, (bit - 1) is 0xffff... therefore b is retained.
397 * If the bit is 1, (bit - 1) is 0 therefore b is set to 0.
398 */
399 b &= (bit - 1);
400 }
401 return b;
402}
403
404CC_INLINE CC_CONST unsigned
405cc_ctz32_fallback(uint32_t data)
406{
407 unsigned int b = 0;
408 unsigned int bit = 0;
409 // Work from MSB to LSB
410 for (int i = 31; i >= 0; i--) {
411 bit = (data >> i) & 1;
412 // If the bit is 0, update the "trailing zero bits" counter.
413 b += (1 - bit);
414 /* If the bit is 0, (bit - 1) is 0xffff... therefore b is retained.
415 * If the bit is 1, (bit - 1) is 0 therefore b is set to 0.
416 */
417 b &= (bit - 1);
418 }
419 return b;
420}
421
422CC_INLINE CC_CONST unsigned
423cc_ctz64_fallback(uint64_t data)
424{
425 unsigned int b = 0;
426 unsigned int bit = 0;
427 // Work from MSB to LSB
428 for (int i = 63; i >= 0; i--) {
429 bit = (data >> i) & 1;
430 // If the bit is 0, update the "trailing zero bits" counter.
431 b += (1 - bit);
432 /* If the bit is 0, (bit - 1) is 0xffff... therefore b is retained.
433 * If the bit is 1, (bit - 1) is 0 therefore b is set to 0.
434 */
435 b &= (bit - 1);
436 }
437 return b;
438}
439
440/*!
441 * @function cc_clz32
442 * @abstract Count leading zeros of a nonzero 32-bit value
443 *
444 * @param data A nonzero 32-bit value
445 *
446 * @result Count of leading zeros of @p data
447 *
448 * @discussion @p data is assumed to be nonzero.
449 */
450CC_INLINE CC_CONST unsigned
451cc_clz32(uint32_t data)
452{
453 cc_assert(data != 0);
454#if __has_builtin(__builtin_clz)
455 cc_static_assert(sizeof(unsigned) == 4, "clz relies on an unsigned int being 4 bytes");
456 return (unsigned)__builtin_clz(data);
457#else
458 return cc_clz32_fallback(data);
459#endif
460}
461
462/*!
463 * @function cc_clz64
464 * @abstract Count leading zeros of a nonzero 64-bit value
465 *
466 * @param data A nonzero 64-bit value
467 *
468 * @result Count of leading zeros of @p data
469 *
470 * @discussion @p data is assumed to be nonzero.
471 */
472CC_INLINE CC_CONST unsigned
473cc_clz64(uint64_t data)
474{
475 cc_assert(data != 0);
476#if __has_builtin(__builtin_clzll)
477 return (unsigned)__builtin_clzll(data);
478#else
479 return cc_clz64_fallback(data);
480#endif
481}
482
483/*!
484 * @function cc_ctz32
485 * @abstract Count trailing zeros of a nonzero 32-bit value
486 *
487 * @param data A nonzero 32-bit value
488 *
489 * @result Count of trailing zeros of @p data
490 *
491 * @discussion @p data is assumed to be nonzero.
492 */
493CC_INLINE CC_CONST unsigned
494cc_ctz32(uint32_t data)
495{
496 cc_assert(data != 0);
497#if __has_builtin(__builtin_ctz)
498 cc_static_assert(sizeof(unsigned) == 4, "ctz relies on an unsigned int being 4 bytes");
499 return (unsigned)__builtin_ctz(data);
500#else
501 return cc_ctz32_fallback(data);
502#endif
503}
504
505/*!
506 * @function cc_ctz64
507 * @abstract Count trailing zeros of a nonzero 64-bit value
508 *
509 * @param data A nonzero 64-bit value
510 *
511 * @result Count of trailing zeros of @p data
512 *
513 * @discussion @p data is assumed to be nonzero.
514 */
515CC_INLINE CC_CONST unsigned
516cc_ctz64(uint64_t data)
517{
518 cc_assert(data != 0);
519#if __has_builtin(__builtin_ctzll)
520 return (unsigned)__builtin_ctzll(data);
521#else
522 return cc_ctz64_fallback(data);
523#endif
524}
525
526// MARK: -- Find first bit set
527
528/*!
529 * @function cc_ffs32_fallback
530 * @abstract Find first bit set in a 32-bit value
531 *
532 * @param data A 32-bit value
533 *
534 * @result One plus the index of the least-significant bit set in @p data or, if @p data is zero, zero
535 */
536CC_INLINE CC_CONST unsigned
537cc_ffs32_fallback(int32_t data)
538{
539 unsigned b = 0;
540 unsigned bit = 0;
541 unsigned seen = 0;
542
543 // Work from LSB to MSB
544 for (int i = 0; i < 32; i++) {
545 bit = ((uint32_t)data >> i) & 1;
546
547 // Track whether we've seen a 1 bit.
548 seen |= bit;
549
550 // If the bit is 0 and we haven't seen a 1 yet, increment b.
551 b += (1 - bit) & (seen - 1);
552 }
553
554 // If we saw a 1, return b + 1, else 0.
555 return (~(seen - 1)) & (b + 1);
556}
557
558/*!
559 * @function cc_ffs64_fallback
560 * @abstract Find first bit set in a 64-bit value
561 *
562 * @param data A 64-bit value
563 *
564 * @result One plus the index of the least-significant bit set in @p data or, if @p data is zero, zero
565 */
566CC_INLINE CC_CONST unsigned
567cc_ffs64_fallback(int64_t data)
568{
569 unsigned b = 0;
570 unsigned bit = 0;
571 unsigned seen = 0;
572
573 // Work from LSB to MSB
574 for (int i = 0; i < 64; i++) {
575 bit = ((uint64_t)data >> i) & 1;
576
577 // Track whether we've seen a 1 bit.
578 seen |= bit;
579
580 // If the bit is 0 and we haven't seen a 1 yet, increment b.
581 b += (1 - bit) & (seen - 1);
582 }
583
584 // If we saw a 1, return b + 1, else 0.
585 return (~(seen - 1)) & (b + 1);
586}
587
588/*!
589 * @function cc_ffs32
590 * @abstract Find first bit set in a 32-bit value
591 *
592 * @param data A 32-bit value
593 *
594 * @result One plus the index of the least-significant bit set in @p data or, if @p data is zero, zero
595 */
596CC_INLINE CC_CONST unsigned
597cc_ffs32(int32_t data)
598{
599 cc_static_assert(sizeof(int) == 4, "ffs relies on an int being 4 bytes");
600#if __has_builtin(__builtin_ffs)
601 return (unsigned)__builtin_ffs(data);
602#else
603 return cc_ffs32_fallback(data);
604#endif
605}
606
607/*!
608 * @function cc_ffs64
609 * @abstract Find first bit set in a 64-bit value
610 *
611 * @param data A 64-bit value
612 *
613 * @result One plus the index of the least-significant bit set in @p data or, if @p data is zero, zero
614 */
615CC_INLINE CC_CONST unsigned
616cc_ffs64(int64_t data)
617{
618#if __has_builtin(__builtin_ffsll)
619 return (unsigned)__builtin_ffsll(data);
620#else
621 return cc_ffs64_fallback(data);
622#endif
623}
624
625// MARK: -- Overflow wrappers
626#define cc_add_overflow __builtin_add_overflow
627
628// On 32-bit architectures, clang emits libcalls to __mulodi4 when
629// __builtin_mul_overflow() encounters `long long` types.
630//
631// The libgcc runtime does not provide __mulodi4, so for Linux on ARMv7
632// we cannot call __builtin_mul_overflow().
633//
634// Using __has_builtin(__builtin_mul_overflow) would be better but that will
635// return the correct response for ARMv7/Linux only with LLVM-14 or higher.
636#if defined(__clang__) && defined(__arm__) && CC_LINUX
637CC_INLINE bool
638cc_mul_overflow(uint64_t a, uint64_t b, uint64_t *r)
639{
640 *r = a * b;
641 return (a != 0) && ((*r / a) != b);
642}
643#else
644#define cc_mul_overflow __builtin_mul_overflow
645#endif
646
647// MARK: -- Heavyside Step
648/* HEAVISIDE_STEP (shifted by one)
649 * function f(x): x->0, when x=0
650 * x->1, when x>0
651 * Can also be seen as a bitwise operation:
652 * f(x): x -> y
653 * y[0]=(OR x[i]) for all i (all bits)
654 * y[i]=0 for all i>0
655 * Run in constant time (log2(<bitsize of x>))
656 * Useful to run constant time checks
657 */
658#define CC_HEAVISIDE_STEP(r, s) do { \
659 cc_static_assert(sizeof(uint64_t) >= sizeof(s), "max type is uint64_t"); \
660 const uint64_t _s = (uint64_t)s; \
661 const uint64_t _t = (_s & 0xffffffff) | (_s >> 32); \
662 r = (uint8_t)((_t + 0xffffffff) >> 32); \
663} while (0)
664
665/* Return 1 if x mod 4 =1,2,3, 0 otherwise */
666#define CC_CARRY_2BITS(x) (((x>>1) | x) & 0x1)
667#define CC_CARRY_3BITS(x) (((x>>2) | (x>>1) | x) & 0x1)
668
669/*!
670 * @brief CC_MUXU(r, s, a, b) is equivalent to r = s ? a : b, but executes in constant time
671 * @param a Input a
672 * @param b Input b
673 * @param s Selection parameter s. Must be 0 or 1.
674 * @param r Output, set to a if s=1, or b if s=0.
675 */
676#define CC_MUXU(r, s, a, b) do { \
677 cc_assert((s) == 0 || (s) == 1); \
678 r = (~((s)-1) & (a)) | (((s)-1) & (b)); \
679} while (0)
680
681#endif // _CORECRYPTO_CC_INTERNAL_H_
682