2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

compression function

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<i\leq 1095\\ H(M) &= h_{1095} \end{align}

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

Note the index difference

|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ thank you so much! I got it! $\endgroup$ – theantomc Nov 15 '19 at 11:51

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.