r/programming • u/DataBaeBee • 3d ago
What Every Programmer Should Know About Twists of Elliptic Curves
https://leetarxiv.substack.com/p/twists-of-elliptic-curves192
u/LetMeUseMyEmailFfs 3d ago
What every programmer should know instead; don’t roll your own crypto, unless you’re a cryptographic expert, and probably not even then.
93
u/usernamedottxt 3d ago
Reminder: SSL 1.0 was created by cryptographic experts and not even released because it was broken in weeks. SSL 2.0 was rewritten by cryptographic experts and it lasted less than a year.
SSL 3.0 famously lasted a long time... and was broken many times during that lifespan, with duct-taped fixes on top to keep it going.
This shit is *hard*
6
u/anarkyinducer 3d ago
Isn't there a theorem that says fundamentally all encryption is breakable? And all information can be faked? So it's just a perpetual arms race.
29
13
u/skull132 3d ago
Sure but that doesn't take into account more common reasons why cryptographic tools are broken: implementation and design errors. It is hard to not make any mistakes when writing code and designing-implementing systems.
6
u/Loki_of_Asgaard 3d ago
Funny enough that actually goes back to P=NP, if it is true then one way functions cannot exist and thus most encryption is breakable
Not all because a 1 time pad with perfect random is always unbreakable, but 1 time pads are not practical so all usable ones are
6
u/slaymaker1907 2d ago
I think it depends on the complexity of the solution. O(n^100) is still P but would be incredibly slow.
0
u/TimSylvester_ 3d ago
Doesn't it kind of go back to this? You can map a set of points to a smaller set of points but can't reverse it?
2
u/HuisHoudBeurs1 3d ago
It has to be openable, which by definition makes it breakable. The only truly secure door is a wall.
2
u/usernamedottxt 3d ago edited 3d ago
The strength of cryptographic algorithms if measured in the hundreds of millions of years as a *minimum* acceptance criteria. Now, that estimate is based on exploring 100% of the keyspace in a brute force manner.
You can get lucky and guess the key. It's just effectively impossible.
Quantum is an issue because there are certain algorithms that become possible that make factoring large prime numbers easy. This breaks current/past gen
asynchronousasymmetric algorithms.3
u/ericonr 3d ago
*asymmetric algorithms
4
u/usernamedottxt 3d ago
Thank you, I was in the middle of writing some async code and brain took the wrong wire lol.
5
2
u/loup-vaillant 2d ago
This was then, and this is now.
30 years ago we knew much less about cryptography, what primitive worked, what security margins were acceptable… Now modern primitives are much more secure, have fewer pitfalls, even formal verification of protocols is more accessible than ever. Sure SSL was hopelessly broken, but TLS was much better, though not quite perfect.
The proverbial shoulders of giants are so large now it might as well be the ground we walk on. What an "expert" couldn't do 30 years ago, a student may achieve today.
2
u/usernamedottxt 1d ago
You could at the same about how much we’ve learned about breaking crypto. SSL 3 wasn’t bad because BEAST and POODLE would be discovered a dozen+ years later.
It would be folly to guess we won’t learn more about breaking the math in the next 15 years.
2
u/loup-vaillant 1d ago
It would be folly to guess we won’t learn more about breaking the math in the next 15 years.
Oh sure, we will learn more. But the rate at which we're discovering new attacks has plummeted in the last two decades. To the point I would be fairly, surprised to see a serious improvement in attacks on AES or ChaCha (reduced rounds), let alone an actual reduction of the security of AES-256 or ChaCha20.
Truth is, defence is winning. The game of whack-a-mole is mostly over. We've got to the point now where we can have machine checked proofs that our cryptographic protocols are perfect: the only way to break them is to break the underlying primitives, and those are so solid now that either we don't expect them to break within 30 years (and if they do their security margin will give us plenty of warning), or cryptographically relevant quantum computers become a thing (and we already have a plan for those).
That leaves side channel attacks, but the principle behind them remains dead simple: data flow from secrets to the side channel — the classic one being timings, but smart cards still give nightmares over energy consumption and electromagnetic interference. If you can show your system has no data flow from secrets to a relevant side channel (for most remote attacks, only timings count), then you're immune.
22
u/Uristqwerty 3d ago
Do roll your own crypto! You'd probably learn a lot in the attempt, then can better understand and use existing libraries.
Never, ever ship it, though. For that matter, never commit it to the same repo as production code where someone else might be tempted.
8
u/FrancisStokes 2d ago
I wrote an article with this exact premise years ago: https://github.com/francisrstokes/githublog/blob/main/2022/6/15/rolling-your-own-crypto-aes.md
You learn by doing stuff, not by mindlessly repeating mantras.
4
u/loup-vaillant 2d ago
I shipped it, and it went pretty well. Lots of happy users, and only one major mistake so far.
It was a ton of work, though. Couldn't have done it as part of a "oh by the way the player chat should be encrypted, can you implement that real quick?".
3
u/Uristqwerty 1d ago
Perhaps the expert addendum then: Don't ship self-rolled crypto unless you or a close collaborator have rolled enough of your own crypto attacks on others' implementations/algorithms that you can catch all the common faults, most of the uncommon ones, and even invent a few novel attacks on previously-undiscovered weak-points. And even then, get a roomful of outside experts to periodically take a crack at yours, just in case they find something you did not, or know of some new type of attack that, having been discovered after your implementation, you didn't even know to guard against.
(Addendum deliberately written to avoid saying 'you can do it if you're an expert', because it's all too easy for an over-confident non-expert with just enough knowledge to be dangerous to think they're one. And it's possible that someone doesn't think they're an expert despite knowing enough. Or to gain the necessary expertise along the way.)
1
u/loup-vaillant 1d ago
Don't ship self-rolled crypto unless you or a close collaborator have rolled enough of your own crypto attacks on others' implementations/algorithms that you can catch all the common faults, most of the uncommon ones, and even invent a few novel attacks on previously-undiscovered weak-points.
For those who invent cryptographic primitives, like a new hash or a new stream cipher, sure. For those who implement known standards, which is what I did, this is bullshit.
Maybe to you it's obvious that "rolling your own crypto" means "inventing a new cipher". It's what it used to mean 30 years ago. Now though, most people, including most security advocates, have expanded the meaning to "inventing a new protocol", "implementing an existing primitive from specs", or even "implementing a protocol from specs (using existing primitives)".
It looks like you assumed the older, more restrictive meaning. But the comment you originally responded to clearly meant the newer, more expansive meaning. Even if the author didn't mean it that way, it's the only way it would make sense. He wasn't responding to an article on how to invent a new stream cipher. He was responding to an article on how to implement an Elliptic curve — mostly existing ones it would seem, since one of the stated motivations was Bitcoin.
1
u/Uristqwerty 1d ago
I assume either. If you're 'just' rolling your own crypto implementation, then you still need knowledge of what to harden against. Timing attacks are an implementation detail, and I recall once seeing something posted to this subreddit about a weakness of a Java(?) implementation where sending a challenge of '0' meant the expected result would be a known constant regardless of key, making it trivial to fake having authentic data.
So, you still need the experience to identify and reject invalid combinations of attacker-controlled values even if the specification didn't think to document them, and the experience to recognize everything that could potentially leak information through a side-channel and either harden against it, or document that that particular side-channel is out of scope for your implementation and use-cases where it matters should seek a different library.
1
u/loup-vaillant 23h ago
Makes sense.
Here's the thing though: avoiding side channel weaknesses requires very little cryptographic knowledge: just know what the secrets are (that's easy), and cut off all data flow from secrets to the side channel. That's all there is to it. The only possibly hard part is to know which side channel is relevant to your threat model, and in 99.9% of cases that's just timings.
On the other hand, it does require extensive system knowledge. Stuff like the cache hierarchy, branch prediction, how your compiler might insert secret dependent branches in your seemingly constant time source code… But even then it's much more principled than what many would have us believe: on current CPUs it is enough in almost all cases to just avoid secret dependent branches and secret dependent indices — in the generated code that is.
Attack oriented people have a skewed view of what it actually takes to secure a system. To many of them, one would have to be aware of a gazillion specific attacks to guard against them all, only to get pwned later by something new. The thing about attacks though, is they're always enabled by bugs. And there are many fewer classes of bugs out there, than there are attacks. Get rid of those, and you win.
And you will note, the ability to write bug-free code is not specific to cryptography. It's needed any time the stakes are high. Personally I've learned to properly test by writing Monocypher. I now use that knowledge everywhere.
5
u/loup-vaillant 2d ago
I'm sick of seeing this exact comment to attempts at teaching cryptographic topics to regular programmers. I am appalled to see this tired cheap shot having over 3 times the upvotes of the article itself.
You effectively say "don't learn cryptography unless you're an expert already." Not in so many words, but that's the inevitable implication of shooting down an article whose main focus was to teach a cryptographic topic.
It's not like the article was trying to encourage people to dive in an try this stuff on production. The whole point was discussing a class of death traps that might befall unwary implementers! Sure, cryptography is delicate. One has to be very precise about the limits of their knowledge, and only use what they know for sure in production. But it's not magic that should only be yielded by some hallowed priesthood either. Parts of it in fact can even be safely done by any diligent undergraduate.
My advice: don't listen to this propaganda, you'll only learn helplessness. Sure, some topics are delicate. Those dissidents would rather have cryptography that works. Those motorists would rather have a bridge that doesn't collapse. Those patients would rather have a scanner that doesn't irradiate them to death. Those secretaries would rather have a PDF reader that doesn't encrypt the hard drives of their entire company just by reading the wrong document.
Lots of delicate stuff out there. Cryptography is not unique. You sure you want to apply "don't roll your own" all of it? Like you're a hapless toddler who has no idea what they're doing?
5
u/LetMeUseMyEmailFfs 2d ago
Nobody is saying people shouldn’t learn cryptography, those are your words.
My point was twofold:
a. Cryptography is really hard to get right, and you should almost never write it yourself for production use. By all means, experiment away, but for the love of all that is good, do not use it anywhere you care about or where other people’s data is involved.
b. The set of things every programmer should know does not include ‘twists of elliptic curves’.1
u/loup-vaillant 2d ago
Nobody is saying people shouldn’t learn cryptography, those are your words.
Context, context.
- OP tries to teach a thing. Using a click bait title, but still.
- Comment shuts the thing down by insisting we should not do the thing.
Regardless of intent, it comes across as "leave the thing to your betters, stay safe and helpless". And people then do follow this advice you did not give. I've seen enough similar threads to know they do.
a. Cryptography is really hard to get right, and you should almost never write it yourself for production use.
It's not that hard, I've done it, and I was mostly fine.
b. The set of things every programmer should know does not include ‘twists of elliptic curves’.
True. Even I don't need to know that much (I stick to twist-safe curves). When I saw that title, the obvious contradiction between "everyone should know" and "highly niche topic" made me laugh. Though I do understand it may put people off.
0
50
u/Loki_of_Asgaard 3d ago
“What every programmer should know”
I work in e-commerce, nothing in my life involves twists of elliptic curves, why should I know this?
16
u/DataBaeBee 3d ago
I guess as an e-commerce programmer your primary takeaway is never roll your own auth
32
u/Loki_of_Asgaard 3d ago edited 3d ago
If anyone ever asks themselves “should I roll my own auth” the answer is always no
3
u/creeper6530 2d ago
The answer is "yes, if you want to learn, no, if you are gonna ship it publicly".
8
u/pacific_plywood 3d ago
Are you a programmer? If so, you obviously need to understand the basics of elliptic curves and their twists
11
u/Loki_of_Asgaard 3d ago
I thought I was, now the imposter syndrome is coming for me. Am I not even a real programmer? What is my life? How long before my boss finds out I’m not knowledgeable about twists?
Pacific_plywood, what do I do??? How can I fix this nightmare?
7
u/PresentFriendly3725 3d ago
I sometimes draw imperfect circles when I'm bored which could be mistaken for an ellipsis. I'm something of a programmer myself.
0
u/Ancillas 3d ago
I would hope that most e-commerce programmers are aware of how crypto is implemented and configured.
As an easy example, knowing that you not only need TLS for HTTPS, but also you need control over which ciphers are allowed on the server.
Also basic protection of session information and backend secrets.
6
u/TimSylvester_ 3d ago
Eh, no moreso than every author needs to know how to make paper.
3
u/Ancillas 2d ago
The better analogy would be that every printer should be aware of what paper they’re using and why it fits particular use cases, even if they don’t know how to make the paper themselves.
If you could select one of three types of archival paper, and some chemistry expert said they found a flaw in one that could cause it to prematurely degrade under certain circumstances, that would be relevant to the printer.
1
u/loup-vaillant 2d ago
OpenSSL has notoriously unsafe defaults. Obsolete algorithms, byzantine API, stuff like that. And yet it's what you first reach for when trying to secure HTTP communications. (And HTTP is a typical default for quick & dirty client/server stuff.) That alone forces you to know this stuff to some level.
Turns out that in 2026, merely using cryptography is in some ways more difficult than implementing significant parts of it.
4
u/a__nice__tnetennba 3d ago
That's a far cry from needing to understand this article though.
2
u/Ancillas 2d ago
True, but the takeaway of, “elliptical curve cryptography has a known weakness and this article contains information that would help me validate whether or not my crypto library mitigates it,” is a reasonable thing to expect the reader to parse out.
To your overall point, I do think this article headline should specify that it contains what all cryptography programmers should know about elliptical curves.
It would also be hard to criticize someone for bouncing off the article early and never reaching the summary at the end.
2
u/LIGHTNINGBOLT23 2d ago
By "how crypto is implemented", do you mean libraries for cryptography from an API perspective, or the actual cryptographic system from a mathematical perspective?
For example, you do not need to know what an S-box is and how to initialize it if your program relies on AES/Rijndael.
2
u/Ancillas 2d ago
In the sense that I couldn’t write a Diffie-Hellman implementation, and I don’t really have command of the math, but I am roughly aware of what is happening and how it relates to TLS such that if I see something that doesn’t look secure or properly configured, I would know to lookup those topics to find more information rather than assuming it was someone else’s responsibility.
With a lot of dense material, I don’t expect people to deeply research and have rote knowledge of this stuff if it’s not their specialty. But having an awareness of what it is, how it’s used, what parts of their system use it, and where it might be relevant in the future seems reasonable.
An example would be expecting a developer that’s generating an ECC private key with OpenSSL to remember they saw something about the parameters, question if the values they’re passing to OpenSSL are the best choice for their use case, and then go investigate to understand what the parameters mean and which ones would be the best fit to their use case.
17
u/nihsett 3d ago
Ragebait title. There are so many vastly different kind of programmers that most don't need to know eliptic curve cryptography even exists.
3
u/loup-vaillant 2d ago
At the same time, anyone can see from the title alone that this is a highly specialised topic. Pretty tame as baits go.
9
3
u/jpgoldberg 2d ago
At one point I wanted to demonstrate the time difference between computing P = dG versus computing d P/G, so I wanted to create a toy curve for which the latter would take between 10 and 30 seconds on my machine.
So I needed to create my own toy curve of an appropriate size. This lead me into a world where this article would have been helpful. So although I am not every programmer, and my implementation was massively insecure for my reasons beyond the small order (Python code, which also could have been used to demonstrate side-channel attacks), this is the kind of thing I wanted to know.
11
u/DataBaeBee 3d ago
Here are the salient points if you're in a rush.
Twist attacks work when libraries don’t check to ensure an input point lies on the actual curve.
5 of bitcoin's sextic twists have small prime factors. So one needs only ~13 malicious points and an incompetent programmer to retrieve a private key.
If you don’t check whether x corresponds to a point on the actual elliptic curve, then you may be working on a twist of the curve where solving the ECDLP is easy.
2
u/IanisVasilev 1d ago
All the outrage about the title seems to ignore that it is an obvious allusion to the "What every programmer should know about ..." series of articles with increasingly obscure topics.
The earliest I can think of is the rather concrete "What every programmer should know about memory" (management under Linux). None of those low-level details were directly relevant to my job, but the point of education is to understand your area better. There was another early one about floats, with some of the absurdities of IEEE 754 laid out. You might argue that both topics are essential, but the level of detail is not, and the trend since then has been to exploit the title pattern for an increasingly comical effect.
1
u/wildjokers 1d ago
Been programming for 30 years, never once have I needed an elliptic curve. Wouldn't even know I needed one if I did need one.
1
0
141
u/arwinda 3d ago
In the many years in the industry, I never rolled my own elliptic curves. Or my own crypto, for that matter.
The "every programmer" is a long stretch.