+1! I am one of those lurkers trying to grasp. Thank you Trevor!
On Mon, Nov 7, 2016 at 5:16 AM, Ron Garret <[email protected]> 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 <[email protected]> wrote: > > > On Thu, Nov 3, 2016 at 7:01 PM, Andy Isaacson <[email protected]> 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 > [email protected] > https://moderncrypto.org/mailman/listinfo/curves >
_______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
