A secure (constant time and memory access) memory comparaison function is needed to handle secret data. Namely, l_ecc_scalar tends to be instantiated with secret, and _vli_cmp leak "how much" different it is from the prime p. The secure memcmp is defined in ell/util.h to be available to projects using ELL. --- ell/ecc-private.h | 33 +++++++++++++++++++++ ell/ecc.c | 2 +- ell/util.h | 73 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 107 insertions(+), 1 deletion(-) diff --git a/ell/ecc-private.h b/ell/ecc-private.h index 70d9607..a700983 100644 --- a/ell/ecc-private.h +++ b/ell/ecc-private.h @@ -24,6 +24,7 @@ #include <stdint.h> #include "ecc.h" +#include "util.h" struct l_ecc_curve; @@ -49,6 +50,38 @@ struct l_ecc_scalar { const struct l_ecc_curve *curve; }; +/* + * Performs a secure memory comparison of two uint64_t buffers of size bytes + * representing an integer. Blobs are ordered in little endian. It returns + * a negative, zero or positif value if a < b, a == b or a > b respectively. + */ +static inline int l_secure_memcmp_64(const uint64_t *a, const uint64_t *b, + size_t size) +{ + uint64_t aa_64, bb_64; + + int res = 0, mask; + + int i = 0; + + if (size) { + /* + * Arrays store blobs in LE, we will process each blob as a byte array + * of size 8 using l_secure_memcmp. We need to make sure to feed a BE + * byte array to avoid unexpected behavior on different architectures. + */ + do { + aa_64 = L_CPU_TO_BE64(a[i]); + bb_64 = L_CPU_TO_BE64(b[i]); + mask = l_secure_memcmp(&aa_64, &bb_64, 8); + res = (mask & res) | mask; + i++; + } while(i != size); + } + + return res; +} + void _ecc_be2native(uint64_t *dest, const uint64_t *bytes, unsigned int ndigits); diff --git a/ell/ecc.c b/ell/ecc.c index 250f7e8..c69057f 100644 --- a/ell/ecc.c +++ b/ell/ecc.c @@ -603,7 +603,7 @@ LIB_EXPORT struct l_ecc_scalar *l_ecc_scalar_new( _ecc_be2native(c->c, buf, curve->ndigits); if (!vli_is_zero_or_one(c->c, curve->ndigits) && - _vli_cmp(c->c, curve->n, curve->ndigits) < 0) + l_secure_memcmp_64(curve->n, c->c, curve->ndigits) > 0) return c; l_ecc_scalar_free(c); diff --git a/ell/util.h b/ell/util.h index 6e88505..d87ec2e 100644 --- a/ell/util.h +++ b/ell/util.h @@ -315,6 +315,79 @@ const char *l_util_get_debugfs_path(void); while (__result == -1L && errno == EINTR); \ __result; })) +/* + * Taken from https://github.com/chmike/cst_time_memcmp, adding a volatile to + * ensure the compiler does not try to optimize the constant time behavior. + * The code has been modified to add comments and project specific code + * styling. + * This specific piece of code is subject to the following copyright: + * + * The MIT License (MIT) + * + * Copyright (c) 2015 Christophe Meessen + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * This function performs a secure memory comparison of two buffers of size + * bytes, representing an integer (byte order is big endian). It returns + * a negative, zero or positif value if a < b, a == b or a > b respectively. + */ +static inline int l_secure_memcmp(const void *a, const void *b, + size_t size) +{ + const volatile uint8_t *aa = a; + const volatile uint8_t *bb = b; + int res = 0, diff, mask; + /* + * We will compare all bytes, starting with the less significant. When we + * find a non-zero difference, we update the result accordingly. + */ + if (size > 0) { + do { + --size; + diff = aa[size] - bb[size]; + /* + * The following couple of lines can be summarized as a constant + * time/memory access version of: + * if (diff != 0) res = diff; + * + * From the previous operation, we know that diff is in [-255, 255] + * The following figure show the possible value of mask, based on + * different cases of diff: + * + * diff | diff-1 | ~diff | ((diff-1) & ~diff) | mask + * -------|------------|------------|--------------------|------ + * < 0 | 0xFFFFFFXX | 0x000000YY | 0x000000ZZ | 0 + * == 0 | 0xFFFFFFFF | 0xFFFFFFFF | 0xFFFFFFFF | 0xF..F + * > 0 | 0x000000XX | 0xFFFFFFYY | 0x000000ZZ | 0 + * + * Hence, the mask allows to keep res when diff == 0, and to set + * res to diff otherwise. + */ + mask = (((diff - 1) & ~diff) >> 8); + res = (res & mask) | diff; + } while (size != 0); + } + + return res; +} + #ifdef __cplusplus } #endif -- 2.25.4