Re: [Cfrg] Requesting removal of CFRG co-chair

[Trevor Perrin <[e-mail]>]

On Fri, Jan 3, 2014 at 9:01 AM, Scott Fluhrer (sfluhrer)
<[e-mail]> wrote:
>
>
>> -----Original Message-----
>> From: Cfrg [mailto:[e-mail]] On Behalf Of Trevor Perrin
>> Sent: Friday, December 27, 2013 10:57 AM
>> To: David McGrew (mcgrew)
>> Cc: [e-mail]; [e-mail]
>> Subject: Re: [Cfrg] Requesting removal of CFRG co-chair
>>
>>
>> I'm still not sure what you're asking.  Let's just look at a crude
>> analysis of the "40-loops" countermeasure Kevin endorsed, comparing
>> CFRG draft-00 vs draft-01/draft-02.
>>
>> Let's assume that modular square roots are calculated via modular
>> exponentiation, and that Legendre symbol calculations take less time.
>> Let's also ignore the variable time taken by a Legendre symbol
>> calculation and other conditional logic, and just count the number of
>> ops.
>>
>> In draft-00, the hunt-and-peck loop in 3.2.1 performs Legendre symbol
>> calculations until it finds a square (probability ~1/2), at which
>> point a square root is performed.  So:
>>  - 1 modular exponentiation
>>  - Variable number of Legendre symbol calculations
>>    - geometric distribution with mean ~2, variance ~2
>>
>> In draft-01 and draft-02, the hunt-and-peck loop continues until it
>> completes 40 loops, with a probability ~1/2 of performing a modular
>> exponentiation on each iteration.  So:
>>  - Variable number of modular exponentiations
>>    - binomial distribution with mean ~20, variance ~10
>>  - 40 Legendre symbol calculations
>>
>> The 40-loops algorithm was intended to reduce timing variance but
>> instead increases it, and increases computation cost as well.  So I
>> think "ineffective" is a fair description.  Do you agree?
>
> I think we agree that what Dan specified in the draft is broken.  However, I believe that's because Dan got it wrong (and I was busy elsewhere, and did not review the draft).

Hi Scott,

In 2012 I can imagine you were thinking of something like your below
pseudocode.  However, Dan seems to have understood your 2012 messages
as saying that simply performing 40 loops of the draft-00 algorithm
was a sufficient timing-attack countermeasure.  I don't think we can
blame Dan entirely for that - your messages weren't as clear and
detailed as your current pseudocode.

In any case, I think everyone now agrees Dan's understanding, embodied
in CFRG drafts 01 and 02, is incorrect.  Work still needs to be done
to ensure individual loop iterations don't leak secret info.


> I believe my suggestion is an improvement (but still needs caution; the checking if x^3+ax+b is a QR must be done in constant time, or in random time via blinding; I believe that in this case blinding is easier).
>
> Now, I believe the issue is 'did Kevin endorse my suggestion, or did he endorse Dan's implementation?'

Kevin seems to have shared Dan's understanding.  Or at least: he
considered the issue resolved in drafts 01 and 02, and made no effort
to look more deeply into the timing question.


Scott's proposals:
http://www.ietf.org/mail-archive/web/cfrg/current/msg03260.html
http://www.ietf.org/mail-archive/web/cfrg/current/msg03265.html

Dan and Kevin's reception:
http://www.ietf.org/mail-archive/web/cfrg/current/msg03262.html
http://www.ietf.org/mail-archive/web/cfrg/current/msg03263.html
http://www.ietf.org/mail-archive/web/cfrg/current/msg03264.html


Kevin's endorsement of draft-01 and draft-02:

"The design looks mature, it addresses a real need, and no one has
raised any issues."
http://www.ietf.org/mail-archive/web/cfrg/current/msg03383.html

"Kevin reports to TLS WG chairs that CFRG did not find any problems
with Dragonfly."
http://www.ietf.org/mail-archive/web/cfrg/current/msg03707.html


Trevor