[cryptography] Implementing constant-time string comparison

Jeffrey Walton noloader at gmail.com
Thu Jun 19 05:38:32 EDT 2014


On Wed, Jun 18, 2014 at 5:18 PM, D. J. Bernstein <djb at cr.yp.to> wrote:
> ...
>> would be unable to shortcut the loop if the
>> arguments were merely declared as pointers to volatile storage
>
> The compiler would be required to access the storage but would still be
> allowed to skip the intermediate calculations. For example, it could
> convert
>
>    int result = 0;
>    int iszero;
>    for (i = 0;i < n;++i) result |= (x[i] ^ y[i]);
>    iszero = (result == 0);
>    return iszero - 1;
>
> into
>
>    int iszero = 1;
>    for (i = 0;i < n;++i) if (x[i] ^ y[i]) iszero = 0;
>    return iszero - 1;
>
> or into
>
>    int iszero = 1;
>    for (i = 0;i < n;++i) if (x[i] != y[i]) iszero = 0;
>    return iszero - 1;
>
> or into
>
>    for (i = 0;i < n;++i) if (x[i] != y[i]) goto shortcut;
>    return 0;
>    shortcut: while (++i < n) { x[i]; y[i]; }
>    return -1;
>
> without violating the C language specification. You're deluding yourself
> if you think that the guarantees made by the C specification are
> adequate for writing constant-time code.
>
> What's the chance of a compiler screwing things up in this way? This
> isn't a question of language lawyering; it's a question of what the
> compiler writer is thinking. Has the compiler writer seen examples where
> it might seem useful to replace
>
>    result = 0; result |= ...; result |= ...; result == 0
>
> with
>
>    iszero = 1; if (...) iszero = 0; if (...) iszero = 0; iszero
>
> which would then hook nicely into early exits? Sure, the early exits
> should check for volatile memory accesses in the skipped calculations,
> but this doesn't mean that the replacement has to check for volatile.
The GCC folks interpret the standard to mean volatile applies to
memory mapped from hardware. Using it in software to tame the
optimizer is an abuse. [1]

Microsoft compilers, on the other hand, interpret volatile that's
amicable to software (for example, a second thread changing the value
at a memory location). [2]

Jeff

[1] https://gcc.gnu.org/onlinedocs/gcc/Qualifiers-implementation.html
[2] http://msdn.microsoft.com/en-us/library/12a04hfd%28v=vs.100%29.aspx


More information about the cryptography mailing list