2
$\begingroup$

I'm studying up on Merkle Damgård construction for hashing and having some trouble understanding the "padding block", at the end of the message blocks.

When you look it up it says that in the padding block "the message length is encoded in the block". But I'm having some trouble understanding what that actually means.

If the message length is 16, does that mean that the padding block is = 10000? or does it mean that the padding block is a string of zeros of length 16?

$\endgroup$
0
4
$\begingroup$

Merke-Damgård construction uses a compression function $C$ that takes two inputs in each iteration. The previous block and a new message block. For example;

In SHA-256, the message is operated in 512-bit and the previous output of the previous compression function is the 256-bit input. The first compression function takes the Initial Values (IV)

$$C:\{0,1\}^{256}\times \{0,1\}^{512} \to \{0,1\}^{256}$$ and

$$H_i= C(H_{i-1},m_i)$$ with $H_0 =IV$, the last $H$ is the hash, and $m_i$ are the 512-bit.

Like in the CBC mode, the last message block needs padding to fit a multiple of the block size of the hash function.

Due to the MOV attack (see in Handbook of Applied Cryptography; Chapter 9, Example 9.23 or here ) the message length added to the end.

Depending on the hash function, some use 64-bit length encodings like SHA-1 and SHA-256 or 128-bit length encoding like SHA-512.

The padded message is $$\text{padded message} = [\underbrace{message}_{\text{message length } \ell}\mathbin\|\underbrace{1}_{\text{bit 1}}\mathbin\|\underbrace{0\cdots0}_{k \text{ zeroes}}\mathbin\|\underbrace{\text{length encoding}}_{64|128-bit}]$$

A more real example is

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

Usually, we operate on bytes, display in hex, in this case, the 100 part is 80..0.

If the message length is 16, does that mean that the padding block is = 10000? or does it mean that the padding block is a string of zeros of length 16?

No, depends on the hash algorithm it is either 64-bit or 128-bit encoded. So for SHA-256 (length encoding is 64-bit), you need to encode a message of length 16 bits in binary as

0000000000000000000000000000000000000000000000000000000000010000

Note that padding must be minimum, i.e. for SHA-256, in the below equation

$$\ell+1+k \equiv 448 \bmod 512$$

the minimum of $k\geq 0$ (number of zeroes) must be taken. Here, the $\ell$ is the message length, 1 for the added 1 are known and the $k$ must be determined minimally.

In the case of SHA-512, you will need to encode the message length into 128-bit. The minimal $k$ must be found with

$$\ell+1+k \equiv 896 \bmod 1024$$


Historical note: Merkle–Damgård construction was independently described by Ralph Merkle and Ivan Damgård.

  • Merkle, in their thesis mention only padding with 0s, page 14.
  • Damgård, in their article mentions only padding with 0s with adding the length of the padding at the end, page 420.
$\endgroup$
6
  • $\begingroup$ thx! but in the padded message=[𝑚𝑒𝑠𝑠𝑎𝑔𝑒‖1‖0⋯0‖length encoding] it looks as if the final block consist of four parts: 1.final message block 2. a bit 1 3. some 00's but how many? 4.the message length encoded? $\endgroup$ Jun 1 at 16:29
  • 1
    $\begingroup$ Firstly, the final block may not contain the message bits at all. Consider that message has only 512-bit. $k$ defines the number of ones. One needs to solve the equation to find the minimum number of 0. yes, the last part is always the encoded message length. Also, the number of zeroes can be 0. The zeros can come from the length encoding. $\endgroup$
    – kelalaka
    Jun 1 at 16:31
  • $\begingroup$ I don't really understand what "k defines the number of ones mean"? is it as many ones as is in the ciphertext, what is k? $\endgroup$ Jun 1 at 16:37
  • $\begingroup$ In the zeroes part of the padding add $k$ zero after $k$ is determined. $\endgroup$
    – kelalaka
    Jun 1 at 16:38
  • 1
    $\begingroup$ yes, that's it. $\endgroup$
    – kelalaka
    Jun 1 at 16: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.