Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [merkle-damgaard]

The Merkle–Damgård construction — used in the design of many popular hash algorithms such as MD5, SHA1 and SHA2 — is a method of building collision-resistant cryptographic hash functions from collision-resistant one-way compression functions. The Merkle–Damgård construction is also referred to as the Merkle–Damgård hash function.

Filter by
Sorted by
Tagged with
2
votes
2answers
151 views

Why not use chacha derivatives (BLAKE, rumba) to make an [H]MAC for use with chacha? Why use poly1305?

Why not use chacha derivatives (BLAKE, rumba) to make an [H]MAC for use with chacha? Why use poly1305? This question is especially interesting considering... "The security of Poly1305[...] is very ...
2
votes
1answer
35 views

Merkle–Damgård transformation example

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 ...
6
votes
2answers
2k views

If hash functions append the length, why does length extension attack work? [duplicate]

I have understood that it's trivial to reconstruct the internal state of a hasher for many hash functions, if one only knows the output hash. Then, one can append data after the original data and ...
0
votes
0answers
64 views

Why is Proof of non-inclusion in a Merkle Tree harder than Proof of inclusion?

I am new to cryptography and I am wondering Why is Proof of non-inclusion in a Merkle Tree harder than Proof of inclusion? My naive thought for Proof of non-inclusion is that I would look for ...
2
votes
2answers
257 views

Have there been efforts to prevent length extension attacks of hashing algorithms that are based on the Merkle–Damgård construction?

Have there ever been some publicized efforts to prevent length extension attacks of hashing algorithms that are based on the Merkle–Damgård construction (MD5, SHA1, SHA2, ...)?
1
vote
1answer
106 views

How is an IV used in a Merkle-Damgard construction- Explicit example

I am interested to know how an IV is used in this simple Merkle-Damgard construction. I am referring to this image from the associated Wikipedia page as I explain further. For the purpose of ...
6
votes
2answers
807 views

Compression function is not collision resistant but Merkle-Damgard is collision resistant

Is it possible that you can still have a collision resistance in Merkle-Damgard even if the compression function has a collision?
1
vote
0answers
66 views

A modification of the NMAC construction

Consider the NMAC construction: This is a proposed exercise in my notes: Assume F is a PRP with $n = l(n)$. Is it secure to replace $k_0$ by $F_{0^n}(k_0)$ and $k_i$ by $F_{0^n}(k_i)$? In ...
3
votes
1answer
92 views

Is tweakable block-cipher based on the Merkle-Damgård construction secure if $F$ is a PRP

