include/internal/constant_time.h

   1 /*
   2  * Copyright 2014-2021 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License 2.0 (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 OSSL_INTERNAL_CONSTANT_TIME_H
  11 # define OSSL_INTERNAL_CONSTANT_TIME_H
  12 # pragma once
  13
  14 # include <stdlib.h>
  15 # include <string.h>
  16 # include <openssl/e_os2.h>              /* For 'ossl_inline' */
  17
  18 /*-
  19  * The boolean methods return a bitmask of all ones (0xff...f) for true
  20  * and 0 for false. This is useful for choosing a value based on the result
  21  * of a conditional in constant time. For example,
  22  *      if (a < b) {
  23  *        c = a;
  24  *      } else {
  25  *        c = b;
  26  *      }
  27  * can be written as
  28  *      unsigned int lt = constant_time_lt(a, b);
  29  *      c = constant_time_select(lt, a, b);
  30  */
  31
  32 /* Returns the given value with the MSB copied to all the other bits. */
  33 static ossl_inline unsigned int constant_time_msb(unsigned int a);
  34 /* Convenience method for uint32_t. */
  35 static ossl_inline uint32_t constant_time_msb_32(uint32_t a);
  36 /* Convenience method for uint64_t. */
  37 static ossl_inline uint64_t constant_time_msb_64(uint64_t a);
  38
  39 /* Returns 0xff..f if a < b and 0 otherwise. */
  40 static ossl_inline unsigned int constant_time_lt(unsigned int a,
  41                                                  unsigned int b);
  42 /* Convenience method for getting an 8-bit mask. */
  43 static ossl_inline unsigned char constant_time_lt_8(unsigned int a,
  44                                                     unsigned int b);
  45 /* Convenience method for uint64_t. */
  46 static ossl_inline uint64_t constant_time_lt_64(uint64_t a, uint64_t b);
  47
  48 /* Returns 0xff..f if a >= b and 0 otherwise. */
  49 static ossl_inline unsigned int constant_time_ge(unsigned int a,
  50                                                  unsigned int b);
  51 /* Convenience method for getting an 8-bit mask. */
  52 static ossl_inline unsigned char constant_time_ge_8(unsigned int a,
  53                                                     unsigned int b);
  54
  55 /* Returns 0xff..f if a == 0 and 0 otherwise. */
  56 static ossl_inline unsigned int constant_time_is_zero(unsigned int a);
  57 /* Convenience method for getting an 8-bit mask. */
  58 static ossl_inline unsigned char constant_time_is_zero_8(unsigned int a);
  59 /* Convenience method for getting a 32-bit mask. */
  60 static ossl_inline uint32_t constant_time_is_zero_32(uint32_t a);
  61
  62 /* Returns 0xff..f if a == b and 0 otherwise. */
  63 static ossl_inline unsigned int constant_time_eq(unsigned int a,
  64                                                  unsigned int b);
  65 /* Convenience method for getting an 8-bit mask. */
  66 static ossl_inline unsigned char constant_time_eq_8(unsigned int a,
  67                                                     unsigned int b);
  68 /* Signed integers. */
  69 static ossl_inline unsigned int constant_time_eq_int(int a, int b);
  70 /* Convenience method for getting an 8-bit mask. */
  71 static ossl_inline unsigned char constant_time_eq_int_8(int a, int b);
  72
  73 /*-
  74  * Returns (mask & a) | (~mask & b).
  75  *
  76  * When |mask| is all 1s or all 0s (as returned by the methods above),
  77  * the select methods return either |a| (if |mask| is nonzero) or |b|
  78  * (if |mask| is zero).
  79  */
  80 static ossl_inline unsigned int constant_time_select(unsigned int mask,
  81                                                      unsigned int a,
  82                                                      unsigned int b);
  83 /* Convenience method for unsigned chars. */
  84 static ossl_inline unsigned char constant_time_select_8(unsigned char mask,
  85                                                         unsigned char a,
  86                                                         unsigned char b);
  87
  88 /* Convenience method for uint32_t. */
  89 static ossl_inline uint32_t constant_time_select_32(uint32_t mask, uint32_t a,
  90                                                     uint32_t b);
  91
  92 /* Convenience method for uint64_t. */
  93 static ossl_inline uint64_t constant_time_select_64(uint64_t mask, uint64_t a,
  94                                                     uint64_t b);
  95 /* Convenience method for signed integers. */
  96 static ossl_inline int constant_time_select_int(unsigned int mask, int a,
  97                                                 int b);
  98
  99
 100 static ossl_inline unsigned int constant_time_msb(unsigned int a)
 101 {
 102     return 0 - (a >> (sizeof(a) * 8 - 1));
 103 }
 104
 105
 106 static ossl_inline uint32_t constant_time_msb_32(uint32_t a)
 107 {
 108     return 0 - (a >> 31);
 109 }
 110
 111 static ossl_inline uint64_t constant_time_msb_64(uint64_t a)
 112 {
 113     return 0 - (a >> 63);
 114 }
 115
 116 static ossl_inline size_t constant_time_msb_s(size_t a)
 117 {
 118     return 0 - (a >> (sizeof(a) * 8 - 1));
 119 }
 120
 121 static ossl_inline unsigned int constant_time_lt(unsigned int a,
 122                                                  unsigned int b)
 123 {
 124     return constant_time_msb(a ^ ((a ^ b) | ((a - b) ^ b)));
 125 }
 126
 127 static ossl_inline size_t constant_time_lt_s(size_t a, size_t b)
 128 {
 129     return constant_time_msb_s(a ^ ((a ^ b) | ((a - b) ^ b)));
 130 }
 131
 132 static ossl_inline unsigned char constant_time_lt_8(unsigned int a,
 133                                                     unsigned int b)
 134 {
 135     return (unsigned char)constant_time_lt(a, b);
 136 }
 137
 138 static ossl_inline uint64_t constant_time_lt_64(uint64_t a, uint64_t b)
 139 {
 140     return constant_time_msb_64(a ^ ((a ^ b) | ((a - b) ^ b)));
 141 }
 142
 143 static ossl_inline unsigned int constant_time_ge(unsigned int a,
 144                                                  unsigned int b)
 145 {
 146     return ~constant_time_lt(a, b);
 147 }
 148
 149 static ossl_inline size_t constant_time_ge_s(size_t a, size_t b)
 150 {
 151     return ~constant_time_lt_s(a, b);
 152 }
 153
 154 static ossl_inline unsigned char constant_time_ge_8(unsigned int a,
 155                                                     unsigned int b)
 156 {
 157     return (unsigned char)constant_time_ge(a, b);
 158 }
 159
 160 static ossl_inline unsigned char constant_time_ge_8_s(size_t a, size_t b)
 161 {
 162     return (unsigned char)constant_time_ge_s(a, b);
 163 }
 164
 165 static ossl_inline unsigned int constant_time_is_zero(unsigned int a)
 166 {
 167     return constant_time_msb(~a & (a - 1));
 168 }
 169
 170 static ossl_inline size_t constant_time_is_zero_s(size_t a)
 171 {
 172     return constant_time_msb_s(~a & (a - 1));
 173 }
 174
 175 static ossl_inline unsigned char constant_time_is_zero_8(unsigned int a)
 176 {
 177     return (unsigned char)constant_time_is_zero(a);
 178 }
 179
 180 static ossl_inline uint32_t constant_time_is_zero_32(uint32_t a)
 181 {
 182     return constant_time_msb_32(~a & (a - 1));
 183 }
 184
 185 static ossl_inline unsigned int constant_time_eq(unsigned int a,
 186                                                  unsigned int b)
 187 {
 188     return constant_time_is_zero(a ^ b);
 189 }
 190
 191 static ossl_inline size_t constant_time_eq_s(size_t a, size_t b)
 192 {
 193     return constant_time_is_zero_s(a ^ b);
 194 }
 195
 196 static ossl_inline unsigned char constant_time_eq_8(unsigned int a,
 197                                                     unsigned int b)
 198 {
 199     return (unsigned char)constant_time_eq(a, b);
 200 }
 201
 202 static ossl_inline unsigned char constant_time_eq_8_s(size_t a, size_t b)
 203 {
 204     return (unsigned char)constant_time_eq_s(a, b);
 205 }
 206
 207 static ossl_inline unsigned int constant_time_eq_int(int a, int b)
 208 {
 209     return constant_time_eq((unsigned)(a), (unsigned)(b));
 210 }
 211
 212 static ossl_inline unsigned char constant_time_eq_int_8(int a, int b)
 213 {
 214     return constant_time_eq_8((unsigned)(a), (unsigned)(b));
 215 }
 216
 217 /*
 218  * Returns the value unmodified, but avoids optimizations.
 219  * The barriers prevent the compiler from narrowing down the
 220  * possible value range of the mask and ~mask in the select
 221  * statements, which avoids the recognition of the select
 222  * and turning it into a conditional load or branch.
 223  */
 224 static ossl_inline unsigned int value_barrier(unsigned int a)
 225 {
 226 #if !defined(OPENSSL_NO_ASM) && defined(__GNUC__)
 227     unsigned int r;
 228     __asm__("" : "=r"(r) : "0"(a));
 229 #else
 230     volatile unsigned int r = a;
 231 #endif
 232     return r;
 233 }
 234
 235 /* Convenience method for uint32_t. */
 236 static ossl_inline uint32_t value_barrier_32(uint32_t a)
 237 {
 238 #if !defined(OPENSSL_NO_ASM) && defined(__GNUC__)
 239     uint32_t r;
 240     __asm__("" : "=r"(r) : "0"(a));
 241 #else
 242     volatile uint32_t r = a;
 243 #endif
 244     return r;
 245 }
 246
 247 /* Convenience method for uint64_t. */
 248 static ossl_inline uint64_t value_barrier_64(uint64_t a)
 249 {
 250 #if !defined(OPENSSL_NO_ASM) && defined(__GNUC__)
 251     uint64_t r;
 252     __asm__("" : "=r"(r) : "0"(a));
 253 #else
 254     volatile uint64_t r = a;
 255 #endif
 256     return r;
 257 }
 258
 259 /* Convenience method for size_t. */
 260 static ossl_inline size_t value_barrier_s(size_t a)
 261 {
 262 #if !defined(OPENSSL_NO_ASM) && defined(__GNUC__)
 263     size_t r;
 264     __asm__("" : "=r"(r) : "0"(a));
 265 #else
 266     volatile size_t r = a;
 267 #endif
 268     return r;
 269 }
 270
 271 static ossl_inline unsigned int constant_time_select(unsigned int mask,
 272                                                      unsigned int a,
 273                                                      unsigned int b)
 274 {
 275     return (value_barrier(mask) & a) | (value_barrier(~mask) & b);
 276 }
 277
 278 static ossl_inline size_t constant_time_select_s(size_t mask,
 279                                                  size_t a,
 280                                                  size_t b)
 281 {
 282     return (value_barrier_s(mask) & a) | (value_barrier_s(~mask) & b);
 283 }
 284
 285 static ossl_inline unsigned char constant_time_select_8(unsigned char mask,
 286                                                         unsigned char a,
 287                                                         unsigned char b)
 288 {
 289     return (unsigned char)constant_time_select(mask, a, b);
 290 }
 291
 292 static ossl_inline int constant_time_select_int(unsigned int mask, int a,
 293                                                 int b)
 294 {
 295     return (int)constant_time_select(mask, (unsigned)(a), (unsigned)(b));
 296 }
 297
 298 static ossl_inline int constant_time_select_int_s(size_t mask, int a, int b)
 299 {
 300     return (int)constant_time_select((unsigned)mask, (unsigned)(a),
 301                                       (unsigned)(b));
 302 }
 303
 304 static ossl_inline uint32_t constant_time_select_32(uint32_t mask, uint32_t a,
 305                                                     uint32_t b)
 306 {
 307     return (value_barrier_32(mask) & a) | (value_barrier_32(~mask) & b);
 308 }
 309
 310 static ossl_inline uint64_t constant_time_select_64(uint64_t mask, uint64_t a,
 311                                                     uint64_t b)
 312 {
 313     return (value_barrier_64(mask) & a) | (value_barrier_64(~mask) & b);
 314 }
 315
 316 /*
 317  * mask must be 0xFFFFFFFF or 0x00000000.
 318  *
 319  * if (mask) {
 320  *     uint32_t tmp = *a;
 321  *
 322  *     *a = *b;
 323  *     *b = tmp;
 324  * }
 325  */
 326 static ossl_inline void constant_time_cond_swap_32(uint32_t mask, uint32_t *a,
 327                                                    uint32_t *b)
 328 {
 329     uint32_t xor = *a ^ *b;
 330
 331     xor &= mask;
 332     *a ^= xor;
 333     *b ^= xor;
 334 }
 335
 336 /*
 337  * mask must be 0xFFFFFFFF or 0x00000000.
 338  *
 339  * if (mask) {
 340  *     uint64_t tmp = *a;
 341  *
 342  *     *a = *b;
 343  *     *b = tmp;
 344  * }
 345  */
 346 static ossl_inline void constant_time_cond_swap_64(uint64_t mask, uint64_t *a,
 347                                                    uint64_t *b)
 348 {
 349     uint64_t xor = *a ^ *b;
 350
 351     xor &= mask;
 352     *a ^= xor;
 353     *b ^= xor;
 354 }
 355
 356 /*
 357  * mask must be 0xFF or 0x00.
 358  * "constant time" is per len.
 359  *
 360  * if (mask) {
 361  *     unsigned char tmp[len];
 362  *
 363  *     memcpy(tmp, a, len);
 364  *     memcpy(a, b);
 365  *     memcpy(b, tmp);
 366  * }
 367  */
 368 static ossl_inline void constant_time_cond_swap_buff(unsigned char mask,
 369                                                      unsigned char *a,
 370                                                      unsigned char *b,
 371                                                      size_t len)
 372 {
 373     size_t i;
 374     unsigned char tmp;
 375
 376     for (i = 0; i < len; i++) {
 377         tmp = a[i] ^ b[i];
 378         tmp &= mask;
 379         a[i] ^= tmp;
 380         b[i] ^= tmp;
 381     }
 382 }
 383
 384 /*
 385  * table is a two dimensional array of bytes. Each row has rowsize elements.
 386  * Copies row number idx into out. rowsize and numrows are not considered
 387  * private.
 388  */
 389 static ossl_inline void constant_time_lookup(void *out,
 390                                              const void *table,
 391                                              size_t rowsize,
 392                                              size_t numrows,
 393                                              size_t idx)
 394 {
 395     size_t i, j;
 396     const unsigned char *tablec = (const unsigned char *)table;
 397     unsigned char *outc = (unsigned char *)out;
 398     unsigned char mask;
 399
 400     memset(out, 0, rowsize);
 401
 402     /* Note idx may underflow - but that is well defined */
 403     for (i = 0; i < numrows; i++, idx--) {
 404         mask = (unsigned char)constant_time_is_zero_s(idx);
 405         for (j = 0; j < rowsize; j++)
 406             *(outc + j) |= constant_time_select_8(mask, *(tablec++), 0);
 407     }
 408 }
 409
 410 /*
 411  * Expected usage pattern is to unconditionally set error and then
 412  * wipe it if there was no actual error. |clear| is 1 or 0.
 413  */
 414 void err_clear_last_constant_time(int clear);
 415
 416 #endif                          /* OSSL_INTERNAL_CONSTANT_TIME_H */