# Diffie-Hellman key agreement with both Server Authentication and Perfect Forward Secrecy

I am trying to find the protocol with the least overhead, which still meets the following requirements:

• Server Authentication of server identity to client. The client has an authentic copy of the server long term public key.
• Perfect Forward Secrecy.
• Confidentiality, integrity, authenticity of payload, including:
• Replay protection.
• As little clear text Handshake and Header data as possible, to aid application specific implementations of traffic analysis counter measures.
• The protocol operates over TCP (or equivalent, or higher). Serialization of messages is assumed. In particular, both sides are presumed to maintain a state that, at all times, unequivocally determines which content encryption key to use for decrypting any packet that arrives from the other side.
• No Client Authentication of client identity to server. This is presumed to be done by the protected application layer, if necessary.
• The Client and Server share fixed, implementation specific security parameters, including Diffie-Hellman domain parameters, KDF and AE algorithm choices etc. However, these parameters might differ between different implementations.

I have seen the CurveCP protocol, which appears to have slightly different design criteria.

This is what I came up with:

$Label_i$ denotes a fixed, implementation specific octet string. Different labels will be used for key derivation at different steps in the protocol.

All protocol messages have a header that consist only of a protocol version field and a length field. Both are included as authenticated data in the MAC calculation if the message is encrypted.

The long term key pair of the server is denoted $S^0$.

1. $Client$: Generate ephemeral key pair $C^1_{publ}, C^1_{priv}$
2. $Client \rightarrow Server$: $Hello_C^1 \leftarrow C^1_{publ}$
3. $Server$: Verify that $C^1_{publ}$ is not congruent to 0, 1 or -1, and that it belongs to the right subgroup.
4. Both $Client$ and $Server$: Calculate the intermediate shared secret $M^1_{tmp}$ from $S^0$ and $C^1$. Calculate $k_{tmp} \leftarrow KDF(M^1_{tmp},Label_0)$
5. $Server$: Generate ephemeral key pair $S^1_{publ}, S^1_{priv}$.
6. $Server \rightarrow Client$: $Hello_S^1 \leftarrow AE_{k_{tmp}}(S^1_{publ})$
7. $Client$: Verify and decrypt $Hello_S^1$. Verify that $S^1_{publ}$ is not congruent to 0, 1 or -1, and that it belongs to the right subgroup.
8. Both $Client$ and $Server$: Calculate the shared secret $M^1$ from $S^1$ and $C^1$.
9. Both $Client$ and $Server$: Calculate $k^1_S \leftarrow KDF(M^1,Label_1)$ and $k^1_C \leftarrow KDF(M^1,Label_2)$
10. Both $Client$ and $Server$: Set $Ctr_S \leftarrow 0$ and $Ctr_C \leftarrow 0$
11. ... $Client \rightarrow Server$: $Packet_{Ctr_C} \leftarrow AE_{k^1_C}(Ctr_C||"m"||Message)$
12. ... $Server \rightarrow Client$: $Packet_{Ctr_S} \leftarrow AE_{k^1_S}(Ctr_S||"m"||Message)$

... later rekey before the counters wrap around to zero, as follows:

1. $Client$: Generate ephemeral key pair $C^i_{publ}, C^i_{priv}$
2. $Client \rightarrow Server$: $Hello_C^i \leftarrow AE_{k^{i-1}_C}(Ctr_C||"hello"||C^i_{publ})$
3. $Server$: Verify and decrypt $Hello_C^i$. Verify that $C^i_{publ}$ is not congruent to 0, 1 or -1, and that it belongs to the right subgroup.
4. Both $Client$ and $Server$: Calculate the intermediate shared secret $M^i_{tmp}$ from $S^{i-1}$ and $C^i$. Calculate $k_{tmp} \leftarrow KDF(M^i_{tmp},Label_0)$
5. $Server$: Generate ephemeral key pair $S^i_{publ}, S^i_{priv}$.
6. $Server \rightarrow Client$: $Hello_S^i \leftarrow AE_{k_{tmp}}(S^i_{publ})$
7. $Client$: Verify and decrypt $Hello_S^i$. Verify that $C^i_{publ}$ is not congruent to 0, 1 or -1, and that it belongs to the right subgroup.
8. Both $Client$ and $Server$: Calculate the shared secret $M^i$ from $S^i$ and $C^i$.
9. Both $Client$ and $Server$: Calculate $k^i_S \leftarrow KDF(M^i,Label_1)$ and $k^i_C \leftarrow KDF(M^i,Label_2)$
10. Both $Client$ and $Server$: Set $Ctr_S \leftarrow 0$ and $Ctr_C \leftarrow 0$

...etc.

Does this protocol meet the requirements, or is something missing?

• You're leaving out of the description many important details that are relevant to the protocol security, such as how the message length is sent. Is it encrypted? How? Is is sent in clear text? How is padding specified? It's specified by the AE method used or by any other means? – SDL Mar 11 '13 at 22:08
• Step 4 is ambiguous, as some other steps. IMHO you should write a technical paper and publish it. Even in that case, analyzing a transport protocol is not an easy task, so it's rarely done for free. – SDL Mar 11 '13 at 22:09
• Thank you for you comments. Regarding step 4, Diffie-Hellman works like this: Client calculates $M^1_{tmp} \leftarrow (S^0_{publ})^{C^1_{priv}}$ and server calculates $Mî_{tmp} \leftarrow (C^1_{publ})^{S^0_{priv}}$ – Henrick Hellström Mar 11 '13 at 23:29
• @HenrickHellström I'm curious. If I understand correctly then step 5-8 are there in order to prevent replay attacks. Why not simply return a nonce in the clear from the server, that is mixed with the shared secret to produce the symmetric key? – Nuoji Jun 28 '13 at 23:19
• @Nuoji: No, step 5-8 are there to provide perfect forward secrecy, as well as prevent replay attacks. – Henrick Hellström Jun 28 '13 at 23:46

