HMAC ipad and opad choice

Question

It is written in the HMAC paper that the ipad=0x36 and opad=0x5C were chosen such that it maximize the Hamming-Distance of the part of the key used in the inner and outer part of the HMAC process.

Since 0x36=0b0110110 and 0x5c=0b1011100, it seems that the Hamming distance is 4, but I would expect that ipad and opad with Hamming distance of 8 would have been used.

Do you know how does those exact ipad and opad values make the scheme stronger?

Answer 1

To quote from the paper you linked:

The above particular values of $\mathrm{opad}$ and $\mathrm{ipad}$ were chosen to have a very simple representation (to simplify the function’s specification and minimize the potential of implementation errors), and to provide a high Hamming distance between the pads. The latter is intended to exploit the mixing properties attributed to the compression function underlying the hash schemes in use. These properties are important in order to provide computational independence between the two derived keys.

Note that a "high" Hamming distance is not exactly the right term: In fact, $4$ is the mean Hamming distance, i.e., half of the bits are flipped.

For lower distances, we have $\mathrm{opad}\approx\mathrm{ipad}$, thus the keys fed into the compression function are very similar: Those seem more likely to trigger some vulnerability of the underlying compression function than keys without such a simple relation.

Similarly, high Hamming distances imply that $\mathrm{opad}\approx\overline{\mathrm{ipad}}$ (and in the extreme case $8$ we have equality), so there is again a nice relation between the two pads, falling under the same reasoning. _{^{(For example, even though not a hash function, DES has the complement property $E_k(x)=\overline{E_{\bar k}(\bar x)}$, showing that such things can indeed happen in cryptographic primitives.)}}

Thus, it seems like a reasonable choice to select pads that have the most "non-regular" Hamming distance: This means flipping not too few and not too many bits.

---

And indeed, it turned out later that those values do matter in some situations: The 2012 paper Generic related-key attacks for HMAC presents a related-key attack on HMAC that depends on the values of $\mathrm{opad}$ and $\mathrm{ipad}$. The authors state:

In the case of HMAC this is possible only when $k=m$ or $k=m-1$ since the last bit of ipad and opad are equal (otherwise, for a smaller key the attacker can not build a proper related-key). This shows that the choice of ipad and opad is not anecdotal. For example, if ipad and opad were very similar, then our attacks would work for basically any key length.