2
$\begingroup$

In the Length extension attack of Wikipedia

The following information summarizes the relevant information provided on the page at the time of posting this question.

The provided parameters are

  • secret length: 14
  • message: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
  • the original signature is 6d5f807e23db210bc254a28be2d6759a0f5f5d99
  • the page does not explicitly state it, but we can infer that the hash algorithm used in the example is SHA-1 (using SHA-1 yields the new signature provided in the example, 0e41270260895979317fff3898ab85668953aaa2)

The extended message (referred to on the page as "New data", reformatted here to remove the line breaks and spaces) is listed as: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02\x28&waffle=liege

The padding should yield a message length in bits (excluding the extension) that is a multiple of 512.

Counting the bits in "New data" (excluding the extension):

  • message length in bits = 55 * 8 = 440
  • secret length in bits = 14 * 8 = 112
  • padding in bits: 58 * 8 = 464
  • total length in bits (excluding the extension) = 1016

Based on the above calculation, there are 8 bits missing, so "New data" should include another \x00. Is my calculation/reasoning/understanding wrong?

Improve this question
$\endgroup$
2
  • $\begingroup$ Thanks for your comment @kelalaka. I'm only asking about the length of the padding in the extended message example that is shown on the page. It seems like the padding in the example is wrong because the total length should be a multiple of 512, in this case 1024, but it is 1016. Will you help me understand, please? $\endgroup$
    – ajh158
    Commented May 6, 2021 at 20:47
  • $\begingroup$ Thanks for the good edit, @fgrieu $\endgroup$
    – ajh158
    Commented May 6, 2021 at 20:49

1 Answer 1

Reset to default
2
$\begingroup$

50- byte padding staring with 1 and rest is zero ( each \ is a byte)

\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
\x00\x00

8-byte size part of padding where the size is encoded ( SHA-1 has 64-bit length encoding in the padding that makes 8-byte)

\x00\x00\x00\x00\x00\x00\x02\x28

0x228 = 552 and we have 69 bytes of message size.

That is correct. 55-byte message and 14-byte secret make a 69-byte message.

The message in bits makes 552 bits that are over one block of SHA-1 that has a 512-bit block size. So in total, we need 1024 bits for hashing, two blocks. 64 bits reserved for the message size. This left 960 bits. Now subtract the 552-bit message size and we have 408 bits. So we need 51 bytes of padding starting with 0x80 but we have 50, i.e. $\color{red}{\text{1-byte is missing. Your calculations are correct}}$.

We should have;

$$\underbrace{secret}_{14-byte}\mathbin\|\underbrace{message}_{55-byte}\mathbin\|\underbrace{100\ldots00}_{51-byte \text{ padding 10 part}}\mathbin\|\underbrace{000\ldots 0228}_{8-byte \text{ length part}}$$

SHA-1 padding rule

append the bit $\texttt{1}$ to the message e.g. by adding byte $\texttt{0x80}$ if message length is a multiple of 8 bits i.e. byte-oriented.

append $0 \leq k < 512$ bits of zeroes, such that the resulting message length in bits is congruent to $$−64 \equiv 448 \pmod{512}$$

append the original message length, as a 64-bit big-endian integer. Thus, the total length is a multiple of 512 bits.

The real extension;

Wikipedia doesn't show the required padding after &waffle=liege is appended. This is 13 bytes text and the size of the message will be $1024+13*8= 1128$. Therefore we will need 3 blocks for the extension that makes total of 1536 bits. 64 bits of this will be the new size encoding and this will need 344 bits of $1000.000$

$$\underbrace{secret}_{14-byte}\mathbin\|\underbrace{message}_{55-byte}\mathbin\|\underbrace{100\ldots00}_{51-byte \text{ padding 10 part}}\mathbin\|\underbrace{000\ldots 0228}_{8-byte \text{ length part}} \mathbin\|\underbrace{\text{&waffle=liege}}_{13-byte \text{ extended message}} \mathbin\|\underbrace{100\ldots00}_{43-byte \text{ padding 10 part}} \mathbin\|\underbrace{000\ldots 0468}_{8-byte \text{ extended length part}} $$

In other view;

$$\text{SHA-1}(\text{secret_key}\mathbin\|\text{message}\mathbin\| \text{pad1}\mathbin\| \text{appended_data} \mathbin\| \text{pad2})$$

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Based on discussion with @kelalaka (in now-deleted comments), the padding on the wikipedia page was wrong - as proposed in the question. I edited the wikipedia page to add the missing byte. $\endgroup$
    – ajh158
    Commented May 6, 2021 at 21:51

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.