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

51–60 of 67 posts

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

#51

Post by newpavlov »

oleganza wrote: post #25
vitalnodo wrote: post #16

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…

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…

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

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

#52

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

#53

Post by oconnor663 »

newpavlov wrote: post #51
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…

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

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

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

#54

Post by newpavlov »

oconnor663 wrote: post #53
newpavlov wrote: post #51

Earlier quoted context omitted.

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

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

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.

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

#56

Post by oleganza »

newpavlov wrote: post #54
oconnor663 wrote: post #53

Earlier quoted context omitted.

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

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.

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.

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

#57

Post by AnotherGoodName »

cvwright wrote: post #40
vitalnodo wrote: post #16

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…

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…

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

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

#58

Post by looofooo0 »

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…

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

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

#59

Post by mti »

graybanana wrote: post #44
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…

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.

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

#60

Post by gary_0 »

AnotherGoodName wrote: post #57
cvwright wrote: post #40

Earlier quoted context omitted.

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…

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

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.
Post reply on HN