# Tag Info

## Hot answers tagged merkle-damgaard

14

MD5, like other hash functions, uses the Merkle-Damgard construction. You take the message and break it up into fixed-size blocks. You start with an intialization vector (IV), which you feed into a compression function along with the first block. Take the output (it will be the same length as the IV), and feed it into the compression function along with the ...

9

The Merkle–Damgård hash construction customarily pads the message $M$ to be hashed with a single bit set to 1, a minimal number of bit(s) set to 0, and the representation of the length of the message in binary over some fixed number of bits. The padded message is then formed of a number of blocks $B_i$. The hash is computed by repeatedly applying a ...

7

Actually, the Merkle–Damgård construction also specifies a padding bit after the message. The length is there the ensure that a padded message cannot be the suffix of a different longer message. A collision at the prefix leads to a collision in both messages. With a padding bit, a singe byte message 0x30 vs a 2 byte message 0x30 0x00 are padded to 0x30 0x80 ...

7

A compression function takes two fixed size inputs: a chaining value and a message and returns a fixed size value. So it's essentially a hash function with fixed input size. Merkle-Damgård is a domain extender, which turns that compression function into a hash which supports arbitrarily long messages. MD uses the output of the compression of one block as ...

7

As far as I am aware, there are no practical known second pre-image attacks on MD5, under the conditions you listed. However: if the attacker can control any part of the original, I would worry about using MD5 in this setting. Its security in this setting may be fragile and there may well be cleverer attacks than anything currently in the literature. I ...

7

How does the length extension attack against $H(k||m)$ work? For Merkle-Damgård hashes, if you know $H(x)$ but not $x$ you can still choose an $e$ and then compute $H(x||p||e)$. With $x=k||m$ you can compute $H((k||m||p)||e)=H(k||(m||p||e))$ which is a valid authentication tag for $m||p||e$. Why doesn't it work against $H(m||k)$? With a length extension ...

6

One issue with this construction is described in section 6 of the original HMAC paper, "Keying hash functions for message authentication" by Bellare, Canetti and Krawczyk, where they note that finding a collision on $\mathcal H$, i.e. two inputs $x \ne x'$ such that $\mathcal H(x) = \mathcal H(x')$, directly yields a collision on $\mathcal C$ such that $\... 5 One reason is convenience: if the IV was variable, it would have to be transmitted to a party verifying the hash, and we'd have to deal with its integrity. Another reason is that it avoids an attack in a Merkle–Damgård variant with padding reduced to appending a single 1 bit and as many zeros as necessary to end the block. With such scheme and common ... 5 Yes, if the length is formatted in a constant-size value (e.g. 64-bit field) or in an otherwise uniquely decodable manner. With such a length field, no hash input can be the the prefix of another valid input. Thus there is no length-extension attack. (Assumptions include that you reveal no intermediate values, of course.) 5 There is a beautiful characterization for the collision preserving padding rule of any Merkle–Damgård-construction: the padding rule should be suffix free. See the 2009 paper Characterizing Padding Rules of MD Hash Functions Preserving Collision Security by Mridul Nandi for more details. The length of the message, as it turns out to be, is the simplest ... 4 The answer is that you can't; if you have a collision in$h^*$, you also have a collision in$h$. The standard way to prove a collision-resistant hash based on a hash-resistant primitive is to show that if we are given a collision in the full hash, we can show that gives us a collision in the primitive. Hence if we believe we can't find a collision in the ... 3 No, it is not possible. If two inputs with different length produce identical hash outputs, then there would be a collision in the last invocation of the compression function. This is because the last input to the compression function always encodes the length of the original message. If two inputs with identical length produce identical hash outputs, then ... 3 You understanding is a bit incorrect. There is no requirement that the output length of the compression function is exactly half of that of the input. Typical compression functions have an output which is much shorter than half the input length. The Merkle-Damgård construction uses a compression function which takes an input with a length that is the sum of ... 2 The MAC you created is what's commonly called a keyed hash function. The way you have done it has a couple of issues. One is that you're hashing the message and then the key, but it's better to do the key and then the message. The reason for that is that if someone finds a collision with your message, then they are going to end up with the same MAC. It is ... 2 Isn't it still possible to find two different inputs that will be padded to the same value and then deliver the same hash? Well, no, it isn't. Given a padded message (that is, padded by adding a 1 bit, and then as many 0 bits as needed to fill it out to a multiple of the internal block size), we can unambiguously recover the original message -- by ... 2 In most Merkle–Damgård hash functions, it uses a block cipher in the compression function, with the inputs being the padded message blocks and the IV. The IV is the fixed width input plaintext to the cipher, and the message becomes the key. The hashing of the input block x1 works by expanding it (using a key expansion) so that there are as many subkeys as ... 2 The relevant part of Neven et al is this: What this means for practice is that one should not instantiate the hash function with a Merkle-Damgård iteration of an$n$-bit compression function. Instead, one should probably simply truncate the output of a$2n$-bit hash function to$n$bits. (Such a method would in our situation be reminiscent of Lucks’ wide-... 2 It depends on the exact Merkle-Damgaard hash. MD5 will literally take an arbitrary length; that's because the value placed in the padding is actually computed modulo$2^{64}$. For SHA-1 and the SHA-2 hashes, yes, you are correct; there is an upper bound on the length of the preimages that could potentially be hashed; for SHA-1, SHA-224 and SHA-256, it's$2^...

2

If you want to construct a PRF for arbitrarily-long inputs using AES, then just use CBC-MAC (while prepending the message length in the first block). I don't see any advantage in what you are proposing and therefore don't see any point in trying to analyze something non-standard.

2

Yes, a Merkle–Damgård hash can be one-way. Even MD5 hasn't been broken in that way. Target collision resistance (TCR) is a notion similar to second preimage resistance (but for keyed functions). Preimage resistance, i.e. one-wayness, does not imply second preimage resistance, so a hash function can be one-way without even having second preimage resistance. ...

1

If you go through what Ferguson said, I'm sure he'll include a condition that $m$ and $m'$ are the same length, which is also a multiple of the hash block size. In this case, $m||X$ and $m'||X$ will not be preprocessed into single blocks; instead, they'll be processed as (at least) two blocks; one being $m$ (or $m'$), and the rest consisting only of $X$. ...

1

Using AES as a Davies Meyer compression function is a bad idea: It has a block size of 128 bits, which limits its collision resistance to 64 bits, which is rather weak. This limitation could be overcome by using Rijndael with a 256 bit block size, but then you'd need to use a higher number of rounds. AES has been designed to work with randomly chosen keys,...

1

Yes, of course it is possible. Let's consider with below example: Our compression function: $f:\{0,1\}^{(128+512+1)} → \{0,1\}^{128}$ Message $x$ has 1000 bits: ($y$'s are our input blocks and $z$'s are output blocks. Considered a Merkle–Damgård construction.) $y_1$ is first 512 bits of $x$ $y_2$ is last 488 bits of $x||0^{24}$ $y_3$ is \$0^{480}||“32-bit\...

Only top voted, non community-wiki answers of a minimum length are eligible