From: "Igoe, Kevin M." <kmigoe@nsa.gov>
To: "'Scott Fluhrer (sfluhrer)'" <sfluhrer@cisco.com>,
 "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: 40 bit loop and DragonFly
Thread-Index: Ac8Jtz8QHBqZuWIRSrC0AhG0eZjDKgAnaYVwACaLG2A=
Date: Mon, 6 Jan 2014 16:46:46 +0000
Message-ID: <3C4AAD4B5304AB44A6BA85173B4675CABA9A0B90@MSMR-GH1-UEA03.corp.nsa.gov>
References: <3C4AAD4B5304AB44A6BA85173B4675CABA99F80C@MSMR-GH1-UEA03.corp.nsa.gov>
 <A113ACFD9DF8B04F96395BDEACB340420B77D4CC@xmb-rcd-x04.cisco.com>
In-Reply-To: <A113ACFD9DF8B04F96395BDEACB340420B77D4CC@xmb-rcd-x04.cisco.com>
Accept-Language: en-US
Content-Language: en-US
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Subject: Re: [Cfrg] 40 bit loop and DragonFly
Precedence: list

For the record, some observations:

1) We will often need to try more than one x until we find=20
one where f =3D x**3+a*x*b is a quadratic residue mod p (probability=20
(1/2)**k that it takes k tries).  Requiring that we always pass=20
through the loop
     { update x;=20
       calculate f;=20
      check if f is a quadratic residue; }=20
a fixed number of times (I suggested 40) masks how many steps=20
were actually need to find an x for which f is a QR.

2) Since computing a Jacobi symbol is faster than exponentiation,=20
I like your idea of blinded calculation of the Jacobi symbol. =20
to see whether or not a given f is a QR. It's nice that the client=20
and server can use independent blinding factors and still arrive=20
at the same result.

3) When 2^k | p-1 for k>1, some square root calculations are=20
faster than others, but taking the square root of the blinded
f should mask that just fine.=20

4) That just leaves multiplying sqrt((r**2)*f ) =3D r*sqrt(f)
by (1/r) =3D> need to calculate 1/r, which can be done either=20
by an exponentiation or by the extended Euclidean algorithm.
Since the extended Euclidean algorithm is variable time, it=20
might leak information about r, so exponentiating by p-2 is=20
the safer alternative.  Fortunately, this only has to be done
once, not "40" times.

------------------------------------------------------------

I believe there aren't any insurmountable issues associated=20
with DragonFly, but that doesn't mean Dan and the RG don't=20
have some work to do. =20


> -----Original Message-----
> From: Scott Fluhrer (sfluhrer) [mailto:sfluhrer@cisco.com]
> Sent: Sunday, January 05, 2014 3:36 PM
> To: Igoe, Kevin M.; 'cfrg@irtf.org'
> Subject: RE: 40 bit loop and DragonFly
>=20
>=20
>=20
> > -----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.
>=20
> Both your procedure and mine look good.
>=20
> 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.
>=20
> This might be fairly obvious; however I don't know if we want to omit
> obvious precautions.
>=20
> >
> > First an elementary (and somewhat obscure)fact:
> >
> >   For any prime p =3D 3 mod 4 and any non-zero f in Z/p, let
> >             r =3D f**((p+1)/4).
> >   If f is a quadratic residue mod p (i.e. has a square root mod p),
> >   then r**2 =3D f, otherwise r**2 =3D -f.
> >
> > (This is easy to see since
> >              r**2 =3D f**((p+1)/2) mod p
> >                   =3D f * f**((p-1)/2) mod p and f**((p-1)/2) =3D 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 =3D 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 =3D []
> > Good =3D []
> > for t in range(40):
> >     x  =3D one_way_update(x)
> >     f  =3D x**3 + a*x + b mod p
> >     r  =3D f**((p+1)/4)
> >     f1 =3D r**2
> >     if f1 =3D=3D f:
> >         Good.append( (x,r) )
> >     else:
> >         Bad.append( (x,r) )
> >
> > if len(Good) =3D=3D 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 ~=3D 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 =3D 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