1 /*
2 * Copyright (C) 2017 - This file is part of libecc project
3 *
4 * Authors:
5 * Ryad BENADJILA <ryadbenadjila@gmail.com>
6 * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
7 * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr>
8 *
9 * Contributors:
10 * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr>
11 * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr>
12 *
13 * This software is licensed under a dual BSD and GPL v2 license.
14 * See LICENSE file at the root folder of the project.
15 */
16 #define NN_CONSISTENCY_CHECK
17 #include <libecc/nn/nn.h>
18
19 /*
20 * Used for the conditional swap algorithm SCA
21 * resistance, see below in the implementation of
22 * nn_cnd_swap.
23 */
24 #include <libecc/utils/utils_rand.h>
25
26 /*
27 * Except otherwise specified, all functions accept *initialized* nn.
28 * The WORD(NN_MAX_WORD_LEN + WORDSIZE) magic is here to detect modules
29 * compiled with different WORDSIZE or NN_MAX_WORD_LEN and are binary
30 * incompatible.
31 */
32
33 #define NN_MAGIC ((word_t)((0xb4cf5d56e2023316ULL ^ (WORD(NN_MAX_WORD_LEN + WORDSIZE)))))
34
35 /*
36 * Local helper internally used to check that the storage space
37 * above wlen is made of zero words. The function does NOT check
38 * if given nn has been initialized. This must have been done
39 * by the caller.
40 *
41 * Due to its performance cost, this consistency check is used
42 * in SHOULD_HAVE macros, meaning that it will only be present
43 * in DEBUG mode. Hence the ATTRIBUTE_UNUSED so that no warning
44 * (error in -Werror) is triggered at compilation time.
45 *
46 */
__nn_is_wlen_consistent(nn_src_t A)47 ATTRIBUTE_WARN_UNUSED_RET static int ATTRIBUTE_UNUSED __nn_is_wlen_consistent(nn_src_t A)
48 {
49 word_t val = 0;
50 u8 i;
51
52 for (i = A->wlen; i < NN_MAX_WORD_LEN; i++) {
53 val |= (A)->val[i];
54 }
55
56 return (val == 0);
57 }
58
59 /*
60 * Verify that pointed nn has already been initialized. This function
61 * should be used as a safety net in all function before using a nn
62 * received as parameter. Returns 0 on success, -1 on error.
63 */
nn_check_initialized(nn_src_t A)64 int nn_check_initialized(nn_src_t A)
65 {
66 int ret;
67
68 MUST_HAVE((A != NULL), ret, err);
69 MUST_HAVE((A->magic == NN_MAGIC), ret, err);
70 MUST_HAVE((A->wlen <= NN_MAX_WORD_LEN), ret, err);
71 SHOULD_HAVE(__nn_is_wlen_consistent(A), ret, err);
72
73 ret = 0;
74
75 err:
76 return ret;
77 }
78
79 /*
80 * Initialize nn from expected initial byte length 'len', setting its wlen
81 * to associated (ceil) value and clearing whole storage space. Return 0
82 * on success, -1 on error.
83 */
nn_init(nn_t A,u16 len)84 int nn_init(nn_t A, u16 len)
85 {
86 int ret;
87 u8 i;
88
89 MUST_HAVE(((A != NULL) && (len <= NN_MAX_BYTE_LEN)), ret, err);
90
91 A->wlen = (u8)BYTE_LEN_WORDS(len);
92 A->magic = NN_MAGIC;
93
94 for (i = 0; i < NN_MAX_WORD_LEN; i++) {
95 A->val[i] = WORD(0);
96 }
97
98 ret = 0;
99
100 err:
101 return ret;
102 }
103
104 /*
105 * Uninitialize the pointed nn to prevent further use (magic field in the
106 * structure is zeroized). The associated storage space is also zeroized. If
107 * given pointer is NULL or does not point to an initialized nn, the function
108 * does nothing.
109 */
nn_uninit(nn_t A)110 void nn_uninit(nn_t A)
111 {
112 if ((A != NULL) && (A->magic == NN_MAGIC)) {
113 int i;
114
115 for (i = 0; i < NN_MAX_WORD_LEN; i++) {
116 A->val[i] = WORD(0);
117 }
118
119 A->wlen = 0;
120 A->magic = WORD(0);
121 }
122
123 return;
124 }
125
126 /*
127 * Set current value of pointed initialized nn to 0. Returns 0 on success, -1
128 * on error.
129 */
nn_zero(nn_t A)130 int nn_zero(nn_t A)
131 {
132 int ret;
133
134 ret = nn_check_initialized(A); EG(ret, err);
135 ret = nn_init(A, 0);
136
137 err:
138 return ret;
139 }
140
141 /*
142 * Set current value of pointed initialized nn to given word value. Returns 0
143 * on success, -1 on error.
144 */
nn_set_word_value(nn_t A,word_t val)145 int nn_set_word_value(nn_t A, word_t val)
146 {
147 int ret;
148
149 ret = nn_zero(A); EG(ret, err);
150
151 A->val[0] = val;
152 A->wlen = 1;
153
154 err:
155 return ret;
156 }
157
158 /*
159 * Set current value of pointed initialized nn to 1. Returns 0 on success, -1
160 * on error.
161 */
nn_one(nn_t A)162 int nn_one(nn_t A)
163 {
164 return nn_set_word_value(A, WORD(1));
165 }
166
167 /*
168 * Conditionally swap two nn's content *in constant time*. Swapping is done
169 * if 'cnd' is not zero. Nothing is done otherwise. Returns 0 on success, -1
170 * on error.
171 *
172 * Aliasing of inputs is supported.
173 */
nn_cnd_swap(int cnd,nn_t in1,nn_t in2)174 int nn_cnd_swap(int cnd, nn_t in1, nn_t in2)
175 {
176 word_t mask = WORD_MASK_IFNOTZERO(cnd);
177 u8 len, i;
178 word_t t, r;
179 volatile word_t r_mask;
180 int ret;
181
182 ret = nn_check_initialized(in1); EG(ret, err);
183 ret = nn_check_initialized(in2); EG(ret, err);
184
185 MUST_HAVE((in1->wlen <= NN_MAX_WORD_LEN), ret, err);
186 MUST_HAVE((in2->wlen <= NN_MAX_WORD_LEN), ret, err);
187
188 len = (in1->wlen >= in2->wlen) ? in1->wlen : in2->wlen;
189
190 /* Use a random word for randomly masking the delta value hamming
191 * weight as proposed in Algorithm 4 of "Nonce@once: A Single-Trace
192 * EM Side Channel Attack on Several Constant-Time Elliptic
193 * Curve Implementations in Mobile Platforms" by Alam et al.
194 */
195 ret = get_unsafe_random((u8*)&r, sizeof(r)); EG(ret, err);
196 r_mask = r;
197
198 for (i = 0; i < NN_MAX_WORD_LEN; i++) {
199 word_t local_mask = WORD_MASK_IFNOTZERO((i < len));
200 t = ((in1->val[i] ^ in2->val[i]) & mask) ^ r_mask;
201 in1->val[i] ^= ((t & local_mask) ^ (r_mask & local_mask));
202 in2->val[i] ^= ((t & local_mask) ^ (r_mask & local_mask));
203 }
204
205 t = (word_t)(((in1->wlen ^ in2->wlen) & mask) ^ r_mask);
206 in1->wlen ^= (u8)(t ^ r_mask);
207 in2->wlen ^= (u8)(t ^ r_mask);
208
209 err:
210 return ret;
211 }
212
213 /*
214 * Adjust internal wlen attribute of given nn to new_wlen. If internal wlen
215 * attribute value is reduced, words above that limit in A are zeroized.
216 * new_wlen must be in [0, NN_MAX_WORD_LEN].
217 * The trimming is performed in constant time wrt to the length of the
218 * input to avoid leaking it.
219 * Returns 0 on success, -1 on error.
220 */
nn_set_wlen(nn_t A,u8 new_wlen)221 int nn_set_wlen(nn_t A, u8 new_wlen)
222 {
223 int ret;
224 u8 i;
225
226 ret = nn_check_initialized(A); EG(ret, err);
227 MUST_HAVE((new_wlen <= NN_MAX_WORD_LEN), ret, err);
228 MUST_HAVE((A->wlen <= NN_MAX_WORD_LEN), ret, err);
229
230 /* Trimming performed in constant time */
231 for (i = 0; i < NN_MAX_WORD_LEN; i++) {
232 A->val[i] = (word_t)(A->val[i] & WORD_MASK_IFZERO((i >= new_wlen)));
233 }
234
235 A->wlen = new_wlen;
236
237 err:
238 return ret;
239 }
240
241 /*
242 * The function tests if given nn value is zero. The result of the test is given
243 * using 'iszero' out parameter (1 if nn is zero, 0 if it is not). The function
244 * returns 0 on success, -1 on error. 'iszero' is not meaningfull on error.
245 * When A is valid, check is done *in constant time*.
246 */
nn_iszero(nn_src_t A,int * iszero)247 int nn_iszero(nn_src_t A, int *iszero)
248 {
249 int ret, notzero;
250 u8 i;
251
252 ret = nn_check_initialized(A); EG(ret, err);
253 MUST_HAVE((A->wlen <= NN_MAX_WORD_LEN), ret, err);
254 MUST_HAVE((iszero != NULL), ret, err);
255
256 notzero = 0;
257 for (i = 0; i < NN_MAX_WORD_LEN; i++) {
258 int mask = ((i < A->wlen) ? 1 : 0);
259 notzero |= ((A->val[i] != 0) & mask);
260 }
261
262 *iszero = !notzero;
263
264 err:
265 return ret;
266 }
267
268 /*
269 * The function tests if given nn value is one. The result of the test is given
270 * using 'isone' out parameter (1 if nn is one, 0 if it is not). The function
271 * returns 0 on success, -1 on error. 'isone' is not meaningfull on error.
272 * When A is valid, check is done *in constant time*.
273 */
nn_isone(nn_src_t A,int * isone)274 int nn_isone(nn_src_t A, int *isone)
275 {
276 int ret, notone;
277 u8 i;
278
279 ret = nn_check_initialized(A); EG(ret, err);
280 MUST_HAVE(!(A->wlen > NN_MAX_WORD_LEN), ret, err);
281 MUST_HAVE((isone != NULL), ret, err);
282
283 /* val[0] access is ok no matter wlen value */
284 notone = (A->val[0] != 1);
285 for (i = 1; i < NN_MAX_WORD_LEN; i++) {
286 int mask = ((i < A->wlen) ? 1 : 0);
287 notone |= ((A->val[i] != 0) & mask);
288 }
289
290 *isone = !notone;
291
292 err:
293 return ret;
294 }
295
296 /*
297 * The function tests if given nn value is odd. The result of the test is given
298 * using 'isodd' out parameter (1 if nn is odd, 0 if it is not). The function
299 * returns 0 on success, -1 on error. 'isodd' is not meaningfull on error.
300 */
nn_isodd(nn_src_t A,int * isodd)301 int nn_isodd(nn_src_t A, int *isodd)
302 {
303 int ret;
304
305 ret = nn_check_initialized(A); EG(ret, err);
306 MUST_HAVE((isodd != NULL), ret, err);
307
308 *isodd = (A->wlen != 0) && (A->val[0] & 1);
309
310 err:
311 return ret;
312 }
313
314 /*
315 * Compare given nn against given word value. This is done *in constant time*
316 * (only depending on the input length, not on its value or on the word value)
317 * when provided nn is valid. The function returns 0 on success and provides
318 * the comparison value in 'cmp' parameter. -1 is returned on error, in which
319 * case 'cmp' is not meaningful.
320 */
nn_cmp_word(nn_src_t in,word_t w,int * cmp)321 int nn_cmp_word(nn_src_t in, word_t w, int *cmp)
322 {
323 int ret, tmp = 0;
324 word_t mask;
325 u8 i;
326
327 ret = nn_check_initialized(in); EG(ret, err);
328 MUST_HAVE((cmp != NULL), ret, err);
329
330 /* No need to read, we can conclude */
331 if (in->wlen == 0) {
332 *cmp = -(w != 0);
333 ret = 0;
334 goto err;
335 }
336
337 /*
338 * Let's loop on all words above first one to see if one
339 * of those is non-zero.
340 */
341 for (i = (u8)(in->wlen - 1); i > 0; i--) {
342 tmp |= (in->val[i] != 0);
343 }
344
345 /*
346 * Compare first word of nn w/ w if needed. This
347 * is done w/ masking to avoid doing or not doing
348 * it based on 'tmp' (i.e. fact that a high word
349 * of nn is not zero).
350 */
351 mask = WORD_MASK_IFZERO(tmp);
352 tmp += (int)(((word_t)(in->val[i] > w)) & (mask));
353 tmp -= (int)(((word_t)(in->val[i] < w)) & (mask));
354 *cmp = tmp;
355
356 err:
357 return ret;
358 }
359
360 /*
361 * Compare given two nn 'A' and '. This is done *in constant time* (only
362 * depending on the largest length of the inputs, not on their values). The
363 * function returns 0 on success and provides the comparison value in
364 * 'cmp' parameter (0 if A == B, -1 if A < B, +1 if A > B). -1 is returned
365 * on error, in which case 'cmp' is not meaningful.
366 *
367 * Aliasing of inputs is supported.
368 */
nn_cmp(nn_src_t A,nn_src_t B,int * cmp)369 int nn_cmp(nn_src_t A, nn_src_t B, int *cmp)
370 {
371 int tmp, mask, ret, i;
372 u8 cmp_len;
373
374 ret = nn_check_initialized(A); EG(ret, err);
375 ret = nn_check_initialized(B); EG(ret, err);
376 MUST_HAVE((cmp != NULL), ret, err);
377
378 cmp_len = (A->wlen >= B->wlen) ? A->wlen : B->wlen;
379
380 tmp = 0;
381 for (i = (cmp_len - 1); i >= 0; i--) { /* ok even if cmp_len is 0 */
382 mask = !(tmp & 0x1);
383 tmp += ((A->val[i] > B->val[i]) & mask);
384 tmp -= ((A->val[i] < B->val[i]) & mask);
385 }
386 (*cmp) = tmp;
387
388 err:
389 return ret;
390 }
391
392 /*
393 * Copy given nn 'src_nn' value into 'dst_nn'. This is done *in constant time*.
394 * 'dst_nn' must point to a declared nn, but *need not be initialized*; it will
395 * be (manually) initialized by the function. 'src_nn' must have been
396 * initialized prior to the call. The function returns 0 on success, -1 on error.
397 *
398 * Alising of input and output is supported.
399 */
nn_copy(nn_t dst_nn,nn_src_t src_nn)400 int nn_copy(nn_t dst_nn, nn_src_t src_nn)
401 {
402 int ret;
403 u8 i;
404
405 MUST_HAVE((dst_nn != NULL), ret, err);
406 ret = nn_check_initialized(src_nn); EG(ret, err);
407
408 for (i = 0; i < NN_MAX_WORD_LEN; i++) {
409 dst_nn->val[i] = src_nn->val[i];
410 }
411
412 dst_nn->wlen = src_nn->wlen;
413 dst_nn->magic = NN_MAGIC;
414
415 err:
416 return ret;
417 }
418
419 /*
420 * Update wlen value of given nn if a set of words below wlen value are zero.
421 * The function is *not constant time*, i.e. it depends on the input value.
422 * The function returns 0 on sucess, -1 on error.
423 */
nn_normalize(nn_t in1)424 int nn_normalize(nn_t in1)
425 {
426 int ret;
427
428 ret = nn_check_initialized(in1); EG(ret, err);
429
430 while ((in1->wlen > 0) && (in1->val[in1->wlen - 1] == 0)) {
431 in1->wlen--;
432 }
433
434 err:
435 return ret;
436 }
437
438 /*
439 * Convert given consecutive WORD_BYTES bytes pointed by 'val' from network (big
440 * endian) order to host order. 'val' needs not point to a word-aligned region.
441 * The function returns 0 on success, -1 on error. On success, the result is
442 * provided in 'out'. 'out' is not meaningful on error.
443 */
_ntohw(const u8 * val,word_t * out)444 ATTRIBUTE_WARN_UNUSED_RET static int _ntohw(const u8 *val, word_t *out)
445 {
446 word_t res = 0;
447 u8 *res_buf = (u8 *)(&res);
448 int i, ret;
449
450 MUST_HAVE(((val != NULL) && (out != NULL)), ret, err);
451
452 if (arch_is_big_endian()) {
453 /* copy bytes, one by one to avoid alignement issues */
454 for (i = 0; i < WORD_BYTES; i++) {
455 res_buf[i] = val[i];
456 }
457 } else {
458 u8 tmp;
459
460 for (i = 0; i < (WORD_BYTES / 2); i++) {
461 tmp = val[i];
462 res_buf[i] = val[WORD_BYTES - i - 1];
463 res_buf[WORD_BYTES - i - 1] = tmp;
464 }
465
466 VAR_ZEROIFY(tmp);
467 }
468
469 *out = res;
470 ret = 0;
471
472 err:
473 return ret;
474 }
475
476 /* Same as previous function but from host to network byte order. */
_htonw(const u8 * val,word_t * out)477 ATTRIBUTE_WARN_UNUSED_RET static inline int _htonw(const u8 *val, word_t *out)
478 {
479 return _ntohw(val, out);
480 }
481
482 /*
483 * 'out_nn' is expected to point to the storage location of a declared nn,
484 * which will be initialized by the function (i.e. given nn need not be
485 * initialized). The function then imports value (expected to be in big
486 * endian) from given buffer 'buf' of length 'buflen' into it. The function
487 * expects (and enforces) that buflen is less than or equal to NN_MAX_BYTE_LEN.
488 * The function returns 0 on success, -1 on error.
489 */
nn_init_from_buf(nn_t out_nn,const u8 * buf,u16 buflen)490 int nn_init_from_buf(nn_t out_nn, const u8 *buf, u16 buflen)
491 {
492 u8 tmp[NN_MAX_BYTE_LEN];
493 u16 wpos;
494 int ret;
495
496 MUST_HAVE(((out_nn != NULL) && (buf != NULL) &&
497 (buflen <= NN_MAX_BYTE_LEN)), ret, err);
498
499 ret = local_memset(tmp, 0, (u32)(NN_MAX_BYTE_LEN - buflen)); EG(ret, err);
500 ret = local_memcpy(tmp + NN_MAX_BYTE_LEN - buflen, buf, buflen); EG(ret, err);
501
502 ret = nn_init(out_nn, buflen); EG(ret, err);
503
504 for (wpos = 0; wpos < NN_MAX_WORD_LEN; wpos++) {
505 u16 buf_pos = (u16)((NN_MAX_WORD_LEN - wpos - 1) * WORD_BYTES);
506 ret = _ntohw(tmp + buf_pos, &(out_nn->val[wpos])); EG(ret, err);
507 }
508
509 ret = local_memset(tmp, 0, NN_MAX_BYTE_LEN);
510
511 err:
512 return ret;
513 }
514
515 /*
516 * Export 'buflen' LSB bytes of given nn as a big endian buffer. If buffer
517 * length is larger than effective size of input nn, padding w/ zero is
518 * performed. If buffer size is smaller than input nn effective size,
519 * MSB bytes are simply lost in exported buffer. The function returns 0
520 * on success, -1 on error.
521 */
nn_export_to_buf(u8 * buf,u16 buflen,nn_src_t in_nn)522 int nn_export_to_buf(u8 *buf, u16 buflen, nn_src_t in_nn)
523 {
524 u8 *src_word_ptr, *dst_word_ptr;
525 const u8 wb = WORD_BYTES;
526 u16 remain = buflen;
527 int ret;
528 u8 i;
529
530 MUST_HAVE((buf != NULL), ret, err);
531 ret = nn_check_initialized(in_nn); EG(ret, err);
532
533 ret = local_memset(buf, 0, buflen); EG(ret, err);
534
535 /*
536 * We consider each word in input nn one at a time and convert
537 * it to big endian in a temporary word. Based on remaining
538 * length of output buffer, we copy the LSB bytes of temporary
539 * word into it at current position. That way, filling of the
540 * buffer is performed from its end to its beginning, word by
541 * word, except for the last one, which may be shorten if
542 * given buffer length is not a multiple of word length.
543 */
544 for (i = 0; remain && (i < in_nn->wlen); i++) {
545 u16 copylen = (remain > wb) ? wb : remain;
546 word_t val;
547
548 ret = _htonw((const u8 *)&in_nn->val[i], &val); EG(ret, err);
549
550 dst_word_ptr = (buf + buflen - (i * wb) - copylen);
551 src_word_ptr = (u8 *)(&val) + wb - copylen;
552
553 ret = local_memcpy(dst_word_ptr, src_word_ptr, copylen); EG(ret, err);
554 src_word_ptr = NULL;
555
556 remain = (u16)(remain - copylen);
557 }
558
559 err:
560 return ret;
561 }
562
563 /*
564 * Given a table 'tab' pointing to a set of 'tabsize' NN elements, the
565 * function copies the value of element at position idx (idx < tabsize)
566 * in 'out' parameters. Masking is used to avoid leaking which element
567 * was copied.
568 *
569 * Note that the main copying loop is done on the maximum bits for all
570 * NN elements and not based on the specific effective size of each
571 * NN elements in 'tab'
572 *
573 * Returns 0 on success, -1 on error.
574 *
575 * Aliasing of out and the selected element inside the tab is NOT supported.
576 */
nn_tabselect(nn_t out,u8 idx,nn_src_t * tab,u8 tabsize)577 int nn_tabselect(nn_t out, u8 idx, nn_src_t *tab, u8 tabsize)
578 {
579 u8 i, k;
580 word_t mask;
581 int ret;
582
583 /* Basic sanity checks */
584 MUST_HAVE(((tab != NULL) && (idx < tabsize)), ret, err);
585
586 ret = nn_check_initialized(out); EG(ret, err);
587
588 /* Zeroize out and enforce its size. */
589 ret = nn_zero(out); EG(ret, err);
590
591 out->wlen = 0;
592
593 for (k = 0; k < tabsize; k++) {
594 /* Check current element is initialized */
595 ret = nn_check_initialized(tab[k]); EG(ret, err);
596
597 mask = WORD_MASK_IFNOTZERO(idx == k);
598
599 out->wlen = (u8)(out->wlen | ((tab[k]->wlen) & mask));
600
601 for (i = 0; i < NN_MAX_WORD_LEN; i++) {
602 out->val[i] |= (tab[k]->val[i] & mask);
603 }
604 }
605
606 err:
607 return ret;
608 }
609