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 &quot;simple version&quot; 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 &quot;hardened version&quot; 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 &quot;simple&quot; enough? Is the &quot;hardened&quot; 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.