An Illustrated Guide to Elliptic Curve Cryptography Validation

https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/

by alanfranz • 5 years ago

177 22 5 years ago

research.nccgroup.com

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.

loup-vaillant4• 5 years ago

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] https://github.com/google/wycheproof/pull/79

throwaway81523• 5 years ago

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.

loup-vaillant4• 5 years ago

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...

bagels• 5 years ago

Is the compiler or cpu ever turning constant time arithmetic in to non-constant time through optimizations or branch prediction?

account-5• 5 years ago

That's a lot of writing and hardly any illustrations for "An Illustrated Guide".

TacticalCoder2• 5 years ago

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.

drexlspivey2• 5 years ago

You don’t even need the one bit, you can try both points and only one will be on the curve. The new Schnorr Signatures in Bitcoin are encoded in 32 bytes (just the X coordinate)

TacticalCoder2• 5 years ago

you can try both points and only one will be on the curve.

Hmmm. You "decompress" the compressed key (a compressed key is one only transmitted using its x coordinate) and when you decompress, you can have two points on the secp256k1 curve (these are the "two solutions" TFA mentions): which is precisely why you pass the parity bit to get the correct one. There are two points are are going to validate y * 2 = x * 3 + 7 (mod p). So they're both on the curve right?

Now all the Bitcoin/Ethereum docs says that the parity is there to speed up computation: I took it they meant by that that of the two potentially valid public keys, only one shall have fund of them and that's easy to verify. And only the one with funds on it can actually do anything.

So I do agree that you don't technically even need that one bit (it only speeds up computation) however I do disagree that only one point will be on the curve (for both y and -y (aka P - y) will be on the curve).

noworriesnate• 5 years ago

Does anybody know if the concepts behind elliptic curve cryptography be applied to analog data?

marcan_423• 5 years ago

Cryptography only works with digital data. That's quite fundamental to how it works, as far as I know.

kadoban2• 5 years ago

That's mostly but not strictly true, possibly depending on your definition. One example of analog encryption would be there was a system around WWII times where noise from a phonograph was added to a call to avoid evesdropping, and then on the receiving end it was subtracted out using a specially synchronized phonograph.

Another that I'm not sure on exactly, but back when TV was analog, there were some channels designed not to be watchable without paying. Not sure how those worked, it may technically qualify.

SAI_Peregrinus• 5 years ago

Not really, assuming you mean "continuous" by "analog". ECC relies on the existence of an elliptic curve group to be reversible. Groups are inherently discrete structures, I'm not aware of any continuous structures with similarly useful properties.

joppy• 5 years ago

Groups are not inherently discrete - there are many continuous groups (called Lie groups) such as the circle, group of rotations in 3D, etc etc. You can also see this turn up in Fourier theory: the discrete Fourier transform has an underlying discrete group, Fourier series for a periodic function are really using the circle group underneath, and the Fourier transform on the real line is using the continuous group of the real line, with addition as the group operation.

Elliptic curves are nice because they are algebraic groups, so by plugging in complex or real numbers you get a continuous group, and by plugging in finite fields you get a discrete group.

BearsAreCool• 5 years ago

While elliptic curves may sound like they're related to analog data (sinusoidal curves etc), they're actually used in an incredibly discrete way. You have discrete points on an elliptic curves modulo a prime and use them in elliptic curve algebra by multiplying them by integer values, which correspond to drawing lines between different curve points.

high_byte• 5 years ago

as security researcher recently into blockchain I really enjoyed this article. it has well described possible issues with cryptography without diving too deep into the math. well done :)

An Illustrated Guide to Elliptic Curve Cryptography Validation

Related Stories