Assume $F$ is a pseudo-random permutation (PRP) then the tweakable block-cipher based on the Merkle-Damgård construction (take this as the way I understand, here is the equation): $F_k[t](m) := F_{...
12
votes
2answers
344 views

Why was Davies–Meyer chosen over Miyaguchi–Preneel most of the time?

The only Miyaguchi–Preneel MD hash I know is Whirlpool. I suppose there are likely others. Why do most MD hashes choose Davies–Meyer? If anything, Davies–Meyer relies on related-key resistance while ...
3
votes
2answers
331 views

AES-128 as compression function in Merkle-Damgard construction

Using a compression function $f : A × A → A$. A basic version given by: $W_0 = IV$ $W_1 = f(W_0, m_1)$ $W_2 = f(W_1, m_2)$ ... $W_n = f(W_{n-1}, m_n)$ $W_n$ is the output of the hash function, $...
3
votes
1answer
95 views

Can length extension attacks be avoided by a single bit flip?

It always seemed to me that length extensions are possible simply because no special operation is performed after the last operation - for instance in a Merkle-Damgård construction. Basically the MD ...
2
votes
1answer
142 views

Is it possible to perform a length-extension attack if only the last bit of the new message changes?

Given a Merkle-Damgård hash function H, let's say SHA256, that computes a MAC as follows: ...
4
votes
1answer
428 views

What does ChopMD refer to in the default Go ECDSA package?

If one navigates to the ECDSA Go package page, he can observe that: This implementation derives the nonce from an AES-CTR CSPRNG keyed by ChopMD(256, SHA2-512(priv.D || entropy || hash)) While I ...
0
votes
1answer
61 views

Ease of breaking MD constructions

If hashing algorithms such as MD5 or SHA1 both use Merkle-Damgard constructions at their cores, why is it so easy to break them, and yet so much harder to break SHA3, which is also MDC based?
2
votes
1answer
87 views

How to perform Stampery.com's Merkle Proof?

I am using the Stampery API to anchor hashes into different Blockchains. I wanted to independently verify that my hash with the given Merkle Proof from Stampery. I tried to follow their Whitepaper but ...
2
votes
1answer
153 views

Why do you need padding block at the end of Merkle damgard if the input is multiple of block length?

Why do you need padding block at the end of Merkle Damgard if the input is multiple of block length? I learned that it was not collision resistant if a dummy block is not added to the end but I want ...
0
votes
1answer
35 views

AUTHENTICATE MERKLE TREE: In the passage below how is A able to confirm YB in the public file only knowing R, log2 intermediate values, and YB itself?

"If A wishes to confirm B's public enciphering key, then A need only know the first half of the public file, (which is where YB appears) and H(second half of public file) which is only 100 bits long. ...
1
vote
1answer
288 views

Confused about Merkle Damgard Transform - short messages?

With the Merkle Damgard Transform, how does it handle messages that are shorter than the input message length - hash digest length? Or in other words, how is the last block handled? So for example, if ...
2
votes
1answer
176 views

Why does FIPS 180-4 require the final padding block start with a 1?

From FIPS 180-4 § 5.1.1, the padding used for the SHA family of hashes begins with a binary 1, followed by a number of 0s, and finally a 64-bit representation of the message length: Suppose that the ...
3
votes
2answers
5k views

What happens if a SHA-256 input is too long (longer than 512 bits)?

What I understand is: When we parse a message into 512 bit message blocks. Then we extend the first message block to 64 entry array and start with the compression function. What happens if the ...
4
votes
2answers
239 views

Why are theoretical hash constructions based on the hardness of the discrete logarithm problem not really used in practice?

In an old 2010 Q&A at StackOverflow, Pornin states: … a good hash function "should not" allow a property such as surjectivity to be actually proven. This makes sense to me when looking at, for ...
0
votes
1answer
72 views

Why can an arbitrary compression function mapping $\{0,1\}^{m+2^m} \rightarrow \{0,1\}^m$ not seriously be considered collision resistant?

I recently got a question that I’ld like to share here, since answers might be useful (or at least interesting) for people diving into Merkle-Damgård hash constructions for the first time. We know ...
1
vote
2answers
77 views

Merkle–Damgård padded block concatenated outside the compression function hash?

I learned that the output of hash function from Merkle Damgard is H(x) = ZB+1 = h(ZB || L) = h(ZB - 1 || XB || L) where XB = block of padded x and L = XB+1 and ...
6
votes
2answers
548 views

Purpose of hashing last block in Merkle-Damgård?

Is hashing the last block in the Merkle-Damgård necessary in preventing collisions? i.e. What if I just outputted $z_B || L$, where $z_i$ is the hash of the last block of the message, L is the length ...
2
votes
1answer
771 views

Can someone give me an example of a Merkle–Damgård transformation?

I started reading "Bitcoin and Cryptocurrency Technologies - Princeton University" (coursera) and in the first chapter it talks about Merkle–Damgård transformations for SHA-256. I was trying to ...
0
votes
1answer
2k views

I didn't get the hash length extension attacks

I was trying to solve a cryptography challenge and the problem was about "hash length key extension". After some reading in different topics, I don't know why I still didn't solve the challenge. I ...
5
votes
1answer
617 views

Merkle trees instead of the Sponge or the Merkle-Damgård constructions for the design of cryptorgraphic hash functions

Most modern cryptographic hash functions use some form of compression function combined with a construction such as the Merkle-Damgård (MD5, SHA1, SHA2, etc), the Sponge construction (with Keccak as a ...
8
votes
1answer
296 views

Would finding a Merkle-Damgård preimage that doesn't change the initial state allow an attacker to prepend it to any hashed message?

Suppose, a message M was found so that MD5(M) = S, where S is the initial state of the MD5 function (0x01234567, ...). Given a hash MD5(m), would this allow computing MD5(M∥m∥padding), where padding ...
5
votes
1answer
186 views

Simple compression functions an sponge functions for educational purposes

For block ciphers, there are the very well designed schemes of Simple-DES and Simple-AES, which have been created not for security but for teaching the design principles of the real algorithms while ...
0
votes
1answer
119 views

Different literature padding for Merkle-Damgard

I don't think this question addresses what I want to ask. I was taught that the Merkle Damgard scheme worked as in this picture: Here I assume that we are inserting a pad in filling the last block of ...
0
votes
1answer
152 views

Why do MD5 and SHA-3 use different padding schemes?

What is the rationale for the difference between MD5 and SHA-3 padding schemes? MD5 appends 10* and then the 64-bit message length in bits. SHA-3 appends 10*1. Why do they use different padding ...
7
votes
1answer
534 views

How does the sponge construction avoid the weaknesses present in Merkle–Damgård hash function?

How are the weaknesses of the Merkle–Damgård construction (i.e. the Herding attack, multicollisions, length extension, expandable messages) avoided in the sponge construction?
8
votes
1answer
629 views

Why does SHA-2 call for doing 10* padding in addition to appending the message length?

Appending the length of the message when padding of a SHA-2 message is sufficient to satisfy the Merkle-Damgård construction. However the padding in SHA-2 also pads with 10* between the end of the ...
1
vote
2answers
816 views

Is it accurate to say that SHA-3 (keccak) is based on Merkle-Damgård?

I know that sponge functions are different in many ways. Yet I'd like to know if SHA-3 can nonetheless be said to be "based", if not simply "inspired", by the Merkle-Damgård construction. To be more ...
4
votes
2answers
179 views

How to find collisions in a secret-prefix Merkle–Damgård given an adversary that can choose the IV?

I am given the following Merkle–Damgård construction: Let $f \colon (\{0,1\}^n \times \{0,1\}^b) \to \{0,1\}^n$ be a compression function. Fix a string $\mathrm{IV}\in\{0,1\}^n$, and for $M \in (\{0,...
4
votes
3answers
432 views

Can I use M1 straight away and get rid of IV in Merkle–Damgård?

In Merkle–Damgård is there any reason why we use a fixed $IV$ at the beginning? Can we use the first block ($M_1$) right away instead of $IV$ and feed it through the compression function with $M_2$.
2
votes
0answers
111 views

What happens if I modify the Merkle–Damgård hash method? [duplicate]

Does the Merkle–Damgård hash function still offer Collision Resistance (CR) when the following changes are made? Each case is independent from the other. Here is what I want to modify: Say I want to ...
3
votes
1answer
113 views

Is there any hash function for which a preimage of a fixed element is always known?

I'm wondering if there is any collision-resistant hash function $h^s(\cdot)$ satisfying that there is a fixed value $c$ such that, for each $s$, a value $x_s$ satisfying $h^s(x_s) = c$ is known. This ...
4
votes
1answer
235 views

What’s the difference between a Fast wide pipe and a Narrow pipe construction?

I'm learning more about the Merkle–Damgård construction, including its "alternatives". I learned about the fast wide pipe construction and the narrow pipe construction, explained here. However, I can'...
3
votes
1answer
318 views

The Wide Pipe construction

I'm learning more about the Merkle–Damgård construction, including its "alternatives". I think I know how the Wide Pipe construction works, but am confused about the different images being used ...
3
votes
3answers
455 views

What do we gain from hashing the length in Merkle–Damgård?

Assuming our fixed compression function $h$ works for inputs of length $i(n)$ and output strings of length $o(n)$, if $2o(n) < i(n)$, why do we need to calculate $h(z_B||L)$ where L is the input's ...
4
votes
1answer
1k views

Forgery attack for Merkle–Damgård MAC scheme with prefix method

Consider a hash function $H$ based on an iterated hash function $H_0$ with $l$-bit block messages an the Merkle–Damgård strenghtening pad. That is, $m||pad(m)$ has a length multiple of $l$ and $H(...
4
votes
1answer
351 views

What if using a block cipher as compression function in Merkle–Damgård?

The Merkle–Damgård construction builds a hash by iterating a compression function $F$, with $S_{j+1}=F(B_j,S_j)$ where $B_j$ is one of $n$ padded message blocks, $S_0$ is the IV, and $S_n$ is the hash....
1
vote
1answer
472 views

Significance of IV in Merkle-Damgård construction

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 ...
0
votes
1answer
176 views

Partial-Message Collisions on Iterated Hash Functions

In Cryptography Engineering by Ferguson et al it says the following is a problem with iterated hash functions: Because hashing $m$ and $m'$ leads to the same value, $h(m||X) = h(m'||X)$... for all ...
3
votes
0answers
164 views

Unlinkability of Merkle-Damgård hash function results

Question: Are multiple outputs of a Merkle-Damgård hash function (or specifically SHA-256, if this can only be said for a specific algorithm) on unknown data unlinkable? If yes: Can this be formally ...
5
votes
1answer
187 views

Does length-prepending stop length-extension attacks?

Does length-prepending stop length-extension attacks on Merkle-Damgård hash functions, assuming that the length is checked?
1
vote
1answer
83 views

Is this a secure keyed hashing construction?

I need a PRF for use with PBKDF2, however, the only thing I have is the AES block cipher primitive. I'm attempting to derive a keyed hash function from the block cipher. The design is based on the ...
2
votes
0answers
43 views

Why do we need Merkle–Damgård strengthening [duplicate]

Reading through some manuals, wikis and other documentation I'm learning about Merkle–Damgård construction. I understand why padding beginning with '1', followed by '0's is needed, but I can't ...