include/internal/constant_time_locl.h

   1 /*
   2  * Copyright 2014-2018 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #ifndef HEADER_CONSTANT_TIME_LOCL_H
  11 # define HEADER_CONSTANT_TIME_LOCL_H
  12
  13 # include <stdlib.h>
  14 # include <string.h>
  15 # include <openssl/e_os2.h>              /* For 'ossl_inline' */
  16
  17 #ifdef __cplusplus
  18 extern "C" {
  19 #endif
  20
  21 /*-
  22  * The boolean methods return a bitmask of all ones (0xff...f) for true
  23  * and 0 for false. This is useful for choosing a value based on the result
  24  * of a conditional in constant time. For example,
  25  *      if (a < b) {
  26  *        c = a;
  27  *      } else {
  28  *        c = b;
  29  *      }
  30  * can be written as
  31  *      unsigned int lt = constant_time_lt(a, b);
  32  *      c = constant_time_select(lt, a, b);
  33  */
  34
  35 /* Returns the given value with the MSB copied to all the other bits. */
  36 static ossl_inline unsigned int constant_time_msb(unsigned int a);
  37 /* Convenience method for uint32_t. */
  38 static ossl_inline uint32_t constant_time_msb_32(uint32_t a);
  39 /* Convenience method for uint64_t. */
  40 static ossl_inline uint64_t constant_time_msb_64(uint64_t a);
  41
  42 /* Returns 0xff..f if a < b and 0 otherwise. */
  43 static ossl_inline unsigned int constant_time_lt(unsigned int a,
  44                                                  unsigned int b);
  45 /* Convenience method for getting an 8-bit mask. */
  46 static ossl_inline unsigned char constant_time_lt_8(unsigned int a,
  47                                                     unsigned int b);
  48 /* Convenience method for uint64_t. */
  49 static ossl_inline uint64_t constant_time_lt_64(uint64_t a, uint64_t b);
  50
  51 /* Returns 0xff..f if a >= b and 0 otherwise. */
  52 static ossl_inline unsigned int constant_time_ge(unsigned int a,
  53                                                  unsigned int b);
  54 /* Convenience method for getting an 8-bit mask. */
  55 static ossl_inline unsigned char constant_time_ge_8(unsigned int a,
  56                                                     unsigned int b);
  57
  58 /* Returns 0xff..f if a == 0 and 0 otherwise. */
  59 static ossl_inline unsigned int constant_time_is_zero(unsigned int a);
  60 /* Convenience method for getting an 8-bit mask. */
  61 static ossl_inline unsigned char constant_time_is_zero_8(unsigned int a);
  62 /* Convenience method for getting a 32-bit mask. */
  63 static ossl_inline uint32_t constant_time_is_zero_32(uint32_t a);
  64
  65 /* Returns 0xff..f if a == b and 0 otherwise. */
  66 static ossl_inline unsigned int constant_time_eq(unsigned int a,
  67                                                  unsigned int b);
  68 /* Convenience method for getting an 8-bit mask. */
  69 static ossl_inline unsigned char constant_time_eq_8(unsigned int a,
  70                                                     unsigned int b);
  71 /* Signed integers. */
  72 static ossl_inline unsigned int constant_time_eq_int(int a, int b);
  73 /* Convenience method for getting an 8-bit mask. */
  74 static ossl_inline unsigned char constant_time_eq_int_8(int a, int b);
  75
  76 /*-
  77  * Returns (mask & a) | (~mask & b).
  78  *
  79  * When |mask| is all 1s or all 0s (as returned by the methods above),
  80  * the select methods return either |a| (if |mask| is nonzero) or |b|
  81  * (if |mask| is zero).
  82  */
  83 static ossl_inline unsigned int constant_time_select(unsigned int mask,
  84                                                      unsigned int a,
  85                                                      unsigned int b);
  86 /* Convenience method for unsigned chars. */
  87 static ossl_inline unsigned char constant_time_select_8(unsigned char mask,
  88                                                         unsigned char a,
  89                                                         unsigned char b);
  90
  91 /* Convenience method for uint32_t. */
  92 static ossl_inline uint32_t constant_time_select_32(uint32_t mask, uint32_t a,
  93                                                     uint32_t b);
  94
  95 /* Convenience method for uint64_t. */
  96 static ossl_inline uint64_t constant_time_select_64(uint64_t mask, uint64_t a,
  97                                                     uint64_t b);
  98 /* Convenience method for signed integers. */
  99 static ossl_inline int constant_time_select_int(unsigned int mask, int a,
 100                                                 int b);
 101
 102
 103 static ossl_inline unsigned int constant_time_msb(unsigned int a)
 104 {
 105     return 0 - (a >> (sizeof(a) * 8 - 1));
 106 }
 107
 108
 109 static ossl_inline uint32_t constant_time_msb_32(uint32_t a)
 110 {
 111     return 0 - (a >> 31);
 112 }
 113
 114 static ossl_inline uint64_t constant_time_msb_64(uint64_t a)
 115 {
 116     return 0 - (a >> 63);
 117 }
 118
 119 static ossl_inline size_t constant_time_msb_s(size_t a)
 120 {
 121     return 0 - (a >> (sizeof(a) * 8 - 1));
 122 }
 123
 124 static ossl_inline unsigned int constant_time_lt(unsigned int a,
 125                                                  unsigned int b)
 126 {
 127     return constant_time_msb(a ^ ((a ^ b) | ((a - b) ^ b)));
 128 }
 129
 130 static ossl_inline size_t constant_time_lt_s(size_t a, size_t b)
 131 {
 132     return constant_time_msb_s(a ^ ((a ^ b) | ((a - b) ^ b)));
 133 }
 134
 135 static ossl_inline unsigned char constant_time_lt_8(unsigned int a,
 136                                                     unsigned int b)
 137 {
 138     return (unsigned char)constant_time_lt(a, b);
 139 }
 140
 141 static ossl_inline uint64_t constant_time_lt_64(uint64_t a, uint64_t b)
 142 {
 143     return constant_time_msb_64(a ^ ((a ^ b) | ((a - b) ^ b)));
 144 }
 145
 146 static ossl_inline unsigned int constant_time_ge(unsigned int a,
 147                                                  unsigned int b)
 148 {
 149     return ~constant_time_lt(a, b);
 150 }
 151
 152 static ossl_inline size_t constant_time_ge_s(size_t a, size_t b)
 153 {
 154     return ~constant_time_lt_s(a, b);
 155 }
 156
 157 static ossl_inline unsigned char constant_time_ge_8(unsigned int a,
 158                                                     unsigned int b)
 159 {
 160     return (unsigned char)constant_time_ge(a, b);
 161 }
 162
 163 static ossl_inline unsigned char constant_time_ge_8_s(size_t a, size_t b)
 164 {
 165     return (unsigned char)constant_time_ge_s(a, b);
 166 }
 167
 168 static ossl_inline unsigned int constant_time_is_zero(unsigned int a)
 169 {
 170     return constant_time_msb(~a & (a - 1));
 171 }
 172
 173 static ossl_inline size_t constant_time_is_zero_s(size_t a)
 174 {
 175     return constant_time_msb_s(~a & (a - 1));
 176 }
 177
 178 static ossl_inline unsigned char constant_time_is_zero_8(unsigned int a)
 179 {
 180     return (unsigned char)constant_time_is_zero(a);
 181 }
 182
 183 static ossl_inline uint32_t constant_time_is_zero_32(uint32_t a)
 184 {
 185     return constant_time_msb_32(~a & (a - 1));
 186 }
 187
 188 static ossl_inline unsigned int constant_time_eq(unsigned int a,
 189                                                  unsigned int b)
 190 {
 191     return constant_time_is_zero(a ^ b);
 192 }
 193
 194 static ossl_inline size_t constant_time_eq_s(size_t a, size_t b)
 195 {
 196     return constant_time_is_zero_s(a ^ b);
 197 }
 198
 199 static ossl_inline unsigned char constant_time_eq_8(unsigned int a,
 200                                                     unsigned int b)
 201 {
 202     return (unsigned char)constant_time_eq(a, b);
 203 }
 204
 205 static ossl_inline unsigned char constant_time_eq_8_s(size_t a, size_t b)
 206 {
 207     return (unsigned char)constant_time_eq_s(a, b);
 208 }
 209
 210 static ossl_inline unsigned int constant_time_eq_int(int a, int b)
 211 {
 212     return constant_time_eq((unsigned)(a), (unsigned)(b));
 213 }
 214
 215 static ossl_inline unsigned char constant_time_eq_int_8(int a, int b)
 216 {
 217     return constant_time_eq_8((unsigned)(a), (unsigned)(b));
 218 }
 219
 220 static ossl_inline unsigned int constant_time_select(unsigned int mask,
 221                                                      unsigned int a,
 222                                                      unsigned int b)
 223 {
 224     return (mask & a) | (~mask & b);
 225 }
 226
 227 static ossl_inline size_t constant_time_select_s(size_t mask,
 228                                                  size_t a,
 229                                                  size_t b)
 230 {
 231     return (mask & a) | (~mask & b);
 232 }
 233
 234 static ossl_inline unsigned char constant_time_select_8(unsigned char mask,
 235                                                         unsigned char a,
 236                                                         unsigned char b)
 237 {
 238     return (unsigned char)constant_time_select(mask, a, b);
 239 }
 240
 241 static ossl_inline int constant_time_select_int(unsigned int mask, int a,
 242                                                 int b)
 243 {
 244     return (int)constant_time_select(mask, (unsigned)(a), (unsigned)(b));
 245 }
 246
 247 static ossl_inline int constant_time_select_int_s(size_t mask, int a, int b)
 248 {
 249     return (int)constant_time_select((unsigned)mask, (unsigned)(a),
 250                                       (unsigned)(b));
 251 }
 252
 253 static ossl_inline uint32_t constant_time_select_32(uint32_t mask, uint32_t a,
 254                                                     uint32_t b)
 255 {
 256     return (mask & a) | (~mask & b);
 257 }
 258
 259 static ossl_inline uint64_t constant_time_select_64(uint64_t mask, uint64_t a,
 260                                                     uint64_t b)
 261 {
 262     return (mask & a) | (~mask & b);
 263 }
 264
 265 /*
 266  * mask must be 0xFFFFFFFF or 0x00000000.
 267  *
 268  * if (mask) {
 269  *     uint32_t tmp = *a;
 270  *
 271  *     *a = *b;
 272  *     *b = tmp;
 273  * }
 274  */
 275 static ossl_inline void constant_time_cond_swap_32(uint32_t mask, uint32_t *a,
 276                                                    uint32_t *b)
 277 {
 278     uint32_t xor = *a ^ *b;
 279
 280     xor &= mask;
 281     *a ^= xor;
 282     *b ^= xor;
 283 }
 284
 285 /*
 286  * mask must be 0xFFFFFFFF or 0x00000000.
 287  *
 288  * if (mask) {
 289  *     uint64_t tmp = *a;
 290  *
 291  *     *a = *b;
 292  *     *b = tmp;
 293  * }
 294  */
 295 static ossl_inline void constant_time_cond_swap_64(uint64_t mask, uint64_t *a,
 296                                                    uint64_t *b)
 297 {
 298     uint64_t xor = *a ^ *b;
 299
 300     xor &= mask;
 301     *a ^= xor;
 302     *b ^= xor;
 303 }
 304
 305 /*
 306  * table is a two dimensional array of bytes. Each row has rowsize elements.
 307  * Copies row number idx into out. rowsize and numrows are not considered
 308  * private.
 309  */
 310 static ossl_inline void constant_time_lookup(void *out,
 311                                              const void *table,
 312                                              size_t rowsize,
 313                                              size_t numrows,
 314                                              size_t idx)
 315 {
 316     size_t i, j;
 317     const unsigned char *tablec = (const unsigned char *)table;
 318     unsigned char *outc = (unsigned char *)out;
 319     unsigned char mask;
 320
 321     memset(out, 0, rowsize);
 322
 323     /* Note idx may underflow - but that is well defined */
 324     for (i = 0; i < numrows; i++, idx--) {
 325         mask = (unsigned char)constant_time_is_zero_s(idx);
 326         for (j = 0; j < rowsize; j++)
 327             *(outc + j) |= constant_time_select_8(mask, *(tablec++), 0);
 328     }
 329 }
 330
 331 #ifdef __cplusplus
 332 }
 333 #endif
 334
 335 #endif                          /* HEADER_CONSTANT_TIME_LOCL_H */