crypto/ec/curve448/constant_time.h

   1 /*
   2  * Copyright 2017-2018 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 # if defined(__GNUC__) || defined(__clang__)
  40 /*
  41  * Unaligned big (vector?) register.
  42  */
  43 typedef struct {
  44     big_register_t unaligned;
  45 } __attribute((packed)) unaligned_br_t;
  46
  47 /*
  48  * Unaligned word register, for architectures where that matters.
  49  */
  50 typedef struct {
  51     word_t unaligned;
  52 } __attribute((packed)) unaligned_word_t;
  53
  54 #  define HAS_UNALIGNED_STRUCTS
  55 #  define RESTRICT __restrict__
  56 #else
  57 #  define RESTRICT
  58 # endif
  59
  60 /*
  61  * Constant-time conditional swap.
  62  *
  63  * If doswap, then swap elem_bytes between *a and *b.
  64  *
  65  * *a and *b must not alias.  Also, they must be at least as aligned
  66  * as their sizes, if the CPU cares about that sort of thing.
  67  */
  68 static ossl_inline void constant_time_cond_swap(void *RESTRICT a_,
  69                                                 void *RESTRICT b_,
  70                                                 word_t elem_bytes,
  71                                                 mask_t doswap)
  72 {
  73     word_t k;
  74     unsigned char *a = (unsigned char *)a_;
  75     unsigned char *b = (unsigned char *)b_;
  76     big_register_t br_mask = br_set_to_mask(doswap);
  77 # ifndef HAS_UNALIGNED_STRUCTS
  78     unsigned char doswapc = (unsigned char)(doswap & 0xFF);
  79 # endif
  80
  81     for (k = 0; k <= elem_bytes - sizeof(big_register_t);
  82          k += sizeof(big_register_t)) {
  83         if (elem_bytes % sizeof(big_register_t)) {
  84             /* unaligned */
  85 # ifdef HAS_UNALIGNED_STRUCTS
  86             big_register_t xor = ((unaligned_br_t *) (&a[k]))->unaligned
  87                                  ^ ((unaligned_br_t *) (&b[k]))->unaligned;
  88
  89             xor &= br_mask;
  90             ((unaligned_br_t *)(&a[k]))->unaligned ^= xor;
  91             ((unaligned_br_t *)(&b[k]))->unaligned ^= xor;
  92 # else
  93             size_t i;
  94
  95             for (i = 0; i < sizeof(big_register_t); i++) {
  96                 unsigned char xor = a[k + i] ^ b[k + i];
  97
  98                 xor &= doswapc;
  99                 a[k + i] ^= xor;
 100                 b[k + i] ^= xor;
 101             }
 102 # endif
 103         } else {
 104             /* aligned */
 105             big_register_t xor = *((big_register_t *) (&a[k]))
 106                                  ^ *((big_register_t *) (&b[k]));
 107             xor &= br_mask;
 108             *((big_register_t *)(&a[k])) ^= xor;
 109             *((big_register_t *)(&b[k])) ^= xor;
 110         }
 111     }
 112
 113     if (elem_bytes % sizeof(big_register_t) >= sizeof(word_t)) {
 114         for (; k <= elem_bytes - sizeof(word_t); k += sizeof(word_t)) {
 115             if (elem_bytes % sizeof(word_t)) {
 116                 /* unaligned */
 117 # ifdef HAS_UNALIGNED_STRUCTS
 118                 word_t xor = ((unaligned_word_t *)(&a[k]))->unaligned
 119                              ^ ((unaligned_word_t *)(&b[k]))->unaligned;
 120
 121                 xor &= doswap;
 122                 ((unaligned_word_t *)(&a[k]))->unaligned ^= xor;
 123                 ((unaligned_word_t *)(&b[k]))->unaligned ^= xor;
 124 # else
 125                 size_t i;
 126
 127                 for (i = 0; i < sizeof(word_t); i++) {
 128                     unsigned char xor = a[k + i] ^ b[k + i];
 129
 130                     xor &= doswapc;
 131                     a[k + i] ^= xor;
 132                     b[k + i] ^= xor;
 133                 }
 134 # endif
 135             } else {
 136                 /* aligned */
 137                 word_t xor = *((word_t *) (&a[k])) ^ *((word_t *) (&b[k]));
 138                 xor &= doswap;
 139                 *((word_t *)(&a[k])) ^= xor;
 140                 *((word_t *)(&b[k])) ^= xor;
 141             }
 142         }
 143     }
 144
 145     if (elem_bytes % sizeof(word_t)) {
 146         for (; k < elem_bytes; k += 1) {
 147             unsigned char xor = a[k] ^ b[k];
 148
 149             xor &= doswap;
 150             a[k] ^= xor;
 151             b[k] ^= xor;
 152         }
 153     }
 154 }
 155
 156 /*
 157  * Constant-time equivalent of memcpy(out, table + elem_bytes*idx, elem_bytes);
 158  *
 159  * The table must be at least as aligned as elem_bytes.  The output must be word aligned,
 160  * and if the input size is vector aligned it must also be vector aligned.
 161  *
 162  * The table and output must not alias.
 163  */
 164 static ossl_inline void constant_time_lookup(void *RESTRICT out_,
 165                                              const void *table_,
 166                                              word_t elem_bytes,
 167                                              word_t n_table,
 168                                              word_t idx)
 169 {
 170     big_register_t big_one = br_set_to_mask(1), big_i = br_set_to_mask(idx);
 171
 172     /* Can't do pointer arithmetic on void * */
 173     unsigned char *out = (unsigned char *)out_;
 174     const unsigned char *table = (const unsigned char *)table_;
 175     word_t j, k;
 176 # ifndef HAS_UNALIGNED_STRUCTS
 177     unsigned char maskc;
 178 # endif
 179
 180     memset(out, 0, elem_bytes);
 181     for (j = 0; j < n_table; j++, big_i -= big_one) {
 182         big_register_t br_mask = br_is_zero(big_i);
 183         word_t mask;
 184
 185 # ifndef HAS_UNALIGNED_STRUCTS
 186         maskc = (unsigned char)br_mask;
 187 # endif
 188
 189         for (k = 0; k <= elem_bytes - sizeof(big_register_t);
 190              k += sizeof(big_register_t)) {
 191             if (elem_bytes % sizeof(big_register_t)) {
 192                 /* unaligned */
 193 # ifdef HAS_UNALIGNED_STRUCTS
 194                 ((unaligned_br_t *)(out + k))->unaligned |=
 195                         br_mask
 196                         & ((const unaligned_br_t *)
 197                            (&table[k + j * elem_bytes]))->unaligned;
 198 # else
 199                 size_t i;
 200
 201                 for (i = 0; i < sizeof(big_register_t); i++)
 202                     out[k + i] |= maskc
 203                                   & ((unsigned char *) table)
 204                                     [k + (j * elem_bytes) + i];
 205 # endif
 206             } else {
 207                 /* aligned */
 208                 *(big_register_t *)(out + k) |=
 209                         br_mask
 210                         & *(const big_register_t *)(&table[k + j * elem_bytes]);
 211             }
 212         }
 213
 214         mask = word_is_zero(idx ^ j);
 215 # ifndef HAS_UNALIGNED_STRUCTS
 216         maskc = (unsigned char)mask;
 217 # endif
 218         if (elem_bytes % sizeof(big_register_t) >= sizeof(word_t)) {
 219             for (; k <= elem_bytes - sizeof(word_t); k += sizeof(word_t)) {
 220                 if (elem_bytes % sizeof(word_t)) {
 221                     /* input unaligned, output aligned */
 222 # ifdef HAS_UNALIGNED_STRUCTS
 223                     *(word_t *)(out + k) |=
 224                             mask
 225                             & ((const unaligned_word_t *)
 226                                (&table[k + j * elem_bytes]))->unaligned;
 227 # else
 228                     size_t i;
 229
 230                     for (i = 0; i < sizeof(word_t); i++)
 231                         out[k + i] |= maskc
 232                                       & ((unsigned char *)table)
 233                                          [k + (j * elem_bytes) + i];
 234 # endif
 235                 } else {
 236                     /* aligned */
 237                     *(word_t *)(out + k) |=
 238                             mask
 239                             & *(const word_t *)(&table[k + j * elem_bytes]);
 240                 }
 241             }
 242         }
 243
 244         if (elem_bytes % sizeof(word_t)) {
 245             for (; k < elem_bytes; k += 1) {
 246                 out[k] |= mask & table[k + j * elem_bytes];
 247             }
 248         }
 249     }
 250 }
 251
 252 /*
 253  * Constant-time a = mask ? bTrue : bFalse.
 254  *
 255  * The input and output must be at least as aligned as alignment_bytes
 256  * or their size, whichever is smaller.
 257  *
 258  * Note that the output is not __restrict__, but if it overlaps either
 259  * input, it must be equal and not partially overlap.
 260  */
 261 static ossl_inline void constant_time_select_c448(void *a_,
 262                                                   const void *bFalse_,
 263                                                   const void *bTrue_,
 264                                                   word_t elem_bytes,
 265                                                   mask_t mask,
 266                                                   size_t alignment_bytes)
 267 {
 268     unsigned char *a = (unsigned char *)a_;
 269     const unsigned char *bTrue = (const unsigned char *)bTrue_;
 270     const unsigned char *bFalse = (const unsigned char *)bFalse_;
 271     word_t k;
 272     big_register_t br_mask = br_set_to_mask(mask);
 273 # ifndef HAS_UNALIGNED_STRUCTS
 274     unsigned char maskc = (unsigned char)mask;
 275 # endif
 276
 277     alignment_bytes |= elem_bytes;
 278
 279     for (k = 0; k <= elem_bytes - sizeof(big_register_t);
 280          k += sizeof(big_register_t)) {
 281         if (alignment_bytes % sizeof(big_register_t)) {
 282             /* unaligned */
 283 # ifdef HAS_UNALIGNED_STRUCTS
 284             ((unaligned_br_t *)(&a[k]))->unaligned =
 285                     (br_mask & ((const unaligned_br_t *)(&bTrue[k]))->unaligned)
 286                     | (~br_mask
 287                        & ((const unaligned_br_t *)(&bFalse[k]))->unaligned);
 288 # else
 289                     size_t i;
 290
 291                     for (i = 0; i < sizeof(big_register_t); i++)
 292                         a[k + i] = (maskc & ((unsigned char *)bTrue)[k + i])
 293                                    | (~maskc & ((unsigned char *)bFalse)[k + i]);
 294 # endif
 295         } else {
 296             /* aligned */
 297             *(big_register_t *) (a + k) =
 298                     (br_mask & *(const big_register_t *)(&bTrue[k]))
 299                     | (~br_mask & *(const big_register_t *)(&bFalse[k]));
 300         }
 301     }
 302
 303     if (elem_bytes % sizeof(big_register_t) >= sizeof(word_t)) {
 304         for (; k <= elem_bytes - sizeof(word_t); k += sizeof(word_t)) {
 305             if (alignment_bytes % sizeof(word_t)) {
 306                 /* unaligned */
 307 # ifdef HAS_UNALIGNED_STRUCTS
 308                 ((unaligned_word_t *) (&a[k]))->unaligned =
 309                     (mask & ((const unaligned_word_t *)(&bTrue[k]))->unaligned)
 310                     | (~mask &
 311                        ((const unaligned_word_t *)(&bFalse[k]))->unaligned);
 312 # else
 313                 size_t i;
 314
 315                 for (i = 0; i < sizeof(word_t); i++)
 316                     a[k + i] = (maskc & ((unsigned char *)bTrue)[k + i])
 317                                | (~maskc & ((unsigned char *)bFalse)[k + i]);
 318 # endif
 319             } else {
 320                 /* aligned */
 321                 *(word_t *) (a + k) = (mask & *(const word_t *)(&bTrue[k]))
 322                     | (~mask & *(const word_t *)(&bFalse[k]));
 323             }
 324         }
 325     }
 326
 327     if (elem_bytes % sizeof(word_t)) {
 328         for (; k < elem_bytes; k += 1) {
 329             a[k] = (mask & bTrue[k]) | (~mask & bFalse[k]);
 330         }
 331     }
 332 }
 333
 334 #undef RESTRICT
 335 #undef HAS_UNALIGNED_STRUCTS
 336
 337 #endif                          /* __CONSTANT_TIME_H__ */