3
$\begingroup$

As everybody knows in order to calculate HMAC we have to concatenate padding to the message. I am just curious why the padding needs to be fixed-length. Why do we need the blocksize parameter here?

Why not use an arbitrary length key with arbitrary length 0x5c5c5c…5c, 0x363636…36?

Why do we need to truncate the key when it is larger than the blocksize?

$\endgroup$

1 Answer 1

2
$\begingroup$

In HMAC, the key $K$ [after it has been replaced by $H(K)$ if $K$ was wider than the hash's internal block size] is padded with zeros to the hash's internal block size. The question asks why this padding.

In a nutshell: the security argument of HMAC would not hold without that.

HMAC's original and improved security arguments make heavy use of the Merkle–Damgård internal structure of the hash, that is: $$\begin{align} H_0&=\text{IV}&\text{ initialization with a public constant}\\ H_{i+1}&=F(H_i,B_i)&\text{ process }n\text{ padded blocks with the round function }F\\ \text{output}&=H_n&\text{ final result} \end{align}$$ Heavily simplified, a central requirement of the proof is that during the first of the two hashes in HMAC, if the adversary knows nothing ultimately exploitable about $H_i$, then even though she might know and be able to manipulate $B_i$, she will know nothing ultimately exploitable about $H_{i+1}$. The padding performed on $K$ is such that $K$ maps (within XOR with constant ipad) exactly to $B_0$, and that is enough to insure that the adversary knows nothing ultimately exploitable about $H_1$; that bootstraps the proof by induction that the adversary knows nothing ultimately exploitable about any $H_i$ for $i>0$, hence knows nothing ultimately exploitable about the output of the first hash in HMAC. By contrast, without padding, the adversary would be able to manipulate in part $B_0$, which is mixed by $F$ with the known $H_0$, and we'd have no bootstrap of the security argument.

The second hash in HMAC transforms said nothing ultimately exploitable about the output of the first hash into an overall HMAC output which is indistinguishable from random; again the proof uses that the adversary does not know the other input $H_1$ of the function $F$ that receives the first hash's output, since that is entirely within $B_1$, thanks to the padding of $K$.


When the key $K$ is larger than a block, HMAC replaces it with its hash. Keeping the key as is, unpadded, would not be satisfactory for the same reason as above: we'd have no security argument (e.g. for 64-byte block size, 20-byte hash size, 84-byte key of which the first 64 bytes are zero).

I think padding with zeros to the next block would provide adequate security. But compared to that option, replacing the key with its hash:

  • leaves the security argument unchanged (it aims at the security level of the hash width, which is about that of the hashed key substituted to the original);
  • decreases the computational complexity of processing long keys by a factor of 2 (asymptotically);
  • only ever increases the number of internal hash rounds (and then only by 1 round out of at least 6) for a narrow range of key size (for SHA-1 and SHA-256: 120 to 128 bytes).
$\endgroup$
1
  • $\begingroup$ Thank you, now I feel more understand about the reasons behind HMAC but if I understand correctly the padding used to make an attacker unable to control part of B0 but what about "Why the key should be truncated?" part. If I use a long key that fill B0 why the key should be truncated? Is this just for convenient of implementation or someone can mount related key attack to reveal part of key when they can control B1? $\endgroup$ Apr 14, 2014 at 21:16

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.