UKS attack on KEA protocol

Question

I'm trying to understand the UKS attack on KEA protocol.

This is described in this paper: Security Analysis of KEA Authenticated Key Exchange Protocol

So to summarize:

• KEA protocol:

• UKS attack on KEA:

"$\mathbb{M}$ registers a public key $g^a$ of some honest party $\mathbb{A}$ as $\mathbb{M}$'s own public key. Then $\mathbb{M}$ intercepts a key-exchange session between $\mathbb{A}$ and some other honest party $\mathbb{B}$ and at the same time starts a session between $\mathbb{M}$ and $\mathbb{B}$. Now $\mathbb{M}$ forwards ephemeral public key $g^x$ from $\mathbb{A}$ to $\mathbb{B}$ and ephemeral public key $g^y$ from $\mathbb{B}$ to $\mathbb{A}$. Since $\mathbb{M}$ has the same public key as $\mathbb{A}$, both $\mathbb{A}$ and $\mathbb{B}$ will compute identical session keys, however they participate in two different key-exchange sessions. $\mathbb{B}$ participates in a session with $\mathbb{M}$ while $\mathbb{A}$ participates in a session with $\mathbb{B}$. Finally, $\mathbb{M}$ reveals a session key of one of the sessions and announces the other session as a test session. Given a challenge key, $\mathbb{M}$ compares it to the revealed key. If they are the same, $\mathbb{M}$ decides that the challenge is a correct key for the test session and if different, $\mathbb{M}$ decides that the challenge key was chosen at random. The demonstrated attack breaks AKE security against a weak adversary (who can only reveal session keys)."

The thing that I don't understand in the attack description above, is the notion of "challenge key". It is said that the attacker $\mathbb{M}$ reveals a session key of one of the sessions, and then pick a challenge key to guess the key of the test session. But, I thought the key is the same in the two sessions so I don't understand what $\mathbb{M}$ want to guess? Secrets $a$ and $b$?

I think I am missing something, if someone could describe me in detail the attack it would be very nice. Thank you in advance.

Answer 1

Some background on formal key-exchange models

The goal of a key-exchange (KE) is to establish a session key between two parties. Naively, we could say that a KE is secure if no adversary will be able to figure out the session key (in full) established between two honest parties. However, in formal security models we take this a bit further and insist that the adversary should learn nothing about the session key, i.e., the adversary should not be able to glean any partial information about the session key from observing (and possibly interfering with) the KE.

This is formally captured by challenging the adversary on a target session of its choice. The challenge consists of first flipping a secret bit $b$ . If $b$ comes up as 0, then we return the actual session key to the adversary, while if it comes up as 1, then we return a randomly drawn key of the same length (completely independent of the KE). Now the adversary is supposed to guess which key he was given: real or random? If he cannot guess which key he was given with much better probability than $1/2 $, then we say that the KE is secure. This "game" is completely artificial of course, but it nicely covers the idea that the adversary should learn nothing about the key, and is an example of the kind of "over-provisioning" present in formal security models.

In addition, we also allow the adversary to reveal the session keys of sessions unrelated to the target session (if we allowed the session key of the target session to be revealed, then the "game" above would ofc be completely trivial to win). What unrelated means can be quite technical to formulate, but intuitively it means that if $A$ and $B$ runs a KE between them, then this is unrelated to the KE session $A$ established with $C$ for instance, (or $B$ with $C$, or $D$ with $E$, etc...). Thus, if the attacker picks the $A \longleftrightarrow B$ exchange as its target, then it should still be allowed to reveal the session key from the $A \longleftrightarrow C$ exchange. If the KE is secure, then learning the session key from the $A \longleftrightarrow C$ exchange should not help the attacker learn anything about the session key in the $A \longleftrightarrow B$ exchange.

The UKS attack

In the UKS attack, there are two formally (in the sense of the security model) unrelated KE sessions: $A \longleftrightarrow B$ and $M \longleftrightarrow B$. This allows the adversary to reveal the session key from one, and still pick the other as its target session.

But, I thought the key is the same in the two sessions...

And this is exactly where the attack comes from! In practice these two exchanges are not unrelated at all, so when the adversary reveals the session key from, say, the $M \longleftrightarrow B$ session, then it also knows the session key of the $A \longleftrightarrow B$ session. From the point of view of the formal security model, the $A \longleftrightarrow B$ session is still a considered a valid target, so $M$ can trivially win the game (i.e., guess the value of the secret bit $b$).