Nostr Web Client

I'm always a bit torn about stuff like this. On the one hand, CRT is cool and it's even cooler that people have made successful attacks on real world systems using these so-called 'twist attacks' (basically the fuck up is to not check is the "point" you're provided, is actually on the curve).

https://github.com/christianlundkvist/blog/blob/master/2020_05_26_secp256k1_twist_attacks/secp256k1_twist_attacks.md

But, on the other hand, calling it a danger when using secp256k1 for encryption seems a bit wrong when the danger is specifically that you *didn't* use secp256k1!

Indeed the substance of this attack is to exploit the fact that if a curve group has small subgroups, you can apply CRT to get info about secret keys. But secp256k1 doesn't have *any* subgroups. So the attack depends on the victim not checking if an externally given public key, is actually on secp256k1. Combining that key in a DH type exchange leads to naughtiness.

Reply to this note

Please Login to reply.

Discussion

niftynei() 🇺🇸💸🧡 2y ago

ooh. can i fact check myself really fast? im working on my very short intro to elliptic curves for base58, and tell people in the video that the h=1 in the secp paper means exactly this: that there are no “subgroups” for the G group (i think i call them cycles). is that a correct explanation?

niftynei() 🇺🇸💸🧡 2y ago

ok wow this article is shockingly close to what i came up with for the elliptic curve portion of the soon to be released base58 part 2 basics class ❤️ (also confirms my understanding of the subgroups + secp256k1 🙌)

niftynei() 🇺🇸💸🧡 2y ago

loved this detail wrt compressed keys

waxwing 2y ago

Yes indeed. 'Cofactor' is a bit of an obtuse term, i think it's related to the beautiful Lagrange's theorem. Or maybe i only think that because of the term 'coset'. Not sure.

waxwing 2y ago

(continuing on this topic, at possibly absurd length):

The most interesting thing about this write up is that it's principally advocating for using curve25519 (see the 3rd recommendation at the end of the post) for ECDH and thus encryption, based on the idea that it's been designed to handle tricky adversarial behaviour. For example, the curve is designed to make constant-time implementation easier to limit/remove sidechannel attacks. And one thing in particular it has, which is quite special, is: *any* 32 byte string is an acceptable pubkey; this is done with some clever math magic in the curve's design definition. DJB (the author) therefore actually tells people to *not* validate input keys; as long as they're 32 bytes, they're to be accepted.

waxwing 2y ago

But despite the meaningful, but probably over-the-top "immune to sidechannel attacks" claim on curve25519's wikipedia page ("citation needed" - indeed!), the real point to me is that in practice, using a group which is a subgroup of the full curve, is dangerous. And this is borne out, e.g. by this paper from 2017:

https://eprint.iacr.org/2017/806

Quote:

"Since Libgcrypt’s implementation of Curve25519 uses the Montgomery ladder for scalar-by-point multiplication, branchless formulas for point doubling and addition, and built-in countermeasures specially designed to resist cache attacks, our attack cannot observe high-level key dependent behavior, such as key-dependent branches or memory accesses. Instead, we achieve key extraction by combining the specific mathematical structure of Curve25519 with low-level side channel vulnerabilities deep inside Libgcrypt’s basic finite field arithmetic operations. ** By observing the cache access patterns during at most 11 scalar-by-point multiplications, our attack recovers the entire secret scalar within a few seconds**. We note that the mathematical structure that enables our attacks in also present in other popular curves such as Curve41417 [15] and Curve448 [44] (Goldilocks curve) when represented in Montgomery form [57]."

(emphasis mine).

waxwing 2y ago

The TLDR here is that, yes, this was an implementation error, much as Monero made an implementation error in not checking the order of points, using the same curve with cofactor 8. in both cases the errors were patched. But the errors were very easy to miss and absolutely disastrous, especially in the libgcrypt case, allowing cracking of keys in seconds for any process that was sharing the same RAM.

Others, like JP Aumassin (author of the excellent 'Serious Cryptography'), and apparently Matt Green, apparently shared, partly, my skepticism about not validating inputs:

https://research.kudelskisecurity.com/2017/04/25/should-ecdh-keys-be-validated/

which btw links to this entertaining, concrete take on why not checking inputs is dodgy as hell: https://vnhacker.blogspot.com/2015/09/why-not-validating-curve25519-public.html

waxwing 2y ago

Do I have a point in this endless wittering? :) Well, I've always thought that engineers, and sometimes the most brilliant ones are the most guilty of this, have a tendency to over-optimise and over-engineer, and simplicity is absolutely key for robustness. There is nothing simpler than a group with NO structure - a cyclic group of prime order.

And as a counterpoint, building a system which is so cool in its sophistication that you don't need to check whether external inputs are adversarial, just lacks common sense.

Saberhagen The Nameless 2y ago

Interesting. This goes way over my head, but you would probably have a great conversation with @kayabaNerve (Luke Parker) on Twitter about this. Not sure if he's on Nostr