The flaw in Bellare-Rogaway (1995) model on authenticated key exchange

Question

Background:

In their 1995 paper, Bellare and Rogaway describe a formal model for authenticated key exchange in a tripartite setting. In this setting, each client has a shared key with a central server, which is willing to help in key distribution between any two mutually distrustful clients. This model is reminiscent of the security settings for Needham-Schroeder protocol, Kerberos and Active Directory.

For brevity, let's denote the Bellare-Rogaway-1995 model by "BR95."

The adversary in the BR95 model is a probabilistic polynomial-time algorithm, which has total control over the communication between each pair of parties. Moreover, the adversary can mount a number of attacks on any single party. The attacks include revealing the session key, corrupting a party, and a special "TEST" attack, which is described next.

When the adversary has finished with experimenting different attacks on the parties, it makes a final TEST attack. The attack is restricted in several ways; for instance, the adversary cannot mount the TEST attack on a corrupted party, or on a party whose session key is already revealed. (Nor can the adversary mount the test attack on the partner of such party.)

On issuing the TEST attack, the adversary is given either of the following, each with probability 1/2:

1. The session key of the party on which the TEST attack is mounted; or
2. A random string of the same length as the session key.

The idea is that the adversary must be unable to distinguish the above two cases with advantage more than negligibly over 1/2.

---

The Flaw

In another paper, Bellare, Pointcheval, and Rogaway write:

Soon after the appearance of [BR95], Rackoff came up with an example showing how the definition given in that paper was not strong enough to guarantee security for certain applications using the distributed session key. The authors of [BR95] traced the problem to a simple issue: they had wrongly made the restriction that the TEST query be the adversary's last. Removal of this restriction solved the problem. This minor but important change in the definition of [BR95], made in 1995, has since been folklore in the community of researchers in this area, and is explicitly incorporated into our current work.

Along the same lines, Shoup explains:

We have taken the opportunity here to correct a serious flaw that appears in [BR95,...] that was pointed out to the authors of [BR95] by Charles Rackoff. In the formulation in [BR95, ...], the TEST operation is only allowed to be performed at the very end of the adversary's execution, whereas we have allowed it to occur at any time.

Shoup then tries to pinpoint the flaw on a contrived version of a protocol called "DHKE-1" (designed by himself). However, the contrived version is too "non-standard" for me to understand. Specifically, it includes the operation (or attack) core dump, which is not compatible with the attacks listed in the BR95 model.

---

Question

Could you please illustrate the flaw in the BR95 via an example, where disallowing the TEST attack in the middle of execution can result in a false proof of security?

Answer 1

The "protocol interference" attack:

From Fig 2 of http://seclab.cs.ucdavis.edu/papers/Rogaway/3pkd.pdf --

In Flow3A (resp. 3B), before the intended message is delivered, the adversary manages to obtain an encryption under $K_A$ (resp. $K_B$) of a different session key $\sigma'$ (through interacting with $S$ in a higher-level protocol) and sends this "forged" message to $A$ and $B$. This is a successful man-in-the-middle style attack.

Why the security definition should include TEST in the middle of execution:

If the interaction doesn't terminate immediately after TEST, then the forged session breaks security in a very obvious way. Namely, with probability 1/2, the TEST operation hands a key to the adversary; it becomes the "higher-level protocol" we're worried about with constant probability. If the adversary is not forced to immediately halt, then it can use this key to perform the man-in-the-middle attack above (at least in the BR95 scheme).

The security definition given in BR95 is, therefore, too weak as this is a plausible attack (Why would an adversary arbitrarily halt, especially after they've just extracted useful information?). That is, a protocol vulnerable to this attack is (wrongly) proven secure under the given definition.