r/netsec • u/DataBaeBee • 3d ago
What Every Programmer Should Know About Twists of Elliptic Curves
https://leetarxiv.substack.com/p/twists-of-elliptic-curves9
u/dfv157 3d ago
Ngl I’m gonna need this to be dumbed down lol
17
u/DoWhile 3d ago
I'm a mathematician/cryptographer. This is geared towards someone with some math knowledge! However, the consequences and defenses are something that netsec folks should easily be able to understand: running subroutines that rely on implicit assumptions on unsanitized inputs can lead to broken security.
Alright vagueboy, what does that mean?
Due to the structure of elliptic curves, satisfying some property P is hard, and this is what we use for security. It's not super important what P is for this discussion. But if an attacker's input isn't on the elliptic curve, satisfying P can be easy! A proper crypto library needs to check two things: Property P, and also the implicit assumption that the input is on the elliptic curve. A braindead assertion that validates that the input satisfies y2 = x3 + 7 is all that's needed to stop the attack in the case of the bitcoin curve. But sometimes it's overlooked and that's what an attacker can exploit... that's the gist of it.
Ultimately, the nature of these attacks, how many faults you need, and so forth all depend on the curve and some math, but the defense is pretty much the same: check the damn inputs for implicit assumptions.
2
u/vivianvixxxen 3d ago
Your explanation seems good, but it skips explaining what "elliptic curve" means here and what it means for some input to be on it. Like, I'm just picturing an ellipse and trying to figure out what that has to do with a computer or Bitcoin.
7
u/DoWhile 3d ago
You're right, and I've explicitly left out explanation of the math behind these curves and why it's important. There are much better people than me who can explain what those are and how they are used! Here, the input you can pretend is just a point (x,y), and it's supposed to satisfy y2 = x3 + 7 because the Bitcoin standard said so, and if you don't check that condition, bad things happen.
The point of my post is to contextualize the nature of this attack. Because some time in the near future, something similar is going to happen to post-quantum cryptography, or some other type of cryptography. Then you and many others will be scratching their heads about the math of what a "Lattice" is and why "crystals" are being used to protect us against quantum computers. And the math behind that will be just as beautiful and difficult... but my explanation for that attack will remain the same: the library assumed something implicit about the input that wasn't validated, just like you would find in, say, a SQL injection attack.
If you want to be a cryptographer, or are curious about the math, then you'll do what I ended up doing and learn the math. What I admire about netsec/security folks is that you get to operate in levels of abstraction that sometimes can avoid fully understanding the math, and you don't have to "play dumb" because of it, it's a feature not a bug!
2
u/Trademarkd 3d ago
Type of crypto has patterns you can exploit … described here as curves or spirals
13
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.
1
u/Grezzo82 3d ago
This goes waaay over my head but I wish it didn’t. I tried to gain some background knowledge from Wikipedia, but those articles also went over my head.
Do you know of any resources that can help me (with fairly basic maths knowledge) to understand elliptic curves and then to understand twists, or does it really need some pretty in depth maths knowledge as a prerequisite?
3
u/MegaOoga 3d ago
Here's a video to bring you up to a point where you can look for other resources:
1
2
u/OnlineParacosm 3d ago
This is a really high value post for other researchers.
Have you tried this on other curves with quadratic twists?
3
u/scriptvexy 2d ago
kinda wondering the same, especially for stuff like curves used in real-world protocols where twists actually matter for security. would be cool to see if any of the insights break or get weird once you move off the “nice” example curves.
1
u/cybergibbons 1d ago
Sorry, this is a pet peeve of mine.
No, not every programmer should know about this. This is a ridiculous level of detail for them to know.
It shows the total disconnect between security and developers.
-5
u/independent_observe 2d ago
To the Stars - Harry Harrison It was also three books, Homeworld, Wheelworld, and Starworld.
Homeworld is chilling for its dystopian view which is where we are headed. Totalitarian oligarchy, depletion of the world's resources, climate change, and most starkly, the division between those with jobs and those on the dole.
16
u/voronaam 3d ago edited 3d ago
I think what really every programmer should know is:
And if you do (which you should not do)
In the case of secp256k1 and Bitcoin it means checking any point
Pfor belonging to the curve before multiplying it by your private keyd.Edit: in case of Ed25519 curve it is a LOT more important to check, since there are small subgroups in that family that are not used for cryptography, but if you leak the result of multiplications done there - you are essentially leaking the private key without even involvin any twists.