/* * Copyright (C) 2017 - This file is part of libecc project * * Authors: * Ryad BENADJILA <ryadbenadjila@gmail.com> * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr> * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr> * * Contributors: * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr> * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr> * * This software is licensed under a dual BSD and GPL v2 license. * See LICENSE file at the root folder of the project. */ #define NN_CONSISTENCY_CHECK #include <libecc/nn/nn.h> /* * Used for the conditional swap algorithm SCA * resistance, see below in the implementation of * nn_cnd_swap. */ #include <libecc/utils/utils_rand.h> /* * Except otherwise specified, all functions accept *initialized* nn. * The WORD(NN_MAX_WORD_LEN + WORDSIZE) magic is here to detect modules * compiled with different WORDSIZE or NN_MAX_WORD_LEN and are binary * incompatible. */ #define NN_MAGIC ((word_t)((0xb4cf5d56e2023316ULL ^ (WORD(NN_MAX_WORD_LEN + WORDSIZE))))) /* * Local helper internally used to check that the storage space * above wlen is made of zero words. The function does NOT check * if given nn has been initialized. This must have been done * by the caller. * * Due to its performance cost, this consistency check is used * in SHOULD_HAVE macros, meaning that it will only be present * in DEBUG mode. Hence the ATTRIBUTE_UNUSED so that no warning * (error in -Werror) is triggered at compilation time. * */ ATTRIBUTE_WARN_UNUSED_RET static int ATTRIBUTE_UNUSED __nn_is_wlen_consistent(nn_src_t A) { word_t val = 0; u8 i; for (i = A->wlen; i < NN_MAX_WORD_LEN; i++) { val |= (A)->val[i]; } return (val == 0); } /* * Verify that pointed nn has already been initialized. This function * should be used as a safety net in all function before using a nn * received as parameter. Returns 0 on success, -1 on error. */ int nn_check_initialized(nn_src_t A) { int ret; MUST_HAVE((A != NULL), ret, err); MUST_HAVE((A->magic == NN_MAGIC), ret, err); MUST_HAVE((A->wlen <= NN_MAX_WORD_LEN), ret, err); SHOULD_HAVE(__nn_is_wlen_consistent(A), ret, err); ret = 0; err: return ret; } /* * Initialize nn from expected initial byte length 'len', setting its wlen * to associated (ceil) value and clearing whole storage space. Return 0 * on success, -1 on error. */ int nn_init(nn_t A, u16 len) { int ret; u8 i; MUST_HAVE(((A != NULL) && (len <= NN_MAX_BYTE_LEN)), ret, err); A->wlen = (u8)BYTE_LEN_WORDS(len); A->magic = NN_MAGIC; for (i = 0; i < NN_MAX_WORD_LEN; i++) { A->val[i] = WORD(0); } ret = 0; err: return ret; } /* * Uninitialize the pointed nn to prevent further use (magic field in the * structure is zeroized). The associated storage space is also zeroized. If * given pointer is NULL or does not point to an initialized nn, the function * does nothing. */ void nn_uninit(nn_t A) { if ((A != NULL) && (A->magic == NN_MAGIC)) { int i; for (i = 0; i < NN_MAX_WORD_LEN; i++) { A->val[i] = WORD(0); } A->wlen = 0; A->magic = WORD(0); } return; } /* * Set current value of pointed initialized nn to 0. Returns 0 on success, -1 * on error. */ int nn_zero(nn_t A) { int ret; ret = nn_check_initialized(A); EG(ret, err); ret = nn_init(A, 0); err: return ret; } /* * Set current value of pointed initialized nn to given word value. Returns 0 * on success, -1 on error. */ int nn_set_word_value(nn_t A, word_t val) { int ret; ret = nn_zero(A); EG(ret, err); A->val[0] = val; A->wlen = 1; err: return ret; } /* * Set current value of pointed initialized nn to 1. Returns 0 on success, -1 * on error. */ int nn_one(nn_t A) { return nn_set_word_value(A, WORD(1)); } /* * Conditionally swap two nn's content *in constant time*. Swapping is done * if 'cnd' is not zero. Nothing is done otherwise. Returns 0 on success, -1 * on error. * * Aliasing of inputs is supported. */ int nn_cnd_swap(int cnd, nn_t in1, nn_t in2) { word_t mask = WORD_MASK_IFNOTZERO(cnd); u8 len, i; word_t t, r; volatile word_t r_mask; int ret; ret = nn_check_initialized(in1); EG(ret, err); ret = nn_check_initialized(in2); EG(ret, err); MUST_HAVE((in1->wlen <= NN_MAX_WORD_LEN), ret, err); MUST_HAVE((in2->wlen <= NN_MAX_WORD_LEN), ret, err); len = (in1->wlen >= in2->wlen) ? in1->wlen : in2->wlen; /* Use a random word for randomly masking the delta value hamming * weight as proposed in Algorithm 4 of "Nonce@once: A Single-Trace * EM Side Channel Attack on Several Constant-Time Elliptic * Curve Implementations in Mobile Platforms" by Alam et al. */ ret = get_unsafe_random((u8*)&r, sizeof(r)); EG(ret, err); r_mask = r; for (i = 0; i < NN_MAX_WORD_LEN; i++) { word_t local_mask = WORD_MASK_IFNOTZERO((i < len)); t = ((in1->val[i] ^ in2->val[i]) & mask) ^ r_mask; in1->val[i] ^= ((t & local_mask) ^ (r_mask & local_mask)); in2->val[i] ^= ((t & local_mask) ^ (r_mask & local_mask)); } t = (word_t)(((in1->wlen ^ in2->wlen) & mask) ^ r_mask); in1->wlen ^= (u8)(t ^ r_mask); in2->wlen ^= (u8)(t ^ r_mask); err: return ret; } /* * Adjust internal wlen attribute of given nn to new_wlen. If internal wlen * attribute value is reduced, words above that limit in A are zeroized. * new_wlen must be in [0, NN_MAX_WORD_LEN]. * The trimming is performed in constant time wrt to the length of the * input to avoid leaking it. * Returns 0 on success, -1 on error. */ int nn_set_wlen(nn_t A, u8 new_wlen) { int ret; u8 i; ret = nn_check_initialized(A); EG(ret, err); MUST_HAVE((new_wlen <= NN_MAX_WORD_LEN), ret, err); MUST_HAVE((A->wlen <= NN_MAX_WORD_LEN), ret, err); /* Trimming performed in constant time */ for (i = 0; i < NN_MAX_WORD_LEN; i++) { A->val[i] = (word_t)(A->val[i] & WORD_MASK_IFZERO((i >= new_wlen))); } A->wlen = new_wlen; err: return ret; } /* * The function tests if given nn value is zero. The result of the test is given * using 'iszero' out parameter (1 if nn is zero, 0 if it is not). The function * returns 0 on success, -1 on error. 'iszero' is not meaningfull on error. * When A is valid, check is done *in constant time*. */ int nn_iszero(nn_src_t A, int *iszero) { int ret, notzero; u8 i; ret = nn_check_initialized(A); EG(ret, err); MUST_HAVE((A->wlen <= NN_MAX_WORD_LEN), ret, err); MUST_HAVE((iszero != NULL), ret, err); notzero = 0; for (i = 0; i < NN_MAX_WORD_LEN; i++) { int mask = ((i < A->wlen) ? 1 : 0); notzero |= ((A->val[i] != 0) & mask); } *iszero = !notzero; err: return ret; } /* * The function tests if given nn value is one. The result of the test is given * using 'isone' out parameter (1 if nn is one, 0 if it is not). The function * returns 0 on success, -1 on error. 'isone' is not meaningfull on error. * When A is valid, check is done *in constant time*. */ int nn_isone(nn_src_t A, int *isone) { int ret, notone; u8 i; ret = nn_check_initialized(A); EG(ret, err); MUST_HAVE(!(A->wlen > NN_MAX_WORD_LEN), ret, err); MUST_HAVE((isone != NULL), ret, err); /* val[0] access is ok no matter wlen value */ notone = (A->val[0] != 1); for (i = 1; i < NN_MAX_WORD_LEN; i++) { int mask = ((i < A->wlen) ? 1 : 0); notone |= ((A->val[i] != 0) & mask); } *isone = !notone; err: return ret; } /* * The function tests if given nn value is odd. The result of the test is given * using 'isodd' out parameter (1 if nn is odd, 0 if it is not). The function * returns 0 on success, -1 on error. 'isodd' is not meaningfull on error. */ int nn_isodd(nn_src_t A, int *isodd) { int ret; ret = nn_check_initialized(A); EG(ret, err); MUST_HAVE((isodd != NULL), ret, err); *isodd = (A->wlen != 0) && (A->val[0] & 1); err: return ret; } /* * Compare given nn against given word value. This is done *in constant time* * (only depending on the input length, not on its value or on the word value) * when provided nn is valid. The function returns 0 on success and provides * the comparison value in 'cmp' parameter. -1 is returned on error, in which * case 'cmp' is not meaningful. */ int nn_cmp_word(nn_src_t in, word_t w, int *cmp) { int ret, tmp = 0; word_t mask; u8 i; ret = nn_check_initialized(in); EG(ret, err); MUST_HAVE((cmp != NULL), ret, err); /* No need to read, we can conclude */ if (in->wlen == 0) { *cmp = -(w != 0); ret = 0; goto err; } /* * Let's loop on all words above first one to see if one * of those is non-zero. */ for (i = (u8)(in->wlen - 1); i > 0; i--) { tmp |= (in->val[i] != 0); } /* * Compare first word of nn w/ w if needed. This * is done w/ masking to avoid doing or not doing * it based on 'tmp' (i.e. fact that a high word * of nn is not zero). */ mask = WORD_MASK_IFZERO(tmp); tmp += (int)(((word_t)(in->val[i] > w)) & (mask)); tmp -= (int)(((word_t)(in->val[i] < w)) & (mask)); *cmp = tmp; err: return ret; } /* * Compare given two nn 'A' and '. This is done *in constant time* (only * depending on the largest length of the inputs, not on their values). The * function returns 0 on success and provides the comparison value in * 'cmp' parameter (0 if A == B, -1 if A < B, +1 if A > B). -1 is returned * on error, in which case 'cmp' is not meaningful. * * Aliasing of inputs is supported. */ int nn_cmp(nn_src_t A, nn_src_t B, int *cmp) { int tmp, mask, ret, i; u8 cmp_len; ret = nn_check_initialized(A); EG(ret, err); ret = nn_check_initialized(B); EG(ret, err); MUST_HAVE((cmp != NULL), ret, err); cmp_len = (A->wlen >= B->wlen) ? A->wlen : B->wlen; tmp = 0; for (i = (cmp_len - 1); i >= 0; i--) { /* ok even if cmp_len is 0 */ mask = !(tmp & 0x1); tmp += ((A->val[i] > B->val[i]) & mask); tmp -= ((A->val[i] < B->val[i]) & mask); } (*cmp) = tmp; err: return ret; } /* * Copy given nn 'src_nn' value into 'dst_nn'. This is done *in constant time*. * 'dst_nn' must point to a declared nn, but *need not be initialized*; it will * be (manually) initialized by the function. 'src_nn' must have been * initialized prior to the call. The function returns 0 on success, -1 on error. * * Alising of input and output is supported. */ int nn_copy(nn_t dst_nn, nn_src_t src_nn) { int ret; u8 i; MUST_HAVE((dst_nn != NULL), ret, err); ret = nn_check_initialized(src_nn); EG(ret, err); for (i = 0; i < NN_MAX_WORD_LEN; i++) { dst_nn->val[i] = src_nn->val[i]; } dst_nn->wlen = src_nn->wlen; dst_nn->magic = NN_MAGIC; err: return ret; } /* * Update wlen value of given nn if a set of words below wlen value are zero. * The function is *not constant time*, i.e. it depends on the input value. * The function returns 0 on sucess, -1 on error. */ int nn_normalize(nn_t in1) { int ret; ret = nn_check_initialized(in1); EG(ret, err); while ((in1->wlen > 0) && (in1->val[in1->wlen - 1] == 0)) { in1->wlen--; } err: return ret; } /* * Convert given consecutive WORD_BYTES bytes pointed by 'val' from network (big * endian) order to host order. 'val' needs not point to a word-aligned region. * The function returns 0 on success, -1 on error. On success, the result is * provided in 'out'. 'out' is not meaningful on error. */ ATTRIBUTE_WARN_UNUSED_RET static int _ntohw(const u8 *val, word_t *out) { word_t res = 0; u8 *res_buf = (u8 *)(&res); int i, ret; MUST_HAVE(((val != NULL) && (out != NULL)), ret, err); if (arch_is_big_endian()) { /* copy bytes, one by one to avoid alignement issues */ for (i = 0; i < WORD_BYTES; i++) { res_buf[i] = val[i]; } } else { u8 tmp; for (i = 0; i < (WORD_BYTES / 2); i++) { tmp = val[i]; res_buf[i] = val[WORD_BYTES - i - 1]; res_buf[WORD_BYTES - i - 1] = tmp; } VAR_ZEROIFY(tmp); } *out = res; ret = 0; err: return ret; } /* Same as previous function but from host to network byte order. */ ATTRIBUTE_WARN_UNUSED_RET static inline int _htonw(const u8 *val, word_t *out) { return _ntohw(val, out); } /* * 'out_nn' is expected to point to the storage location of a declared nn, * which will be initialized by the function (i.e. given nn need not be * initialized). The function then imports value (expected to be in big * endian) from given buffer 'buf' of length 'buflen' into it. The function * expects (and enforces) that buflen is less than or equal to NN_MAX_BYTE_LEN. * The function returns 0 on success, -1 on error. */ int nn_init_from_buf(nn_t out_nn, const u8 *buf, u16 buflen) { u8 tmp[NN_MAX_BYTE_LEN]; u16 wpos; int ret; MUST_HAVE(((out_nn != NULL) && (buf != NULL) && (buflen <= NN_MAX_BYTE_LEN)), ret, err); ret = local_memset(tmp, 0, (u32)(NN_MAX_BYTE_LEN - buflen)); EG(ret, err); ret = local_memcpy(tmp + NN_MAX_BYTE_LEN - buflen, buf, buflen); EG(ret, err); ret = nn_init(out_nn, buflen); EG(ret, err); for (wpos = 0; wpos < NN_MAX_WORD_LEN; wpos++) { u16 buf_pos = (u16)((NN_MAX_WORD_LEN - wpos - 1) * WORD_BYTES); ret = _ntohw(tmp + buf_pos, &(out_nn->val[wpos])); EG(ret, err); } ret = local_memset(tmp, 0, NN_MAX_BYTE_LEN); err: return ret; } /* * Export 'buflen' LSB bytes of given nn as a big endian buffer. If buffer * length is larger than effective size of input nn, padding w/ zero is * performed. If buffer size is smaller than input nn effective size, * MSB bytes are simply lost in exported buffer. The function returns 0 * on success, -1 on error. */ int nn_export_to_buf(u8 *buf, u16 buflen, nn_src_t in_nn) { u8 *src_word_ptr, *dst_word_ptr; const u8 wb = WORD_BYTES; u16 remain = buflen; int ret; u8 i; MUST_HAVE((buf != NULL), ret, err); ret = nn_check_initialized(in_nn); EG(ret, err); ret = local_memset(buf, 0, buflen); EG(ret, err); /* * We consider each word in input nn one at a time and convert * it to big endian in a temporary word. Based on remaining * length of output buffer, we copy the LSB bytes of temporary * word into it at current position. That way, filling of the * buffer is performed from its end to its beginning, word by * word, except for the last one, which may be shorten if * given buffer length is not a multiple of word length. */ for (i = 0; remain && (i < in_nn->wlen); i++) { u16 copylen = (remain > wb) ? wb : remain; word_t val; ret = _htonw((const u8 *)&in_nn->val[i], &val); EG(ret, err); dst_word_ptr = (buf + buflen - (i * wb) - copylen); src_word_ptr = (u8 *)(&val) + wb - copylen; ret = local_memcpy(dst_word_ptr, src_word_ptr, copylen); EG(ret, err); src_word_ptr = NULL; remain = (u16)(remain - copylen); } err: return ret; } /* * Given a table 'tab' pointing to a set of 'tabsize' NN elements, the * function copies the value of element at position idx (idx < tabsize) * in 'out' parameters. Masking is used to avoid leaking which element * was copied. * * Note that the main copying loop is done on the maximum bits for all * NN elements and not based on the specific effective size of each * NN elements in 'tab' * * Returns 0 on success, -1 on error. * * Aliasing of out and the selected element inside the tab is NOT supported. */ int nn_tabselect(nn_t out, u8 idx, nn_src_t *tab, u8 tabsize) { u8 i, k; word_t mask; int ret; /* Basic sanity checks */ MUST_HAVE(((tab != NULL) && (idx < tabsize)), ret, err); ret = nn_check_initialized(out); EG(ret, err); /* Zeroize out and enforce its size. */ ret = nn_zero(out); EG(ret, err); out->wlen = 0; for (k = 0; k < tabsize; k++) { /* Check current element is initialized */ ret = nn_check_initialized(tab[k]); EG(ret, err); mask = WORD_MASK_IFNOTZERO(idx == k); out->wlen = (u8)(out->wlen | ((tab[k]->wlen) & mask)); for (i = 0; i < NN_MAX_WORD_LEN; i++) { out->val[i] |= (tab[k]->val[i] & mask); } } err: return ret; }
