Side channel security of HMAC in software

Question

Assume we have a processor with a symmetric co-processor that supports AES. This processor does however not provide co-processor support for hash algorithms such as SHA-1 or SHA-256.

I've got the following strongly related questions:

1. Would an HMAC implementation based on a hash implementation in software - which is not explicitly protected against side channel attacks - be vulnerable to side channel attacks?
2. If so, are there reasons why such an attack would be stronger or less strong than e.g. a side channel attack against a symmetric cipher in CBC mode?
3. Would it be possible to retrieve the key used to key the HMAC algorithm?
4. Finally, could it be safer to opt for AES-CMAC instead in case an AES implementation in hardware is available?

It is assumed that the comparison of authentication tag values does not leak information. Both DPA and timing attacks could be considered.

The reason I'm asking is because hash algorithms are often not explicitly protected against side channel attacks. HMAC is still often used in this scenario.

Answer 1

I am answering on the basis of this paper (pdf) linked in the comments, as well as some of the related papers it cites or is cited by. I am not aware of more realistic attacks on HMAC.

It assumes a DPA side channel that leaks the number of bits flipped when a new value is read into a CPU register (or in another instruction in some of the papers). I.e. it leaks the Hamming distance between the old value and the new. This allows a direct key recovery attack on HMAC, made easier by the fact that HMAC uses inner and outer keys that are conveniently a known distance apart.

If you assume such a side channel, there is not much you can securely do on the computer. In fact, a typical hardware implementation of HMAC would be almost equally likely to be vulnerable, if you still have to load the key from memory to use it.

1. Would an HMAC implementation based on a hash implementation in software - which is not explicitly protected against side channel attacks - be vulnerable to side channel attacks?

I do not think it is a matter of software vs. hardware or even side channel protection. If such a side channel as described above exists, there is not much you can do securely on the CPU. Certainly most conventional data processing with secret values has to be rethought.

2. If so, are there reasons why such an attack would be stronger or less strong than e.g. a side channel attack against a symmetric cipher in CBC mode?

Stronger, in the sense that it is a key-recovery attack, unlike e.g. padding oracle attacks that target CBC. But the assumptions are much stronger as well.

3. Would it be possible to retrieve the key used to key the HMAC algorithm?

Yes, assuming.

4. Finally, could it be safer to opt for AES-CMAC instead in case an AES implementation in hardware is available?

Not necessarily. For example, with AES-NI instructions you have to load the AES key into XMM registers, which has the potential of allowing a key-recovery attack in the same manner.

If you have a dedicated crypto chipset that also stores the keys then it may be a different matter. Of course, there is no a priori reason to assume it does not have the side channel too. And you need to get the keys into it securely.