If you’re an applied cryptographer or a developper working on implementing key agreements, it’s very likely that you’ll stumble upon the well known NIST 800-56A rev3 “Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography” document that explains in details how to do things properly to have “secure” key establishments.

Reading between the lines

In that document, in section 5.6.2.2.3.2 (I love these sub-sub-sub-sub-sub-sections) it notably says: “Recipient Obtains Assurance [of the Static Private Key] Directly from the Claimed Owner (i.e., the Other Party)” and proceeds with 2 conditions to be met during a key-agreement for the “Public Key Recipient” to ensure that the other party possesses the corresponding private key:

  1. The recipient of the static public key contributes an ephemeral public key to the key-agreement process, one that is intended to be arithmetically combined with the claimed owner’s (i.e., the other party’s) static private key in computations performed by the claimed owner. (If an appropriate key-agreement scheme is employed, the claimed owner will be challenged to demonstrate current knowledge of his static private key by successfully performing those computations during the transaction.)
  2. The recipient of the static public key is also a key-confirmation recipient, with the claimed owner (i.e., other party) serving as the key-confirmation provider. (By successfully providing key confirmation, the claimed owner can demonstrate ownership of the received static public key and current knowledge of the corresponding static private key.)

Basically these say that you need to contribute an ephemeral key (condition 1) and confirm the resulting agreed upon key is the same for the other party (condition 2).

So that section is basically saying that when these 2 conditions are met in a key agreement protocol, we don’t need to explicitly check the private key possession by the other party using any other mean, i.e. no extra challenge/response protocol or so, because the computations done during key agreement already prove the claimed possession. It also lists the schemes that satisfy both conditions as all of the so-called $C(1e, 2s)$ and $C(1e, 1s)$ schemes, but none of the $C(2e, 2s)$ schemes are listed in that section…

$C(Xe,Ys)$
In case you’re wondering, the $C(Xe,Ys)$ notation is just a way to classify these key agreement schemes depending on the number $X$ of ephemeral keys $e$ and the number $Y$ of static keys $s$ involved in the scheme.

A few question that can arise from this are:

  1. Why don’t the key agreement computations with key confirmation prove possession of the static private key already?
  2. Why don’t $C(2e, 2s)$ schemes with bilateral key confirmation satisfy the given conditions?
  3. It could seem like $C(0e, 2s)$ schemes with bilateral key confirmation should also prove the possession of the static private key, why is the ephemeral key required?

To prevent KCI attacks!

Well, these are excellent questions to ask and one of the kind of attacks that we are trying to prevent here with such mechanisms is called “Key Compromise Impersonation”, where a party obtained your private key (not the other party’s) and is trying to impersonate other parties to you.

Now, let me tackle these questions in the reverse order as it makes more sense to me and should help with the global understanding of the underlying conditions:

Q.3

  1. It could seem like $C(0e, 2s)$ schemes with bilateral key confirmation should also prove the possession of the static private key, why is the ephemeral key required?

No, because when using 2 static keys and 0 ephemeral key, an attacker knowing only our private key, but not the other’s party private key is able to compute the same shared secret as us!

The problem is somewhat hidden in the text we people digging, e.g. in 6.3.3.3 it says:

The successful completion of the key-confirmation process provides each party with assurance that the other party has derived the same secret Z value

So, what we’re getting confirmation about is really just that the derived secret is the same as ours, but not that the other party actually used their knowledge of the secret static key they claim to hold.

So here we’re able to ensure there’s no “Person in the Middle” tampering with our key agreement: we’ve both derived the same agreed upon key.

why is the ephemeral key required?

That’s really the gist of this article, right?

Well, because it’s an ephemeral key that we are creating, the other party can’t know its corresponding ephemeral secret key (e.g. assuming our adversary hasn’t gained persistent access to our device). So during key agreement, since we are combining our secret ephemeral key with their (claimed) public static key, if they don’t know their (claimed) secret static key they won’t be able to perform the same derivation as we did using the ephemeral public key we sent them.

With an ephemeral key here is what’s happening usually on our side:

  1. we combine your ephemeral secret key with their (claimed) static public key, we get a secret $Z_e$
  2. we combine your static secret key with their (claimed) static public key, we get a secret $Z_s$
  3. we use both $Z_e$ and $Z_s$ in our derivation process to get the final shared secret $Z$
  4. we use a key confirmation process to ensure we both derived the same shared secret $Z$.

