Subject: [Cfrg] Comments on side channel draft

From: Watson Ladd <[email-masked]>
Date: Mon, 6 Jan 2014 13:03:15 -0800

What I would like is some rather compelling references. I wrote this
on a plane ride, so it probably has typos galore.

http://datatracker.ietf.org/doc/draft-ladd-sidechannel/

Sincerely,
Watson Ladd

---

From: David McGrew <[email-masked]>
Date: Mon, 06 Jan 2014 16:36:49 -0500

Hi Watson,

> http://datatracker.ietf.org/doc/draft-ladd-sidechannel/

thanks for starting this work!   I will send you some comments and 
references offline.

David

> Sincerely,
> Watson Ladd
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Tue, 07 Jan 2014 14:07:11 +0100

Hi Watson,

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

---

From: Watson Ladd <[email-masked]>
Date: Tue, 7 Jan 2014 16:21:39 -0800

On Tue, Jan 7, 2014 at 2:41 PM, Manuel Pégourié-Gonnard <[email-masked]> 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 <[email-masked]>
> To: Watson Ladd <[email-masked]>, "[email-masked]" <[email-masked]>
>
> Hi Watson,
>

Good idea!

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

> (that is, it must not depend on the most significant bit of the scalar).

Another good point.
> implementation of P521 in Openssl (crypto/ec/ecp_nistp521.c) qualifies

Thanks for the pointer.

> having to test themselves, and maybe an appendix in this draft could be

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

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

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Wed, 08 Jan 2014 18:34:09 +0100

> no timing sidechannels by definition.
Maybe the draft should go into more details about he possible shortcomings of
blinding then.

I feel like, for existing implementations, it's often easier to add blinding at
some well-chosen places than to rewrite their whole arithmetic from scratch to
be constant-time. So, used properly, it can be an interesting way to gradually
enhance the resistance of existing implementations.

> The problem is that one really cannot tell what does and does not contain
> jumps without looking at the assembler output.

Agreed. However, there seems to be ways to code things that are commonly
accepted as producing no hidden branches on common platforms with common compilers.

> Mix in the different compilers, architectures, and compiler options, and
> this is far, far too much work for me to reasonably do.
> 
Sure, but by the same reasoning it's too much work for any implementer wanting
to write portable code (so that assembly isn't an option). IMO this is precisely
in such situations that it is useful to share the collective knowledge of the
CFRG in a document that can then be relied upon by others, even if it's not
exhaustive.

If providing reliable solutions is too hard, then at least the draft could warn
about constructs that may look constant-time but are actually not of some common
platforms. Examples could include integer division (see below), and the "hidden
branch in 'c = (a == b)'" issue if it's still an issue with common compilers on
common platforms.

> Even integer division is not constant time on some CPU families.
Well, it's not just some exotic CPUs, it includes common Intel, AMD, ARM and Via
CPUs at least, according to [1] (which focuses on floating point but also tests
integer operation).

[1]: https://wiki.mozilla.org/User:Bjacob/ArithmeticTimingDifferences

Manuel.