20

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


18

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


18

Let hash be the raw hash function, as you're referring to. You mentioned that the attacker knows hash(message || length), but to be more precise, they know hash(message || padding || length). Let full_hash be the proper hash with padding and length, i.e. full_hash(message) = hash(message || padding || length). You're correct that if the attacker knows hash(...


15

No. That is about as accurate as saying that airplanes are based on motorcycles, because they both have engines. In MD, the input to the hash is converted to a key, which is used by a block cipher to encrypt the initial value, then the entire encrypted value is the hash. In a sponge based hash, the input is XOR'd into the initial value, then the entire ...


13

Using $H(m\mathbin\Vert k)$ with hash function $H$, message $m$ and key $k$, is one possible way to build a MAC algorithm. It is not necessarily a good one; it depends on the used hash function. Even when it is a good one, that does not preclude the possibility of other, "better" algorithms (e.g. for performance). As an illustration of potential security ...


12

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


10

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


9

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


9

If the input message is longer than 512 bits, the input is chopped in “chunks” (read: pieces) with fitting length (512 bits) and those are successively fed to the hash compression function. See, in layman’s terms, SHA-256 processes things like this: init SHA-256 while there are input chunks, update hash compression function with the next input chunk (pad ...


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

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


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


7

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


7

Not quite. But it would allow computing ${\rm MD5}(M \,\|\, {\rm pad}_M \,\|\, m \,\|\, {\rm pad}_m \,\|\, {\rm whatever})$, where ${\rm pad}_M$ and ${\rm pad}_m$ are the extra length padding bytes appended to $M$ and $m$ respectively by the MD5 algorithm, as described in RFC 1321 sections 3.1 and 3.2. To see why, it's worth looking at how the MD5 hash (...


7

Yes, a hash built per the Merkle-Damgård construction can be collision-resistant even if its compression function has a known collision. Consider SHA-256. Note its round function $F:\{0,1\}^{256}\times\{0,1\}^{512}\to\{0,1\}^{256}$ where the first argument is the state and the second is a message block. Now define $F'$ identical to $F$, except that $F'(0^{...


6

A lot of this is explained well on the wikipedia article. The function $f$ is called the compression function. It is a function $$f:\left\{0,1\right\}^n\times\left\{0,1\right\}^\ell\to\left\{0,1\right\}^n.$$ That is, it takes as input an $n$-bit value and an $\ell$-bit value, and outputs an $n$-bit value. This function is a building block for the function $...


6

There's two ways to answer this. One would be to go over the individual M-D weaknesses you list and show why the sponge construction is resistant to them. For example, if you consider length extension, the attacker knows: The permutation $F$, capacity $c$, bitrate $r$ and padding rule used in the sponge instance; The length of a message $m$ and its hash ...


6

Yes. In this paper, Coron and al. showed that a plain MD construction is secure when it's inputs are prefix-free. They actually proved the indifferentiability of the construction. In other words messages need to be encoded in a prefix-free manner. Quoting the paper: A prefix-free code over the alphabet $\{0, 1\}^κ$is an efficiently computable injective ...


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

One issue is that it would make finding preimages significantly easier; with $O(2^{n/2})$ time rather than $O(2^n)$ time. Here's how you would do such a search: Select $2^{n/2}$ distinct initial halves of the message, and determine the intermediate state for the hash after processing each message. Select $2^{n/2}$ distinct final halves of the message, and ...


5

TL;DR: A simple reason why we use the IV is to mitigate second preimage attacks. This is the typical Merkle–Damgård construction: you split your messages in blocs of $k$ bits (input size of the compression function). M1 M2 ... Mn | | | +--|\ +--|\ +--|\ | \ | \ | \ IV ---| |-------| ...


5

As rightly pointed in the question, 0*+length padding would work just as well as 10*+length padding, with the benefit of simplicity and requiring one less block in some cases, like SHA-256 for a message of 56 bytes. I guess SHA-2 does this because SHA-1 did, and before that SHA, MD5, and Ronald Rivest's MD4 (1990), which is the earliest reference that I can ...


5

OK, so the core ChaCha primitive (for any fixed number of rounds) is a function $\operatorname{ChaCha}: \{0,1\}^{256}\times \{0,1\}^{64}\times\{0,1\}^{64}\to \{0,1\}^{512}$ which is believed to be a secure PRF when the first input is the key. So now that we know what ChaCha is, for the three desired functionalities: MAC. Of course a PRF is also immediately ...


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


4

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


4

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


4

Is there any reason why don't more cryptographic hash functions use a Merkle tree-like construction directly instead of just adding them as a way to allow parallelism to existing hash functions on top of the Merkle-Damgård or the Sponge construction? The reason is that a Merkle tree comes with computation overheads that the serial hash functions do ...


4

Your question essentially is how message length is dealt with in Merkle-Damgård constructions. However, your description is flawed so let's clarify some things: The whole point of using this kind of construction is to build a hash function that maps arbitrary-length inputs to fixed-length outputs, given a compression function (that is hopefully collision-...


4

MD5 and SHA-1 have been broken (from a collision-resistance perspective) due to weaknesses of their compression function, not because they are Merkle–Damgård based. SHA-2 hashes (SHA-256, SHA-512..) are Merkle–Damgård based, but use more compute-intensive compression functions, and are so far unbroken. SHA-3 is not Merkle–Damgård based, it uses the sponge ...


4

Let $n$ be the digest length of a hash function $\operatorname{MD}^f:\{0,1\}^*\to\{0,1\}^n$. Now quoting the paper you linked: chopMD. For $0\leq s<n$ we define $\operatorname{chop}_s(x)=x_R$ where $x=x_L\parallel x_R$ and $\left|x_L\right|=s$. In this paper we fix $0<s<n$ and define $\operatorname{chopMD}^f(M)=\operatorname{chop}_s(\...


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