💾 Archived View for dioskouroi.xyz › thread › 29397243 captured on 2021-11-30 at 20:18:30. Gemini links have been rewritten to link to archived content
➡️ Next capture (2021-12-04)
-=-=-=-=-=-=-
________________________________________________________________________________
Fun timing: I just implemented, purely for fun, EC curve public key recovery from signed message in Clojure, using both "regular" maths (and the Java crypto BouncyCastle library) and then handcoded jacobian maths (I did it only for secp256k1 but I take it works with many curves).
Took me quite some head scratching to get working but it was nice when it eventually worked.
Tiny nitpick: _"Hence, when compressing a point, an additional byte of data is used to distinguish the correct y-coordinate."_. It's actually only one additional _bit_ of data that is needed, not a full byte: all you need is the parity of the y-coordinate. Even though that one bit is often encoded in a full byte it's not always so: for example Ethereum, for a very long time, used transactions where the y-coordinate parity was encoded as a single bit, along with the "chain ID" (now with the latest protocols they're encoding the parity in a full byte, which is either 0x00 or 0x01).
It's really a tiny nitpick but there you go.
That's a lot of writing and hardly any illustrations for "An Illustrated Guide".
It is very easy to make mistakes in ECC implementation. If you really want to code it yourself, there's a book by Menezes, Vanstone et al ("Guide to Elliptic Curve Cryptography, I think) that gives very explicit instructions about how to do everything. I used to hack on a P256 implementation. But, it is a bit out of date by now, and IIRC it doesn't say anything about Curve25519.
Thankfully, Curve25519 is much easier to implement, with much fewer death traps than short Weierstraß curves. For X25519, just follow DJB’s advice from ECC Hacks
https://www.youtube.com/watch?v=vEt-D8xZmgE
and make sure your arithmetic is up to snuff (constant time arithmetic is actually the hard part, by default I strongly suggest you steal it from the ref10 implementation).
For EdDSA, just follow the relevant explicit formulas, avoid clever (but dangerous) tricks such as converting to Montgomery form and back, and test with Wycheproof’s Ed25519 test vectors.
https://github.com/google/wycheproof/blob/master/testvectors...
I was worried this would be a silly visualisation where you draw an elliptic curve and talk about tangents, which maybe describes an elliptic curve group, but not the right one, and it doesn’t really give any intuition about what ECC is.
But this article is not that at all, and I like that.
Does anybody know if the concepts behind elliptic curve cryptography be applied to analog data?
Excellent essay, highly recommended.
_With the popularity of Curve25519 and the desire for cryptographers to design more exotic protocols with it, the cofactor value of 8 resurfaced as a potential source of problems. Ristretto was designed as a solution to the cofactor pitfalls._
I’m a bit two face about this: on the one hand, if you don’t want to think and just want a prime order group to work with, Ristretto is a Blessing from the Heavens: fast validation, fast curve operations (thanks to the underlying curve), and no pesky cofactor death trap. Thanks Mike Hamburg, may you live long and happy.
On the other hand, if we know our way around cyclic groups¹, there are almost always very simple (implementation-wise) ways to deal with the cofactor, which lessens the need for Ristretto on carefully crafted protocols—though Ristretto would still simplify those protocols, making them easier to audit.
[1]:
https://loup-vaillant.fr/tutorials/cofactor
_Recently, we also uncovered a critical vulnerability in a number of open-source ECDSA libraries, in which the verification function failed to check that the signature was non-zero, allowing attackers to forge signatures on arbitrary messages_
Oh. That explains a lot.
See, I made _one_ significant mistake in all my time as a cryptographic implementer². The effect was, all-zero signatures were accepted half the time, with any public key. Sounds familiar?
In any case, some people were quick to assume I was a drooling incompetent for failing to perform such a basic check as rejecting the all-zero signature. If I was implementing ECDSA, they’d have been right. Except I was implementing _EdDSA_, which _already_ rejects all-zero signatures with its main algorithm. An explicit all-zero check is not needed at all. DJB himself for instance omits it in TweetNaCl. My bug was more subtle: I didn’t fail to check a standard edge case any decent specification would mention. I _introduced_ an edge case by doing a less-than-safe conversion with a less-than-perfect understanding of the maths involved.
_(To those who wonder why I even tried, I asked around before attempting this, and no one warned me—cryptographers are busy. And to those who are wondering why I didn’t check with Whycheproof from the beginning, that’s because I looked at their list of supported protocols, and didn’t found EdDSA. To this day, their GitHub main page lists neither EdDSA nor Ed25519, despite my pull request from nearly 2 years ago.³ If someone from Google hears this, please…)_
In any case, I now understand the mockery better. Those people likely pattern matched my vulnerability with the corresponding ECDSA beginner error, and shot me down without checking what was actually going on. I guess they too were busy.
[2]:
https://monocypher.org/quality-assurance/disclosures
[3]: