Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

10
votes
1answer
167 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 ...
2
votes
2answers
125 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
74 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
62 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
273 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
58 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?
0
votes
0answers
42 views

What Set and MultiSet Hash allows Secure, Homomorphic, commutative comparison of key-value databases? (Orderless, Online alternative to Merkle trees)

I am interested in Merkle tree like hashes that do not require the data to be ordered, but will hash the data, not the byte by byte, page by page storage but rather hash UNORDERED data (presumably ...
0
votes
0answers
121 views

Davies-Meyer with DES insecure

I'm stuck in coming up with a collision for a hash function $H$, which is built using a Davies-Meyer construction chained in a Merkle-Damgard fashion. I I guess its actually easy using the fact that ...
3
votes
1answer
74 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
79 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
0answers
138 views

Merkle-Damgard: Why not use the input length as the IV?

Would the resulting construction still be collision-resistant? Define the construction as follows: Let n be the number of bits in one block. Let L be the length of input x. Set B := the ...
0
votes
0answers
89 views

Why do we pad the length of the message at the end in Merkle–Damgård constructions? [duplicate]

In a Merkle–Damgård construction we pad the hash of the final block with the length of the actual message. Is this necessary? What happens if prepend the message length instead of appending it? Will ...
0
votes
1answer
24 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
218 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
105 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 ...
2
votes
2answers
2k 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
168 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
52 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
72 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 ...
5
votes
2answers
334 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 ...
1
vote
1answer
398 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
813 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
433 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
281 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 ...
3
votes
0answers
96 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
81 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 ...
1
vote
0answers
109 views

Reasons of the choice of padding scheme

Can you explain me what is the reason of the difference between MD5 and SHA-3 padding schemes? - MD5 has a padding scheme: 10*-message length 64 bit- - SHA-3 has a padding scheme: 10*1 Why they use ...
6
votes
1answer
428 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?
7
votes
1answer
429 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 ...
0
votes
0answers
179 views

Modification of Merkle–Damgård transform

In the Merkle–Damgård transformation, instead of using a fixed IV, if I choose $\mathit{IV}←\{0,1\}^n$ and define $z_0:=\mathit{IV}$. Then set the output to be $\mathit{IV}||h(z_B||L)$. Will the ...
1
vote
2answers
737 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
150 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,...
5
votes
3answers
352 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
79 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
97 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
194 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'...
4
votes
1answer
247 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
390 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 ...
5
votes
1answer
656 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
242 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
409 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
141 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
151 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
152 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?
0
votes
0answers
82 views

Why does Rabin cryptosystem split the message into key blocks?

Why does Rabin cryptosystem split the message into key blocks and not into plain text blocks like in Merkle-Damgård Construction? Is it because it acts in a way similar to IV? Probably not, it doesn'...
1
vote
1answer
79 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
39 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 ...
2
votes
1answer
520 views

Why the $IV$ used in Merkle–Damgård has to be fixed to a specific value?

I just can't figure out why on earth the $IV$ in Merkle–Damgård has to be fixed (that's what the Katz-Lindell book says)? Because even if you choose it randomly from say $\{{0,1}\}^n$ then the ...
1
vote
1answer
608 views

SHACAL-2 vs. AES as underlying block cipher for Secure Hash (aka SHA-256)

The hashing scheme SHA-256 (for instance) is based on Merkle-Damgård construction with the underlying compression function based on the block cipher SHACAL-2 configured in Davies Meyer mode. SHACAL-2 ...
6
votes
1answer
2k views

What is the “compression function” in Merkle-Damgård?

Is the "compression function" in Merkle-Damgård just a collision-resistant, one-way hash function but one that operates only on fixed size inputs? If so, is MD just a way to extend it to work on ...