# Merkle–Damgård transformation example

I m looking at this Example of Merkle–Damgård

I have a similar question about this topic.

I have hash function maps 256b blocks into 128b blocks, how many rounds are required for hashing a 140KB file?

My idea is to transform this 140kb into byte (140000 bytes) and divided this number on 256 ... So I have 546,875. So my hypothesis is that function use about 547 round, 546 are full of byte, and last round have some zeros inside?

I'm thinking good...or I'm too far?

## 1 Answer

Well, not exactly.

The hash function that your MD internally uses a compression function $$f:\{0,1\}^{256} \to \{0,1\}^{128}$$

MD construction uses an IV, in your case 128-bit feed into the first call $$f$$. The first input and output of $$f$$ is $$h_1 = f(IV\mathbin\|m_1)$$. From these, you can deduce that you must divide your message $$m$$ into 128-bit blocks. 1093 rounds that make 1093*128 = 139904 that is 96-bit less than a full block.

Therefore you need padding and also protection against length extension attacks.

Assume that we simply use the last 64-bit as the big-endian length encoding and padding is 1000000...000Length_in_64_bit. In the end, we require that the size after the padding is a minimum multiple of 128. In your case, your message becomes

$$m =\texttt{M}\mathbin\|\texttt{100...0}\mathbin\|\ell$$ where $$\ell$$ is the encoding of your length. 96 bits don't leave space for a 1 and encoded length. Therefore you need 1095 round that is 140160 bits.

Now you can divide your message into 128-bit blocks say; $$m_1,\ldots,m_{1095}$$

\begin{align} h_0 &= f(IV\mathbin\|m_1)\\ h_i &= f(h_{i-1}\mathbin\|m_u), \quad 1

Note that, MD can also apply a finalization with $$g$$ in the end. In this case $$H(m) = g(h_{1095})$$ 