33 ms·

Basic Intro to Elliptic Curve Cryptography (2019)

• deleted 6y ago
  [deleted]
• loup-vaillant 6y ago
  Those who seek to go a step further and actually implement elliptic curves should see the ECC Hacks talk by djb and Tanja Lange: https://www.youtube.com/watch?v=vEt-D8xZmgE https://www.youtube.com/watch?v=vEt-D8xZmgE A couple claims there are a little outdated (we now have better ways of dealing with short Weierstraß curves), but the advice there is sound.
  • beefhash 6y ago
    > we now have better ways of dealing with short Weierstraß curves We do? The complete Renes/Costello/Batina formulas for point addition are significantly slower at a factor of 1.4.[1] The complete formulas presented by Hamburg are still somewhat slower than what you can get on twisted Edwards and almost certain to be patent encumbered by the end of the year.[2] Did I miss something? SafeCurves discounts Renes/Costello/Batina and the like because “many of these formulas are considerably slower and more complicated than standard incomplete scalar-multiplication formulas, creating major conflicts between simplicity, efficiency, and security”.[3] [1] https://cryptojedi.org/papers/complete1-20191011.pdf https://cryptojedi.org/papers/complete1-20191011.pdf [2] https://eprint.iacr.org/2020/437 https://eprint.iacr.org/2020/437 [3] https://safecurves.cr.yp.to/complete.html https://safecurves.cr.yp.to/complete.html
    • loup-vaillant 6y ago
      Correct, but my point was that even if they're slower, we do have complete formulas that aren't the nightmare djb describes. I do reckon however that having to chose between speed and safety is a big problem. Someone is bound to go the fast route and screw up some special case, or leak timing information. I didn't know about possible patents, that sucks. (I live in the EU though, so I can still give them the finger if I need to.) In any case, the best general purpose thing we have now is probably Decaf/Ristretto over (twisted) Edwards curves. Fast complete formulas and a prime order group. Dealing with the cofactor is not too hard, but it's not trivial either: http://loup-vaillant.fr/tutorials/cofactor http://loup-vaillant.fr/tutorials/cofactor (I still love Montgomery curves for variable base scalar multiplication.)
      • beefhash 6y ago
        > I didn't know about possible patents, that sucks. (I live in the EU, though, so I can still give them the finger if I need to.) Hamburg made this IP risk pretty clear in the paper, for a bit more context on it, see [1]. Because in the U.S. you have a full year before you even need to file a patent after publishing, we'll still have to wait and see if Hamburg's employer files a patent on his method. If they don't, nice; if they do, fucking hell this is why we can't have nice things. Renes/Costello/Batina is unencumbered as far as I know. [1] https://www.reddit.com/r/crypto/comments/g46pft/_/fnwp9p2/?context=3 https://www.reddit.com/r/crypto/comments/g46pft/_/fnwp9p2/?c...
  • vmception 6y ago
    What class would one take to understand this? I had a cryptography elective I wanted to take in undergrad but it was in the wrong semester.
    • loup-vaillant 6y ago
      I have no idea. I'm self taught, and I tend to limit myself to implementation techniques. My tutorials on the subjects are mostly implementation focused: http://loup-vaillant.fr/tutorials/fast-scalarmult http://loup-vaillant.fr/tutorials/fast-scalarmult http://loup-vaillant.fr/tutorials/cofactor http://loup-vaillant.fr/tutorials/cofactor http://loup-vaillant.fr/tutorials/128-bits-of-security http://loup-vaillant.fr/tutorials/128-bits-of-security (This one is more about choosing your primitive than implementing it.) If you want to get started in cryptography in general, I can recommend 2 sources: Dan Boneh's course, and crypto101 by lvh: https://www.coursera.org/learn/crypto https://www.coursera.org/learn/crypto https://www.crypto101.io/ https://www.crypto101.io/
    • beefhash 6y ago
      If you want a to get this stuff into your head reasonably fast, go implement a curve. Then do it again, but in Rust (or C) and in constant-time. Then do it again, but actually computationally efficiently (i.e. optimize the hell out of a Rust or C implementation once it works). Choose a different curve each time. Then go and cook your own curve for shits and giggles. You may easily spend a year upwards on this, but by the time you're done, you've basically run into every resource worth knowing about and are able to decently reason about elliptic curves (but by no means are in a position to write papers still).
      • tinganho 6y ago
        Basically, doing this now. I tried to implement x25519 in a highly optimized way in cpp/c and I’m in my 8 month. I dogged through countless of articles and learned a ton of abstract algebra. Though, I still feel like a beginner in this field. I’ve done a few hard projects in my career (compilers, and graphic editor). And I think implementing a elliptic curve in a optimized way, without a math library, must be one of the hardest thing in programming.
