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

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

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