Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 11 down vote accepted

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(.)$ 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(.)$ built out of a compression function $f(.)$, 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}$.

share|improve this answer
    
Wouldn't just one of the pads have sufficed then? What's the rationale behind having two? –  BlueRaja - Danny Pflughoeft Mar 8 '13 at 19:55
    
Obviously, using a single constant would have fitted the security proof; I don't know why they chose two. –  cryptopathe Mar 11 '13 at 9:48
add comment

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.

share|improve this answer
    
Thanks for the second part. –  sneak Jun 22 '12 at 10:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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