Re: [PATCH] crypto_memcmp: add constant-time memcmp

[Daniel Borkmann <dborkman@redhat.com>]

On 09/11/2013 07:20 PM, James Yonan wrote:
> On 10/09/2013 12:57, Daniel Borkmann wrote:
>> There was a similar patch posted some time ago [1] on lkml, where
>> Florian (CC) made a good point in [2] that future compiler optimizations
>> could short circuit on this. This issue should probably be addressed in
>> such a patch here as well.
>>
>>  [1] https://lkml.org/lkml/2013/2/10/131
>>  [2] https://lkml.org/lkml/2013/2/11/381
>
> On 11/09/2013 06:19, Marcelo Cerri wrote:
>> The discussion that Daniel pointed out has another interesting point
>> regarding the function name. I don't think it's a good idea to name it
>> crypto_memcpy since it doesn't have behavior the same way as strcmp.
>>
>> Florian suggested in the thread names such crypto_mem_equal, which I
>> think fits better here.
>
> Ok, here's another stab at this:
>
> * Changed the name to crypto_mem_not_equal.  The "not_equal" seems to
> make more sense because the function returns a nonzero "true" value if
> the memory regions are not equal.

Ok, sounds good.

> * Good point that a smart optimizer might add instructions to
> short-circuit the loop if all bits in ret have been set.  One way to
> deal with this is to disable optimizations that might increase code
> size, since a short-circuit optimization in this case would require
> adding instructions.
>
>     #pragma GCC optimize ("Os")
>
> The nice thing about using #pragma is that older versions of gcc that
> don't recognize it will simply ignore it, and we can probably presume
> that older versions of gcc do not support a short-circuit optimization
> if the latest one does not.  I did a quick test using gcc 3.4.6 at -O2,
> and did not see any evidence of a short-circuit optimization.
>
> * Improved performance when CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS is
> enabled.  This makes the performance roughly on-par with memcmp.

Hm, why don't we take fixed-size versions of Daniel J Bernstein from NaCl
library [1], e.g. for comparing hashes?

E.g. for 16 bytes:

int crypto_verify(const unsigned char *x,const unsigned char *y)
{
   unsigned int differentbits = 0;
#define F(i) differentbits |= x[i] ^ y[i];
   F(0)
   F(1)
   F(2)
   F(3)
   F(4)
   F(5)
   F(6)
   F(7)
   F(8)
   F(9)
   F(10)
   F(11)
   F(12)
   F(13)
   F(14)
   F(15)
   return (1 & ((differentbits - 1) >> 8)) - 1;
}

It will return 0 if x[0], x[1], ..., x[15] are the same as y[0], y[1], ..., y[15],
otherwise it returns -1. That's w/o for loops, so probably more "compiler-proof" ...

   [1] http://nacl.cr.yp.to/

> ----------------
>
> #pragma GCC optimize ("Os")
>
> noinline unsigned long crypto_mem_not_equal(const void *a, const void *b, size_t size)
> {
>      unsigned long ret = 0;
>
> #ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS
> #if BITS_PER_LONG == 64
>      while (size >= 8) {
>          ret |= *(unsigned long *)a ^ *(unsigned long *)b;
>          a += 8;
>          b += 8;
>          size -= 8;
>      }
>      if (!size)
>          return ret;
> #endif /* BITS_PER_LONG == 64 */
>      if (sizeof(unsigned int) == 4) {
>          while (size >= 4) {
>              ret |= *(unsigned int *)a ^ *(unsigned int *)b;
>              a += 4;
>              b += 4;
>              size -= 4;
>          }
>          if (!size)
>              return ret;
>      }
> #endif /* CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */
>      while (size > 0) {
>          ret |= *(unsigned char *)a ^ *(unsigned char *)b;
>          a += 1;
>          b += 1;
>          size -= 1;
>      }
>      return ret;
> }
>
> James