[curves] Climbing the elliptic learning curve (was: Re: Finalizing XEdDSA)

[Sigurd Hogsbro]

+1!

I am one of those lurkers trying to grasp. Thank you Trevor!

On Mon, Nov 7, 2016 at 5:16 AM, Ron Garret <ron at flownet.com> wrote:

> Wow, thanks for taking the time to write this up!  This has been more
> helpful than you can possibly imagine.
>
> I started work on an EC survey a few days ago, but as you might imagine,
> curves are quite the rabbit hole so I don’t expect to have anything ready
> to show for a few weeks at the earliest.  But I thought I would mention it
> just in case anyone else out there is thinking about diving in to this so
> we don’t duplicate efforts.
>
> On Nov 6, 2016, at 3:51 PM, Trevor Perrin <trevp at trevp.net> wrote:
>
> > On Thu, Nov 3, 2016 at 7:01 PM, Andy Isaacson <adi at hexapodia.org> wrote:
> >> As far as I can tell there's a quite remarkable
> >> pile of specialized knowledge necessary to be able to effectively work
> with
> >> elliptic curve cryptography, and this list is mostly for folks who
> already
> >> have the knowledge to discuss things.
> >
> >
> > I think it helps a lot to think of layers built on top of each other,
> > from high-level to low:
> > - Protocols (Signatures, Diffie-Hellman, MQV, etc.)
> > - Groups (where discrete log is hard)
> > - Elliptic Curves (where points form groups)
> > - Fields (the coordinates of elliptic-curve points are field
> > elements, e.g in GF(2^255-19))
> >
> >
> > Here's a (rambling) tour of a couple layers, I'll try to connect it to
> > recent discussion:
> >
> > Groups
> > -------
> > At the level of DH or signatures, elliptic curve crypto is mostly just
> > "discrete log" crypto, i.e. it deals with (cyclic) groups where
> > calculating discrete logs is hard.  Constructs like DH, DSA, etc apply
> > whether the group elements are points on an elliptic curve or integers
> > modulo some prime.
> >
> > In either case you'll have some element (elliptic curve point; or
> > integer mod prime) that generates a group with large prime order q
> > (number of elements), which is where you want to do crypto.  But this
> > group is often part of a larger group, with order = cofactor * q.
> >
> > If cofactor=1 then things are simpler, but cofactor > 1 means there's
> > other groups co-existing with the "main subgroup", and there can be
> > weird interactions.
> >
> > "Small subgroup attacks" on DH with reused keys is the classic case:
> > Someone gives you a DH public value A, you raise it to your reusable
> > DH private value b to get a shared key and encrypt something with that
> > key.
> >
> > However!  Instead of A generating the main subgroup, it was
> > maliciously chosen to generate some small-order subgroup with j
> > elements.  The attacker can trial-decrypt your encrypted data to
> > determine which of the j keys was chosen, thus learning your private
> > key b mod j.  By repeating this with different A_i of order j_i the
> > attacker can calculate b via the Chinese Remainder Theorem.
> >
> > With traditional "mod p" or "finite field" Diffie-Hellman, you can
> > choose a "safe prime" p=2q+1 to get a cofactor of 2 and a main
> > subgroup order of q.  This prevents the attack because the 2-element
> > subgroup containing (1,-1) is easy to test for, and because leaking a
> > single bit of your key (mod 2) doesn't matter much.
> >
> > For traditional Schnorr or DSA signatures you have to send a value
> > (mod q) as part of the signature, so you want a prime p = cofactor*q +
> > 1, where cofactor is large (instead of cofactor=2).  Thus, using
> > DSA-style primes for DH would introduce a risk of small-subgroup
> > attacks against re-used keys, requiring an expensive validation check
> > (exponentiation by q) to ensure received public values are in the
> > correct subgroup.
> >
> > (To make this topical:  A recent paper points out that NIST recommends
> > DSA-style primes for DH in SP800-56A [0,1].  RFC 5114 also recommends
> > specific DSA-style primes for "IKE, TLS, SSH, and SMIME", without
> > mentioning the need for validation checks [2].  The paper analyzes the
> > "fragility" of the implementation landscape that has resulted, though
> > various complications mostly seem to prevent devastating attacks, in
> > the implementations looked at.)
> >
> > So note that group structure and cofactor/subgroup questions are
> > complicated even in "regular" DH, without getting to EC.
> > With EC, cofactors are typically small enough (e.g. 1 for NIST
> > P-curves, 8 for Curve25519) that the above attack isn't that relevant,
> > though sending invalid points (not on the curve) can lead to a similar
> > attack.
> >
> > However, cofactor>1 can still have subtle and unexpected effects, e.g.
> > see security considerations about "equivalent" public keys in RFC
> > 7748, which is relevant to the cofactor multiplication "cV" in
> > VXEdDSA, or including DH public keys into "AD" in Signal's (recently
> > published) X3DH [3].
> >
> >
> > Signatures
> > -----------
> > Discrete-log signatures (El Gamal, Schnorr, DSA, EC-DSA, EdDSA) build
> > on top of the group structure, so can be considered without too much
> > EC detail.
> >
> > Academic intro to crypto books usually cover the basics well, the
> > typical reference points are:
> > * Schnorr's identification protocol
> > * Fiat-Shamir transform
> > * Security proof via Random Oracle Model and oracle rewinding
> >
> > From there, DJB has a great writeup on concrete design details [4], as
> > well as the Ed25519 and "More curves for EdDSA" papers.
> >
> > It's also worth understanding these signatures as instances of
> > "zero-knowledge proofs" which can do fancier things.  E.g. see
> > Camenisch-Stadler [5] examples 2 and 3 on "equality of two discrete
> > logarithms" (relevant to VRF), and "or" proofs (relevant to signature
> > variants like "designated verifier" signatures).
> >
> >
> > Curves
> > -------
> > This is harder math, and I'm not sure Montgomery / Edwards curves have
> > made it into good textbooks and overviews yet.  I think people lean on
> > DJB's Curve25519 and Ed25519 papers, "Twisted Edwards Curves" [6], and
> > their references.  The authors have a "gentle introduction" to EC as
> > well [7].
> >
> > I'm not the person to do it, but if anyone wants to try an overview of
> > modern curve equations / coordinate systems / algorithms, I'm sure it
> > would be widely appreciated (there's about 600 people on this list,
> > probably most here to learn things like that).
> >
> > Trevor
> >
> >
> > [0] https://eprint.iacr.org/2016/995
> > [1] http://nvlpubs.nist.gov/nistpubs/SpecialPublications/
> NIST.SP.800-56Ar2.pdf
> > [2] https://tools.ietf.org/html/rfc5114
> > [3] https://whispersystems.org/docs/specifications/x3dh/
> > [4] https://blog.cr.yp.to/20140323-ecdsa.html
> > [5] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.1208
> > [6] https://eprint.iacr.org/2008/013
> > [7] http://ecchacks.cr.yp.to/
>
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161107/43d3ba06/attachment.html>