1
$\begingroup$

Is Merkle-Damgård essentially encrypting the IV with the given message? I may be wrong but this is how I understand Merkle-Damgård:

There is a message of an arbitrary length, which is broken up into blocks before it can be encrypted; the blocks can be padded if necessary. Then a fixed IV is used and the first block of the message is run through a compression function using something like AES (possibly derived from a block cipher) with the IV. The output is then taken as the IV for the next round. In the end, the resulting output is the same size as the IV.

What is my error in understanding?

$\endgroup$
  • 1
    $\begingroup$ there really isnt much error at all that is essentially correct $\endgroup$ – Richie Frame Oct 16 '16 at 3:30
  • $\begingroup$ crypto.stackexchange.com/questions/11615 $\endgroup$ – Richie Frame Oct 16 '16 at 3:31
  • $\begingroup$ A block cipher in Merkle-Damgård could go really wrong. Also, you have to have some twist in Merkle-Damgård for some block to get a security proof. $\endgroup$ – K.G. Oct 16 '16 at 19:00
4
$\begingroup$

broken up into blocks before it can be (hashed)... Then a fixed IV is used...

In practice, you may not even know the entire message before beginning hashing. So this is incorrect. You divide into blocks as more of the message becomes available.

before it can be encrypted

You are not encrypting. You are hashing.

the blocks can be padded if necessary

Padding is always added, not only added if necessary.

the first block of the message is run through a compression function using something like AES (possibly derived from a block cipher) with the IV

So this is sort of correct. We don't use AES, but the constructions are similar/derived from block cipher principles. The key requirement is that the compression function should be collision resistant. With a block-cipher, you typically need to be able to undo the encryption. This is not necessary for a hash function's compression function.

Specifically related to AES, another reason we don't just use AES is that is only has a 128 bit block size. This is insufficient for the types of hashes we see today, which have at least a 224 bit output (SHA-2). The internal state must be wider than 128 bits.

P.S., thanks to fgrieu for some additional points that I have added.

$\endgroup$
  • 1
    $\begingroup$ Also, "broken up into blocks before it can be (hashed)... Then a fixed IV is used..." does not match practice: the message is commonly hashed before it is fully known and broken into blocks, and the IV is used for that. The practice is why the padding is in the last block, or last two blocks. And: using a single AES would be a poor choice for the compression function, in particular because that would limit the hash to 128 bits, not wide enough for a modern secure hash. Compression functions use the same techniques as ciphers, but typically are custom designed. $\endgroup$ – fgrieu Oct 18 '16 at 6:20

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.