crypto/ec/curve448/constant_time.h

   1 /*
   2  * Copyright 2017 The OpenSSL Project Authors. All Rights Reserved.
   3  * Copyright 2014 Cryptography Research, Inc.
   4  *
   5  * Licensed under the OpenSSL license (the "License").  You may not use
   6  * this file except in compliance with the License.  You can obtain a copy
   7  * in the file LICENSE in the source distribution or at
   8  * https://www.openssl.org/source/license.html
   9  *
  10  * Originally written by Mike Hamburg
  11  */
  12
  13 #ifndef __CONSTANT_TIME_H__
  14 # define __CONSTANT_TIME_H__ 1
  15
  16 # include "word.h"
  17 # include <string.h>
  18
  19 /*
  20  * Constant-time operations on hopefully-compile-time-sized memory
  21  * regions.  Needed for flexibility / demagication: not all fields
  22  * have sizes which are multiples of the vector width, necessitating
  23  * a change from the Ed448 versions.
  24  *
  25  * These routines would be much simpler to define at the byte level,
  26  * but if not vectorized they would be a significant fraction of the
  27  * runtime.  Eg on NEON-less ARM, constant_time_lookup is like 15% of
  28  * signing time, vs 6% on Haswell with its fancy AVX2 vectors.
  29  *
  30  * If the compiler could do a good job of autovectorizing the code,
  31  * we could just leave it with the byte definition.  But that's unlikely
  32  * on most deployed compilers, especially if you consider that pcmpeq[size]
  33  * is much faster than moving a scalar to the vector unit (which is what
  34  * a naive autovectorizer will do with constant_time_lookup on Intel).
  35  *
  36  * Instead, we're putting our trust in the loop unroller and unswitcher.
  37  */
  38
  39 /*
  40  * Unaligned big (vector?) register.
  41  */
  42 typedef struct {
  43     big_register_t unaligned;
  44 } __attribute__ ((packed)) unaligned_br_t;
  45
  46 /*
  47  * Unaligned word register, for architectures where that matters.
  48  */
  49 typedef struct {
  50     word_t unaligned;
  51 } __attribute__ ((packed)) unaligned_word_t;
  52
  53 /*
  54  * Constant-time conditional swap.
  55  *
  56  * If doswap, then swap elem_bytes between *a and *b.
  57  *
  58  * *a and *b must not alias.  Also, they must be at least as aligned
  59  * as their sizes, if the CPU cares about that sort of thing.
  60  */
  61 static ossl_inline void constant_time_cond_swap(void *__restrict__ a_,
  62                                                 void *__restrict__ b_,
  63                                                 word_t elem_bytes,
  64                                                 mask_t doswap)
  65 {
  66     word_t k;
  67     unsigned char *a = (unsigned char *)a_;
  68     unsigned char *b = (unsigned char *)b_;
  69
  70     big_register_t br_mask = br_set_to_mask(doswap);
  71     for (k = 0; k <= elem_bytes - sizeof(big_register_t);
  72          k += sizeof(big_register_t)) {
  73         if (elem_bytes % sizeof(big_register_t)) {
  74             /* unaligned */
  75             big_register_t xor = ((unaligned_br_t *) (&a[k]))->unaligned
  76                                  ^ ((unaligned_br_t *) (&b[k]))->unaligned;
  77
  78             xor &= br_mask;
  79             ((unaligned_br_t *)(&a[k]))->unaligned ^= xor;
  80             ((unaligned_br_t *)(&b[k]))->unaligned ^= xor;
  81         } else {
  82             /* aligned */
  83             big_register_t xor = *((big_register_t *) (&a[k]))
  84                                  ^ *((big_register_t *) (&b[k]));
  85             xor &= br_mask;
  86             *((big_register_t *)(&a[k])) ^= xor;
  87             *((big_register_t *)(&b[k])) ^= xor;
  88         }
  89     }
  90
  91     if (elem_bytes % sizeof(big_register_t) >= sizeof(word_t)) {
  92         for (; k <= elem_bytes - sizeof(word_t); k += sizeof(word_t)) {
  93             if (elem_bytes % sizeof(word_t)) {
  94                 /* unaligned */
  95                 word_t xor = ((unaligned_word_t *)(&a[k]))->unaligned
  96                              ^ ((unaligned_word_t *)(&b[k]))->unaligned;
  97
  98                 xor &= doswap;
  99                 ((unaligned_word_t *)(&a[k]))->unaligned ^= xor;
 100                 ((unaligned_word_t *)(&b[k]))->unaligned ^= xor;
 101             } else {
 102                 /* aligned */
 103                 word_t xor = *((word_t *) (&a[k])) ^ *((word_t *) (&b[k]));
 104                 xor &= doswap;
 105                 *((word_t *)(&a[k])) ^= xor;
 106                 *((word_t *)(&b[k])) ^= xor;
 107             }
 108         }
 109     }
 110
 111     if (elem_bytes % sizeof(word_t)) {
 112         for (; k < elem_bytes; k += 1) {
 113             unsigned char xor = a[k] ^ b[k];
 114
 115             xor &= doswap;
 116             a[k] ^= xor;
 117             b[k] ^= xor;
 118         }
 119     }
 120 }
 121
 122 /*
 123  * Constant-time equivalent of memcpy(out, table + elem_bytes*idx, elem_bytes);
 124  *
 125  * The table must be at least as aligned as elem_bytes.  The output must be word aligned,
 126  * and if the input size is vector aligned it must also be vector aligned.
 127  *
 128  * The table and output must not alias.
 129  */
 130 static ossl_inline void constant_time_lookup(void *__restrict__ out_,
 131                                              const void *table_,
 132                                              word_t elem_bytes,
 133                                              word_t n_table,
 134                                              word_t idx)
 135 {
 136     big_register_t big_one = br_set_to_mask(1), big_i = br_set_to_mask(idx);
 137
 138     /* Can't do pointer arithmetic on void * */
 139     unsigned char *out = (unsigned char *)out_;
 140     const unsigned char *table = (const unsigned char *)table_;
 141     word_t j, k;
 142
 143     memset(out, 0, elem_bytes);
 144     for (j = 0; j < n_table; j++, big_i -= big_one) {
 145         big_register_t br_mask = br_is_zero(big_i);
 146         word_t mask;
 147
 148         for (k = 0; k <= elem_bytes - sizeof(big_register_t);
 149              k += sizeof(big_register_t)) {
 150             if (elem_bytes % sizeof(big_register_t)) {
 151                 /* unaligned */
 152                 ((unaligned_br_t *)(out + k))->unaligned |=
 153                         br_mask
 154                         & ((const unaligned_br_t *)
 155                            (&table[k + j * elem_bytes]))->unaligned;
 156             } else {
 157                 /* aligned */
 158                 *(big_register_t *)(out + k) |=
 159                         br_mask
 160                         & *(const big_register_t *)(&table[k + j * elem_bytes]);
 161             }
 162         }
 163
 164         mask = word_is_zero(idx ^ j);
 165         if (elem_bytes % sizeof(big_register_t) >= sizeof(word_t)) {
 166             for (; k <= elem_bytes - sizeof(word_t); k += sizeof(word_t)) {
 167                 if (elem_bytes % sizeof(word_t)) {
 168                     /* input unaligned, output aligned */
 169                     *(word_t *)(out + k) |=
 170                             mask
 171                             & ((const unaligned_word_t *)
 172                                (&table[k + j * elem_bytes]))->unaligned;
 173                 } else {
 174                     /* aligned */
 175                     *(word_t *)(out + k) |=
 176                             mask
 177                             & *(const word_t *)(&table[k + j * elem_bytes]);
 178                 }
 179             }
 180         }
 181
 182         if (elem_bytes % sizeof(word_t)) {
 183             for (; k < elem_bytes; k += 1) {
 184                 out[k] |= mask & table[k + j * elem_bytes];
 185             }
 186         }
 187     }
 188 }
 189
 190 /*
 191  * Constant-time a = mask ? bTrue : bFalse.
 192  *
 193  * The input and output must be at least as aligned as alignment_bytes
 194  * or their size, whichever is smaller.
 195  *
 196  * Note that the output is not __restrict__, but if it overlaps either
 197  * input, it must be equal and not partially overlap.
 198  */
 199 static ossl_inline void constant_time_select(void *a_,
 200                                              const void *bFalse_,
 201                                              const void *bTrue_,
 202                                              word_t elem_bytes,
 203                                              mask_t mask,
 204                                              size_t alignment_bytes)
 205 {
 206     unsigned char *a = (unsigned char *)a_;
 207     const unsigned char *bTrue = (const unsigned char *)bTrue_;
 208     const unsigned char *bFalse = (const unsigned char *)bFalse_;
 209     word_t k;
 210     big_register_t br_mask = br_set_to_mask(mask);
 211
 212     alignment_bytes |= elem_bytes;
 213
 214     for (k = 0; k <= elem_bytes - sizeof(big_register_t);
 215          k += sizeof(big_register_t)) {
 216         if (alignment_bytes % sizeof(big_register_t)) {
 217             /* unaligned */
 218             ((unaligned_br_t *)(&a[k]))->unaligned =
 219                     (br_mask & ((const unaligned_br_t *)(&bTrue[k]))->unaligned)
 220                     | (~br_mask
 221                        & ((const unaligned_br_t *)(&bFalse[k]))->unaligned);
 222         } else {
 223             /* aligned */
 224             *(big_register_t *) (a + k) =
 225                     (br_mask & *(const big_register_t *)(&bTrue[k]))
 226                     | (~br_mask & *(const big_register_t *)(&bFalse[k]));
 227         }
 228     }
 229
 230     if (elem_bytes % sizeof(big_register_t) >= sizeof(word_t)) {
 231         for (; k <= elem_bytes - sizeof(word_t); k += sizeof(word_t)) {
 232             if (alignment_bytes % sizeof(word_t)) {
 233                 /* unaligned */
 234                 ((unaligned_word_t *) (&a[k]))->unaligned =
 235                     (mask & ((const unaligned_word_t *)(&bTrue[k]))->unaligned)
 236                     | (~mask &
 237                        ((const unaligned_word_t *)(&bFalse[k]))->unaligned);
 238             } else {
 239                 /* aligned */
 240                 *(word_t *) (a + k) = (mask & *(const word_t *)(&bTrue[k]))
 241                     | (~mask & *(const word_t *)(&bFalse[k]));
 242             }
 243         }
 244     }
 245
 246     if (elem_bytes % sizeof(word_t)) {
 247         for (; k < elem_bytes; k += 1) {
 248             a[k] = (mask & bTrue[k]) | (~mask & bFalse[k]);
 249         }
 250     }
 251 }
 252
 253 #endif                          /* __CONSTANT_TIME_H__ */