In the last episode, we've seen how a naive implementation for authenticated Diffie-Hellman allowed an attacker Susan to long-term impersonate Alice, even after the session was long over. We'll therefore modify once again the key-exchange protocol to prevent long-term impersonation through ephemeral leakage.

The story so far

Recall that Alice sends \((\mathit{I_{Alice}}, g^a, \operatorname{sig_{Alice}}(g^a))\) to Bob, where \(\mathit{I_{Alice}}\) is Alice's identity (e.g. her e-mail address), \(g^a\) is her ephemeral short-term public key, and \(\operatorname{sig_{Alice}}(g^a)\) is the signature of \(g^a\) with her long-term private key. Bob is supposed to verify that \(\operatorname{sig_{Alice}}(g^a)\) is indeed the signature of \(g^a\), using Alice's long-term public key. He is also supposed to get Alice's long-term public key from a valid certificate that a CA issued to Alice.

The purpose of signing \(g^a\) was to prevent a man in the middle attack. In unauthenticated Diffie-Hellman, Susan would simply replace \(g^a\) with \(g^s\), and Bob couldn't tell the difference. Adding identities alone wouldn't help: Susan would simply replace \((\mathit{I_{Alice}}, g^a)\) with \((\mathit{I_{Alice}}, g^s)\). Bob can't tell that \(g^s\) doesn't belong to \(\mathit{I_{Alice}}\). That's the purpose of adding \(\operatorname{sig_{Alice}}(g^a)\) to the mix. If Susan merely switched \(g^s\) for \(g^a\), Bob would get \((\mathit{I_{Alice}}, g^s, \operatorname{sig_{Alice}}(g^a))\), and since \(\operatorname{sig_{Alice}}(g^a)\) doesn't match \(g^s\), he won't be duped. But replacing \(\operatorname{sig_{Alice}}(g^a)\) with \(\operatorname{sig_{Susan}}(g^s)\) isn't an option for Susan: Bob, upon getting \((\mathit{I_{Alice}}, g^s, \operatorname{sig_{Susan}}(g^s))\) would immediately see that \(\operatorname{sig_{Susan}}(g^s)\), used with the public key in \(\mathit{I_{Alice}}\)'s certificate, doesn't verify \(g^s\).

This scheme seemed so nice, yet we've seen how Susan was still able to long-term impersonate Alice. What went wrong?

The problem was that if Susan (with the help of Neal), is able to come up with \(a\) corresponding to \(g^a\), she is able to fool Bob with a replay attack: by replaying \((\mathit{I_{Alice}}, g^a, \operatorname{sig_{Alice}}(g^a))\) to Bob sometimes in the future (long after the original Alice-Bob session was over), Bob would compute a key \(k_{AB_2}\), und Susan, with the help of \(a\) would compute \(k_{AB_2}\) as well.

