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

[Trevor Perrin]

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/