• denysvitali 6y ago
  On an unrelated note, DKIM's latest RFC includes ed25519-sha256 but nobody is actually accepting a properly signed email using this signature algorithm. Bummer
  • LeonM 6y ago
    That would be RFC8463 "A New Cryptographic Signature Method for DomainKeys Identified Mail (DKIM)" [0] The biggest improvement on using EC over RSA in DKIM is that the public key will fit in a single DNS TXT rr. The problem here is that email servers are often horribly outdated, so don't expect widespread adoption of the new RFC anytime soon. The suggested transition method would be include both a EC and RSA signature in the email, and publish both keys under separate selectors. The receiver should ignore the EC signature if it doesn't support it, and when it is supported the receiver should only use the EC signature. However, it wouldn't surprise me of this is going to be poorly implemented and you'll en up with the receiver validating both signatures, thus performing multiple DNS lookups. I'm planning on doing a write-up about support for RFC8463 in popular email services. Disclaimer: Founder of an email hardening service. [0] https://www.rfc-editor.org/rfc/rfc8463.html https://www.rfc-editor.org/rfc/rfc8463.html
    • denysvitali 6y ago
      I wanted to point out this thing because I'm in the middle of migrating my mail server and wanted to improve the whole setup by using chasquid and a set of dkim tools [1] that I've forked an improved to include ed25519-sha256. Unfortunately pretty much nobody has implemented RFC8463 yet, and my DNS provider doesn't allow me to use RSA 2048bit DKIM keys because they have a stupid limit on the TXT field value :( [1]: https://github.com/denysvitali/dkim https://github.com/denysvitali/dkim
      • LeonM 6y ago
        You shouldn't rely on only ed25519 for DKIM, always double-sign your email with RSA as a fallback The problem with email will forever be that there are so many badly configured email servers out there. Any new standard in email will always need a backwards compatibility ad infinitum. In your case I'd recommend moving your DNS to another DNS provider. Just pick any and go with that.
• anothermoron 6y ago
  I don't know much about Cryptography but this article made me want to ask this: In his example with facebook and trump, the original handshake to get facebook's public key isn't encrypted, isn't that a problem ? I may be totally not understanding this at all, but lets say when somebody connect to Tor if the original connection isn't encrypted and everybody know that I just connected to Tor isn't that bad even though they can't tell what I'm doing afterward ?
  • tialaramex 6y ago
    That example used is a bit weird and I'm not sure it really motivates the rest of the article well. Encryption can deliver a variety of desirable features, and which you need in particular occasions will vary. For example for getting Facebook's public key you would certainly care about Integrity - the key you received should be the one sent, and about Authenticity - you want to get an answer from Facebook and not the CIA or your kid sister but you may not care about Confidentiality - maybe it doesn't matter to you who knows what you asked, and as a Public key it isn't important to Facebook who knows what it is. Tor itself is not designed to ensure that people can't tell you are using Tor. Its purpose is to ensure adversaries, including an adversary who controls some Tor nodes, can't tell what information you are sending and receiving and who you are sending it to/ receiving it from. Hiding Tor usage from a sophisticated adversary is difficult, technologies such as ScrambleSuit and OBFS try to help you do this, but it can be difficult to assess how well they work unless the adversary is actively blocking you. Perhaps they know exactly what you're doing but are choosing not to intervene?
  • ozim 6y ago
    I down voted the other responder. Because Trump is using public key to encrypt the message. You can share your public key as much as you want and people will be able to send you messages that only you(owner of private key) can decrypt. There is no problem. That is normal use of public key to send encrypted messages to the owner of private key. You can do it also the other way around, encrypt data with private key and only people who have your public key will be able to decrypt it. Which is a bit less useful but it can confirm your identity. So they can be sure that you sent the message.
