6 ms·

An Illustrated Guide to Elliptic Curve Cryptography Validation

177 points by alanfranz 5y ago

high_byte 5y 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 :)
loup-vaillant 5y 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 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 https://monocypher.org/quality-assurance/disclosures [3]: https://github.com/google/wycheproof/pull/79 https://github.com/google/wycheproof/pull/79
dan-robertson 5y ago
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.
throwaway81523 5y 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-vaillant 5y 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 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/eddsa_test.json https://github.com/google/wycheproof/blob/master/testvectors...
  - bagels 5y ago
    Is the compiler or cpu ever turning constant time arithmetic in to non-constant time through optimizations or branch prediction?
    - loup-vaillant 5y ago
      Strictly speaking, programming language standards don't guarantee timings, so the compiler could always insert branches in surprising ways. In some (admittedly rare) cases, they actually do. Some high-level languages like Python don't have constant time arithmetic at all. (On the other hand, having arbitrary precision integer by default makes prototyping very easy. SAGE is based on Python for a reason.) 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.
account-5 5y ago
That's a lot of writing and hardly any illustrations for "An Illustrated Guide".
TacticalCoder 5y 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.
- drexlspivey 5y 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)
  - TacticalCoder 5y 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 5y ago
Does anybody know if the concepts behind elliptic curve cryptography be applied to analog data?
- marcan_42 5y ago
  Cryptography only works with digital data. That's quite fundamental to how it works, as far as I know.
  - kadoban 5y 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.
    - marcan_42 5y ago
      You're thinking of SIGSALY. Not only was it not analog, it was the first digital system to use PCM for audio. https://en.m.wikipedia.org/wiki/SIGSALY 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.
      - kadoban 5y ago
        Thanks, I did not know that was digital.

177 points by alanfranz 5y 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 :)

loup-vaillant 5y 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 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 https://monocypher.org/quality-assurance/disclosures [3]: https://github.com/google/wycheproof/pull/79 https://github.com/google/wycheproof/pull/79

dan-robertson 5y ago

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.

throwaway81523 5y 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-vaillant 5y 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 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/eddsa_test.json https://github.com/google/wycheproof/blob/master/testvectors...
- bagels 5y ago
  Is the compiler or cpu ever turning constant time arithmetic in to non-constant time through optimizations or branch prediction?
  - loup-vaillant 5y ago
    Strictly speaking, programming language standards don't guarantee timings, so the compiler could always insert branches in surprising ways. In some (admittedly rare) cases, they actually do. Some high-level languages like Python don't have constant time arithmetic at all. (On the other hand, having arbitrary precision integer by default makes prototyping very easy. SAGE is based on Python for a reason.) 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.

account-5 5y ago

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

TacticalCoder 5y 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.

drexlspivey 5y 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)
- TacticalCoder 5y 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 5y ago

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

marcan_42 5y ago
Cryptography only works with digital data. That's quite fundamental to how it works, as far as I know.
- kadoban 5y 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.
  - marcan_42 5y ago
    You're thinking of SIGSALY. Not only was it not analog, it was the first digital system to use PCM for audio. https://en.m.wikipedia.org/wiki/SIGSALY 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.
    - kadoban 5y ago
      Thanks, I did not know that was digital.