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

[Ron Garret]

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/