Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
0s, page 14.0s with adding the length of the padding at the end, page 420.
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, 2021 at 16:29
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$