Re: [Cfrg] changes to hunt-and-peck algorithm (Re: Requesting removal of CFRG co-chair)

[Trevor Perrin <[e-mail]>]

On Fri, Jan 3, 2014 at 2:26 PM, David McGrew <[e-mail]> wrote:
> Hi Trevor,
>
> On 12/27/2013 10:56 AM, Trevor Perrin wrote:
>>
>>
>> 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 compared version 00 against version 01 using the IETF diff tool:
>
> http://www.ietf.org/rfcdiff?url1=draft-irtf-cfrg-dragonfly-00&difftype=--html&submit=Go!&url2=draft-irtf-cfrg-dragonfly-01
>
> The only change in the algorithm that you cite (Sections 3.2.1 and 3.2.2.)
> is the change in the conditional statement that you mention.
>
> If  the condition "((x^3 + ax + b) is a quadratic residue mod p)" is checked
> using an efficient method such as the legendre/jacobi symbol, which takes
> significantly less time than the execution of the branch "y = sqrt(x^3 + ax
> + b)", then the number of times that the branch executes will be detectable
> to an attacker.   This will give an attacker information about the password.

You're understating the problem:  a timing-attack risk exists in
draft-01 3.2.1 if the computation performed for quadratic residues
take a different amount of time than the computation for non-residues,
or quadratic residuosity testing takes variable time based on its
input.

Even a small timing difference might be exploitable via statistical
tests (it's not necessary that the timing difference be obvious in a
single run of the protocol).

It's also not necessary for quadratic residuosity testing to take
"significantly less time" than square-root finding.


> So in this case, I agree, versions 01 and 02 seem more vulnerable than
> version 00 to timing attacks.
>
> But an alternative way to implement the algorithm would be to use Shanks
> method for computing square roots mod p, or an algorithm like it, which upon
> termination either outputs the square root or an indication that the number
> that was input is not a quadratic residue.   In this case, version 01 could
> be less vulnerable to timing attacks than version 00.   (I would guess this
> is what Dan had in mind.)

I think the Tonelli/Shanks algorithm takes variable time based on its
input, so while it might reduce the problem I doubt it eliminates it.

Also, while I haven't considered this in detail, I'd be worried the
Tonelli/Shanks algorithm would be inefficient enough for some primes
(such as P-224) that it would eliminate the speed advantage which is
the reason to use elliptic curve crypto.

Dan Bernstein has a paper on square-root algorithms that might be relevant here:

http://cr.yp.to/papers/sqroot.pdf


> Clearly, this algorithm is not specified well enough in the draft to ensure
> that it will be implemented in a way that resists timing attacks.
> Additionally, the most efficient way to implement the algorithm in the draft
> (using the legendre symbol) would lead to vulnerabilities.   These are
> significant problems.
>
> On the subject of Kevin's influence, here is the timeline:
>
> Dec 13 2012.   Kevin summarizes the Dragonfly status, asks for input, and is
> the first person to describe the need for Dragonfly to resist timing
> attacks.   He proposed a solution.   Scott Fluhrer pointed out a problem
> with the proposal, and suggests instead the "40 loop" fix.

Kevin was not the first person to observe that.  It was observed by
the IPsec WG and TLS WG.

IPsec, 2010:
http://www.ietf.org/mail-archive/web/ipsec/current/msg06321.html

TLS, 2011:
http://www.ietf.org/mail-archive/web/tls/current/msg08182.html


> Dec 17.   Kevin again summarizes the Dragonfly status, suggests adopting
> Scott's fix, and calls for feedback.   Dan Harkins responds that
> draft-tls-pwd (a different specification of Dragonfly) already has an
> equivalent fix.
>
> Dec 18 2012.   Scott points out that the Dragonfly spec needs to be more
> clear on its use of the fix, and suggests computing the legendre/jacobi
> symbol instead of computing an actual square root.
>
> However, Scott's suggestions were not picked up in
> draft-irtf-cfrg-dragonfly.   In retrospect, it seems that Dan did not
> understand the points that Scott was trying to make, and there was no follow
> up from anyone in the RG to make sure that the changes had been done, quite
> possibly because people assumed that the fix actually was equivalent.
> Scott has clarified on the list recently, with the essential point being
> that the square root computation can be moved outside of the while loop.
> (As a side note: it would simplify this computation if p = 3 (mod 4).)

Scott also recently suggested blinding the Legendre symbol
calculation, which is a clever idea that was not proposed earlier.


> I suspect that Dan is assuming that something like Shank's method will be
> used.   Your analysis assumes that the Legendre/Jacobi symbol will be used.
> Note, however, that the suggestion to use that computational method came
> after Kevin's suggestion to use the "40 loop" fix.

Avoiding the Legendre/Jacobi symbol calculation would have a
significant performance impact, and would not, by itself, necessarily
fix the problem.


> Having participated in some of the off list conversations about Dragonfly,
> and having recently reviewed the discussions on the mail list, it seems to
> me that Kevin's input was an effort to promote positive changes, review, and
> discussion, and not an attempt to subvert the protocol.    I note that Kevin
> was the first to point out that resisting timing attacks was a goal, and he
> called for review repeatedly.   If he had wanted to influence the protocol
> without arousing suspicion, a far more effective way to have done that would
> have been to send private emails to Dan asking for changes to the draft.

I doubt the Dec 2012 discussion was Kevin trying to plant a backdoor
in the protocol.  I do think his analysis there was sloppy and
unserious.


Trevor