And the other party is doing more or less the same, but they are using our public ephemeral key instead.

(This is a summarised classical $C(1e,2s)$ key agreement, other ones with ephemeral keys work similarily.)

Now, an adversary knowing our secret key is able to mimic step 2, but cannot mimic step 1, thus cannot perform step 3 correctly and will get caught in step 4, if we use an ephemeral key. But if we don’t have an ephemeral key then we are relying only on step 2 in step 3, and thus impersonation isn’t detected in step 4 because they could derive the same key as us without knowing the (claimed) secret static key.

This is really the main point of what’s being said in 5.6.2.2.3.2 first condition (emphasis mine):

  1. The recipient of the static public key contributes an ephemeral public key to the key-agreement process, one that is intended to be arithmetically combined with the claimed owner’s (i.e., the other party’s) static private key in computations performed by the claimed owner. (If an appropriate key-agreement scheme is employed, the claimed owner will be challenged to demonstrate current knowledge of his static private key by successfully performing those computations during the transaction.)

This means that step 1 and 3 needs to occur in my above example.

And then we have the second condition:

  1. The recipient of the static public key is also a key-confirmation recipient, with the claimed owner (i.e., other party) serving as the key-confirmation provider. (By successfully providing key confirmation, the claimed owner can demonstrate ownership of the received static public key and current knowledge of the corresponding static private key.)

This basically means that step 4 must occur, hence providing the assurance that the key derivation process was carried as expected and thus providing assurance that the step 1 couldn’t be “faked” by someone not knowing the secret static key of the received static public key, but instead our own secret static key.

Q.2

Why don’t $C(2e, 2s)$ schemes with bilateral key confirmation satisfy the given conditions?

Well, they usually do!

They can actually satisfy to a much stronger version, where we also obtain assurance of the possession of the (claimed) secret ephemeral key ontop of that of the (claimed) secret static key. If we look at section 5.6.2.2.4, we can see the following:

  1. The recipient of the ephemeral public key also receives a static public key that is presumed to be owned by the other party and is used in the key-agreement transaction. (Therefore, the other party is the claimed owner of both the received static public key and the received ephemeral public key.)
  2. The recipient of the static and ephemeral public keys contributes its own (distinct) ephemeral public key to the key-agreement process, one that is intended to be arithmetically combined with the private key corresponding to the received ephemeral public key in computations performed by the claimed owner of the received static and ephemeral public keys. (If an appropriate key-agreement scheme is employed, the claimed owner of the received public keys will be challenged to demonstrate current knowledge of his ephemeral private key by successfully performing those computations during the transaction.)
  3. The recipient of the static and ephemeral public keys is also a key confirmation recipient, with the claimed owner of the received public keys serving as the key-confirmation provider. (By successfully providing key confirmation, the claimed owner of the received public keys can demonstrate that he is the owner of the received static public key and that he knows the ephemeral private key corresponding to the received ephemeral public key.)

And we can see that the $C(2e, 2s)$ schemes that are satisfying these conditions 2 and 3 naturally satisfy the conditions 1 and 2 of the previous section 5.6.2.2.3.2.

Notice that only the Diffie-Hellman and One Pass Unified model schemes are quoted there, that’s because as it is said in section 7.1 (emphasis mine):

If an MQV scheme (MQV2 or Full MQV) will be employed during a transaction with an adversary who is in possession of a compromised static private key (or a compromised implicit signature corresponding to that static private key), the adversary is limited to masquerading as the owner of the compromised key pair (or as the owner of the static key pair corresponding to the compromised implicit signature). The use of the Full Unified model or dhHybrid1 scheme, however, offers the adversary additional opportunities for masquerading: If an adversary compromises an entity’s static private key, then the adversary may be able to impersonate any other entity during a Full Unified model- or dhHybrid1-based key-agreement transaction with that entity.

The MQV schemes in their “two passes” forms are already resistant to these Key Compromise Impersonation attacks and do not require the extra step that the DH-based or Full Unified model-based schemes do, which are detailed in 5.6.2.2.3.2 and 5.6.2.2.4. This is presumably why they are not explicitly quoted in 5.6.2.2.4.

Q.1

And eventually I think the answer to our first question naturally follows from the above:

  1. Why don’t the key agreement computations with key confirmation prove possession of the static private key already?

No it does not, it could also prove possession of our own static private key instead. This is why we need the ephemeral key steps: to avoid a Key Compromise Impersonation attack against our (long term) static keys.