Two rounds of SHA-256 HMAC? In a project we are working on, we have two applications within our datacenter that exchange messages. The messages are protected by an HMAC, and the secret key is stored on a SafeNet device. 

Update

This is not a hardware token - it is a hardened network storage device called "StorageSecure". The secret key is stored in a SafeNet "cryptainer" on the SafeNet appliance.

The secret key is retrieved by Application #1 from SafeNet to compute the HMAC on the messages that are exchanged with Application #2.  App #2 also has read access to the same SafeNet device, and retrieves the same secret to validate the HMAC of the messages received from App #1. 

To protect the process against the SafeNet secret being compromised and the potential injection of a bogus message by a bad actor, I would like to investigate adding an additional “factor” in the process.  Would there be any benefit in adding a 2nd round of HMAC in the formula in both App #1 and App #2 using perhaps a static key value in code used for the key in a 2nd HMAC such as:

HMAC(HMAC(Message,SafeNetSecretKey),StaticKey)


Or would it be better to use the static key as a salt added to the message:

HMAC(Message+StaticKey,SafeNetSecretKey)


Update

Or since these messages are sent by App1 to App2 via web services, could we consider having App1 compute a nonce and use the nonce in the computation of  the HMAC such as HMAC(SafeNet_K1 || Nonce, Message) and pass the nonce to app2 in the body of the Https request? 

Any advice is much appreciated!
First, you should always use HMAC with the secret data as the key and the (possibly) public data as the message. The proof of its security relies on that. So rather than concatenating the static key to the message, you might want to consider concatenating it to the secret key.

Second, the extra hash doesn't add any security. Anyone who knows the secret key would be able to calculate it just as easily as the HMAC alone. It is only a small layer of obfuscation – you are relying on the attacker not trying it.

So, denoting the "secret key" $k_1$ and the "shared key" $k_2$, there are at least three options:


$H_{k_2}(H_{k_1}(m))$, where you use the secret key first, then the shared.
$H_{k_1}(H_{k_2}(m))$, where you do the opposite.
$H_{k_1||k_2}(m)$, where the keys are concatenated.


The first two differ in the order you use the keys. The reason this matters is that an attacker knowing the inner key could use a collision search to attack the whole MAC. If the inner HMAC collides, the outer one does as well. This only matters if the HMAC hash lacks collision resistance, but collision resistance is not normally required so it is theoretically weaker than necessary even with something like SHA-256.

The last is the most frugal, since you only need one HMAC call. It should be secure even against an attacker who knows one of the keys. It is the one I would recommend.



The nonce idea does not add security, unless you can check its uniqueness, in which case you would avoid replay attacks. With random nonces you would need to store them all to check they are unique, or you could have App2 generate it and send it for App1 to use, adding latency. With an incrementing counter only the previous value needs to be stored (but you need to handle lost messages somehow).

In a replay attack an authenticated message without context information can be copied and sent by an attacker at a later time. Whether you need the nonce to avoid it depends on what information your messages contain and whether sending one of them again would amount to an attack.

If you do use a nonce, it should probably be concatenated with the message rather than the key, since a nonce is public information.