[Cfrg] Constant-time implementations

["D. J. Bernstein" <[e-mail]>]

Parkinson, Sean writes:
> Also, I am concerned that, while some curves are being implemented to
> be constant time, not all curves are being implemented to be cache
> attack resistant.

When I say "constant time", I don't merely mean making the _total_ time
constant: I mean systematically avoiding all data flow from secrets to
the CPU's instruction timing, providing full immunity to cache-timing
attacks, branch-prediction attacks, etc.

On typical CPUs this means avoiding all data flow from secrets to branch
conditions, load addresses, and store addresses. On some CPUs there are
other timing leaks: for example, if there are early-abort multipliers,
then for me "constant time" says, for each multiplication instruction in
the code, that the abort condition is independent of secret data.

Unfortunately, I've often seen "constant time" used for code that
doesn't even try to meet the same requirements, or that tries and fails:

   * OpenSSL added "constant-time" code where there was no dependence on
     secret data in the choice of _cache lines_ being accessed. However,
     https://cryptojedi.org/peter/data/chesrump-20130822.pdf showed that
     this strategy actually produces variable timings and is thus
     inadequate to guarantee protection against cache-timing attacks.

   * Section 1.2 of http://cr.yp.to/hecdh/kummer-20140218.pdf gives two
     examples of DH implementations that were incorrectly claimed to
     take constant time.

I _think_ that all of the CFRG curve proposers are imposing the same
stringent requirements upon their speed reports that I impose upon mine.
For example, Microsoft says that one "should" avoid "leaking access
patterns" and should write "code which does not contain branches
depending on secret data". However, I haven't seen a clear statement of
exactly what protections _are_ actually provided by Microsoft's ECCLib.
Everything that ECCLib says---"regular, constant-time execution" and
"full protection against timing and cache attacks" and "no correlation
between timing and secret data"---is something that could just as easily
have been said about the broken OpenSSL code mentioned above. It would
be helpful for Microsoft to clarify the situation.

I don't mean to suggest that there's a huge performance difference
between constant-time ECC and non-constant-time ECC---usually the gap is
below 20%. I do mean to suggest that getting things right takes work.
What really bugs me about the NIST curves (and the Brainpool curves and
to a smaller extent Microsoft's curves) isn't their slowness but rather
their excessive complexity, leading to security problems:

   http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf

We know how to eliminate many of these problems by choosing our
cryptographic systems more carefully.

---Dan