Security of a security protocol for key exchange, using symmetric-key cryptography

Question

This is an exam question:

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$ xor $k_2$

4. $A \to B$: $E_{k_s}(...)$

5. $B \to A$: $E_{k_s}(...)$

The protocol is based on a long term secret $k_{AB}$ shared between Alice and Bob.The session, which begins at message 4, is supposed to be confidential and secure against reflection, replay, and re-ordering of the contents ( with $E_{k_s}(...)$ in step 4 and 5 can be anything as long as the protocol satisfy the above requirement).There does exist a flaw in the protocol, can you find it and explain why it constitute an attack on the protocol ?

I can tell that a man in the middle attack doesn't work because $k_1$ and $k_2$ are encrypted so the attacker can not know $k_s$ therefore can not continue to send messages to A and B after the authentication phase.

Another 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$ xor $k_1$ = 0 then the attacker know $k_s$ then 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

If we assume that $E$ is just semantically secure, without providing authenticity and integrity of the encrypted message then this scheme is has a huge drawback. It would be possible for an attacker to pose himself as either A or B, or to alter any message send from A to B.

So without authenticated encryption, this scheme may protect against eavesdropping, but not against alteration of messages. Although the attacker won't be able to decrypt messages from the other party, it is possible for an attacker to create an active attack and inject garbage into the messages received by either A or B.

As indicated, many smart cards provide similar key establishment routines, but those schemes use two master keys and two session keys - one for encryption providing confidentiality (symmetric encryption) and one for entity authentication and message authentication (MAC), although a single key and authenticated encryption (CCM or GCM) may also be used for $E$.

---

Note that above does not constitute a full crypto-analysis of the protocol, it simply points out that $E$ should be an authenticated cipher.

Answer 2

I assume that Alice is capable of accepting a connection while
negotiating another, and let $A_2$ and $A_1$ denote her two roles.

1. $\;\; A_1 \to M \:$ : $\:$ Alice, $nonce_1$

2. $\;\; M\to A_2 \:$ : $\:$ Bob, $nonce_1$

3. $\;\; A_2 \to M \:$ : $\:$ $nonce_2$, $E_{k_{AB}}\hspace{-0.04 in}(nonce_1||k_2)$

4. $\;\; M\to A_1 \:$ : $\:$ $nonce_2$, $E_{k_{AB}}\hspace{-0.04 in}(nonce_1||k_2)$

5. $\;\; A_1 \to M \:$ : $\:$ $E_{k_{AB}}\hspace{-0.04 in}(nonce_2||k_1)$

6. $\;\; M\to A_2 \:$ : $\:$ $E_{k_{AB}}\hspace{-0.04 in}(nonce_2||k_1)$

7. $\;\; A_1$ and $A_2$ both output $\: k_1 \operatorname{xor} \hspace{.02 in} k_2$

Since $A_1$ initiated and $A_2$ responded, their roles with respect to that session key are compatible.
In particular, if the session only has the two parties indicate their role
(rather than their identity) to prevent reflection attacks within the session,
then $A$ will accept messages from itself while reporting that they are from $B$.

(fgrieu's now-removed comment made me realize that reflection
could be much more powerful than I had been thinking.)

Answer 3

I'll assume the 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.

Including when $E$ is authenticated encryption (as stated in a comment to the question), and we suppose the origin and step number is inserted in each message encrypted in the session and verified on the receiving side (preventing replay of earlier messages in a session and limiting the impact of Ricky Demer's reflexion attack before it impacts the session itself), an imperfection remains.

A conceivable goal of the protocol could be that each party is assured that $k_s$ used during the session is uniformly random as long has $k_a$ or $k_b$ that party generated at steps 2 or 3 is uniformly random; that is part of a common definition of a key agreement protocol [which is the apparent goal of 1/2/3]; and that goal is not met, for a cheating Alice could choose $k_2=k_s\oplus k_1$.

That does not go against objectives stated in the question, but has practical significance. Rigging devices has been among the arsenal of people doing surveillance, including state-appointed agencies, for decades. From their point of view, rigging should

• work even though key material $k_{AB}$ or $k_s$ is injected or generated after the rigging takes place;
• allow passive intercepts, which are much easier to perform and less likely to be detected than active ones;
• be unlikely to be detectable by an audit; including undetectable by a check, with knowledge of the keys, that all messages exchanged are per the protocol;
• work with only one party using a rigged device [it is impractical and sometime undesirable to rig every implementation];

With the protocol as it stands, if Alice's device is rigged to generate $k_2=\operatorname{AES}_{k_M}(nounce_A)\oplus k_1$, that allows a passive interceptor knowing $k_M$ to decode a session effortlessly, while messages exchanged will appear genuine. That attack could be blocked by having Alice send a commitment of $k_2$ at step 1.

---

In the rest of this answer I'll assume $E$ in steps 2/3 provides confidentiality but not integrity; that's compatible with the question alone as is stands now. With that assumption, the protocol does NOT provide confidentiality of the messages sent by Bob against an active adversary Mallory.

I'll prove this with a particular example of $E$ that provides confidentiality, a block cipher such as AES in CBC mode with random IV, with $nounce$ and $k$ each of the same width as the block size. The data sent at step 2 [resp. 3] is $nounce_B\|IV_2\|C_{2.1}\|C_{2.2}$ [resp. $IV_3\|C_{3.1}\|C_{3.2}$], with $C_{2.2}=\text{AES_ENC}_{k_{AB}}(k_1\oplus C_{2.1})$ and $C_{3.2}=\text{AES_ENC}_{k_{AB}}(k_2\oplus C_{3.1})$.

Mallory monitors 1/2 without alteration, and in step 3 changes $C_{3.2}$ to $C_{3.2}'=C_{2.2}$ in the message sent by Alice to Bob. This will change $k_2$ deciphered by Bob to $k_2'=k_1\oplus C_{2.1}\oplus C_{3.1}$, thus $k_s'=k_1\oplus k_2'=C_{2.1}\oplus C_{3.1}$ used by Bob is known to Mallory.

In steps 4 and 5, Mallory acts to Bob as Alice is expected to, except that Mallory uses $k_s'=C_{2.1}\oplus C_{3.1}$, can choose at will the information allegedly sent by Alice to Bob, and gets the information Bob expects to send her confidentially.