[PATCH 01/25] memcmp: Introduce and use consttime_memcmp

[Mark Wooding]

Ian Jackson <ijackson at chiark.greenend.org.uk> wrote:

> +int consttime_memcmp(const void *s1in, const void *s2in, size_t n)
> +{
[...]
> +    return !!accumulator;
> +}

I think this function is named misleadingly.  In particular, its return
value merely tells you whether the two regions are unequal, and not
their relative ordering.  I'd call it something like `consttime_memneq'.
Or change the sense of the output and call it `consttime_memeq', which
is (more like) what I actually did.

The `!!accumulator' is safe for the uses here, since the non-constant-
time boolean canonification is done after the critical decision point,
but it means that this function won't compose with other constant-time
operations in a constant-time way (e.g., as is necessary when doing OAEP
decoding).

For example:

	int consttime_bool_canon(unsigned x)
	{
	  assert(CHAR_BIT * sizeof(unsigned) <= 128);
	  x |= x >> 8 >> 8 >> 8 >> 8 >> 8 >> 8 >> 8 >> 8;
	  x |= x >> 8 >> 8 >> 8 >> 8;
	  x |= x >> 8 >> 8;
	  x |= x >> 8;
	  x |= x >> 4;
	  x |= x >> 2;
	  x |= x >> 1;			/* bottom bit now set if any */
	  x &= 1u;			/* now either 0 or 1 */
	  return x;
	}

-- [mdw]