The reason this attack succeeded was not so much that Alice leaked \(\operatorname{sig_{Alice}}(g^a)\) (though it helped and was necessary for the man in the middle attack to work at all), it was that \(\operatorname{sig_{Alice}}(g^a)\) lacked freshness. Susan could re-use a stale \(\operatorname{sig_{Alice}}(g^a)\) signature of \(g^a\) that Alice provided initially, to impersonate her forever (or at least until Alice's certificate expired in a couple of months, invalidating \(\operatorname{sig_{Alice}}(g^a)\) along the way). Or, to put it differently, Alice leaked a pair \((g^a, \operatorname{sig_{Alice}}(g^a))\) that was valid forever. This unlimited validity is the actual culprit.

Maybe adding freshness to \(\operatorname{sig_{Alice}}(g^a)\), such that it won't stay valid beyond the end of the session would help make this issue go away? That's what Basic Authenticated Diffie-Hellman (BADH) is all about.

Basic Authenticated Diffie-Hellman (BADH)

How do we limit the length of time that \(\operatorname{sig_{Alice}}(g^a)\) is valid? Well, by including in \(\operatorname{sig_{Alice}}(g^a)\) not only \(g^a\) but another parameter that changes from session to session! What about adding both \(g^a\) and \(g^b\) to \(\operatorname{sig_{Alice}}\), calling it now \(\operatorname{sig_{Alice}}(g^a, g^b)\)? Surely, this signature would be valid for the current session, but since Bob will present \(g^{b_2}\) in a subsequent session, Susan won't be able to replay \(\operatorname{sig_{Alice}}(g^a, g^b)\) to Bob, since he'll be expecting \(\operatorname{sig_{Alice}}(g^a, g^{b_2})\) instead... which she can't compute, since she doesn't have Alice's long-term secret key.

In other words, \(\operatorname{sig_{Alice}}(g^a, g^b)\) will always stay fresh, since it changes with each new session. Even if Susan recorded  the sequence \((g^{a_1}, g^{b_1}, \operatorname{sig_{Alice}}(g^{a_1}, g^{b_1})), (g^{a_2}, g^{b_2}, \operatorname{sig_{Alice}}(g^{a_2}, g^{b_2})), \cdots, (g^{a_n}, g^{b_n}, \operatorname{sig_{Alice}}(g^{a_n}, g^{b_n}))\) of previous sessions between Alice and Bob, she still won't be able to come up with an \((g^{a_n}, g^{b_{n+1}}, \operatorname{sig_{Alice}}(g^{a_n}, g^{b_{n+1}}))\), when trying to initiate a session with Bob, who offered her \(g^{b_{n+1}}\) as the next ephemeral public key.

With the current version of the protocol, Alice doesn't yet have \(g^b\), so she can't just compute (\(g^a || g^b\) means \(g^a\) concatenated with \(g^b\)):

\[ \operatorname{sig_{Alice}}(g^a, g^b) \leftarrow \operatorname{sign}(\mathit{I_{Alice}}, g^a || g^b) \]

But Bob sure has both \(g^a\) and \(g^b\), so he can:

\[ \operatorname{sig_{Bob}}(g^a, g^b) \leftarrow \operatorname{sign}(\mathit{I_{Bob}}, g^a || g^b) \].

We'll therefore add one message to the handshake:

1. Alice sends \((\mathit{I_{Alice}}, g^a)\) to Bob,
2. Bob sends \((\mathit{I_{Bob}}, g^b, \operatorname{sig_{Bob}}(g^a, g^b))\) to Alice,
3. Alice sends \(\operatorname{sig_{Alice}}(g^a, g^b)\) to Bob.

The full protocol now looks like this:

Alice:

• \(k_{pr}(A) := a \overset{R}{\leftarrow} \{2, 3, ..., p-2 \}\) (uniformly pick a random element \(a\) as my private key)
• \(k_{pub}(A) := A \leftarrow g^{a} \pmod{p}\) (compute my public key \(A\))
• Send \((\mathit{I_{Alice}}, A)\) to Bob
• Receive \((\mathit{I_{Bob}}, B, \operatorname{sig_{Bob}}(A, B))\) from Bob
• Compute \(\operatorname{verify}(\mathit{I_{Bob}}, A || B, \operatorname{sig_{Bob}}(A, B))\). Stop if false.
• Compute \(\operatorname{sig_{Alice}}(A, B) \leftarrow \operatorname{sign}(\mathit{I_{Alice}}, A || B)\)
• Send \(\operatorname{sig_{Alice}}(A, B)\) to Bob
• Compute \(k_{AB} \leftarrow B^a \pmod{p}\)
• Use \(k_{AB}\) as the shared key

Bob:

• \(k_{pr}(B) := b \overset{R}{\leftarrow} \{2, 3, ..., p-2 \}\) (uniformly pick a random element \(b\) as my private key)
• \(k_{pub}(B) := B \leftarrow g^{b} \pmod{p}\) (compute my public key \(B\))
• Receive \((\mathit{I_{Alice}}, A)\) from Alice
• Compute \(\operatorname{sig_{Bob}}(A, B) \leftarrow \operatorname{sign}(\mathit{I_{Bob}}, A || B)\).
• Send \((\mathit{I_{Bob}}, B, \operatorname{sig_{Bob}}(A, B))\) to Alice
• Receive \((\mathit{I_{Alice}}, A, \operatorname{sig_{Alice}}(A, B))\) from Alice
• Compute \(\operatorname{verify}(\mathit{I_{Alice}}, A || B, \operatorname{sig_{Alice}}(A, B))\). Stop if false.
• Compute \(k_{AB} \leftarrow A^b \pmod{p}\)
• Use \(k_{AB}\) as the shared key

Conclusion?

Susan is finally defeated: her evil plot of replaying recorded Alice messages to Bob is foiled, once and for all. She can't play her man in the middle attacks anymore...

... or can she? Find out in the next episode!

Source

Present article covers minutes 45:30 ot 49:55 of Hugo's talk "What Are Key Exchange Protocols?". Slides.

Literature

• [K18] Hugo Krawczyk: An Introduction to the Design and Analysis of Key Exchange Protocols. Bar Ilan Winter School, Feb 2018.  (sildes pdf via BIU, slides pdf via Technion)