Designing a simple challenge-response symmetric mutual authentication protocol

Question

I am designing a protocol that 2 devices will use to mutually authenticate over an unreliable, unsecure channel. The system must be fast and low-power, so symmetric cryptography is a requirement. I was thinking of using a challenge-response protocol, but cannot find existing ones that offer mutual authentication and use keys instead of passwords; so I decided to design my own and wanted your opinion.

Let Alice and Bob be 2 parties, with their respective identities encoded as $id_A$ and $id_B$. They share a symmetric key $K$ of 128 bits or more. Note: it's a key, not a password. $n_A, n_B$ are true-random nonces. $hash$ is a secure one-way function without length-extension vulnerabilities, like SHA3 or HMAC-SHA256.

The "simple version" of the protocol would be this one:

• $A \rightarrow B: id_A, n_A$ --- challenge
• $B \rightarrow A: id_B, n_B, hash(K||n_A)$ --- response and 2nd challenge
• $A \rightarrow B: hash(K||n_B)$ --- 2nd response

I also have a "hardened version" like the following, where I'm adding better MACs, binding between messages and hardcoded values (1, 2 and 3) in the hashes to enforce a message order and difference between them.

• $A \rightarrow B: id_A, n_A, hash(K||1||id_A||n_A)$ --- authenticated challenge
• $B \rightarrow A: id_B, n_B, hash(K||2||id_A||n_A||id_B||n_B)$ -- response and authenticated 2nd challenge
• $A \rightarrow B: hash(K||3||id_A||n_A||id_B||n_B)$ --- response to 2nd challenge

My question is: which one should I use? Is the "simple" enough? Is the "hardened" overengineered? Is there a better protocol out there with this level of simplicity?

Answer 1

You probably want to use HMAC instead of any hash function. I will use the notation $H(K, x)$ to denote a keyed MAC.

Your simple protocol version seems to allow a reflection attack.

First the adversary $A$ initiates a session with $B$:

$A \to B$: $\mathrm{id}_A$, $n_A$

$B \to A$: $\mathrm{id}_B$, $n_B$, $H(K, n_A)$

Then $A$ initiates a second session with the nonce $n_B$:

$A \to B$: $\mathrm{id}_A$, $n_B$

$B \to A$: $\mathrm{id}_B$, $n_B'$, $H(K, n_B)$

Now $A$ sends $H(K, n_B)$ to Bob in the first session:

$A \to B$: $H(K, n_B)$

You always want to include the message number, and additionally, who is sending the message and who is receiving the message. You also want to authenticate every piece of that information.

Answer 2

If you trust $hash$ and the randomness of nonces and $K$ and its length, I do not see a particular issue with the simple version. (except one, I will return to this)

It does allow any attacker to acquire $hash(K||x)$ for any chosen $x$ (unlike the "hardened" version) but considering that the attacker is able to sniff the traffic, they might have already harvested enough hashed nonce+key pairs to perform an attack if the $K$ is weak, non-random or $hash$ is not secure - depends on how often is the authentication made.

Overall, the "hardened" version might provide slight advantage if the $hash$ or randomness is partially unreliable, but if you cannot trust these, you have a serious problem elsewhere.

Now to the one issue I mentioned, let's say $A$ sends challenge, $B$ attempts to send the correct answer, but $C$ (being the attacker) controls the unsecure channel and captures the message and resends it from his machine. Now $A$ received correct response to the challenge but from a different machine. Does $A$ now send unencrypted sensitive data to $C$? If not, the attacker still could make $A$ send traffic to $C$ instead of $B$ effectively performing kind of a denial of service on $B$. Be very careful about the implementation.