Re: [Cfrg] Constant-time implementations

[Mike Hamburg <[e-mail]>]

On 10/14/2014 08:05 AM, Watson Ladd wrote:
> On Tue, Oct 14, 2014 at 6:49 AM, Yoav Nir <[e-mail]> wrote:
>> Doesn’t it become better (or at least safer) at some point to set a timer before beginning the operation and then not use the results until the timer expires?
>>
>> Sure this has a cost in memory, but any fool can write an implementation with an upper bound on processing time, whereas true constant time is both hard and has a 20% overhead (according to DJB’s message upthread).
>
This ends up working very poorly for many reasons, beyond (as Watson 
said) not solving your problem.  Estimating maximum time is difficult, 
especially across different platforms, and especially on a loaded system 
where you might miss cache or be descheduled.  It will probably be more 
than 20% overhead, whereas DJB's dataflow-constant-time definition 
usually has *less than* 20% overhead (from my numbers, ~6% for 
Goldilocks on Haswell).  Worse, you will need to figure out how to 
measure time, and how to sleep. That means threading libraries or 
busy-waiting, neither of which is appealing.

It is also important to recognize that timing isn't the only side 
channel.  In particular, constant-time array indexing (with logic 
operations) will be much leakier than direct lookups for a power-channel 
adversary.  So for software which runs on a PC or server, then timing- 
(, cache-, branch-) invariance is the important thing, but on an 
embedded device, power, EM and possibly fault resistance are more 
important.  This will necessitate blinding instead of constant-time 
array indexing, and usually has a much higher overhead.  As Torsten 
said, smart cards don't even use constant-time multiply.

I skimmed the ECClib code.  They seem to take efforts to avoid leaking 
data to addresses, with a masking approach to constant-time lookups.  
They use cmovc; is that constant-time?  IIRC it is at least on recent 
Intel chips.  Anyway, I think the authors clearly intended to avoid 
dataflow to addresses or branches, though a confirmation would be nice.

I agree that they should have used untwisted Edwards instead of twisted 
Edwards, but that's easy enough to fix: CFRG can just adopt the 
isogenous untwisted curves instead.  Is this what you mean by "excessive 
complexity"?  Is there another problem with those curves, that other 
curves with the same field size would not have?

For the record, since DJB seems to be calling people out on precision: 
my Ed448-Goldilocks software is designed not to let secret data flow to 
addresses, branch conditions or operations which are variable-time on 
most CPUs.  If it does, that's a bug.  However, secret data can flow to 
multiply and multiply-accumulate instructions, which are variable-time 
on some embedded CPUs. Furthermore, my code is mostly in C and so is at 
the mercy of the compiler and optimizer.  Finally, while I'm not using 
any blinded variable-time algorithms today (such as blinded EGCD), I 
consider them to be a safe and reasonable thing to do in the right 
circumstances.

Cheers,
-- Mike