3 ms·

Sage is wonderful. It has a huge number of uses but I mostly use it for cryptography. Sage has the best (certainly open source) support I know of for a myriad o

by lvh 8y ago

Sage is wonderful. It has a huge number of uses but I mostly use it for cryptography. Sage has the best (certainly open source) support I know of for a myriad of things like group theory and elliptic curves. Here's a short example for how easy it is to play around with a tiny elliptic curve: sage: p = 19; p.is_prime() True sage: K = GF(p); K Finite Field of size 19 sage: E = EllipticCurve(K, [5, 9]); E Elliptic Curve defined by y^2 = x^3 + 5*x + 9 over Finite Field of size 19 sage: E.count_points(), E.order(), E.gens() (19, 19, [(4 : 6 : 1)]) There are far too many things to name that sage can do, but the CLI has a great autocomplete. Here's an example: let's say you have ECDH with point compression, and you specify only an x coordinate. Point compression limits the effectiveness of invalid curve attacks, where an attacker gives you a maliciously picked Diffie-Hellman value that isn't actually on the curve you're supposed to be on. However, if the x coordinate doesn't map to a point on the curve, it's necessarily on its "nontrivial quadratic twist". Sage makes this easy to play with because sage makes pretty much everything easy to play with: sage: E.lift_x(6, all=True) [] sage: E.quadratic_twist() Elliptic Curve defined by y^2 = x^3 + 6*x + 13 over Finite Field of size 19 sage: E.quadratic_twist().lift_x(6, all=True) [(6 : 6 : 1), (6 : 13 : 1)] If you want to do a full-on invalid curve attack, the easiest way to do that is with Sage. You look up how the explicit formulas work in the EFD[efd], you write a ladder, you figure out how to create other elliptic curves for which the short Weierstrass doubling formulas still work (which parameter doesn't appear in the formula?), and then just let sage generate every possible curve and see which ones have the poor cryptographic properties you're after. There's a reason the introduction to Cryptopals Set 8[set8] sends with the words: > By the time you're done, you will have written an ad hoc, informally-specified, bug-ridden, slow implementation of one percent of SageMath. [efd]: https://www.hyperelliptic.org/EFD/g1p/auto-shortw.html https://www.hyperelliptic.org/EFD/g1p/auto-shortw.html [set8]: https://cryptopals.com/sets/8 https://cryptopals.com/sets/8

mmirate 8y ago
Aren't both of those attacks all-but-negated by djb's Curve25519?
- lvh 8y ago
  Effectively, yes. Curve25519 has a few tricks that make this hard to do: it defines a curve compression format that mandates using 32-byte public keys and uses a single-coordinate ladder. It has the same property that points not on the curve are on the twist, but the twist is also secure. Curve25519's main innovation was to make the secure thing the default and the obvious thing to do: it was not the first twist-secure curve, it was not the first curve to have point compression that forces a point to be on the curve or the twist, plain old NIST P-256 had both of thsose. We also had a 1-coordinate ladder for Weierstrass prior to Curve25519, but it was far less used than effective point compression. But it is true that it is not incorrect to use P-256 without point compression which makes it easy to have these sorts of problems, and it is incorrect to do so in Curve25519, because the spec encompasses more than just the mathematical object of the curve. Curve25519 and its sister curve Ed25519 are really good at what they were designed for. Unfortunately people also use them for things that they're not good at, and then you get bugs like the Monero double spend. Montgomery curves necessarily don't have cofactor 1 -- so that's an example of a bug that could only have occurred on X25519.

by lvh 8y ago

mmirate 8y ago

Aren't both of those attacks all-but-negated by djb's Curve25519?

lvh 8y ago
Effectively, yes. Curve25519 has a few tricks that make this hard to do: it defines a curve compression format that mandates using 32-byte public keys and uses a single-coordinate ladder. It has the same property that points not on the curve are on the twist, but the twist is also secure. Curve25519's main innovation was to make the secure thing the default and the obvious thing to do: it was not the first twist-secure curve, it was not the first curve to have point compression that forces a point to be on the curve or the twist, plain old NIST P-256 had both of thsose. We also had a 1-coordinate ladder for Weierstrass prior to Curve25519, but it was far less used than effective point compression. But it is true that it is not incorrect to use P-256 without point compression which makes it easy to have these sorts of problems, and it is incorrect to do so in Curve25519, because the spec encompasses more than just the mathematical object of the curve. Curve25519 and its sister curve Ed25519 are really good at what they were designed for. Unfortunately people also use them for things that they're not good at, and then you get bugs like the Monero double spend. Montgomery curves necessarily don't have cofactor 1 -- so that's an example of a bug that could only have occurred on X25519.