1
$\begingroup$

In the book Information Security Principles and Practice, the author explains why HMAC should be used for integrity with a symmetric key with the message, to prevent a MiTM to replace both the message and its MAC.

He explains why it is not secure to prepend the key to the message, with notation h(K, M). I don't understand how the attack works. Here's the paragraph:

Suppose we choose to compute an HMAC as h(K,M). Most cryptographic hashes hash the message in blocks—for MD5, SHA-1, and Tiger, the block size is 512 bits. As a result, if M = {B1, B2), where each Bi is 512 bits, then h(M) = F(F(A, B1), B2) = F(h(B1), B2) (5.2)
for some function F, where A is a fixed initial constant.
For example, in the Tiger hash, the function F consists of the outer rounds illustrated in Figure 5.2, with each Bi corresponding to a 512-bit block of input and A
corresponding to the 192-bit initial value (a,b,c).

If Trudy chooses M' so that M' = (M, X), Trudy might be able to use equation (5.2) to find
h(K, M') from h(K, M) without knowing K since, for K, M, and X
of the appropriate size, h(K, M') = h(K, M, X) = F(h(K, M),X), where the function F is known.

The last paragraph is the attack.

I don't understand, how does the attack work? How can Trudy find h(K, M') from h(K, M) without knowing K?

$\endgroup$
  • 1
    $\begingroup$ This is the length extension attack. Also, the hash functions pads the message before hashing. So one needs to consider {B1,B2} as padded message. $\endgroup$ – kelalaka Apr 10 at 13:03
  • $\begingroup$ Could you also edit the quoted part to make it clear? the vvv's and 5,2 has no usage here. You can also add a picture for the figure. $\endgroup$ – kelalaka Apr 10 at 13:07
  • $\begingroup$ @kelalaka edited; there is no picture $\endgroup$ – kewiro5 Apr 11 at 14:17
1
$\begingroup$

This is a basic length extension attack. For hash functions like SHA-1 and SHA-2 the final state of hashing $h(K \| M)$ block by block is the output. If you hash $h(K \| M \| X)$ then you simply continue hashing from the given state (i.e. the last output).

In practice though the final block must contain a valid padding and length, which is added to $K \| M$. So basically you can create a valid hash for $K \| M \| P \| LE \| X$ where $P$ is the padding and $LE$ is the length encoding. You cannot just create any message that starts with $M$.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Length extension attacks are KMPLEX :P $\endgroup$ – Maarten Bodewes Apr 13 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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