[HN Gopher] There Is No Diffie-Hellman but Elliptic Curve Diffie...
___________________________________________________________________
There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman
Author : todsacerdoti
Score : 120 points
Date : 2025-05-24 20:53 UTC (4 days ago)
(HTM) web link (keymaterial.net)
(TXT) w3m dump (keymaterial.net)
| cgio wrote:
| The logical click bait on this one. I could not resist thinking
| it's like saying there is no circle other than a round circle,
| but I had no idea if it's equivalent and fair comment given my
| limited cryptography knowledge (as in non existent). So I had to
| read it, and while I got little, by osmosis, I feel falling for
| the bait was worth it.
| techNoob123 wrote:
| lol same - but i needed this comment to take the bait
| bawolff wrote:
| For historical context, TLS only really started to use the
| eliptic curve version of diffie-helman in the mid 2010s. Prior
| to that, plain diffie helman was more popular. (E.g. here is a
| thread from a decade ago complaining about lack of support
| https://security.stackexchange.com/questions/59459/how-widel...
| ).
|
| ECC also used to have patents which restricted adoption back in
| the day.
|
| There also used to be a lot of conspiracy theories that NSA
| backdoored nist curved ( e.g.
| https://m.slashdot.org/story/191445 ). Probably fud, but it
| slowed down adoption of eliptic curves.
| tgma wrote:
| I believe the patent issue was by far the dominant friction
| for adoption in 2000s. On the NIST curve problem, well, maybe
| FUD, but evidently, they indeed backdoored the elliptic
| curve-based random number generator, so I would say some
| distrust is warranted.
|
| Irrespective of the curve issue, ed25519/x25519 is superior
| and has other nice properties like not catastrophically
| breaking if you can't generate a unique random "k" for ECDSA
| as PlayStation discovered the hard way[1].
|
| [1]: https://youtu.be/DUGGJpn2_zY?t=2142
| xyzzyz wrote:
| > like not catastrophically breaking if you can't generate
| a unique random "k" for ECDSA
|
| How does that work? I thought that this vulnerability was
| independent of the curve that is used. Ed25519 has a bunch
| of other nice properties related to resistance to
| programming errors, but I never heard of this one.
| cesarb wrote:
| > How does that work? I thought that this vulnerability
| was independent of the curve that is used.
|
| The trick is that this value in Ed25519 is a
| deterministic hash of the private key and the message,
| which means that for the same message, the same value
| will always be chosen, and since the private key is part
| of the hash, for different messages the value is
| basically random unless you already know the private key.
|
| Yes, the same trick can be used with any curve, and it
| will avoid the vulnerability; but for Ed25519, it's
| always been part of the specification so everyone does it
| that way, while for ECDSA it's a later addition (RFC
| 6979) and many implementations still do it the old way.
| phkahler wrote:
| >> Probably fud, but it slowed down adoption of eliptic
| curves.
|
| Not FUD at all. NIST revoked their recommendation to use
| those curves because of it. The facts are that a "backdoor"
| exists whether anyone knows what it is or not, and NSA could
| not explain how those particular numbers were chosen so out
| of caution we must assume they know the backdoor and not use
| those curves.
| tgma wrote:
| I believe you are mixing up NIST ECC curves with
| _Dual_EC_DRBG_ [1] which is a random number generator based
| on elliptic curves which is _widely considered_ to be
| backdoored and they revoked its recommendation (there are
| much better ways to construct an RNG so it was stupid to
| use in practice for reasons other than backdoor too.)
|
| The P-series curves are still a NIST recommendation and
| widely deployed in TLS. The B-series fell out of fashion
| due to practical reasons.
|
| [1]: https://en.wikipedia.org/wiki/Dual_EC_DRBG
| shiandow wrote:
| What insanity led someone to use 0 for the terminal object?
| pwdisswordfishz wrote:
| It makes some sense in the category of rings, but basically
| only there.
| cionx wrote:
| It's also the standard notation for zero objects, i.e., for
| terminal objects that are also initial. This entails all
| abelian/additive/preadditive categories, such as categories
| of modules, vector spaces, or abelian groups. (But there are
| also counterexamples, such as the categories of groups and of
| pointed sets.)
|
| But I'd agree that it's not standard notation to use 0 for a
| terminal object in an arbitrary category. I'd guess that most
| people use 1 instead, so that for example 1 x X [?] X. (The
| post talks about group objects in the category of algebraic
| varieties (over some field), in which case 1 seems to be more
| appropriate than 0.)
| mti wrote:
| The relevant category is really abelian group schemes
| (because DH necessarily works in a cyclic group), so 0 is
| quite reasonable.
| eximius wrote:
| So, addition under a particular elliptic curve is isomorphic to
| multiplication under integer modulo groups...
|
| But for some reason the author keeps referring to the underlying
| group as "Diffie-Hellman" instead of the process operating on
| some group.
|
| The result is interesting, the journey to get there was very
| confusing.
| tgma wrote:
| Not a cryptographer, but my expectation of the admitted-to-be-
| clickbait title would be to see a proof or some claim of that
| sort that characterizes traditional finite-field integer DH as a
| special case of ECDH. However, --and please correct me if I am
| wrong as I am not a cryptographer or a math wiz anymore-- my
| understanding is you could characterize both as instantiations of
| an abstract protocol on a cyclic group with some properties, so
| in that sense, they are siblings derived from a more general
| idea, not derivable from each other.
| cmrx64 wrote:
| isn't that how the article ends? maybe I don't understand what
| you mean
| tgma wrote:
| As I see it, the article describes something in that vein,
| but then immediately flips and reasserts the title, which
| suggests integer DH is a special case of ECDH, which does not
| seem a convincing characterization to me (it could be my
| misunderstanding; maybe someone could further clarify if it
| is conclusive).
| graybanana wrote:
| While not completely explained in the article, the author
| correctly notes that the non-singular points on a singular
| cubic curve over a finite field form a group (under the same
| elliptic curve group law) that is isomorphic (in an easily
| computable way) to either the multiplicative or additive group
| of a finite field.
|
| You can find more details in Silverman's book on elliptic
| curves, or if you don't have access to that, see Section 24.7
| in Lecture 24 of https://ocw.mit.edu/courses/18-783-elliptic-
| curves-spring-20....
|
| One could nitpick by pointing out that singular cubics are not
| elliptic curves (which are, by definition, smooth projective
| curves). One could also nitpick that the real reason you don't
| want to use DH in the multiplicative group of a finite field is
| that there is a known subexponential time algorithm that breaks
| DH in that setting (forcing > 3000-bit key sizes) whereas for
| elliptic curves the only known attacks take exponential time
| (and 256-bit keys are fine). But I don't think either of these
| nitpicks contradicts the author's thesis.
| mti wrote:
| While not mentioned by the author, there is an alternate
| reason why finite field DH can be seen as a special case of
| ECDH, kind of: namely, there exists special elliptic curves
| (actual, smooth projective curves) that do have an
| efficiently computable endomorphism to a suitable form of the
| multiplicative group, via pairings. This is in essence the
| MOV attack against the XTR cryptosystem. That doesn't fit
| neatly in OP's framework, though, because the map isn't a
| morphism of algebraic groups (it is efficient for other
| reasons), and it is cheating a little bit, because the
| inverse map isn't efficiently computable.
|
| Another point that the author glosses over a bit is that
| higher dimensional abelian varieties offer other instances of
| DH that are genuinely different from ECDH, and that are
| occasionally useful (mostly the case of Jacobians of
| hyperelliptic curves of genus 2). There isn't really a trick
| to make an arbitrary hyperelliptic curve DH/abelian variety
| DH instance a special case of ECDH: if anything, the
| relationship would be in the reverse direction.
| glitchc wrote:
| It's a nice article, just the title needs a small tweak to add
| the word practical, as in "There is no _practical_ DH... "
| ogogmad wrote:
| I think the article's point is that the notion of "groups" per se
| is too coarse for DH, because it abstracts away the data
| structure you use to represent the elements of the group.
| However, the notion of Algebraic Groups doesn't have this
| weakness, because it comes with an implied data structure: The
| data structure is tuples over finite fields, and the group
| operations are expressible as polynomials, which importantly are
| also algorithms. Done.
|
| It then turns out that if you search for the algebraic groups
| that you can use for DH, you end up looking for candidates within
| the 2 possible kinds of algebraic groups: linear algebraic groups
| and abelian varieties. Within the abelian varieties, it turns out
| that elliptic curves are both the simplest kind, while also being
| perfect for DH. Within the linear algebraic groups, the possible
| cyclic groups are just the additive and multiplicative ones: The
| additive ones are hopelessly insecure, while the multiplicative
| ones are just the unit groups of a field, which are special cases
| of elliptic curves anyway. So elliptic curves really are all you
| need for DH.
| vitalnodo wrote:
| Just wondering -- has anyone come across a course or resource
| that explores how cryptographic systems are built up from smaller
| building blocks?
|
| Like, using something like SageMath for algebraic structures, a
| prover like Lean to verify properties -- to get a feel for how
| things actually fit together.
|
| There's something cool about trying to reimplement known
| standards just to understand them better (with the usual "don't
| roll your own crypto" warning, of course). By the way, it would
| be nice to have a kind of sandbox for the more formal path to
| explore how to build my own SP-network, prove that the Decisional
| Diffie-Hellman assumption holds or something.
|
| I've seen cryptopals and cryptohack.
| moi2388 wrote:
| That'd indeed be nice to do.
| cmrx64 wrote:
| the types of arguments and proofs used in cryptography are
| notoriously difficult to mechanize, a little bit of lean isn't
| going to go get anywhere close to stating a security property.
|
| eg CryptHOL needs a ton of infrastructure, and in still very
| limited: https://eprint.iacr.org/2017/753.pdf
| oleganza wrote:
| When I learned crypto 5-10 years ago, it turned out that a lot
| of "building blocks" are mostly hacks. Looking back from 2020s
| we see that some of the standards that we use for the last
| 20-30 years can in principle be thrown out of the window (they
| can't for compatibility reasons, though) and replaced with much
| cleaner and more universal replacements.
|
| If we do not talk about modern exotic stuff (post-quantum
| crypto, zkSNARKS, homomorphic encryption), the 99% of everyday
| cryptography is based on two building blocks:
|
| 1. Symmetric crypto for ciphers and hash functions.
|
| 2. Algebraic group with "hard discrete log problem" for key
| exchange, signatures, asymmetric encryption and simple zero-
| knowledge proofs.
|
| Historically, these two categories are filled with a zoo of
| protocols. E.g. AES is a block cipher, but SHA(1,2) is a hash
| function.
|
| Today, you can roughly achieve everything of the above with two
| universal building blocks:
|
| - Keccak for all of symmetric crypto: it is suited both for
| encryption, hashing, duplex transcripts for ZK protocols etc.
|
| - Ristretto255 group based on Curve 25519: for diffie-hellman,
| signatures, key derivation, threshold schemes, encryption and
| more.
|
| The problem is that none of the described features is
| implemented in a turnkey standard, and we are still stuck using
| older crypto. Heck, even Git is using SHA-1 still.
|
| Then, after you have your building blocks, there are more hairy
| stuff such as application-specific protocols: TLS, Signal,
| PAKE/OPAQUE, proprietary hardware security schemes for full
| disk encryption and access controls etc.
| eXpl0it3r wrote:
| I'm absolutely clueless about crypto, isn't there also a
| trade-off between being mathematically superior and well
| optimized in software/hardware implementation?
| oleganza wrote:
| The tradeoff is not that simple (I wish it was :-).
|
| Usually it goes like that: someone made something useful
| optimised for a specific use-case with certain time (or
| competence) constraints, within a total lack of decent
| alternatives. Then people adopt and use it, it becomes the
| standard. Then people want to do more things with it, and
| try to build around that thing, or on top of that thing and
| Frankenstein monsters get born and also become standard.
|
| If you start from scratch you can do a crypto protocol that
| is both better designed (causes less UX pain and critical
| bugs) AND performs better on relevant hardware. Also do not
| forget that performance is easily solved by hardware:
| Moore's law and then custom hardware extensions are a
| thing.
|
| Example: Keccak is so much better from the composition
| perspective, that when used ubiquitously you'd definitely
| have ubiquitous hardware support. But if everyone continues
| to use a mishmash of AES and SHA constructions on the
| pretext of "Keccak" is not as fast, then we'd never move
| forward. People would continue building over-complicated
| protocols, bearing subpar performance and keeping the
| reputation of dark wizardry inaccessible for mere mortals.
| eXpl0it3r wrote:
| > Also do not forget that performance is easily solved by
| hardware: Moore's law
|
| "Just write slow algorithms, hardware will eventually get
| faster" doesn't really work when talking about
| performance implications _now_. If the hash algorithm
| used million of times doesn 't perform on current user
| hardware, then the algorithm is simply not a good fit.
|
| > and then custom hardware extensions are a thing.
|
| That's the kind of trade-off I eluded to as well. As a
| developer of a tool (e.g. git), I'd pick hash algorithms
| that do have hardware extensions on the most common
| hardware and not use something, that may eventually get
| hardware extensions.
|
| I guess developing such protocols right now for the
| future might still be advisable, but it seems odd to
| critic software that use well-optimized algorithms and
| fulfill the requirements.
| looofooo0 wrote:
| sha-1 in git was just supposed to catch corruption, it was
| never intended to be used for security.
| oleganza wrote:
| That's a valid point. However, modern hardware and crypto
| algorithms are fast enough that it pays off to have "do it
| all" protocols, with as little tradeoffs as possible.
|
| Example: Git users do need both corruption protection AND
| secure authentication. If authentication is not built in,
| it will have to be built around. Building around is always
| going to be more costly in the end.
|
| Unfortunately, 20-30 years ago considerations such as "sha1
| is shorter + faster" were taken seriously, plus all the
| crypto that existed back then sucked big time. Remember
| Snowden scandal in 2013? That, plus Bitcoin and blockchains
| moving towards mainstream brought about review of TLS,
| started SHA-3 competition. Many more brains turned to
| crypto since then and the new era began.
| hannob wrote:
| This is a justification that was made up after Git came
| under increasing criticism for its poor choise of a hash
| function after the shattered attack. It was already known
| that SHA-1 is weak before Git was invented.
|
| The problem is... it doesn't line up with the facts.
|
| Git has been using SHA-1 hashes for signatures since very
| early on. It also has claims in its documentation about
| "cryptographic security". It does not rigorously define
| what "cryptographic security" means, but plausibly, it
| should mean using a secure hash function without known
| weaknesses.
| looofooo0 wrote:
| Torvald claimed:
|
| So that was one of the issues. But one of the issues
| really was, I knew I needed it to be distributed, but it
| needed to be really, really stable. And people kind of
| think that using the SHA-1 hashes was a huge mistake. But
| to me, SHA-1 hashes were never about the security. It was
| about finding corruption.
|
| Because we'd actually had some of that during the
| BitKeeper things, where BitKeeper used CRCs and MD5s,
| right, but didn't use it for everything. So one of the
| early designs for me was absolutely everything was
| protected by a really good hash.
|
| https://github.blog/open-source/git/git-turns-20-a-qa-
| with-l...
| kbolino wrote:
| If this were true, then wouldn't MD5 have been the better
| choice?
|
| Also, SHA-1's preimage resistance (which still isn't
| broken) is necessary for the security of signed commits,
| regardless of the hash function used for the signature
| itself, since a commit object references its tree and
| predecessor commit by their SHA-1 hashes.
| aiaiaiaiaiaiai wrote:
| Really nice summary! Thank you.
| newpavlov wrote:
| >Keccak for all of symmetric crypto: it is suited both for
| encryption, hashing, duplex transcripts for ZK protocols etc.
|
| Unfortunately, Keccak and sponge constructions in general are
| inherently sequential. Even with hardware acceleration it
| heavily restricts possible performance. For example, AES-CBC
| encryption is 4-8 times slower than AES-CTR on high-end CPUs
| with AES-NI available. VAES makes the difference even bigger.
| Algorithms like AES-GCM, ChaCha20, and BLAKE3 are designed
| specifically to allow parallelization.
| oconnor663 wrote:
| Fwiw I don't think there's anything inherently sequential
| about the Keccak permutation itself. KangarooTwelve is a
| fully parallelizable hash built on Keccak. (Though they did
| use the sponge construction on the XOF side, so that part
| is serial.)
| newpavlov wrote:
| I meant the absorb and squeeze part. The permutation
| itself (or more specifically its round) could be
| efficiently implemented in hardware, but you can't mask
| latency by parallel application of the permutation. Yes,
| KangarooTwelve is an improvement in this regard, but the
| grandparent was talking specifically about Keccak/SHA-3.
| oleganza wrote:
| Sorry for lack of clarity, but i was saying "Keccak" and
| not "sha3" for that specific reason: it's a permutation
| building block suitable for a whole range of
| constructions - cshake, kangaroo etc. sha3 specifically
| is an overkill and unnecessary imho.
|
| CShake128 is much better replacement for hmac and sha512
| in (zk)proofs, while Kangaroo for things like FDE and
| massive volumes of data.
| aleph_minus_one wrote:
| > Unfortunately, Keccak and sponge constructions in general
| are inherently sequential.
|
| Couldn't you simply using BLAKE3 instead? To my knowledge
| BLAKE3 exactly was designed to solve this "parallelism
| problem" by combining the "cryptographic ideas" of BLAKE2
| with the binary tree structure of Bao (the latter was
| designed to make the hash construction easy to
| parallelize).
| rainsford wrote:
| How much does the lack of parallelization matter in
| practice though? Sure, AES-CTR can be parallelized, but the
| authentication function you're probably pairing it with
| likely can't. And in a lot of cases I'm aware of where
| encryption parallelism is important for performance (e.g.
| line-rate VPN encryption), you can achieve parallelism for
| the operation as a whole without achieving stream based
| parallelism. In the VPN example, even if you can't encrypt
| all the blocks in a single packet in parallel, you can
| probably achieve just as much parallelism speedup by
| encrypting multiple packets in parallel.
| k__ wrote:
| Not really, but I liked this one.
|
| https://github.com/nakov/practical-cryptography-for-develope...
| cvwright wrote:
| There are no proofs of the hardness of DDH or RSA etc. That's
| why they're called assumptions.
|
| OTOH if you want to win a Turing Award...
| AnotherGoodName wrote:
| Just to add to the above for clarity a proof that key based
| encryption isn't reversible requires a proof of P!=NP which
| hasn't been done.
|
| That may surprise people but we have no proof of the
| robustness of the encryption we use. In fact it might not
| work! Consider a one time pad for really extreme security
| needs. One time pads do have a proof (see the work of
| Shannon).
| gary_0 wrote:
| Shor's algorithm suggests that a lot of encryption _doesn
| 't_ actually work, but of course it requires a quantum
| computer that hasn't yet been built, and may not be
| practical to build, so fingers crossed. At least there are
| quantum-resistant encryption algorithms, and OTPs are still
| provably secure like you say.
| jhanschoo wrote:
| The author seems to be a busy person, but I would appreciate it
| if they would consider modifying their blog publishing software
| so that the math and definitions could be rendered in text and
| KaTeX instead of raster images.
| thaumasiotes wrote:
| What would that help with?
|
| I know KaTeX supposedly lets you copy-and-paste the text, but
| that won't get you text that is fit for any purpose.
| willvarfar wrote:
| (hopefully modern screen reading software is clever enough to
| OCR and summarise images as it does text.
|
| And if not, then that seems to be something that is now
| within reach of modern AI and just needs application.)
| thaumasiotes wrote:
| It wouldn't really matter; the image includes a lot of
| structure that isn't present in the text that KaTeX
| provides. A text-only screen reader will never produce
| anything but gibberish if you feed it KaTeX output.
|
| KaTeX will also style the text so that it visually
| resembles the image, stopping this problem from occurring
| for non-blind readers. You could have a screen reader that
| parsed all of the layout, but it seems like you might just
| as well OCR the image at that point.
| James_K wrote:
| The image does have LaTeX source as it's alt text, so
| should be at least somewhat understandable for screen
| readers.
| red_trumpet wrote:
| Better typography helps with reading. The same reason someone
| would complain if this was typed in Comic Sans. Also the
| images don't scale well, so if you look at this with a high
| resolution display, either the images are too small or not
| sharp.
| thaumasiotes wrote:
| Well, having gone and looked at the website, I'd have to
| agree that KaTeX would be an improvement, but not for
| reasons that relate to whether the math is rendered as an
| image.
|
| Rather:
|
| - The background of the math images is white, which doesn't
| match the background of the website;
|
| - The baseline of the text in the images is not aligned
| with the baseline of the surrounding text.
|
| I was imagining a more-competently-put-together website.
| rco8786 wrote:
| Random fun fact. Whit Diffie is cousin to the late country music
| singer Joe Diffie. Their Wiki pages make no mention of this,
| though they do mention the other's page in case users end up on
| the wrong one.
| tromp wrote:
| The plot at the bottom is of Y^2 = X^3 + X^2, not Y^2 = X^3 - X^2
| as stated.
| red_trumpet wrote:
| I don't get this article. They make a big fuss about looking for
| the right category, because apparently the category of groups
| cannot explain the difficulty of breaking Diffie-Hellman, since
| there is an isomorphism <g> -> Z/nZ. But the same isomorphism
| exists in the category of algebraic varieties! So was all in
| vain?
|
| To me this sounds a bit like an a-posteriori justification of why
| people use elliptic curves to do cryptography. This feels weird
| to me, as elliptic curves are a well-studied subject in algebraic
| geometry, whose history reaches back over 150 years to Clebsch.
| So when Victor Miller and Neal Koblitz proposed to do
| cryptography with them, they already knew very well about
| elliptic curves (both have a background in algebraic geometry of
| finite fields).
| graybanana wrote:
| I think the author's point is that while you might a priori
| think there are lots of groups out there that might be good
| candidates for DH, it turns out that elliptic curves are a
| strictly better choice than every alternative, and the reasons
| for this were definitely no fully known at the time Miller and
| Koblitz proposed ECC.
|
| There was a period during which there was lots of interest in
| using abelian varieties of higher dimension (arising as
| Jacobians of curves of higher genus), with dimensions g=3 and
| g=4 being particularly attractive because then you could work
| over a very computationally friendly base field like Fp with p
| = 2^61-1. But it turns out the discrete logarithm problem (and
| therefore DH) is strictly easier in these settings (one can
| exploit Weil restrictions to get an algorithm that is still
| exponential-time but strictly better than O(p^(g/2)). But this
| wasn't known until the 2000's.
|
| That leaves g=1 and g=2 as the best choices, and the group law
| is faster and simpler for g=1, and as far as I know nobody is
| really working on the g=2 case anymore (but there was a lot of
| activity in this area 10-20 years ago).
| cryptothrow101 wrote:
| I find it very hard to follow the overall reasoning, in
| particular due to the inconsistency around whether one should
| only consider algebraic structures up to isomorphism or not.
|
| For any n, there is only one finite cylic group of size n, up to
| isomorphism (namely Z/nZ). As the author mentions, there are
| concrete choices of finite cyclic groups (like Z/nZ) that make
| Diffie-Hellman insecure. Consequently, the security comes
| entirely from the choice of the _representation_ of the group
| elements (since the algebraic structure is the same, i.e., it is
| just a relabeled Z/nZ).
|
| In a similar spirit, people sometimes argue that Diffie-Hellman
| in some group G must be equally secure as in another group H,
| because the groups are isomorphic. This is unsound. In order to
| make such an argument sound, one needs to prove (or at least
| mention in case it is trivial) that one can _efficiently_ compute
| the isomorphism and its inverse.
| cdelsolar wrote:
| wtf did i just read
___________________________________________________________________
(page generated 2025-05-28 23:02 UTC)