contrib/wpa/src/utils/const_time.h

   1 /*
   2  * Helper functions for constant time operations
   3  * Copyright (c) 2019, The Linux Foundation
   4  *
   5  * This software may be distributed under the terms of the BSD license.
   6  * See README for more details.
   7  *
   8  * These helper functions can be used to implement logic that needs to minimize
   9  * externally visible differences in execution path by avoiding use of branches,
  10  * avoiding early termination or other time differences, and forcing same memory
  11  * access pattern regardless of values.
  12  */
  13
  14 #ifndef CONST_TIME_H
  15 #define CONST_TIME_H
  16
  17
  18 #if defined(__clang__)
  19 #define NO_UBSAN_UINT_OVERFLOW \
  20         __attribute__((no_sanitize("unsigned-integer-overflow")))
  21 #else
  22 #define NO_UBSAN_UINT_OVERFLOW
  23 #endif
  24
  25
  26 /**
  27  * const_time_fill_msb - Fill all bits with MSB value
  28  * @val: Input value
  29  * Returns: Value with all the bits set to the MSB of the input val
  30  */
  31 static inline unsigned int const_time_fill_msb(unsigned int val)
  32 {
  33         /* Move the MSB to LSB and multiple by -1 to fill in all bits. */
  34         return (val >> (sizeof(val) * 8 - 1)) * ~0U;
  35 }
  36
  37
  38 /* Returns: -1 if val is zero; 0 if val is not zero */
  39 static inline unsigned int const_time_is_zero(unsigned int val)
  40         NO_UBSAN_UINT_OVERFLOW
  41 {
  42         /* Set MSB to 1 for 0 and fill rest of bits with the MSB value */
  43         return const_time_fill_msb(~val & (val - 1));
  44 }
  45
  46
  47 /* Returns: -1 if a == b; 0 if a != b */
  48 static inline unsigned int const_time_eq(unsigned int a, unsigned int b)
  49 {
  50         return const_time_is_zero(a ^ b);
  51 }
  52
  53
  54 /* Returns: -1 if a == b; 0 if a != b */
  55 static inline u8 const_time_eq_u8(unsigned int a, unsigned int b)
  56 {
  57         return (u8) const_time_eq(a, b);
  58 }
  59
  60
  61 /**
  62  * const_time_eq_bin - Constant time memory comparison
  63  * @a: First buffer to compare
  64  * @b: Second buffer to compare
  65  * @len: Number of octets to compare
  66  * Returns: -1 if buffers are equal, 0 if not
  67  *
  68  * This function is meant for comparing passwords or hash values where
  69  * difference in execution time or memory access pattern could provide external
  70  * observer information about the location of the difference in the memory
  71  * buffers. The return value does not behave like memcmp(), i.e.,
  72  * const_time_eq_bin() cannot be used to sort items into a defined order. Unlike
  73  * memcmp(), the execution time of const_time_eq_bin() does not depend on the
  74  * contents of the compared memory buffers, but only on the total compared
  75  * length.
  76  */
  77 static inline unsigned int const_time_eq_bin(const void *a, const void *b,
  78                                              size_t len)
  79 {
  80         const u8 *aa = a;
  81         const u8 *bb = b;
  82         size_t i;
  83         u8 res = 0;
  84
  85         for (i = 0; i < len; i++)
  86                 res |= aa[i] ^ bb[i];
  87
  88         return const_time_is_zero(res);
  89 }
  90
  91
  92 /**
  93  * const_time_select - Constant time unsigned int selection
  94  * @mask: 0 (false) or -1 (true) to identify which value to select
  95  * @true_val: Value to select for the true case
  96  * @false_val: Value to select for the false case
  97  * Returns: true_val if mask == -1, false_val if mask == 0
  98  */
  99 static inline unsigned int const_time_select(unsigned int mask,
 100                                              unsigned int true_val,
 101                                              unsigned int false_val)
 102 {
 103         return (mask & true_val) | (~mask & false_val);
 104 }
 105
 106
 107 /**
 108  * const_time_select_int - Constant time int selection
 109  * @mask: 0 (false) or -1 (true) to identify which value to select
 110  * @true_val: Value to select for the true case
 111  * @false_val: Value to select for the false case
 112  * Returns: true_val if mask == -1, false_val if mask == 0
 113  */
 114 static inline int const_time_select_int(unsigned int mask, int true_val,
 115                                         int false_val)
 116 {
 117         return (int) const_time_select(mask, (unsigned int) true_val,
 118                                        (unsigned int) false_val);
 119 }
 120
 121
 122 /**
 123  * const_time_select_u8 - Constant time u8 selection
 124  * @mask: 0 (false) or -1 (true) to identify which value to select
 125  * @true_val: Value to select for the true case
 126  * @false_val: Value to select for the false case
 127  * Returns: true_val if mask == -1, false_val if mask == 0
 128  */
 129 static inline u8 const_time_select_u8(u8 mask, u8 true_val, u8 false_val)
 130 {
 131         return (u8) const_time_select(mask, true_val, false_val);
 132 }
 133
 134
 135 /**
 136  * const_time_select_s8 - Constant time s8 selection
 137  * @mask: 0 (false) or -1 (true) to identify which value to select
 138  * @true_val: Value to select for the true case
 139  * @false_val: Value to select for the false case
 140  * Returns: true_val if mask == -1, false_val if mask == 0
 141  */
 142 static inline s8 const_time_select_s8(u8 mask, s8 true_val, s8 false_val)
 143 {
 144         return (s8) const_time_select(mask, (unsigned int) true_val,
 145                                       (unsigned int) false_val);
 146 }
 147
 148
 149 /**
 150  * const_time_select_bin - Constant time binary buffer selection copy
 151  * @mask: 0 (false) or -1 (true) to identify which value to copy
 152  * @true_val: Buffer to copy for the true case
 153  * @false_val: Buffer to copy for the false case
 154  * @len: Number of octets to copy
 155  * @dst: Destination buffer for the copy
 156  *
 157  * This function copies the specified buffer into the destination buffer using
 158  * operations with identical memory access pattern regardless of which buffer
 159  * is being copied.
 160  */
 161 static inline void const_time_select_bin(u8 mask, const u8 *true_val,
 162                                          const u8 *false_val, size_t len,
 163                                          u8 *dst)
 164 {
 165         size_t i;
 166
 167         for (i = 0; i < len; i++)
 168                 dst[i] = const_time_select_u8(mask, true_val[i], false_val[i]);
 169 }
 170
 171
 172 static inline int const_time_memcmp(const void *a, const void *b, size_t len)
 173 {
 174         const u8 *aa = a;
 175         const u8 *bb = b;
 176         int diff, res = 0;
 177         unsigned int mask;
 178
 179         if (len == 0)
 180                 return 0;
 181         do {
 182                 len--;
 183                 diff = (int) aa[len] - (int) bb[len];
 184                 mask = const_time_is_zero((unsigned int) diff);
 185                 res = const_time_select_int(mask, res, diff);
 186         } while (len);
 187
 188         return res;
 189 }
 190
 191 #endif /* CONST_TIME_H */