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

["Dan Harkins" <[e-mail]>]

  Scott,

  Thank you for this very constructive comment. I appreciate the
suggestion on improving the draft. I will look at it closely. Your
help is most appreciated.

  regards,

  Dan.

On Fri, January 3, 2014 9:01 am, Scott Fluhrer (sfluhrer) 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).
>
> 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?'
>
>
>
> For the record, a better implementation of my suggestion in dragonfly
> would be:
>
>        found = 0
>        counter = 1
>        n = len(p) + 64
>        do {
>          base = H(max(Alice,Bob) | min(Alice,Bob) | password | counter)
>          temp = KDF-n(seed, "Dragonfly Hunting And Pecking")
>          seed = (temp mod (p - 1)) + 1
>          if (seed < p)
>          then
>            x = seed
>            if ( (x^3 + ax + b) is a quadratic residue mod p)
>            then
>              found_x = x
>              found = 1
>            fi
>        } while((found == 0) || (counter < k))
>
>        x = found_x
>        y = sqrt(x^3 + ax + b)
>        if (lsb(y) == lsb(base))
>        then
>          PE = (x,y)
>        else
>          PE = (x,p-y)
>        fi
>
> (this stops on the last acceptable 'x' value found; you could try to
> select the 'middle-value'; I picked the last because it was the easiest to
> specify).
>
> As for determining if a value is a QR, the easiest way to do it without
> leaking any information in the time taken would be to blind the value
> randomly, as in:
>
>     temp = (x^3 + ax + b mod p)
>     r = 1 + random(p-2)      /* Random value between 1 and p-1) */
>     temp = (temp * r * r) mod p
>     if random(2)                   /* 0.5 chance */
>         temp =  (temp * qr) mod p
>         bit = 0
>     else
>         temp =  (temp *qnr) mod p
>         bit = 1
>     fi
>     /* At this point, temp takes on all values between 1 and p-1 with
> equal probability */
>     output = bit ^ legendre_symbol(temp, p)
>
> where qr, qnr are fixed values which are respectively a quadric residue,
> and quadratic nonresidue mod p, and are the same size (and so the
> multiplications take the same amount of time).
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>