Score:3

Why is an ephemeral key required to prove possession of a static private key in Key-Establishment Schemes

br flag

In the NIST 800-56A rev3 "Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography" in section 5.6.2.2.3.2 "Recipient Obtains Assurance [of the Static Private Key] Directly from the Claimed Owner (i.e., the Other Party)" it requires 2 conditions to be met during a key-agreement transaction for the "Public Key Recipient" to prove that the other party possesses the corresponding private key. Basically PKR needs to contribute an ephemeral key (condition 1) and confirm the agreed upon key is also shared by the other party (condition 2).

As far as I understand, as long as these 2 conditions are met we don't need to explicitly check the private key possession by other methods, i.e. no additional challenge/response is required, as the calculations already proves the possession. Then it lists the schemes that satisfy both conditions as all of the C(1e, 2s) and C(1e, 1s) schemes, but none of the C(2e, 2s) schemes with the requirement "shall employ one of the following".

Adding to the confusion, in the assumptions of C(1e, 2s) schemes it requires the assumption 6 "The recipient of a static public key has obtained assurance that its (claimed) owner is (or was) in possession of the corresponding static private key, as specified in Section 5.6.2.2.3." "shall be true".

My questions are:

  1. The key agreement calculations with key confirmation also proves the possession of the static private key, so there is no need to ask other questions to the other party, is this correct?
  2. C(2e, 2s) schemes with bilateral key confirmation should also satisfy the given conditions, right?
  3. It seems to me C(0e, 2s) schemes with bilateral key confirmation should also prove the possession of the static private key, why is the ephemeral key required?
Score:2
cn flag

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, I'll try to tackle your different questions in a different order as it makes more sense to me and should help with the global understanding of the underlying conditions:

Q.3

  1. It seems to me 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, when using 2 static keys and 0 ephemeral key, an attacker knowing only your private key, but not the other's party private key is able to compute the same shared secret as you.

The problem is somewhat hidden in the text, 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 you're getting confirmation about is really just that the derived secret is the same as yours, but not that the other party actually used their knowledge of the secret static key they claim to hold.

So here you're able to ensure there's no Person in the Middle tampering with your key agreement: you've both derived the same agreed upon key.

why is the ephemeral key required?

Because it's an ephemeral key that we just created, the other party won't know its corresponding ephemeral secret key (assuming an adversary with only knowledge of your static secret key).
So during key agreement, since you are combining your 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 you did using the ephemeral public key you sent them.

With an ephemeral key here is what's happening usually on your side:

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

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

(This is a summarised classical C(1e,2s) key agreement.)

Now, an adversary knowing your 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 you use an ephemeral key. But if you don't have an ephemeral key then you are only relying only on step 2 in step 3, and thus impersonation isn't detected in step 4.

This is really the gist 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.

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 your own secret static key.

Q.2

  1. C(2e, 2s) schemes with bilateral key confirmation should also satisfy the given conditions, right?

Yes, they usually do. They can actually satisfy to a much stronger version, where you also obtain assurance of the possession of the (claimed) secret ephemeral key. If you look at section 5.6.2.2.4, the C(2e, 2s) schemes that are satisfying the conditions 2 and 3 naturally satisfy the conditions 1 and 2 of 5.6.2.2.3.2.

Notice that only the DH and One Pass Unified model are quoted there, that's because as it is said in 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 your first question naturally follows from the details above:

  1. The key agreement calculations with key confirmation also proves the possession of the static private key, so there is no need to ask other questions to the other party, is this correct?

No it does not, it could also prove possession of your static private key instead. This is why we need the ephemeral key steps.

br flag
Thanks for the detailed response. If someone has my private key they can impersonate me for sure, but I never thought the possibility of the other way around, which makes sense. I also understand why Unified Model fails to provide KCI - since the attacker can generate its own ephemeral keys and easily calculate the secret - and why MQV succeeds - because the attacker needs either other party's static private key or my ephemeral private key.
br flag
Can't we provide KCI simply by signing the ephemeral public key with the static private key?
cn flag
@obareey Yes, we totally could, but adding a signature protocol to the mix wouldn't make things really simpler, also from an analysis point of view. Also it hurts "repudiation", because signatures are "binding" the ephemeral key to your long term static key, whereas an ephemeral key based scheme doesn't say which key was used to establish the agreed upon key: it could be the other party fabricating things all along (they cannot prove they didn't).
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.