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)

3 files changed, 313 insertions, 1 deletions

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)       \
   ({                              \
@@ -1099,6 +1102,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.
  *
  * @param a pointer to @a n bytes which should be tested for the
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 <stddef.h>
+#include <inttypes.h>
+
+/*
+ * "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);
+}