• sage3 6y ago
  I can't even escape US internal politics on a cryptography blog
  • JshWright 6y ago
    Yeah, maybe it's just the fact that things are particularly tense here at the moment, but the choice of example definitely adds some extra baggage that wasn't necessary. For me personally it interferes a bit with my ability to simply read and enjoy the post.
    • deleted 6y ago
      [deleted]
    • irontoby 6y ago
      Just read the original Ars Technica article he "borrowed" all the images from. It's a great article I've referred back to many times; it's better-written and still easy to understand for those not familiar w/ the concepts. The ECC-specific content begins on page 2. https://arstechnica.com/information-technology/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ https://arstechnica.com/information-technology/2013/10/a-rel...
  • julianeon 6y ago
    I don't know, I liked it for being relevant and showing a real use case. Politics is a good example because if it was like grocery stores or something, it would be easy to conclude, I guess if you're paranoid okay but that sounds like overkill for such a modest use case. Basically for 'enterprise' but not for me. In reading this I thought, yes I'm sure FaceBook wants a secure fast way to communicate with high-value users, that's a good example, and also something real-life people would want to corrupt. They could've used "Ambassador of Country A would like to send a message to Ambassador of Country B" but that would've made it seem like something only high level infosec types would care about; this made it seem topical to me. And as it happens, as a US resident, I can confirm the example wasn't sensationalized - that's something that would realistically be posted in that situation, without exaggeration or underhanded commentary.
  • 6y ago
• alecbenzer 6y ago
  I'm assuming that given a starting point A and a number of operations n, there's a much faster way of computing the end point than just iterating n times? Otherwise, determining n given A and an end point would just be a matter of iterating from A until you hit the end point and counting, right? Also, how do you actually use the keys to encrypt/decrypt?
  • lordnacho 6y ago
    > I'm assuming that given a starting point A and a number of operations n, there's a much faster way of computing the end point than just iterating n times? Yes, this is in fact the basis of the cryptographic security. There's a way to iterate the generator whatever number of times, fast. This is called multiplication, just like there's a way to multiply arithmetic numbers in school without adding over and over. The thing is it isn't quite so easy given the starting point and the result what you multiplied by.
    • alecbenzer 6y ago
      Right, but while most people understand multiplication, it doesn't seem clear how to efficiently perform repeated application of the dot operation. I'm guessing the operation is associative, which lets you do it fast.
  • neikos 6y ago
    > ould just be a matter of iterating from A until you hit the end point and counting, right? Yes, you could brute-force all the points. The good thing is, ECC is done on fields that are very large, so that actually enumerating them is not practical. Check out Curve25519[1] for some numbers. [1]: https://en.wikipedia.org/wiki/Curve25519 https://en.wikipedia.org/wiki/Curve25519
    • alecbenzer 6y ago
      Right, but the point is that doing the transformation in one direction needs to be fast in order of the scheme to be viable. So there must be some faster way of doing n iterations, which the post doesn't mention.
• opus132 6y ago
  Nigel Smart's Cryptography Made Simple is a great book which covers elliptic curve cryptography amougst many other topics; despite its name it's a very technical book, but it's easily accessible to anyone with a CS/EE/Maths/Physics degree. You can grab a copy from SpringerLink for free at the moment here: https://link.springer.com/book/10.1007%2F978-3-319-21936-3 https://link.springer.com/book/10.1007%2F978-3-319-21936-3
  • ykevinator 6y ago
    I second this m
  • thr0w__4w4y 6y ago
    Agreed. Also Christof Paar's book [1] and 25-episode YouTube series[2] do an excellent job of explaining not only elliptic curve cryptography, but also RSA and a lot of other cryptography, including symmetric ciphers and cryptographic hash functions. The blog post seems to be essentially, "I read these good posts on Ars [3] and F5 [4] [5] and here is my summary of my understanding of them". Nothing wrong with that, but the post has some issues and doesn't add anything to the sources cited IMO. [1] http://www.crypto-textbook.com/ http://www.crypto-textbook.com/ (ironic that https isn't available?!?!) [2] https://www.youtube.com/channel/UC1usFRN4LCMcfIV7UjHNuQg https://www.youtube.com/channel/UC1usFRN4LCMcfIV7UjHNuQg [3] https://arstechnica.com/information-technology/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ https://arstechnica.com/information-technology/2013/10/a-rel... [4] https://devcentral.f5.com/s/articles/real-cryptography-has-curves-making-the-case-for-ecc-20832 https://devcentral.f5.com/s/articles/real-cryptography-has-c... [5] https://youtu.be/dCvB-mhkT0w https://youtu.be/dCvB-mhkT0w
