Can adding nonces make challenge response authentications weaker?

Question

In a custom protocol we want to replace an aged tiger32 based challenge response authentication. I suggested that we use something existing, so threw HMAC into the room. As per wikipedia it works as:

$\textit{HMAC}(K, m) = H \left( (K \oplus opad) | H((K \oplus ipad) | m)\right) $

where $m$ would be the nonce. Now The Architect™ suggested "Let us put a few more nonces in there, more randomness does not hurt." and came up with this:

$\textit{HMAC}(K, m_{0..4}) = H \left(m_0 | (K \oplus opad) | m_1 | H(m_2|(K \oplus ipad) | m_3)|m_4\right) $

Although I could not see anything immediately wrong with it, my reply was "We are no cryptographic experts, let us stay with something that has proven to be good in real world applications already."

So we are kind of still arguing and now need input of cryptographic experts. The two main questions here that arise are (Always under the assumption that key, nonce and hash are sufficiently good):

• In this specific instance, will adding those nonces hurt security? That is, will it make authenticating without knowing $K$ any easier, or will it make recovering $K$ from intercepted traffic any easier?
• For the general case, if possible, will in similar situations ("hashing stuff for authentication") adding nonces always make things better, or are there situations to be aware of were adding them could make things worse?

Answer 1

This is vulnerable to a length extension attack. Given a valid nonce/MAC, the nonce can be extended to forge a new valid nonce/MAC value. This is because $m_4$ is appended to the end inside the outer hash.

How this affects you will depend on how you validate your nonce. But in general, this is not a secure construction.

There's probably more things wrong with it, but this was the one that stood out the most to me.

Now The Architect™ suggested "Let us put a few more nonces in there, more randomness does not hurt."

Don't fall for this. Saying doing X doesn't hurt is NOT a valid reason do it. You'll end up buying yourself nothing, and possibly decreasing security. And it's also not a standard algorithm, so it won't exist in any programming libraries.