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

[Ian Jackson]

Mark Wooding writes ("Re: [PATCH 01/25] memcmp: Introduce and use consttime_memcmp"):
> 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.

Good point.

> 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).

Hmm.

> 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;
> 	}

I can see an clever compiler spotting this.  I will think about this
some more.

Ian.