Spoofing protocol nonce

Amy and Betty have a shared key $k$, and the protocol below is to provide a mutual authentication for both Betty and Amy.

1. A sends B : $n_a$

2. B sends A : $n_b \;\|\; E(k, n_a)$

3. A sends B : $E(k, n_b)$

Where

• $n_a$ is a nonce from Amy

• $n_b$ is a nonce by Betty

Can spoofing take place here where someone pretends to be Amy even without knowing the shared key?

-

Yes, there are several ways in which Mallory could pretend to be Amy.

One obvious way, which doesn't even involve Amy herself in any way, would be for Mallory to perform steps 1 and 2 of the protocol normally, as if he were Amy. Then, given Betty's nonce $n_b$, Mallory can start a second, parallel instance of the protocol, again pretending to be Amy, and submit $n_b$ as Amy's nonce. The response from Betty then contains $E(k, n_b)$, which Mallory can send back to Betty to complete the original authentication protocol:

1. M(A) → B: $n_a$ (= arbitrary nonce chosen by Mallory, pretending to be Amy)
2. B → M(A): $n_b \;\|\; E(k, n_a)$
Second, parallel session:
1'. M(A) → B: $n_b$
2'. B → M(A): $n_b' \;\|\; E(k, n_b)$
3. M(A) → B: $E(k, n_b)$

Of course, if Amy is also willing to respond to authentication attempts initiated by Betty (or by Mallory pretending to be her), then Mallory can perform the parallel steps 1' and 2' with Amy instead of Betty. Thus, even if Betty's smart enough to check whether the nonce she receives in step 1' matches her own earlier nonce (or even if she simply refuses to participate in more than one authentication exchange at a time), she will not be able to detect this version of the attack.

As owlstead suggests, the way to defeat this attack is to disambiguate the encrypted values sent in step 2 and 3, so that the value from step 2 cannot be used by Mallory in step 3. Some possible ways to do this would be to:

• Include a step number in the encrypted strings, e.g.:

1. A → B: $n_a$
2. B → A: $n_b \;\|\; E(k, 2 \;\|\; n_a)$
3. A → B: $E(k, 3 \;\|\; n_b)$
• Include both nonces in each encrypted strings (in different order), e.g.:

1. A → B: $n_a$
2. B → A: $n_b \;\|\; E(k, n_a \;\|\; n_b)$
3. A → B: $E(k, n_b \;\|\; n_a)$
• Include the (assumed) identities of the sending and receiving parties in the encrypted strings (NOTE: does not protect against the modified attack where Mallory contacts Amy instead of Betty for steps 1' and 2'), e.g.:

1. A → B: $n_a$
2. B → A: $n_b \;\|\; E(k, id_b \;\|\; id_a \;\|\; n_a)$
3. A → B: $E(k, id_a \;\|\; id_b \;\|\; n_b)$
• All of the above, e.g.:

1. A → B: $n_a$
2. B → A: $n_b \;\|\; E(k, 2 \;\|\; id_a \;\|\; n_a \;\|\; id_b \;\|\; n_b)$
3. A → B: $E(k, 3 \;\|\; id_b \;\|\; n_b \;\|\; id_a \;\|\; n_a)$

Personally, I would recommend the last option, if only because it makes the encrypted strings self-documenting: $E(k, 3 \;\|\; id_b \;\|\; n_b \;\|\; id_a \;\|\; n_a)$ can be read as "Amy ($id_a$) authenticating with nonce $n_a$ to Betty ($id_b$) with nonce $n_b$ in step 3", which is exactly what the message is supposed to communicate.

Also, obviously, the encryption method $E$ needs to be non-malleable, and the combining operation $\|$ should not introduce any ambiguity. In fact, calling $E$ "encryption" is somewhat misleading here: the protocol works fine even if $E(k,m)$ is just a MAC, but has obvious attacks if $E$ is a malleable (but still semantically secure) encryption scheme like CTR mode encryption, as Mallory can simply take $E(k, n_a)$ and turn it into $E(k, n_b)$ by flipping the appropriate bits.

The protocol as described also has other potential issues, depending on how it's used. For example, if Mallory can insert himself as a middle-man between Amy and Betty, then he can simply relay any messages he receives from Amy to Betty, and vice versa, thereby trivially convincing both that they're talking directly to each other, even though both are actually talking to Mallory. Fundamentally, without some extra out-of-band information, there's no way to prevent this attack from within the authentication stage of the protocol: as long as Amy and Betty just receive messages from some unspecified network, there's no way for them to tell whose hands they've passed through.

The only solution is for Amy and Betty to encrypt their subsequent communications using the shared key $k$ (or, better yet, an ephemeral session key derived from $k$ and the nonces $n_a$ and $n_b$, and preferably also the identities $id_a$ and $id_b$) with a secure, non-malleable encryption scheme to ensure that, even if Mallory can intercept their messages, he will not be able to decrypt or alter them. (Of course, the messages should also carry sequence numbers / timestamps and sender / receiver IDs to prevent replay attacks.)

-
Fixed my name, think your message format is better than the one I suggested (which only included minimal changes). And +1 of course. –  Maarten Bodewes Jul 22 '14 at 18:28

Yes, because Mallory can use Amy and Betty to get any encrypted nonce; Amy and Betty are oracles for Mallory. She just has to send the nonce she has to encrypt to either one of them and they perform the task for her (in another "authentication attempt", using step 1 & 2).

Usually you protect against this kind of situation by performing an encryption over $E(k, n_b \;\|\; n_a \;\|\; id_b)$ instead, this way the newly generated random nonce protects against oracle and replay attacks.

$id_b$ - an ID or serial number of Betty - should also be included, if anywhere possible.

-
thanks for the reply. What do you mean by Amy and Betty are oracles? –  user16475 Jul 20 '14 at 13:58
Mallory can send any nonce to either one of them, and they happily encrypt it for her in step 2. So note that the other party (Mallory in this case) is not authenticated to them in any way yet. –  Maarten Bodewes Jul 20 '14 at 14:01
however in the 3rd step, Amy will have to authenticate herself by encrypting nb with the shared key which only Betty and Amy have. Without the shared key how will Mallory send the 3rd msg? –  user16475 Jul 20 '14 at 14:15
@user16475 Mallory takes the nonce $n$ that he receives (in the original session) and either starts with Amy or Betty another "malicious" authentication attempt, where he sends as nonce $n$. Then he will get back the encryption of $n$ under $k$ and can send this in the original session and the authentication is complete. –  DrLecter Jul 20 '14 at 14:22
@user16475 He just sends $nb$ as a new (parallel) authentication attempt (first message) to either Amy or Betty and will receive in return $E(k,nb)$ (as part of the response, the other nonce can be discarded). That is what owlstead meant by using Amy or Betty as oracles. –  DrLecter Jul 20 '14 at 14:32