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.
- 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.
- 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.
- Would it be possible to retrieve the key used to key the HMAC algorithm?
- 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.