45
$\begingroup$

Wikipedia lists the following pseudocode for HMAC:

function hmac (key, message)
    if (length(key) > blocksize) then
        key = hash(key) // keys longer than blocksize are shortened
    end if
    if (length(key) < blocksize) then
        // keys shorter than blocksize are zero-padded ('∥' is concatenation) 
        key = key ∥ [0x00 * (blocksize - length(key))] 
    end if

    // Where blocksize is that of the underlying hash function   
    o_key_pad = [0x5c * blocksize] ⊕ key 
    // Where ⊕ is exclusive or (XOR)
    i_key_pad = [0x36 * blocksize] ⊕ key 

    // Where '∥' is concatenation   
    return hash(o_key_pad ∥ hash(i_key_pad ∥ message)) 
end function

Why are they there? How were they chosen?

It seems to me that $hash(key + hash(message))$ (where + is concatenation) would suffice.

Obviously I'm missing something. What is it?

$\endgroup$

2 Answers 2

29
$\begingroup$

Those "magic numbers" are related to the security proof behind the HMAC construction.

In their Crypto'96 paper, Bellare, Canetti and Krawczyk first prove that $\mathrm{NMAC}_{(k_1, k_2)}(x) = F_{k_2}(F_{k_1}(x))$ forms a secure MAC ("message authentication code") provided $F_k(\cdot)$ is an iterated and keyed compression function enjoying some good security properties and $k_1$ and $k_2$ are statistically independent keys. NMAC could be instantiated by common iterated hash functions, such as SHA-256, but one should be able to replace the IV by the key, which is not possible with standard implementations.

To avoid this practical problem, the authors have defined another mechanism, named HMAC. Given a single key $k$ as well as an iterated hash function $H(\cdot)$ built out of a compression function $f(\cdot)$, they first derive two keys $k_1 = f(k \oplus \mathtt{opad})$ and $k_2 = f(k \oplus \mathtt{ipad})$ out of $k$ and define $\mathrm{HMAC}_k(x) = \mathrm{NMAC}_{(k_1, k_2)}(x)$. Thus, the constants $\mathtt{ipad}$ and $\mathtt{opad}$ are just meant to be different, such that the inputs $k \oplus \mathtt{opad}$ and $k \oplus \mathtt{ipad}$ to the compression function are different. Their values have been arbitrarily chosen by the HMAC designers, and any pair $(\mathtt{opad}, \mathtt{ipad})$ could have been selected, as long as $\mathtt{opad} \neq \mathtt{ipad}$.

$\endgroup$
2
  • 3
    $\begingroup$ Wouldn't just one of the pads have sufficed then? What's the rationale behind having two? $\endgroup$ Mar 8, 2013 at 19:55
  • $\begingroup$ Obviously, using a single constant would have fitted the security proof; I don't know why they chose two. $\endgroup$ Mar 11, 2013 at 9:48
15
$\begingroup$

The original security proof of HMAC, as well as a new one not requiring collision-resistance of hash, are for the construction hash(o_key_pad ∥ hash(i_key_pad ∥ message)) with o_key_pad different from i_key_pad (and both filling a block). That's the rationale for at least one of the constant. The other plays no role, it just must be different from the first. That's well explained in cryptopathe's detailed answer.

Also, notice that the proposed substitute hash(key ∥ hash(message)) fails to be indistinguishable from a random function for unknown key if the hash is MD5 (or another hash with broken collision resistance): it is easy to make messages colliding for MD5, thus for this construct; while HMAC-MD5 still stands relatively strong, thanks to the extra i_key_pad.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.