• blargmaster33 6y ago
  Next time do not insert you TDS in your tech article.
• seesawtron 6y ago
  Cool stuff. I wrote a similar post explaining and implementing RSA in python on Colab[0]. I did NOT leave the math out because that was the most exciting part that I enjoyed while studying RSA. Maybe you'd wanna make a similar implementation for fun for ECC. [0] https://colab.research.google.com/drive/1ccyVKHHXFczk_3u5WoV-3OGtyS-FJnO3?usp=sharing https://colab.research.google.com/drive/1ccyVKHHXFczk_3u5WoV...
• lordgrenville 6y ago
  The Ars Technica article linked in the article is much better-written and more comprehensive. https://arstechnica.com/information-technology/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ https://arstechnica.com/information-technology/2013/10/a-rel... Fun fact: elliptic curves (specifically the Taniyama–Shimura conjecture about their relationship to modular forms) played a key role in Wiles' proof of Fermat's Last Theorem, one of the most famous problems in mathematics.
  • nbardy 6y ago
    Yea. This article just hijacks all the graphics from the ars technica article and makes it harder to read.
• techman9 6y ago
  It looks like several of the images in this post are taken (without credit?) from Cloudflare's primer? https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ https://blog.cloudflare.com/a-relatively-easy-to-understand-...
  • judge2020 6y ago
    Images (at least now) link to an ArsTechnica article [0] written by Nick Sullivan, the same person who wrote said blog post (the article and CF's blog post are the same thing, with ArsTechnica going up a day later). https://arstechnica.com/information-technology/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ https://arstechnica.com/information-technology/2013/10/a-rel...
• staycoolboy 6y ago
  Very cool. I would love an ELI5 why some curves are more or less secure than others (e.g. p256r1 is the hot curve now, but why?)
  • john_alan 6y ago
    When you say p-256r1 are you talking about secp256r1 or Brainpool? The security of a curve is defined by p, the prime field over which it is defined, a and b the curve co-efficient. There exists attacks against curves in various ways, composite order attacks, anomalous curves (where the curve order === field order).
    • staycoolboy 6y ago
      secp256r1 > There exists attacks against curves in various ways, composite order attacks, anomalous curves (where the curve order === field order). This is where I need the ELI5 part. :) But I realize some things just require hard work to understand... like ECC theory.
      • john_alan 6y ago
        Haha, well I guess. To start you off: Composite order attacks: things that are prime tend to be hard to attack. If your curve doesn’t use prime stuff then you can take the factors of the thing and attack it in little groups. Anomalous curves: elliptic curves have a total number of points. We call that the order. So does the “field” (kinda like a box) that the curve lives in. If the number of elements in the field and the number of elements in the curve are the same, you can kinda “lift” the curve out of its box and put it in another box that’s easier to smash it in. :)
        • staycoolboy 6y ago
          Thanks, this answer is helpful for focusing my search terms!
• svnpenn 6y ago
  I finally get it now. I feel like "public key" is a misnomer. It's really a "public safe". You put something in the public safe and then it's locked. Then only the person with the private key can unlock it.
  • nyolfen 6y ago
    i saw someone on twitter suggest that public keys should be called 'padlocks'; definitely a more intuitive way to think of them
• null0pointer 6y ago
  Jeremy Kun also has a good blog series on ECC. Although from memory it gets pretty technical into pure maths pretty quickly. https://jeremykun.com/2014/02/08/introducing-elliptic-curves/ https://jeremykun.com/2014/02/08/introducing-elliptic-curves...
• blackrock 6y ago
  How trustworthy is ECC? Considering it was developed in collaboration with the NSA.
  • john_alan 6y ago
    ECC wasn’t developed by the NSA. Elliptic curves have been studied in mathematics for 150 years. Elliptic curve cryptography was introduced by Victor Miller and Neal Koblitz in 1985. The NSA just released some compromised tech using curves.