Re: [Cfrg] Constant-time implementations

[David Jacobson <[e-mail]>]

On 10/14/14, 2:36 AM, D. J. Bernstein wrote:
> 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
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>
Sometimes data dependent branches cannot be avoided without a serious 
performance penalty.  I'm thinking of modular inversion using the binary 
method. But it that case it is easy to use blinding.

1/k = b * (1 / (b * k))

where b is a random blinding value.

In this case, I think it is still fair consider this leakage resistant, 
even though the inversion is actually full of data dependent branches.

Of course, the time to compute b has to be included in the benchmark.  
But do those blinding values  have to be generated with heavy-weight 
schemes such as the algorithms in NIST SP 800-90A, or is it, in 
practice, safe to use something fast like the keystream from RC4?

     --David Jacobson