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

[David McGrew <[e-mail]>]

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.   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.)

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.

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).)

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.

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.

If you have more questions about what Kevin did and why, please direct 
them to him.

regards,

David