Re: [Cfrg] 40 bit loop and DragonFly

["Igoe, Kevin M." <[e-mail]>]

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.  


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