<div dir="ltr">+1!<div> </div><div>I am one of those lurkers trying to grasp. Thank you Trevor!</div></div><div class="gmail_extra"> <div class="gmail_quote">On Mon, Nov 7, 2016 at 5:16 AM, Ron Garret <<a href="mailto:ron@flownet.com" target="_blank">ron@flownet.com</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">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. <div class="HOEnZb"><div class="h5"> On Nov 6, 2016, at 3:51 PM, Trevor Perrin <<a href="mailto:trevp@trevp.net">trevp@trevp.net</a>> wrote: > On Thu, Nov 3, 2016 at 7:01 PM, Andy Isaacson <<a href="mailto:adi@hexapodia.org">adi@hexapodia.org</a>> 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] <a href="https://eprint.iacr.org/2016/995" rel="noreferrer" target="_blank">https://eprint.iacr.org/2016/995</a> > [1] <a href="http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf" rel="noreferrer" target="_blank">http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Ar2.pdf</a> > [2] <a href="https://tools.ietf.org/html/rfc5114" rel="noreferrer" target="_blank">https://tools.ietf.org/html/rfc5114</a> > [3] <a href="https://whispersystems.org/docs/specifications/x3dh/" rel="noreferrer" target="_blank">https://whispersystems.org/docs/specifications/x3dh/</a> > [4] <a href="https://blog.cr.yp.to/20140323-ecdsa.html" rel="noreferrer" target="_blank">https://blog.cr.yp.to/20140323-ecdsa.html</a> > [5] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.1208" rel="noreferrer" target="_blank">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.1208</a> > [6] <a href="https://eprint.iacr.org/2008/013" rel="noreferrer" target="_blank">https://eprint.iacr.org/2008/013</a> > [7] <a href="http://ecchacks.cr.yp.to/" rel="noreferrer" target="_blank">http://ecchacks.cr.yp.to/</a> _______________________________________________ Curves mailing list <a href="mailto:Curves@moderncrypto.org">Curves@moderncrypto.org</a> <a href="https://moderncrypto.org/mailman/listinfo/curves" rel="noreferrer" target="_blank">https://moderncrypto.org/mailman/listinfo/curves</a> </div></div></blockquote></div> </div>