Re: [Cfrg] Comments on side channel draft

[Manuel Pégourié-Gonnard <[e-mail]>]

Hi Watson,

On 06/01/2014 22:03, Watson Ladd wrote:
> http://datatracker.ietf.org/doc/draft-ladd-sidechannel/
> 
A few comments:

1. Concerning the attack model:

   In certain scenarios the power generated by individual operations can
   be effectively measured. This is a very difficult setting to work in,
   and will not be considered further in this document. But if someone
   leaves a multimeter in your machine room, watch out!

I think the draft might mention that sometimes (smartcards, etc.) the
attacker may also be able to inject faults at specific times, which is
also a very difficult setting to work in, and will not be considered
further in this document. For example, the counter-measure you mention
later:

           Alternatively one uses a standard radix-k multiplication, but
   to load an entry from the table one reads through the entire table,
   using the following conditional load code:

      c=c*bit+a*(1-bit)

   or some varation thereof.

is susceptible to a fault attack: if the attacker causes a corruption
when we're reading one entry, the result of the operation will be
incorrect if and only if it was the entry we're actually using, which
reveals bits of the exponents. Of course, in most circumstances the
attackers doesn't have this level of physical access, so this
counter-measure is indeed useful as it protects against attacks that
require a lesser level of access.

2. Concerning modular inverses:

                                      Modular inverses should always be
   computed through exponentiation: if this is not possible the binary
   Euclidean algorithm should be run for a constant number of steps,
   calculated as the number for the worst case. (For reference, the
   worst case is two consecutive Fibonacci numbers)

Do you mean to imply that blinding isn't an option here? I may be
mistaken, but I think the following should be OK for computing x^{-1}
mod n:

    r = random(1.. n-1);
    xb = x * r;
    xib = inv_mov(xb, n); // using non-constant time Euclidean algorithm
    xi = xib * r;

(Well, that's assuming n is prime. Otherwise the first line should be
replaced with "pick r uniformly at random in (Z/nZ)*" obviously.) This
is particularly convenient if x happens to be already randomized.

3. Concerning ladders, it might seem obvious, but it is probably useful
to mention explicitly that the number of iterations must be fixed
(that is, it must not depend on the most significant bit of the scalar).

4. A totally minor point:

                             Freely usable implementations taking these
   precautions exist for P224, P256, Curve25519, Curve3617, and some
   GLS/GLV curves with endomorphisms.

I didn't look at it very closely, but it seems to me that the 64-bits
implementation of P521 in Openssl (crypto/ec/ecp_nistp521.c) qualifies
too.

5. A more general question: I wonder if it could be appropriate to add,
in an appendix, examples of real code in C and/or other languages for
a reliable constant-time way to implement some common operations, as it
is not always clear what is constant-time.

For example, see the discussion in section 4 of this blog article [1].
The author basically argues that C code such as 'a = (b == c);' hides a
branch. According to my experiments, this is not true with recent
compilers for the x86 plaftorm (they will use the SETcc instruction
rather than a conditional jump, probably because conditional jumps are
bad for performance, but in this case it happens to be good for us).

[1]: http://rdist.root.org/2010/01/07/timing-independent-array-comparison/

I did not test (yet) on other platforms and/or with other compilers, so it
might indeed be true that 'a = (b == c);' hides a branch on some
platforms with some compilers. It would be great for developpers to have
a central, reliable source of information about such things, rather than
having to test themselves, and maybe an appendix in this draft could be
a good place for that.

Manuel.