Designing a simple challenge-response symmetric mutual authentication protocol

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?

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.

• Good point, did not see the reflection vulnerability! Is there any reason why I should use HMAC if the hash is not vulnerable to length-extension attacks? Nov 19, 2020 at 15:35
• MACs are the right primitive for authenticating information - sure, the homegrown MAC based on a hash function might work, but it's better to rely on tried and tested primitives. Hope I could help! Nov 20, 2020 at 20:03
• I agree, but SHA3 was explicitly designed to not need HMACs crypto.stackexchange.com/questions/42736/… Nov 22, 2020 at 9:49

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.

• I plan to use true-random nonces of 128+ bits so harvesting enough data should not be an issue for the next few million years. The key will also be true-random and the hash decently strong (considering the low power requirements). I was thinking of Ascon-Hash. I don't plan to transmit any new data, just authentication so the devices know about each other's presence. Nov 19, 2020 at 15:39
• I am not familiar with Ascon-Hash; I would personally use SHA-3, I think your low power device can handle that. Also note that if one of your devices get compromised the whole system falls apart due to nature of symmetric ciphers/pre-shared secrets. Nov 19, 2020 at 22:12