Basic Intro to Elliptic Curve Cryptography (2019)
qvault.io
qvault.io
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
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/ (ironic that https isn't available?!?!)
[2] https://www.youtube.com/channel/UC1usFRN4LCMcfIV7UjHNuQg
[3] https://arstechnica.com/information-technology/2013/10/a-rel...
[4] https://devcentral.f5.com/s/articles/real-cryptography-has-c...
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.
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.
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
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
(I still love Montgomery curves for variable base scalar multiplication.)
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/?c...
I had a cryptography elective I wanted to take in undergrad but it was in the wrong semester.
http://loup-vaillant.fr/tutorials/fast-scalarmult
http://loup-vaillant.fr/tutorials/cofactor
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:
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).
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.
https://arstechnica.com/information-technology/2013/10/a-rel...
[0] https://colab.research.google.com/drive/1ccyVKHHXFczk_3u5WoV...
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?
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.
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.
If you want 13P you do
2P = P + P
4P = 2P + 2P
8P = 4P + 4P
12P = 8P + 4P
13P = 12P + P
To use this for encryption you do a Diffie-Hellman operation, where A and B pick secrets a and b, send each other a x G and b x G, and compute the shared secret a x b x G = b x a x G. (Where G is a standard point.)
You can call "b x G" the public key and do ephemeral-static DH if you are not doing a key exchange between two online peers.
---
I mean, once you have the keys, how do you actually use them to transform data?
Instead we usually multiply our private key by someone else’s public key to get a point.
We take that points x value, hash it and use the output as a symmetric key.
The other person can take our public key and multiply it by their private key to get the same point.
We end up with something like this:
OurPrivate * TheirPub == secret point.
(TheirPub is actually equal to TheirPrivateG, thus the secret point is really OurPrivateTheirPrivate*G)
“Encryption” with elliptic curves is just ECDH and then using a symmetric cipher like AES.
Signature is a little more complicated. It’s not just “encrypting a hash”
One of the changes in modern cryptography compared to stuff from the 1990s is that we rarely have cause to use public key encryption at all.
A typical modern design uses a key agreement algorithm to choose a large shared secret known to both parties which is then used to do encryption with symmetric algorithms.
The elliptic curves show up in the key agreement algorithm and in a Digital Signature scheme used after the encryption switches on to prove who you really are, but we often don't use them to actually encrypt anything (and so likewise we don't use them to decrypt anything either).
As a classroom exercise you can use RSA to encrypt the message "I like toast". You turn "I like toast" into a big number. Using a public key you do the (textbook) RSA operation and out comes a different big number. The recipient uses the private key to get the first big number back - and it translates as "I like toast". Nobody did that in real crypto systems, even in the 1990s, and the way you'd do it as a classroom exercise is inherently unsafe, but you can watch it being done and it's somewhat helpful in understanding RSA.
Nothing like that is usually done with elliptic curves.
Fortunately we didn't want to send a message like "I like toast" with public key crypto anyway, we always actually want to agree symmetric cryptographic keys.
And agreeing keys we can do with elliptic curves. Such as https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93...
What's the difference? The key agreement protocol doesn't let you choose the message. Alice and Bob will definitely agree on some shared key at the end of the protocol, but neither Alice nor Bob can choose what it is. For a key this doesn't matter, indeed it's arguably desirable to use random keys nobody actually picked, lots of things to like about that outcome.
Does that help?
? I'm not talking about encrypting data with RSA, but how else do you perform signing with RSA except by using the private key to transform some message that can then be verified with the public key?
I see now the article's trying to describe elliptic curve Diffie-Hellman, which makes much more sense (but makes the comparison to RSA in the article confusing...)
Basically, adding point to itself n times requires O(log(n)) operations. That's how you can have n be as big as 2^255 or 2^448.
So yeah, you can still count back, but I'm not sure you'll be done before the heat death of the universe. There are better attacks than that, but they're still O(sqrt(n)), which is exponentially bigger than the O(log(n)) required for legitimate uses.
According to [0], the Stelliferous Era alone will last ~3 zettaseconds, which at a best already achieved clock rate of 12 attoseconds gives ~2^127 cycles, easily enough to break common 128-bit-'secure' cryptography with good probability on a single, serial computer.
Checking [1], converting the Virgo Supercluster into sand-grain-sized computer cores would give parallelism on the order of 2^170, enough to break 297-bit security ratings with certainty, and uncomfortably cut into even 384-bit security.
> as big as 2^255 or 2^448.
448-bit security (not 448-bit elliptic curves, but 896-bit curves) is probably okay, despite that these are still fairly underestimated[2] limits - you get better (smaller) limits based off dissipating waste heat at CMB temperatures, so even 384-bit security might be safe in practice.
These are all rather off-the-cuff estimates (read, I looked up the largest and smallest plausible-sounding numbers and divided them), but it's rather disturbing that most people don't even seem to think to wonder "what if the adversary was willing/able to sink a significant fraction of the mass and lifespan of the universe into breaking this cryptography?", much less keep semi-exact numbers handy when estimating security margins.
0: http://en.wikipedia.org/wiki/Orders_of_magnitude_(time)
1: http://en.wikipedia.org/wiki/Orders_of_magnitude_(mass)
2: 2^127 and 2^170 are both fairly achieveable (ie underestimated) individually, but dismantling all the stars you can access to build computers raises the question of how you're then going to power those computers, so I'm not sure just multiplying them together to get 2^297 actually works.
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.
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.
https://jeremykun.com/2014/02/08/introducing-elliptic-curves...
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 ?
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?
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.
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).
> 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.
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. :)
The ECC-specific content begins on page 2.
https://arstechnica.com/information-technology/2013/10/a-rel...
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.
That doesn't mean it wasn't provocative, just that a community like this needs its members to work on core strength, so we can keep this place functioning for curious conversation.
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.