4
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Dan
    Mar 14 at 20:11
  • 2
    $\begingroup$ 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 $\endgroup$ Mar 14 at 21:35

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
15
  • 7
    $\begingroup$ "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? $\endgroup$
    – Maarten Bodewes
    Mar 14 at 22:42
  • 1
    $\begingroup$ @MaartenBodewes unfortunately, the terminology is standard. 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. $\endgroup$
    – Mark
    Mar 14 at 23:18
  • 5
    $\begingroup$ 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, well not a good document. $\endgroup$
    – kelalaka
    Mar 14 at 23:22
  • 1
    $\begingroup$ 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 introduces split-KEM for this reason, and claims CSIDH might satisfy the security assumptions, but doesn't make a claim of it. $\endgroup$ Mar 14 at 23:41
  • 2
    $\begingroup$ No key agreement is not KEM. Sheesh. And it is called TMKE where E is for Establishment when talking about the generic idea. $\endgroup$
    – Maarten Bodewes
    Mar 15 at 21:54
9
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Mar 14 at 22:46
  • $\begingroup$ @MaartenBodewes: yes, with RSA, it's be expensive - however, if you wanted to, you could do it with (say) ElGammal... $\endgroup$
    – poncho
    Mar 14 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.