$Adversary\:$ receives $C^1_{publ}$

$Adversary\:$ adaptively queries an oracle that implements:
take $C^2$ as input, generate $S^1_{publ}$, set $\: k_{adv} = KDF\left(\left(C_2\right)^{S^0_{priv}},label_0\right) \:$, $\:$ output $\: AE_{k_{adv}}\left(S^1_{publ}\right)$

Note that $\:Adversary\:$ can (with, heuristically, overwhelming accuracy) test whether or not a given
value was used as $k_{adv}$ on a given query to that oracle (since the encryption is authenticated).

$Adversary\:$ guesses $k_{tmp}$ and then runs the rest of the protocol with $\:Client\:$.
If the guess was correct, then $\:Client\:$ will accept with $k_S$ and $k_C$ known to $\:Adversary\:$.

(There is slightly more that the adversary can do, which I'll
explain if you don't think the above justifies my next sentence)

It seems that it would be very difficult to prove security against the above sort of attack
without proving that even if the oracle instead outputs [if $\: C^2 = C^1_{publ} \:$ then $\perp$ else $k_{adv}$],
it would still be infeasible to distinguish $k_{tmp}$ from a randomly chosen key.
That is the analogue of CCA2 security for Diffie-Hellman+your-KDF.

You could reduce the main security assumption to KDF-Diffie-Hellman by having
$Server$'s$\:$ long term key pair be for signatures, replacing the step 6 message with
$S^1_{publ}\;||\;\text{sign}_{S^0_{priv}}\left(C^1_{publ}\:||\:S^1_{publ}\right)\;$, $\;\;$ and then removing step 4 and the "decrypt" part of step 7.

Both of these methods use two messages, and I will assume they are done using Elliptic Curves
and that the $AE$ in step 6 of yours does not include an IV (since the plaintext has high min-entropy,
and that particular plaintext doesn't actually need to be confidential). $\;\;$ In both of these protocols,
the length of the first message is $\:2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k\:$,$\:$ where $k$ is the (confidentiality) security parameter.
In your protocol, the length of the second message if $\:(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k)+\sigma\:$,$\:$ where $\:Adversary$
has a trivial attack that will violate explicit authentication with probability $1/(2^{\sigma})$
and cause $\:Client\:$ to reject otherwise. $\;\;$ In my protocol, the length of the second
message is $\:(2\hspace{-0.03 in}\cdot\hspace{-0.03 in}k)+(4\hspace{-0.035 in}\cdot\hspace{-0.03 in}k_{\hspace{.01 in}0})\:$,$\;$ where $\hspace{.02 in}k_{\hspace{.01 in}0}\hspace{.01 in}$ is the authentication security parameter.

• I think you might have to spell out the steps involved in this attack. The presumption is that $Adversary$ might see $C^1_{publ}$, but not $C^1_{priv}$. How does $Adversary$ make $Client$ perform step 4 based on $S^0_{publ}$ and $Adv^1_{priv}$, which seems to be necessary in order for the client to perform step 7 without failure, given that the step 6 has been injected by $Adversary$ in the way you describe? – Henrick Hellström Mar 11 '13 at 23:27
• I guess you meant to describe a repeated adaptive attack that would reduce the security bounds, rather than an immediate break? Choosing 2048/256 bit DH parameters and a properly designed HMAC-SHA256 based KDF, seeding AES-GCM, would seem to be adequate for at least 100 bits of CCA2 security. Would anything be gained by changing the key derivation step 4, in such way that the server hello message includes a random nonce that is mixed in with the Diffie-Hellman shared secret $M^1_{tmp}$ when $k_{tmp}$ is derived? – Henrick Hellström Mar 12 '13 at 0:13
• (My saying that the adversary would see $C^1$ was a typo; I'd meant that the adversary would see $C^1_{publ}$.) $\;\;\;$ It could conceivably be that DDH is completely infeasible yet such an attack would be only slightly difficult. However, I could imagine showing that a knowledge-of-exponent assumption plus KDF-is-a-random-oracle imply the analogue of CCA2 security that I described. $\;\;$ – user991 Mar 12 '13 at 0:47
• No, nothing would be gained by a step 4 nonce. $\:$ (It might help a little bit, $\hspace{2 in}$ but it might make things worse instead.) $\;\;$ – user991 Mar 12 '13 at 0:56
• I think I follow your reasoning, but can Diffie-Hellman+KDF ever be IND-CCA2 in that sense, and does it have to be? Obviously, it is equally trivial to test if a signed server hello message includes either an implicit $C^1_{publ}$ or $Adv^1_{publ}$. – Henrick Hellström Mar 12 '13 at 1:58

Maybe instead of trying to design your protocol you should first take a look at TLS 1.2 (http://en.wikipedia.org/wiki/Secure_Sockets_Layer), which seems to provide exactly what you need, when Diffie-Hellman is negotiated. You could easily force the client/server to use a predefined set of ciphersuites or abort. Also you could force the client/server not to downgrade to previous versions of TLS/SSL.

• Well, fwiw, I have already done that. (Read it, analyzed it, implemented it.) But that is largely beside the point, since TLS 1.2 clearly isn't the protocol with the least overhead that meets the requirements listed in the question. Even if you fix the cipher suite (and possibly invent a new one for a DH_DHE key agreement), you will have to send and process redundant negotiation messages. Hence my question. – Henrick Hellström Mar 11 '13 at 17:41