[tor-dev] memcmp() & co. timing info disclosures?

[Marsh Ray]

On 05/06/2011 08:00 PM, Nick Mathewson wrote:
> .  The particular case that you mention is (I think) safe (see
> discussion there),

I figured it probably was, but illustrated some red flags.

> but the problem in general is worrisome and we
> should indeed replace (nearly) all of our memcmps with
> data-independent variants.

Maybe some of the str*cmps too? I grep 681 of them.

We should also look for other cases where any data or padding might be 
checked, decompressed, or otherwise operated on without being as obvious 
as calling memcmp. Lots of error conditions can disclose timing information.

> (Pedantic nit-pick: we should be saying "data-independent," not
> "constant-time."  We want a memcmp(a,b,c) that takes the same number
> of cycles for a given value of c no matter what a and b are.  That's
> data-independence.  A constant-time version would be one that took the
> same number of cycles no matter what c is.)

That's a good point. In most of the code I glanced at, the length was 
fixed at compile-time. I suppose a proper "constant-time" function would 
have to take as much time as a 2GB comparison (on 32) :-).

> int mem_neq(const void *m1, const void *m2, size_t n)
> {
>   const uint8_t *b1 = m1, *b2 = m2;
>   uint8_t diff = 0;
>   while (n--)
>     diff |= *b1++ ^ *b2++;
>   return diff != 0;
> }
> #define mem_eq(m1, m2, n) (!mem_neq((m1), (m2),(n)))

Looks good to me.

What if n is 0? Is 'equals' or 'neq' a more conservative default ?

Would it make sense to die in a well-defined way if m1 or m2 is NULL?

Also, if the MSB of n is set it's an invalid condition, the kind that 
could result from a conversion from a signed value.

- Marsh