4
$\begingroup$

In the NIST 800-56A rev3 "Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography" in section 6.1.1.2 "(Cofactor) Full Unified Model, C(2e, 2s, ECC CDH) Scheme" the shared secret is calculated as follows:

Party U Calculates:

  1. $Z_s = d_{s,U} Q_{s,V}$
  2. $Z_e = d_{e,U} Q_{e,V}$
  3. $Z = Z_s || Z_e$

Party V Calculates:

  1. $Z_s = d_{s,V} Q_{s,U}$
  2. $Z_e = d_{e,V} Q_{e,U}$
  3. $Z = Z_s || Z_e$

where $d_{s,X}, Q_{s,X}$ are the static private and public keys of party $X$ respectively and $d_{e,X}, Q_{e,X}$ are the ephemeral private and public keys of party $X$ respectively.

However, this scheme is vulnerable to "Key Compromise Impersonation" (KCI) attacks. This means if someone obtains $d_{s,U}$, they can impersonate any other party to $U$. The same is true for $V$. This is also acknowledged in the NIST publication and also see here for more details.

As far as I can see, if we cross calculate the shared secrets as follows:

Party U Calculates:

  1. $Z_1 = d_{s,U} Q_{e,V}$
  2. $Z_2 = d_{e,U} Q_{s,V}$
  3. $Z = Z_1 || Z_2$

Party V Calculates:

  1. $Z_2 = d_{s,V} Q_{e,U}$
  2. $Z_1 = d_{e,V} Q_{s,U}$
  3. $Z = Z_1 || Z_2$

we can prevent KCI attacks without compromising any other assurance given by the scheme.

I understand that this breaks the symmetry between parties, i.e. now both parties must know which role they are in. But in my mind this would be a much simpler scheme if parties already know their roles, which is implicitly assumed for some other schemes by the way.

So, my question is, am I missing something here? Has this scheme got all the assurances given in "Table 23: Summary of assurances"?

$\endgroup$
0

2 Answers 2

3
+25
$\begingroup$

The proposed protocol looses the Forward Secrecy that the original protocol offers. Recall that's defined in NIST SP 800-56A Rev. 3 as

Forward Secrecy (FS): Assurance obtained by one party in a key-agreement transaction that the keying material derived during that transaction is secure against the future compromise of the static private key-agreement keys (if any) of the participants.

Notice that with the static private keys $d_{s,U}$ and $d_{s,V}$, and a transcript of a transaction of the proposed protocol (which will include $Q_{e,U}$ and $Q_{e,V}$), we can compute $$Z:=(d_{s,U}\,Q_{e,V})\mathbin\|(d_{s,V}\,Q_{e,U})$$


Proposition to get the best of the two protocols, while remaining symmetric.

Party $U$ does

  • $Z_s:=d_{s,U}\,Q_{s,V}$
  • $Z_e:=d_{e,U}\,Q_{e,V}$
  • $Z_{1,U}:=d_{s,U}\,Q_{e,V}$
  • $Z_{2,U}:=d_{e,U}\,Q_{s,V}$
  • $Z:=Z_s\mathbin\|Z_e\mathbin\|\min(Z_{1,U},Z_{2,U})\mathbin\|\max(Z_{1,U},Z_{2,U})$

and the other party $V$ does

  • $Z_s:=d_{s,V}\,Q_{s,U}$
  • $Z_e:=d_{e,V}\,Q_{e,U}$
  • $Z_{1,V}:=d_{s,V}\,Q_{e,U}$
  • $Z_{2,V}:=d_{e,V}\,Q_{s,U}$
  • $Z:=Z_s\mathbin\|Z_e\mathbin\|\min(Z_{1,V},Z_{2,V})\mathbin\|\max(Z_{1,V},Z_{2,V})$

$Z$ is shared, can be used for session key derivation, and I think this is KCI secure. Aside from side channel issues (which are manageable), and computational cost about doubled, I don't see any drawback compared to the original protocol.

$\endgroup$
3
  • $\begingroup$ I'm not decided about if we can get away with the slightly simpler $Z:=Z_s\mathbin\|Z_e\mathbin\|(Z_{1,U}\oplus Z_{2,U})\\\quad=Z_s\mathbin\|Z_e\mathbin\|(Z_{1,V}\oplus Z_{2,V})$ $\endgroup$
    – fgrieu
    May 31, 2023 at 7:22
  • $\begingroup$ Thanks for the response. You are right, I didn't think about FS. But I think we can get away without calculating $Z_s$ in your proposition. What do you think? PS: There is a small typo in $Z_{1,V}$ and $Z_{2,V}$ calculations. The private keys must belong to $V$. $\endgroup$
    – obareey
    May 31, 2023 at 9:31
  • $\begingroup$ @obareey: I fixed the typo, thanks. Your proposal to remove $Z_s$ makes sense; I'll think about it. But I lack a scientific method to decide if a protocol is safe! $\endgroup$
    – fgrieu
    May 31, 2023 at 9:42
2
$\begingroup$

The way one avoids KCI attacks in C(2e, 2s) is to obtain assurance of the possession of a private static key as per Section 5.6.2.2.3.

In NIST SP 800-56A Rev. 3, this is unfortunately not considered necessary and therefore not part of their schemes, because in their description of the C(2e, 2s) schemes, they assume it was done, see Section 6.1.1 where they say it is an assumption that:

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

The typical way of performing such validation is just like explained in Section 5.6.2.2.3 (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.)

But as you've pointed out, both FFC DH and ECC CDH C(2e, 2s) schemes are not mixing the ephemeral keys with the static keys and so are vulnerable to KCI attacks unless the assurance of the possession of the private static key was obtained prior to running them, which is assumed. This is why they don't need to do anything fancy to mix ephemeral keys and static keys to achieve it.

Real world protocols (e.g. Signal's protocol) typically achieve this by signing ephemeral keys using the static keys during the ephemeral key exchange. Then you cannot sign your public ephemeral key without knowledge of the static secret key, and therefore you cannot impersonate someone to the first party by only knowing this party's private static key.

$\endgroup$
2
  • $\begingroup$ Thank you for the response. If we sign the ephemeral keys using the static keys, then there is no need to calculate $Z_s$? As far as I understand, this is how (mutual) TLS 1.2 works, i.e. the parties use the static keys only for signing the ephemeral keys to validate their identities (prove the possession of static private keys), but the shared secret is calculated only with the ephemeral keys. $\endgroup$
    – obareey
    Jun 1, 2023 at 16:40
  • $\begingroup$ Correct. On a related note, have you checked the Noise Protocol framework? It allows some nice analysis of such exchanges, including visualizations with the Noise Explorer $\endgroup$
    – Lery
    Jun 5, 2023 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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