Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman

keymaterial.net

Post reply on HN
Print view View original

41–50 of 67 posts

Re: There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman

#41

Post by red_trumpet »

thaumasiotes wrote: post #19
jhanschoo wrote: post #18

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.

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.

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.

Re: There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman

#42

Post by hannob »

looofooo0 wrote: post #29
oleganza wrote: post #25

Earlier quoted context omitted.

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, z…

sha-1 in git was just supposed to catch corruption, it was never intended to be used for security.

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.

Re: There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman

#43

Post by red_trumpet »

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 -> 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).

Re: There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman

#44

Post by graybanana »

tgma wrote: post #6

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 wi…

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.

Re: There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman

#45

Post by graybanana »

red_trumpet wrote: post #43

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 -> 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 crypt…

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).

Re: There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman

#46

Post by cryptothrow101 »

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.

Re: There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman

#47

Post by cesarb »

xyzzyz wrote: post #34
tgma wrote: post #13

Earlier quoted context omitted.

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…

> 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.

> 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.

Re: There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman

#48

Post by [deleted] »

looofooo0 wrote: post #29
oleganza wrote: post #25

Earlier quoted context omitted.

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, z…

sha-1 in git was just supposed to catch corruption, it was never intended to be used for security.

[deleted]

Re: There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman

#49

Post by [deleted] »

hannob wrote: post #42
looofooo0 wrote: post #29

Earlier quoted context omitted.

sha-1 in git was just supposed to catch corruption, it was never intended to be used for security.

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…

[deleted]

Re: There Is No Diffie-Hellman but Elliptic Curve Diffie-Hellman

#50

Post by kbolino »

looofooo0 wrote: post #29
oleganza wrote: post #25

Earlier quoted context omitted.

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, z…

sha-1 in git was just supposed to catch corruption, it was never intended to be used for security.

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.

Post reply on HN