From 0541fd19426994e42decf5987253978634e1f865 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Fri, 3 Apr 2020 15:18:58 +0200 Subject: [PATCH] adding a GNUNET_memcmp_priv for constant-time comparing of data; fixes #6152 (modulo actually finding specific places where this SHOULD be used instead of GNUNET_memcmp) --- src/include/gnunet_common.h | 34 ++++- src/util/Makefile.am | 1 + src/util/consttime_memcmp.c | 279 ++++++++++++++++++++++++++++++++++++ 3 files changed, 313 insertions(+), 1 deletion(-) create mode 100644 src/util/consttime_memcmp.c diff --git a/src/include/gnunet_common.h b/src/include/gnunet_common.h index 6d9652a16..76c2b9352 100644 --- a/src/include/gnunet_common.h +++ b/src/include/gnunet_common.h @@ -1,6 +1,6 @@ /* This file is part of GNUnet. - Copyright (C) 2006-2013 GNUnet e.V. + Copyright (C) 2006-2020 GNUnet e.V. GNUnet is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published @@ -1089,6 +1089,9 @@ GNUNET_ntoh_double (double d); /** * Compare memory in @a a and @a b, where both must be of * the same pointer type. + * + * Do NOT use this function on arrays, it would only compare + * the first element! */ #define GNUNET_memcmp(a, b) \ ({ \ @@ -1098,6 +1101,35 @@ GNUNET_ntoh_double (double d); }) +/** + * Compare memory in @a b1 and @a b2 in constant time, suitable for private + * data. + * + * @param b1 some buffer of size @a len + * @param b2 another buffer of size @a len + * @param len number of bytes in @a b1 and @a b2 + * @return 0 if buffers are equal, + */ +int +GNUNET_memcmp_ct_ (const void *b1, + const void *b2, + size_t len); + +/** + * Compare memory in @a a and @a b in constant time, suitable for private + * data. Both @a a and @a b must be of the same pointer type. + * + * Do NOT use this function on arrays, it would only compare + * the first element! + */ +#define GNUNET_memcmp_priv(a, b) \ + ({ \ + const typeof (*b) * _a = (a); \ + const typeof (*a) * _b = (b); \ + GNUNET_memcmp_ct_ (_a, _b, sizeof(*a)); \ + }) + + /** * Check that memory in @a a is all zeros. @a a must be a pointer. * diff --git a/src/util/Makefile.am b/src/util/Makefile.am index ffe95a24f..ae72abb44 100644 --- a/src/util/Makefile.am +++ b/src/util/Makefile.am @@ -46,6 +46,7 @@ libgnunetutil_la_SOURCES = \ common_logging.c \ configuration.c \ configuration_loader.c \ + consttime_memcmp.c \ container_bloomfilter.c \ container_heap.c \ container_meta_data.c \ diff --git a/src/util/consttime_memcmp.c b/src/util/consttime_memcmp.c new file mode 100644 index 000000000..820ba9835 --- /dev/null +++ b/src/util/consttime_memcmp.c @@ -0,0 +1,279 @@ +/* +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. +*/ + +/* Minimally modified for libgnunetutil: added license header + (from https://github.com/chmike/cst_time_memcmp, LICENSE file), and + renamed the exported symbol: */ +#define consttime_memcmp GNUNET_memcmp_ct_ +/* Rest of the file is 'original' */ + + +#include +#include + +/* + * "constant time" memcmp. Time taken depends on the buffer length, of + * course, but not on the content of the buffers. + * + * Just like the ordinary memcmp function, the return value is + * tri-state: <0, 0, or >0. However, applications that need a + * constant-time memory comparison function usually need only a + * two-state result, signalling only whether the inputs were identical + * or different, but not signalling which of the inputs was larger. + * This code could be made significantly faster and simpler if the + * requirement for a tri-state result were removed. + * + * In order to protect against adversaries who can observe timing, + * cache hits or misses, page faults, etc., and who can use such + * observations to learn something about the relationship between the + * contents of the two buffers, we have to perform exactly the same + * instructions and memory accesses regardless of the contents of the + * buffers. We can't stop as soon as we find a difference, we can't + * take different conditional branches depending on the data, and we + * can't use different pointers or array indexes depending on the data. + * + * Further reading: + * + * .Rs + * .%A Paul C. Kocher + * .%T Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems + * .%D 1996 + * .%J CRYPTO 1996 + * .%P 104-113 + * .%U http://www.cryptography.com/timingattack/paper.html + * .%U http://www.webcitation.org/query?url=http%3A%2F%2Fwww.cryptography.com%2Ftimingattack%2Fpaper.html&date=2012-10-17 + * .Re + * + * .Rs + * .%A D. Boneh + * .%A D. Brumley + * .%T Remote timing attacks are practical + * .%D August 2003 + * .%J Proceedings of the 12th Usenix Security Symposium, 2003 + * .%U https://crypto.stanford.edu/~dabo/abstracts/ssl-timing.html + * .%U http://www.webcitation.org/query?url=https%3A%2F%2Fcrypto.stanford.edu%2F%7Edabo%2Fabstracts%2Fssl-timing.html&date=2012-10-17 + * .%U http://www.webcitation.org/query?url=http%3A%2F%2Fcrypto.stanford.edu%2F%7Edabo%2Fpubs%2Fpapers%2Fssl-timing.pdf&date=2012-10-17 + * .Es + * + * .Rs + * .%A Coda Hale + * .%T A Lesson In Timing Attacks (or, Don't use MessageDigest.isEquals) + * .%D 13 Aug 2009 + * .%U http://codahale.com/a-lesson-in-timing-attacks/ + * .%U http://www.webcitation.org/query?url=http%3A%2F%2Fcodahale.com%2Fa-lesson-in-timing-attacks%2F&date=2012-10-17 + * .Re + * + */ + +/* + * A note on portability: + * + * We assume that char is exactly 8 bits, the same as uint8_t, and that + * integer types with exactly 16 bits and exactly 32 bits exist. (If + * there is ever a need to change this, then the actual requirement is + * that we need a type that is at least two bits wider than char, and + * another type that is at least two bits wider than that, or we need to + * fake it somehow.) + * + * We do not assume any particular size for the plain "int" type, except + * that it is at least 16 bits, as is guaranteed by the C language + * standard. + * + * We do not assume that signed integer overflow is harmless. We + * ensure that signed integer overflow does not occur, so that + * implementation-defined overflow behaviour is not invoked. + * + * We rely on the C standard's guarantees regarding the wraparound + * behaviour of unsigned integer arithmetic, and on the analagous + * guarantees regarding conversions from signed types to narrower + * unsigned types. + * + * We do not assume that the platform uses two's complement arithmetic. + */ + +/* + * How hard do we have to try to prevent unwanted compiler optimisations? + * + * Try compiling with "#define USE_VOLATILE_TEMPORARY 0", and examine + * the compiler output. If the only conditional tests in the entire + * function are to test whether len is zero, then all is well, but try + * again with different optimisation flags to be sure. If the compiler + * emitted code with conditional tests that do anything other than + * testing whether len is zero, then that's a problem, so try again with + * "#define USE_VOLATILE_TEMPORARY 1". If it's still bad, then you are + * out of luck. + */ +#define USE_VOLATILE_TEMPORARY 0 + +int +consttime_memcmp (const void *b1, const void *b2, size_t len) +{ + const uint8_t *c1, *c2; + uint16_t d, r, m; + +#if USE_VOLATILE_TEMPORARY + volatile uint16_t v; +#else + uint16_t v; +#endif + + c1 = b1; + c2 = b2; + + r = 0; + while (len) + { + /* + * Take the low 8 bits of r (in the range 0x00 to 0xff, + * or 0 to 255); + * As explained elsewhere, the low 8 bits of r will be zero + * if and only if all bytes compared so far were identical; + * Zero-extend to a 16-bit type (in the range 0x0000 to + * 0x00ff); + * Add 255, yielding a result in the range 255 to 510; + * Save that in a volatile variable to prevent + * the compiler from trying any shortcuts (the + * use of a volatile variable depends on "#ifdef + * USE_VOLATILE_TEMPORARY", and most compilers won't + * need it); + * Divide by 256 yielding a result of 1 if the original + * value of r was non-zero, or 0 if r was zero; + * Subtract 1, yielding 0 if r was non-zero, or -1 if r + * was zero; + * Convert to uint16_t, yielding 0x0000 if r was + * non-zero, or 0xffff if r was zero; + * Save in m. + */v = ((uint16_t) (uint8_t) r) + 255; + m = v / 256 - 1; + + /* + * Get the values from *c1 and *c2 as uint8_t (each will + * be in the range 0 to 255, or 0x00 to 0xff); + * Convert them to signed int values (still in the + * range 0 to 255); + * Subtract them using signed arithmetic, yielding a + * result in the range -255 to +255; + * Convert to uint16_t, yielding a result in the range + * 0xff01 to 0xffff (for what was previously -255 to + * -1), or 0, or in the range 0x0001 to 0x00ff (for what + * was previously +1 to +255). + */d = (uint16_t) ((int) *c1 - (int) *c2); + + /* + * If the low 8 bits of r were previously 0, then m + * is now 0xffff, so (d & m) is the same as d, so we + * effectively copy d to r; + * Otherwise, if r was previously non-zero, then m is + * now 0, so (d & m) is zero, so leave r unchanged. + * Note that the low 8 bits of d will be zero if and + * only if d == 0, which happens when *c1 == *c2. + * The low 8 bits of r are thus zero if and only if the + * entirety of r is zero, which happens if and only if + * all bytes compared so far were equal. As soon as a + * non-zero value is stored in r, it remains unchanged + * for the remainder of the loop. + */r |= (d & m); + + /* + * Increment pointers, decrement length, and loop. + */ + ++c1; + ++c2; + --len; + } + + /* + * At this point, r is an unsigned value, which will be 0 if the + * final result should be zero, or in the range 0x0001 to 0x00ff + * (1 to 255) if the final result should be positive, or in the + * range 0xff01 to 0xffff (65281 to 65535) if the final result + * should be negative. + * + * We want to convert the unsigned values in the range 0xff01 + * to 0xffff to signed values in the range -255 to -1, while + * converting the other unsigned values to equivalent signed + * values (0, or +1 to +255). + * + * On a machine with two's complement arithmetic, simply copying + * the underlying bits (with sign extension if int is wider than + * 16 bits) would do the job, so something like this might work: + * + * return (int16_t)r; + * + * However, that invokes implementation-defined behaviour, + * because values larger than 32767 can't fit in a signed 16-bit + * integer without overflow. + * + * To avoid any implementation-defined behaviour, we go through + * these contortions: + * + * a. Calculate ((uint32_t)r + 0x8000). The cast to uint32_t + * it to prevent problems on platforms where int is narrower + * than 32 bits. If int is a larger than 32-bits, then the + * usual arithmetic conversions cause this addition to be + * done in unsigned int arithmetic. If int is 32 bits + * or narrower, then this addition is done in uint32_t + * arithmetic. In either case, no overflow or wraparound + * occurs, and the result from this step has a value that + * will be one of 0x00008000 (32768), or in the range + * 0x00008001 to 0x000080ff (32769 to 33023), or in the range + * 0x00017f01 to 0x00017fff (98049 to 98303). + * + * b. Cast the result from (a) to uint16_t. This effectively + * discards the high bits of the result, in a way that is + * well defined by the C language. The result from this step + * will be of type uint16_t, and its value will be one of + * 0x8000 (32768), or in the range 0x8001 to 0x80ff (32769 to + * 33023), or in the range 0x7f01 to 0x7fff (32513 to + * 32767). + * + * c. Cast the result from (b) to int32_t. We use int32_t + * instead of int because we need a type that's strictly + * larger than 16 bits, and the C standard allows + * implementations where int is only 16 bits. The result + * from this step will be of type int32_t, and its value wll + * be one of 0x00008000 (32768), or in the range 0x00008001 + * to 0x000080ff (32769 to 33023), or in the range 0x00007f01 + * to 0x00007fff (32513 to 32767). + * + * d. Take the result from (c) and subtract 0x8000 (32768) using + * signed int32_t arithmetic. The result from this step will + * be of type int32_t and the value will be one of + * 0x00000000 (0), or in the range 0x00000001 to 0x000000ff + * (+1 to +255), or in the range 0xffffff01 to 0xffffffff + * (-255 to -1). + * + * e. Cast the result from (d) to int. This does nothing + * interesting, except to make explicit what would have been + * implicit in the return statement. The final result is an + * int in the range -255 to +255. + * + * Unfortunately, compilers don't seem to be good at figuring + * out that most of this can be optimised away by careful choice + * of register width and sign extension. + * + */return (/*e*/ int) (/*d*/ + (/*c*/ int32_t) (/*b*/ uint16_t) (/*a*/ (uint32_t) r + 0x8000) + - 0x8000); +} -- 2.25.1