💾 Archived View for dioskouroi.xyz › thread › 29397243 captured on 2021-12-04 at 18:04:22. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2021-11-30)
-=-=-=-=-=-=-
________________________________________________________________________________
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.
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)
> 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).
You are right, after re-reading BIP340 they decompress the X coordinate and they always pick the even Y coordinate to break ambiguity.
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...
Is the compiler or cpu ever turning constant time arithmetic in to non-constant time through optimizations or branch prediction?
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.
RC4 doesn't have any shifts; I think you must be thinking of another algorithm. What it does have is data-dependent loads, which are also undesirable.
Edit: I think you were probably thinking of RC5. That one does have data-dependent shifts. It's never been in wide use, though.
Ah, RC5, OK. Thanks for the correction.
That's a lot of writing and hardly any illustrations for "An Illustrated Guide".
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.
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
Does anybody know if the concepts behind elliptic curve cryptography be applied to analog data?
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.
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.
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.
Cryptography only works with digital data. That's quite fundamental to how it works, as far as I know.
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.
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
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.
Thanks, I did not know that was digital.
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 :)