# Tag Info

## Hot answers tagged merkle-damgaard

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

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

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

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

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

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

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

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

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

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

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

5

Some ideas (not a definitive answer): Davies–Meyer is one of the two simplest among the 12 secure methods by which a block cipher and XOR can be turned into an iterative hash with one encryption per block, per the analysis of Bart Preneel, René Govaerts, Joos Vandewalle's Hash functions based on block ciphers: a synthetic approach, in proceedings of Crypto ...

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

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

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

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(\... 4 Why not use chacha derivatives (BLAKE, rumba) to make an [H]MAC for use with chacha? Why use poly1305? Performance. Poly1305 is extremely cheap to compute, and the computation can be essentially arbitrarily parallelized, because it's just evaluating a polynomial modulo$2^{130} - 5$. In contrast, functions like BLAKE2 and Rumba20 can't be parallelized ... 3 Take any standard hash function family$\{h_s(\cdot)\}_s$, a point$c$and a list of inputs$(x_s)_s$and define$h'_s : x \mapsto h_s(x)$if$x\neq x_s$, and$c$otherwise. As you said, it does not contradict collision resistance or preimage resistance - in other words, you can prove that if$(h_s)_s\$ is a family of (say) collision-resistant hash functions, ...

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