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 uint64_t constant_time_is_zero_64(uint64_t a)
 186 {
 187     return constant_time_msb_64(~a & (a - 1));
 188 }
 189
 190 static ossl_inline unsigned int constant_time_eq(unsigned int a,
 191                                                  unsigned int b)
 192 {
 193     return constant_time_is_zero(a ^ b);
 194 }
 195
 196 static ossl_inline size_t constant_time_eq_s(size_t a, size_t b)
 197 {
 198     return constant_time_is_zero_s(a ^ b);
 199 }
 200
 201 static ossl_inline unsigned char constant_time_eq_8(unsigned int a,
 202                                                     unsigned int b)
 203 {
 204     return (unsigned char)constant_time_eq(a, b);
 205 }
 206
 207 static ossl_inline unsigned char constant_time_eq_8_s(size_t a, size_t b)
 208 {
 209     return (unsigned char)constant_time_eq_s(a, b);
 210 }
 211
 212 static ossl_inline unsigned int constant_time_eq_int(int a, int b)
 213 {
 214     return constant_time_eq((unsigned)(a), (unsigned)(b));
 215 }
 216
 217 static ossl_inline unsigned char constant_time_eq_int_8(int a, int b)
 218 {
 219     return constant_time_eq_8((unsigned)(a), (unsigned)(b));
 220 }
 221
 222 /*
 223  * Returns the value unmodified, but avoids optimizations.
 224  * The barriers prevent the compiler from narrowing down the
 225  * possible value range of the mask and ~mask in the select
 226  * statements, which avoids the recognition of the select
 227  * and turning it into a conditional load or branch.
 228  */
 229 static ossl_inline unsigned int value_barrier(unsigned int a)
 230 {
 231 #if !defined(OPENSSL_NO_ASM) && defined(__GNUC__)
 232     unsigned int r;
 233     __asm__("" : "=r"(r) : "0"(a));
 234 #else
 235     volatile unsigned int r = a;
 236 #endif
 237     return r;
 238 }
 239
 240 /* Convenience method for uint32_t. */
 241 static ossl_inline uint32_t value_barrier_32(uint32_t a)
 242 {
 243 #if !defined(OPENSSL_NO_ASM) && defined(__GNUC__)
 244     uint32_t r;
 245     __asm__("" : "=r"(r) : "0"(a));
 246 #else
 247     volatile uint32_t r = a;
 248 #endif
 249     return r;
 250 }
 251
 252 /* Convenience method for uint64_t. */
 253 static ossl_inline uint64_t value_barrier_64(uint64_t a)
 254 {
 255 #if !defined(OPENSSL_NO_ASM) && defined(__GNUC__)
 256     uint64_t r;
 257     __asm__("" : "=r"(r) : "0"(a));
 258 #else
 259     volatile uint64_t r = a;
 260 #endif
 261     return r;
 262 }
 263
 264 /* Convenience method for size_t. */
 265 static ossl_inline size_t value_barrier_s(size_t a)
 266 {
 267 #if !defined(OPENSSL_NO_ASM) && defined(__GNUC__)
 268     size_t r;
 269     __asm__("" : "=r"(r) : "0"(a));
 270 #else
 271     volatile size_t r = a;
 272 #endif
 273     return r;
 274 }
 275
 276 static ossl_inline unsigned int constant_time_select(unsigned int mask,
 277                                                      unsigned int a,
 278                                                      unsigned int b)
 279 {
 280     return (value_barrier(mask) & a) | (value_barrier(~mask) & b);
 281 }
 282
 283 static ossl_inline size_t constant_time_select_s(size_t mask,
 284                                                  size_t a,
 285                                                  size_t b)
 286 {
 287     return (value_barrier_s(mask) & a) | (value_barrier_s(~mask) & b);
 288 }
 289
 290 static ossl_inline unsigned char constant_time_select_8(unsigned char mask,
 291                                                         unsigned char a,
 292                                                         unsigned char b)
 293 {
 294     return (unsigned char)constant_time_select(mask, a, b);
 295 }
 296
 297 static ossl_inline int constant_time_select_int(unsigned int mask, int a,
 298                                                 int b)
 299 {
 300     return (int)constant_time_select(mask, (unsigned)(a), (unsigned)(b));
 301 }
 302
 303 static ossl_inline int constant_time_select_int_s(size_t mask, int a, int b)
 304 {
 305     return (int)constant_time_select((unsigned)mask, (unsigned)(a),
 306                                       (unsigned)(b));
 307 }
 308
 309 static ossl_inline uint32_t constant_time_select_32(uint32_t mask, uint32_t a,
 310                                                     uint32_t b)
 311 {
 312     return (value_barrier_32(mask) & a) | (value_barrier_32(~mask) & b);
 313 }
 314
 315 static ossl_inline uint64_t constant_time_select_64(uint64_t mask, uint64_t a,
 316                                                     uint64_t b)
 317 {
 318     return (value_barrier_64(mask) & a) | (value_barrier_64(~mask) & b);
 319 }
 320
 321 /*
 322  * mask must be 0xFFFFFFFF or 0x00000000.
 323  *
 324  * if (mask) {
 325  *     uint32_t tmp = *a;
 326  *
 327  *     *a = *b;
 328  *     *b = tmp;
 329  * }
 330  */
 331 static ossl_inline void constant_time_cond_swap_32(uint32_t mask, uint32_t *a,
 332                                                    uint32_t *b)
 333 {
 334     uint32_t xor = *a ^ *b;
 335
 336     xor &= mask;
 337     *a ^= xor;
 338     *b ^= xor;
 339 }
 340
 341 /*
 342  * mask must be 0xFFFFFFFF or 0x00000000.
 343  *
 344  * if (mask) {
 345  *     uint64_t tmp = *a;
 346  *
 347  *     *a = *b;
 348  *     *b = tmp;
 349  * }
 350  */
 351 static ossl_inline void constant_time_cond_swap_64(uint64_t mask, uint64_t *a,
 352                                                    uint64_t *b)
 353 {
 354     uint64_t xor = *a ^ *b;
 355
 356     xor &= mask;
 357     *a ^= xor;
 358     *b ^= xor;
 359 }
 360
 361 /*
 362  * mask must be 0xFF or 0x00.
 363  * "constant time" is per len.
 364  *
 365  * if (mask) {
 366  *     unsigned char tmp[len];
 367  *
 368  *     memcpy(tmp, a, len);
 369  *     memcpy(a, b);
 370  *     memcpy(b, tmp);
 371  * }
 372  */
 373 static ossl_inline void constant_time_cond_swap_buff(unsigned char mask,
 374                                                      unsigned char *a,
 375                                                      unsigned char *b,
 376                                                      size_t len)
 377 {
 378     size_t i;
 379     unsigned char tmp;
 380
 381     for (i = 0; i < len; i++) {
 382         tmp = a[i] ^ b[i];
 383         tmp &= mask;
 384         a[i] ^= tmp;
 385         b[i] ^= tmp;
 386     }
 387 }
 388
 389 /*
 390  * table is a two dimensional array of bytes. Each row has rowsize elements.
 391  * Copies row number idx into out. rowsize and numrows are not considered
 392  * private.
 393  */
 394 static ossl_inline void constant_time_lookup(void *out,
 395                                              const void *table,
 396                                              size_t rowsize,
 397                                              size_t numrows,
 398                                              size_t idx)
 399 {
 400     size_t i, j;
 401     const unsigned char *tablec = (const unsigned char *)table;
 402     unsigned char *outc = (unsigned char *)out;
 403     unsigned char mask;
 404
 405     memset(out, 0, rowsize);
 406
 407     /* Note idx may underflow - but that is well defined */
 408     for (i = 0; i < numrows; i++, idx--) {
 409         mask = (unsigned char)constant_time_is_zero_s(idx);
 410         for (j = 0; j < rowsize; j++)
 411             *(outc + j) |= constant_time_select_8(mask, *(tablec++), 0);
 412     }
 413 }
 414
 415 /*
 416  * Expected usage pattern is to unconditionally set error and then
 417  * wipe it if there was no actual error. |clear| is 1 or 0.
 418  */
 419 void err_clear_last_constant_time(int clear);
 420
 421 #endif                          /* OSSL_INTERNAL_CONSTANT_TIME_H */