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

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. - Is E authenticated encryption? \; – Ricky Demer Jun 2 '14 at 20:13 Have you tried using an automated protocol analyzer, like AVISPA, ProVerif, CryptoVerif, Scyther, Tamarin, EasyCrypt, CertiCrypt, Maude-NPA, etc.? – D.W. Jun 2 '14 at 21:49 It didn't explicitly state what E is so I don't think the flaw lies there. – user3283751 Jun 3 '14 at 12:21 @fgrieu: The question in rev 6 is exactly what it is in the exam paper. – user3283751 Jun 5 '14 at 8:49 @D.W.: your remark to user3283751 "you edited your question to incorporate the attack found in the answers" does not apply to the quantitatively major change in revision 6: adding a 6-steps attack, which does not even remotely resemble any attack suggested in the answer. – fgrieu Jun 7 '14 at 20:05 ## 3 Answers 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. - Of course, if E is ECB mode encryption and the nonce is a single block, then all bets are off, but I've made the jump to semantically secure, supplying confidentiality. I've not jumped to authenticated encryption as there is nothing in the question that would suggest such a thing. – Maarten Bodewes Jun 2 '14 at 22:54 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.) - I don't think this work because , similiar to the man in the middle attack I mentioned above while you can bypass the authentication phase you still don't know the session key k_s so you can not fake subsequent messages so it does not constitute an attack. Also mention above the session which begins at message 4 is supposed to be confidential and secure against reflection, replay, and re-ordering of the contents that means it will be something like this E_{k_{AB}}$$(m1 \| Alice \| counter)$ –  user3283751 Jun 3 '14 at 8:28
Since $M$ "can not fake subsequent messages", the top part of my answer "does not constitute an attack" on implicit authentication. $\:$ Since $A$ reports success even though $B$ was not conducting a session negotiation, the top part of my answer does constitute an attack on explicit authentication. $\:$ Would the thing like that use a tripling function‌​? $\:$ (If it just uses concatenation and enough of the fields are not fixed-length, then there may still be a useful attack within the sessions.) $\;\;\;\;$ –  Ricky Demer Jun 3 '14 at 8:41
No it would not use tripling function. In message 4 and 5 $E_{k_{AB}}$(...) can be anything as long as the protocol is confidential and secure against reflection, replay, and re-ordering of the contents, my $E_{k_{AB}}$($m1 \| Alice \| counter$) is just an example of what it could be. –  user3283751 Jun 3 '14 at 10:50
And after step 7 of the new answer, except if messages in steps 4 and 5 of the question include an ID and Alice checks that, $A_2$ will accept messages from $A_1$, thinking they are from Bob; similarly $A_1$ will accept messages from $A_2$, thinking they are from Bob. –  fgrieu Jun 3 '14 at 12:15
The question state that there does exist a flaw in the protocol that means the attack will work regardless of what $E_{k_{AB}}$(...) in step 4 and 5 is but if $E_{k_{AB}}$(...) = $E_{k_{AB}}$($m1 \| Alice \| counter$) then your attack doesn't work. So I don't think your answer is what the examiners are looking for. –  user3283751 Jun 3 '14 at 14:07

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.

-
cleaned up a bunch of old comments that related to an older version of the answer –  mikeazo Jun 5 '14 at 12:07
The question as I understand means that from step 4 the session is confidential and secure against reflection, replay, and re-ordering of the contents with $E_{k_{AB}}$(...) can be anything as long as the protocol satisfy the above requirement. That means 1. Mallory can not reshuffle message (because it is secure against reordering) . –  user3283751 Jun 7 '14 at 18:07
And if $E_{k_{AB}}$(...) is of this form $E_{k_{AB}}$$(m_1 \| Alice \| counter)$ then attack at 2. doesn't work either. –  user3283751 Jun 7 '14 at 18:10
@user3283751: I've fixed the answer to read the question as you intent it to be. Beware that "is supposed to" can be understood as introducing a goal, rather than an assumed property, at least to someone to which English is a second language. –  fgrieu Jun 7 '14 at 18:43