Re: [Cfrg] 40 bit loop and DragonFly

> -----Original Message-----
> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Igoe, Kevin M.
> Sent: Saturday, January 04, 2014 8:41 PM
> To: 'cfrg@irtf.org'
> 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
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg