Attack on a key-exchange,symmetric-key cryptography protocol

Question

This is an exam question in Oxford 's Computer Security course:

Here is the start of a protocol, based on a long-term secret key $k_{AB}$ previously shared between Alice and Bob, designed to offer bilateral authentication and establishment of a session key $k_s$. The session, which begins at message 4, is supposed to be confidential and secure against reflection, replay, and re-ordering of the contents.
1.$A \to B$: Alice, $nonce_A$
2.$B \to A$: $nonce_B$, $E_{k_{AB}}$$(nonce_A \| k_1)$
3.$A \to B$: $E_{k_{AB}}$$(nonce_B \| k_2)$
Alice and Bob both compute $k_s$ = $k_1$ ⊕ $k_2$
4.$A \to B$: $E_{k_s}(...)$
5.$B \to A$: $E_{k_s}(...)$

a) Why would Alice and Bob want a session key $k_s$, rather than simply using the already shared secret key $k_{AB}$ for session encryption?
b) How should Alice and Bob format the contents of their session, messages 4 onwards, to meet the aims of the protocol?
c) If they additionally wish to ensure the integrity of the session, what should they add to the protocol?
d) Does this protocol provide key agreement or does it provide key transport? Explain your answer.
The following appears to be a man-in-the-middle attack on the protocol, under the usual Dolev- Yao model:

1.$A→I_B$: Alice ,$nonce_A$
1´.$I_A→B$: Alice, $nonce_A$
2´.$B→I_A$: $nonce_B$,$E_{k_{AB}}$$(nonce_A ∥ K_1)$
2.$I_B→A$: $nonce_B$,$E_{k_{AB}}$$(nonce_A∥K_1)$
3.$A→I_B$: $E_{k_{AB}}$$(nonce_B∥K_2)$
3´.$I_A→B$: $E_{k_{AB}}$$(nonce_B∥K_2)$
Alice and Bob continue their sessions with the intruder.
e) Why does the above sequence not constitute an attack on the protocol?
f) Although not subject to man-in-the-middle attacks, there does exist a flaw in the protocol. Find it, and explain carefully why it does constitute an attack on the protocol.

Part f) is where I'm currently stuck.

One attack I can think of is when $nonce_A = nonce_B$ a Dolev-Yao attacker can pose as B and send A $E_{k_{AB}}$$(nonce_A ∥ k_1)$ in message 3 then $k_s = k_1 ⊕ k_1 = 0$ then the attacker know s$k_s$ and he can send message and decrypt message. But the chance $nonce_A = nonce_B$ is very small, so I'm not sure if it constitutes an attack.

Answer 1

I'm not sure but in my point of view.

Since $k_{AB}$ is used to authenticate both side.
Mapped $nounce_x:E_{k_{AB}}$$(nonce_x∥k_x)$ pair on one side can be used on both side.
Thus we can gather $nounce_x:E_{k_{AB}}$$(nonce_x∥k_x)$ pairs from $B$ since $B$ will happily echo $E_{k_{AB}}$$(nonce_x∥k_x)$ for every $nounce_x$ I asked.

This doesn't form practical MITM attack but I can make $A$ agree on $randomK_1⊕k_2$ as $k_s$ while on the other side $B$ will accept $k_1⊕k_2$ as $k_s$. In another word we can make $A$ and $B$ agree on different values at probability equivalent to (or more than because we can query it ourself) birthday attack.

This might make some cryptanalysis possible but I don't know the details.

---

As you suggested in chat: $nonce$ collision is unnecessary we rather change the scheme to something like:
After received $nonce_A$ we send it to $B$ twice but only sent the first response to $A$

Answer 2

Summary: The statement is ambiguous. My best guess is that the flaw thought in f) is the feasibility of the reflexion-to-different instance attack found by Ricky Demer, allowing Mallory to authenticate to Alice as Bob without involving Bob, constituting a valid attack against 1/2/3 in the Dolev-Yao model, and breaching the "bilateral authentication" goal assigned to steps 1/2/3 in the protocol. The affirmation in f) that "the protocol" is "not subject to man-in-the-middle attacks" is narrowly justified by noting that "the protocol" includes 4/5, and we modified that in b) so that no message will be accepted by Alice when the attack is performed.

---

I apologize that this answer is mostly an exegesis of the problem statement. Bear with me: that's my honest attempt to make sense [in the context of the rest of the problem] of the fragment:

f) Although not subject to man-in-the-middle attacks, there does exist a flaw in the protocol. Find it, and explain carefully why it does constitute an attack on the protocol.

I'll assume the unstated but obvious: Alice checks $nounce_A$ deciphered from data received at step 2 before proceeding to step 3, and Bob checks $nounce_B$ deciphered from data received at step 3 before proceeding to step 4.

It is much less easy to guess what we can assume about $E$. On reading the statement up to b), it would seem that $E$ is only assumed to be a symmetric encryption scheme/function providing confidentiality. However that turns out to be inconsistent with later developments:

1. b) ask us to introduce fixes such that "the session" of 4 onwards is "confidential and secure against reflection, replay, and re-ordering of the contents". Our fixes must be limited to how "Alice and Bob format the contents of their session". My reading is that the later at least of these "contents" is what's noted $...$ in steps 4 onwards, and "reformatting" precludes adding a MAC to that [in particular because we don't have a key at hand]. Such fix would not be possible for some $E$ providing confidentiality, including a block cipher in OFB mode and random IV: even if we add origin, sequence number and redundancy [say a hash], the session remains vulnerable to an adversary knowing the plaintext [Mallory replays earlier cryptograms with alterations fixing the sequence number and redundancy we introduced].
2. f) states that the protocol is "not subject to man-in-the-middle attacks" [including steps 1/2/3 that "offer bilateral authentication and establishment of a session key $k_s$", with $k_s$ confidential], while we can exhibit a man-in-the-middle attack breaching these objectives for some $E$ that provides confidentiality: a block cipher in CBC mode, random IV, and $k_1$/$k_2$ corresponding to a whole block [Mallory replaces the block corresponding to $k_2$ in the cryptogram of step 3 with the block corresponding to $k_1$ in the cryptogram of step 2, to the effect of convincing Bob to run 4 onwards with a $k_s$ that Mallory can compute. For details, see the second part of my other answer about this protocol].

Perhaps $E$ is a variable-width block cipher [not requiring a mode of operation to handle its inputs in the protocol]. That would be the closest symmetric-key equivalent to $E$ considered in Danny Dolev and Andrew C. Yao's article On the Security of Public Key Protocols [IEEE Transactions on Information Theory, 1983], alluded to by "the usual Dolev-Yao model" in d). Or $E$ could be a symmetric encryption mode of a block cipher providing authenticated encryption [even though these are usually not functions, thus do not fit an requirement in the original Dolev-Yao article]. Whatever the reason, we must suppose that $E$ is such that its matching decryption procedure $D$, when fed with an input $E$ did not produce, would output something indistinguishable from random [that's non-malleability, a common assumption only for block ciphers when using the Dolev-Yao model for symmetric cryptography]; or reject that input [that's insuring integrity]; or perhaps we operate in some abstract model where our adversary can shuffle cryptograms but can't alter them.

Even with such assumption, steps 1/2/3 of the protocol are vulnerable to a "man-in-the-middle attack on the protocol" as defined in d) by reference to the "Dolev-Yao model", for that allows to carry a reflexion-to-different-instance attack on steps 1/2/3 of the protocol, described in Ricky Demer's answer. That attack is not standard reflexion, although it uses the same messages: Mallory reflects to Alice playing the recipient role what Alice concurrently playing the initiator role sends, and vice versa. It leads to bogus authentication of Bob by Alice even though Bob is not part of the protocol, under assumptions that

• Alice can carry the initiator and recipient roles as explicitly assumed by the Dolev-Yao model, and can do this concurrently [which is very realistic if Alice implements client and server sides of the protocol using independent processes, threads, or state machines].
• Alice uses the same long-term key $k_{AB}$ for these two different roles [the original Dolev-Yao article does not consider it because it deals with asymmetric cryptography, but this seems a reasonable interpretation of "long-term secret key $k_{AB}$ previously shared between Alice and Bob" in the statement].

That attack breaches the "bilateral authentication" goal assigned to steps 1/2/3 in the introduction of the problem, and can be completed by a "man-in-the-middle"; it can trivially be extended to involve Bob, and thus match any hypothetical definition of "man-in-the-middle attack" artificially excluding attacks which do not involve the impersonated party.

Notice that in the reflexion-to-different-instance attack, Mallory does not get to know the value of $k_s$ that Alice wrongly conclude is shared with Bob, and that let us narrowly make sense of "not subject to man-in-the-middle attacks" in f) by noting that this affirmation applies to "the protocol", which includes 4 onwards as we modified it in b), and these changes avoid that Alice accepts as from Bob session plaintexts that really came from her.

If we somewhat reject the reflexion-to-different-instance attack, I fail to find "a flaw in the protocol" [and I would be surprised if a systematic analysis by the Dolev-Yao algorithm concluded otherwise], when I restrict to the objectives stated in the introduction for steps 1/2/3:

offer bilateral authentication and establishment of a session key $k_s$

and the unstated but obvious requirement that an adversary must not get to know $k_s$ [I ignore the objectives stated for 4 onwards, because they must have been met by whatever we changed in b)].

---

My only alternate proposition is hairy: we could consider that in d), it was introduced the requirement that "this protocol provide key agreement" between two parties. By a usual definition (emphasis and ellipsis mine)

a key-agreement protocol is a protocol whereby two (..) parties can agree on a key in such a way that both influence the outcome

and by a strict reading, that requirement is not met: Alice can choose $k_s$ and compute $k_2=k_1\oplus k_s$. As explained in the first part of my other answer about this protocol, that's a weakness in some situations, like when trying to prevent decryption of passive intercepts of communications between honest parties, one of which unwillingly using a device rigged in manner bound to not transmit data beyond the requirement of the protocol, in order to make detection of the rigging less likely.

---

The statement [as transcribed in the question and without reference to the definitions used] is subject to interpretations, and arguably incorrect_^[*]

1. There are uncertainties about what properties of $E$ are assumed. Is it non-malleable? Does it provide integrity?
2. There are uncertainties about capabilities of adversaries: can they exploit a malleability of $E$? Dolev-Yao adversaries don't, but real ones do.
3. There are uncertainties about the goals, in particular integrity of deciphered plaintext.
4. It is unclear if the word "contents" is used to mean the output [ciphertext] or some of the input [plaintext] of $E$, in the introduction, and [perhaps independently] in b).
5. It is unclear what exactly we are allowed to change in b) and c), and how much of that is assumed in f).
6. It is questionable that the protocol is "not subject to man-in-the-middle attacks".

_{^{[*] Incorrect problem statements happen, including when stakes are high. I experienced it personally a long time ago, with a physics problem statement so wrong that the competition had to be re-done, much to my dismay at the time. I had managed to prove the statement wrong in its first part (involving increasing the amplitude of a swing using gestures that did not), understand the intent from an electrical analogy in the second part, complete the first as intended, and overall performed well; I did poorly in the competition re-run, that narrowed my choices of engineering school, and ultimately diploma.}}