Re: [Cfrg] 40 bit loop and DragonFly

[Watson Ladd <[e-mail]>]

On Mon, Jan 6, 2014 at 8:46 AM, Igoe, Kevin M. <[e-mail]> wrote:
> For the record, some observations:
>
> 1) We will often need to try more than one x until we find
> one where f = x**3+a*x*b is a quadratic residue mod p (probability
> (1/2)**k that it takes k tries).  Requiring that we always pass
> through the loop
>      { update x;
>        calculate f;
>       check if f is a quadratic residue; }
> a fixed number of times (I suggested 40) masks how many steps
> were actually need to find an x for which f is a QR.
>
> 2) Since computing a Jacobi symbol is faster than exponentiation,
> I like your idea of blinded calculation of the Jacobi symbol.
> to see whether or not a given f is a QR. It's nice that the client
> and server can use independent blinding factors and still arrive
> at the same result.
>
> 3) When 2^k | p-1 for k>1, some square root calculations are
> faster than others, but taking the square root of the blinded
> f should mask that just fine.
>
> 4) That just leaves multiplying sqrt((r**2)*f ) = r*sqrt(f)
> by (1/r) => need to calculate 1/r, which can be done either
> by an exponentiation or by the extended Euclidean algorithm.
> Since the extended Euclidean algorithm is variable time, it
> might leak information about r, so exponentiating by p-2 is
> the safer alternative.  Fortunately, this only has to be done
> once, not "40" times.
>
> ------------------------------------------------------------
>
> I believe there aren't any insurmountable issues associated
> with DragonFly, but that doesn't mean Dan and the RG don't
> have some work to do.

What about that 2^{-40} failure probability? Why aren't we using
Elligator to fix it?

I still haven't found a formal security claim that is true about Dragonfly.

There also are possible issues over F_{p}^{\times}: in particular
multitarget variations
of index-calculus get an improvement. This needs to be analyzed, and I
really don't feel
like doing it, because we have J-PAKE.

Why are we still trying to fix Dragonfly? We've got alternatives that
don't have the
significant theoretical issues, don't have the implementation issues,
don't have the IPR issues
(pith and marrow makes me think Dragonfly is covered by SPEKE patent),
and have been
vetted far more extensively.

Sincerely,
Watson Ladd

>
>
>> -----Original Message-----
>> From: Scott Fluhrer (sfluhrer) [mailto:[e-mail]]
>> Sent: Sunday, January 05, 2014 3:36 PM
>> To: Igoe, Kevin M.; '[e-mail]'
>> Subject: RE: 40 bit loop and DragonFly
>>
>>
>>
>> > -----Original Message-----
>> > From: Cfrg [mailto:[e-mail]] On Behalf Of Igoe, Kevin M.
>> > Sent: Saturday, January 04, 2014 8:41 PM
>> > To: '[e-mail]'
>> > Subject: [Cfrg] 40 bit loop and DragonFly
>> >
>> > Scott Fluhrer wrote:
>> >
>> > 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?'
>> > ---------------------------------
>> >
>> > Actually I had something more like the process outlined below in
>> mind.
>>
>> Both your procedure and mine look good.
>>
>> The only thing (and I think we ought to be explicit about it) is that
>> the various operations need to run in constant time; we need to
>> explicitly state that the modular additions and multiplications need to
>> be run in time independent of the values being added and multiplied.
>> The only exception in either of our proposals is the Legendre symbol
>> computation, and that's true IF you are using blinding like I
>> suggested; that's safe because the time it takes is not correlated with
>> any value we need to keep secret.
>>
>> This might be fairly obvious; however I don't know if we want to omit
>> obvious precautions.
>>
>> >
>> > First an elementary (and somewhat obscure)fact:
>> >
>> >   For any prime p = 3 mod 4 and any non-zero f in Z/p, let
>> >             r = f**((p+1)/4).
>> >   If f is a quadratic residue mod p (i.e. has a square root mod p),
>> >   then r**2 = f, otherwise r**2 = -f.
>> >
>> > (This is easy to see since
>> >              r**2 = f**((p+1)/2) mod p
>> >                   = f * f**((p-1)/2) mod p and f**((p-1)/2) = 1 mod p
>> > if f has a square root mod p and is
>> > -1 otherwise).
>> >
>> > Aside from cases of vanishingly small probability (e.g f = 0, 1 or
>> > -1), the time to do this exponentiation  depends upon two publicly
>> > known values, the modulus p and the exponent ((p+1)/4), and not upon
>> > the secret values x and f.  I'd advise using Montgomery arithmetic as
>> > this is a very efficient and methodical technique for doing mod p
>> arithmetic.
>> >
>> > So what had I envisioned is something like this (in pythonese):
>> >
>> > Bad = []
>> > Good = []
>> > for t in range(40):
>> >     x  = one_way_update(x)
>> >     f  = x**3 + a*x + b mod p
>> >     r  = f**((p+1)/4)
>> >     f1 = r**2
>> >     if f1 == f:
>> >         Good.append( (x,r) )
>> >     else:
>> >         Bad.append( (x,r) )
>> >
>> > if len(Good) == 0:
>> >     raise ValueError
>> > else:
>> >     return Good[0]
>> >
>> >
>> > Observations:
>> >  - This should be consant in time and memory usage.
>> >  - Prob of hitting the error condition is 2**-40 ~= 10**-12.
>> >  - The 40 could be increased if the RG deems that to be prudent.
>> >
>> >
>> > Potential IPR issues:
>> > Certicom has granted permission to the IETF to use the NIST curves,
>> > and at least two of these, P256 and P384, have p = 3 mod 4.  Not
>> being
>> > a patent lawyer, I have no idea what impact the Certicom patents have
>> > on the use of newer families of curves, such as Edwards curves.
>> > RFC 6090 outlines elliptic curve technology which predates the
>> > Certicom patents.
>> > _______________________________________________
>> > Cfrg mailing list
>> > [e-mail]
>> > http://www.irtf.org/mailman/listinfo/cfrg
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin