Re: [Cfrg] Comments on side channel draft

[Watson Ladd <[e-mail]>]

On Tue, Jan 7, 2014 at 2:41 PM, Manuel Pégourié-Gonnard <[e-mail]> wrote:
> Hi,
>
> Since I received a notification from gmail that my email was rejected due to
> being considered spam, and I know mailman is sometimes configured to avoid
> sending copies of messages when people are cc'ed, I'm now re-sending this (using
> a different SMTP server) in case you didn't receive the first copy.
>
> If this is a duplicate, please ignore it.
>
> Manuel.

Sorry to everyone whose threading gets busted because of this gmail issue.

>
>
> -------- Original Message --------
> Subject: Re: [Cfrg] Comments on side channel draft
> Date: Tue, 07 Jan 2014 14:07:11 +0100
> From: Manuel Pégourié-Gonnard <[e-mail]>
> To: Watson Ladd <[e-mail]>, "[e-mail]" <[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:

Good idea!

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

Blinding is my second choice compared to constant time. The reason is
that blinding might not work perfectly, whereas circuit-like programs have
no timing sidechannels by definition.

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

Another good point.
>
> 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.

Thanks for the pointer.

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

The problem is that one really cannot tell what does and does not
contain jumps without looking
at the assembler output. Mix in the different compilers,
architectures, and compiler options, and this
is far, far too much work for me to reasonably do.

Even integer division is not constant time on some CPU families.

I'll wait two weeks for more comments, and then post an updated draft.
Sincerely,
Watson Ladd
>
> Manuel.
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>
>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin