Score:4

I don't see how a ECDH is useful

ph flag

I'm having a hard time understanding the usefulness of using an ECDH over traditional asymmetric encryption. Both parties have to exchange public keys to compute the ECDH, so why wouldn't they just encrypt their messages with the public keys they just exchanged?

The only use case for ECDH I can think of is if Alice loses her original message after sending it to Bob, with ECDH she can still decrypt it. But why would she lose it? This example seems too contrived for me.

Does anyone know any good examples/scenarios/use cases where ECDH shines/is required?

mu flag
Dan
For the moment ignoring authentication -- are you including ephemeral ECDH ("ECDHE") in your question? if so, imagine if Bob or Alice's private key is compromised. Now everything is discoverable, all history from the past. Same reason TLS1.3 did away with RSA for key transport. Look up forward secrecy & backward secrecy.
WizardOfMenlo avatar
ph flag
Another concern is that of efficiency. DH (and KEM mechanism in general) are usually used to establish a common shared secret, which then can be used with symmetric cryptography (which is usually orders of magnitudes faster). You can definitely use PKE to achieve the same thing (in fact, PKEs and KEMs are equivalent) but using a KEM directly is usually more natural. DH also can be done in a noninteractive manner, which is quite useful in complex async protocols such as Signal's
Score:9
my flag

I'm having a hard time understanding the usefulness of using an ECDH over traditional asymmetric encryption.

The only use case for ECDH I can think of is if Alice loses her original message after sending it to Bob, with ECDH she can still decrypt it.

Actually, the advantage of ECDH is exactly the opposite of that - it's so Alice (or Bob) can't decrypt the message later on.

That is, both Alice and Bob generate the ECDH private values, use it for that one exchange, and then zeroize them (and the symmetric keys as well) after the messages have been exchanged. Then, neither Alice nor Bob can recover the secret keys, and hence cannot decrypt the message.

Why is this an advantage? Suppose that one of the two sides were later subverted (either by a hacker or by a legal warrant) - in that case, the message is still secure. "Yes, judge, you have issued a warrant, but we literally do not have (and cannot get) the information you are asking for".

This property is known as Perfect Forward Secrecy; you can also obtain it by using public key encryption (generating a public/private keypair prior to the exchange and deleting the private key afterwards) - however, that approach has no particular advantage over ECDH.

Maarten Bodewes avatar
in flag
Isn't the fact that key pair generation is efficient for DH and ECDH the main difference? Forward security is all nice, but if the server or client has to generate a 4K RSA key pair for each key establishment then the efficiency of the protocol could become problematic.
poncho avatar
my flag
@MaartenBodewes: yes, with RSA, it's be expensive - however, if you wanted to, you could do it with (say) ElGammal...
Score:4
ng flag

ECDH is known as a Key Encapsulation Mechanism, which as you mention is similar to public key encryption, but not the same. There are many reasons to prefer KEMs, I will quickly mention one. First, note that a KEM is (formally) a tuple of three algorithms $(\mathsf{KGen}, \mathsf{Encaps}, \mathsf{DCaps})$, where

  1. $\mathsf{KGen}$ takes as input some security parameter $1^\lambda$, and outputs a keypair $(sk, pk)$

  2. $\mathsf{Encaps}$ takes as input a public key $pk$ (and perhaps some randomness, which is often only implicit), and returns a pair $(k, c)$ of a derived key $k$, and "ciphertext" $c$

  3. $\mathsf{Decaps}$ takes as input a secret key $sk$ and "ciphertext" $c$, and outputs another derived key $k'$.

The KEM is correct if $k = k'$ in the end, e.g. the two derived keys agree. The security notion of KEMs is similar to that of PKE, meaning there is a natural way to extend the traditional notions of IND-CPA/IND-CCA security.

Note that one can build a KEM using any PKE, by having $\mathsf{Encaps}_{pk}(r) = \mathsf{Enc}_{pk}(r)$, where $r$ is the randomness used by the KEM (this is the "encrypt uniformly random keys" idea you mentioned). Maybe we should explicitly write $\mathsf{Enc}_{pk}(f(r))$ is some function of the randomness --- I will not bother being this explicit.

So why care about KEMs? While there are other things you can mention, a major point is that there are certain properties that "natural" KEMs (such as ECDH) have that a KEM constructed from the "encrypt random keys" approach do not have. This is to say that ECDH is not "just" a KEM, and can be used in applications where encrypting random keys does not work.

Perhaps the most obvious property to point to is "non-interactivity". In particular, ECDH can be written as

  1. both parties exchanging a diffie hellman keypair $(g, g^{s_i})$, and then
  2. computing some simple function of these key-pairs.

If we try to write this with the syntax of a KEM, we might say that $\mathsf{KGen}(1^\lambda)$ produces one key-pair $(g, s_0, g^{s_0})$, and that $\mathsf{Encaps}_{g^{s_0}}(r) = (g, s_1, g^{s_1})$ produces another key-pair, where we model the "ciphertext" as $g^{s_1}$. This has a very curious property though --- $g^{s_1}$, the "ciphertext" of the scheme, does not depend on the public key at all (besides via the group generator $g$, which can be standardized as a public parameter).

This is a quite surprising property, and one that the "encrypt a random key" scheme does not have. It is known as being a Non-interactive Key Exchange (NIKE) scheme. The property is both

  1. useful in practice --- Signal's "double ratchet" uses this property in a key way, which makes it hard to "drop in" another KEM to use for signal, and

  2. theoretically non-trivial --- generically constructing NIKE requires some fancy primitive such as FHE/Functional encryption. There are known results that show that it is probably not possible to build NIKE using lattices (and plausibly codes) with "small parameters".

In fact (excluding lattice-based schemes with large parameters), I am only aware of one post-quantum NIKE, namely CSIDH. This is to say a straightforward modification of Signal to be post-quantum either

  • uses CSIDH,
  • uses a less-efficient variant of a NIST PQC scheme (say a lattice-based scheme with small parameters), or
  • modifies the Signal protocol itself in some way, usually with some efficiency hit.

While there are more nuanced things you can say to compare PKE and KEMs, theoretically there is a very large benefit to ECDH --- it is an efficient NIKE, which are not very common at all.

Marc Ilunga avatar
tr flag
Nice answer with details on KEMs. I am however confused as to how ECDH fits the KEM paradigm. It is not clear how correctness is defined here
Mark avatar
ng flag
If you want ECDH to be a NIKE, you need to model that you have some cryptographic group $(G, g)$ standardized as public parameters, and add a final post-processing step where $k= KDF(g^{s_0}, g^{s_1}, g^{s_0s_1})$ for some key-derivation function $KDF$. I omitted this as it is "straightforward" in the case of ECDH. Note that correctness of KEMs becomes less straightforward when dealing with primitives such as code/lattice-based KEMs --- they are generally only "statistically correct", e.g. correct with probability $\geq 1-\delta$ for very small $\delta$.
Mark avatar
ng flag
This is a significant difference, as (especially against active adversaries) there are certain "error-boosting" attacks available in this setting that are not available in the setting of perfectly correct KEMs.
Maarten Bodewes avatar
in flag
"ECDH is known as a Key Encapsulation Mechanism" Huh? Isn't ECDH known as a key agreement algorithm? Sometimes I wonder if cryptographers understand normal language. If ECDH algorithm doesn't encapsulate anything, then it cannot be an encapsulation mechanism, right?
Mark avatar
ng flag
@MaartenBodewes unfortunately, the [terminology is standard](https://en.wikipedia.org/wiki/Key_encapsulation_mechanism). And KEMs can be used for key exchange, but they are named separately from PKE (which can also be used) to emphasize the syntactic difference between the two --- in one, you can "choose the secret key", in the other, you cannot.
kelalaka avatar
in flag
I agree with @MaartenBodewes on this. There is no key encapsulated, only part of the key construction information. So DH is a key agreement. If one refers to [this](https://info.isl.ntt.co.jp/crypt/eng/psec/dl/iso/psec-kem_v2.2_20080414e.pdf), well not a good document.
Mark avatar
ng flag
Yes, but if one refers to the research surrounding the NIST PQC standardization (which has half of its goal to standardize a KEM/PKE), the terminology KEM is standard. See for example [this influential paper of Hofheinz et al](https://eprint.iacr.org/2017/604.pdf), which focuses on handling the case of "non-perfect correctness" I alluded to 2 comments ago.
meshcollider avatar
gb flag
I think being a KEM alone is a weaker notion. For example, ECDH provides implicit authentication of the sender/encapsulator's public key, whereas generally a KEM does not (the only input is the receiver's public key). [This paper](https://eprint.iacr.org/2019/1356) introduces split-KEM for this reason, and claims CSIDH *might* satisfy the security assumptions, but doesn't make a claim of it.
Maarten Bodewes avatar
in flag
@Mark NIST currently only seems to evaluate KEM's, although one KEM is derived from a key agreement mechanism similar to DH.
cn flag
@MaartenBodewes KEMs and 2-message key agreement are for all intents and purposes the same thing.
Maarten Bodewes avatar
in flag
No key agreement is not KEM. Sheesh. And it is called TMKE where E is for Establishment when talking about the generic idea.
President James K. Polk avatar
sh flag
ECDH is not a key encapsulation mechanism.
cn flag
@MaartenBodewes Yes, every two message key agreement is also a key encapsulation mechanism. The first message is the public key, the second message is the ciphertext. And conversely every key encapsulation mechanism is also a two message key agreement. That you apparently don't like the term doesn't change that at all.
Maarten Bodewes avatar
in flag
If it uses ciphertext to encapsulate a master key then I agree. I don't agree when a master key is generated from the public / private keys, usually followed by a KDF, which is *definitely* the case for ECDH (to bring it back to the answer).
cn flag
Then you do not know the definition of a KEM. ‍♂️
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.