Run util/openssl-format-source on the Curve448 code
[openssl.git] / 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  * @brief 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 __inline__ void
62     __attribute__ ((unused, always_inline))
63     constant_time_cond_swap(void *__restrict__ a_,
64                         void *__restrict__ b_, word_t elem_bytes, 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 =
76                 ((unaligned_br_t *) (&a[k]))->unaligned
77                 ^ ((unaligned_br_t *) (&b[k]))->unaligned;
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 =
96                     ((unaligned_word_t *) (&a[k]))->unaligned
97                     ^ ((unaligned_word_t *) (&b[k]))->unaligned;
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]))
104                     ^ *((word_t *) (&b[k]));
105                 xor &= doswap;
106                 *((word_t *) (&a[k])) ^= xor;
107                 *((word_t *) (&b[k])) ^= xor;
108             }
109         }
110     }
111
112     if (elem_bytes % sizeof(word_t)) {
113         for (; k < elem_bytes; k += 1) {
114             unsigned char xor = a[k] ^ b[k];
115             xor &= doswap;
116             a[k] ^= xor;
117             b[k] ^= xor;
118         }
119     }
120 }
121
122 /**
123  * @brief 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 __inline__ void
131     __attribute__ ((unused, always_inline))
132     constant_time_lookup(void *__restrict__ out_,
133                      const void *table_,
134                      word_t elem_bytes, word_t n_table, 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                     |=
154                     br_mask &
155                     ((const unaligned_br_t
156                       *)(&table[k + j * elem_bytes]))->unaligned;
157             } else {
158                 /* aligned */
159                 *(big_register_t *) (out + k) |=
160                     br_mask & *(const big_register_t
161                                 *)(&table[k + j * elem_bytes]);
162             }
163         }
164
165         mask = word_is_zero(idx ^ j);
166         if (elem_bytes % sizeof(big_register_t) >= sizeof(word_t)) {
167             for (; k <= elem_bytes - sizeof(word_t); k += sizeof(word_t)) {
168                 if (elem_bytes % sizeof(word_t)) {
169                     /* input unaligned, output aligned */
170                     *(word_t *) (out + k) |=
171                         mask &
172                         ((const unaligned_word_t
173                           *)(&table[k + j * elem_bytes]))->unaligned;
174                 } else {
175                     /* aligned */
176                     *(word_t *) (out + k) |=
177                         mask & *(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  * @brief 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 __inline__ void
200     __attribute__ ((unused, always_inline))
201     constant_time_select(void *a_,
202                      const void *bFalse_,
203                      const void *bTrue_,
204                      word_t elem_bytes, mask_t mask, 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__ */