An Illustrated Guide to Elliptic Curve Cryptography Validation
research.nccgroup.com
research.nccgroup.com
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.
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).
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...
The CPU on the other hand is more reliable: while every branch it takes will have variable timings, arithmetic timings are almost always independent from the content of the operands. There are two important exceptions to this:
- If your CPU doesn't have a barrel shifter, the timings of arithmetic shifts depends on by how many bits you shift. That's why modern cryptographic primitives now shift by constant amounts, unlike RC4.
- Some small CPUs have variable time multiplication. 64-bit multiplication is the worst, because you need compiler support to emulate it on 32-bit platforms and smaller.
On modern desktop/laptop/palmtop CPUs, all you care about are secret dependant branches and secret dependent indices in your generated binary code. And that is pretty easy to test with Valgrind. Replace your secret inputs by uninitialised blobs of data, see how it reacts: if Valgrind complains about a jump or indirection depending on uninitialised data, you may have a problem (you'll have at least one in the case of verifiers). If it doesn't complain however, you're good.
Edit: I think you were probably thinking of RC5. That one does have data-dependent shifts. It's never been in wide use, though.
But this article is not that at all, and I like that.
> 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.
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.
https://en.m.wikipedia.org/wiki/SIGSALY
The analog TV stuff isn't encryption, it's scrambling. Those systems used proper digital crypto to generate the keystream, then scrambled video lines using a digital line buffer. They aren't secure (you can decode the picture by correlating lines without having the key) and they still rely on digital bits to do the processing, even if the image itself is transmitted as analog.
So no, analog crypto doesn't exist, though you can certainly obfuscate analog signals in various ways. For crypto to be analog the actual cryptography would have to be performed in the analog domain. To my knowledge, that doesn't exist and can't exist.
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.