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
1
vote
1answer
33 views

Is the MD5 algorithm only useful for bytes, rather than bits?

The MD5 algorithm is designed to accept a message of any length and produce a 512-bit message digest. Because of the way it pads the original message, by adding a 1-bit then a number of 0-bits, the ...
1
vote
1answer
82 views

How do herding attacks on hash functions work?

I read this paper Herding Hash Functions and the Nostradamus Attack, 2005 of Kelsey and Kohno on herding attacks but I do not understand how it works. Would anyone be able to give me a summary of how ...
2
votes
1answer
53 views

How does second pre-image attack on Merkle Signature Scheme work?

I understand that a second pre-image attack on the Merkle tree works by creating another Merkle tree using the intermediate nodes as the leaf nodes, and this will lead to the same root hash (public ...
0
votes
0answers
27 views

Is $f_N$ in this hash function is Matyas-Meyer-Oseas scheme?

I propose a hash function as following: H is an Merkle-Damgard hash function with a compression function $f: \{0,1\}^{3n} \to \{0, 1\}^{2n}$. Output function $f_N: \{0,1\}^{3n} \to \{0, 1\}^n$. M is ...
1
vote
0answers
23 views

Sorted merkle tree versus rsa accumulator

When compared to sorted merkle tree and rsa accumulator, which one is the best? Rsa accumulator has constant proof and it adds/deletes at constant cost. What is the verification cost for rsa ...
0
votes
0answers
15 views

Merkle tree verification cost calculation

I am trying to understand how to calculate verification cost of sorted merkle tree in case of exclusion proof. For example 5 revoked certificate are kept in merkle tree. How can i calculate storage ...
2
votes
1answer
103 views

Merkle Tree space complexity

When searching by using the Merkle tree, the time complexity is $\mathcal O(\log n)$ but I don't understand how space complexity is $\mathcal O(n)$. In my opinion, it should be also $\mathcal O(\log n)...
0
votes
1answer
108 views

Length extension attacks, Merkle–Damgård constructions, and HMACs

The wikipedia page for Length Extension Attacks says "Note that since HMAC doesn't use [Merkle–Damgård constructions], HMAC hashes are not prone to length extension attacks." However, HMACs can be ...
0
votes
1answer
88 views

An unusual use-case for HMAC as compression function in web browsers

It's an unfortunate fact that, right now (2019), browsers don't expose standardized streaming hashing interfaces in SubtleCrypto. The only way to hash a file, is to ...
2
votes
2answers
290 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
1k 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 ...
2
votes
1answer
94 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
132 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 ...
7
votes
2answers
5k 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 ...
0
votes
1answer
173 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 ...
2
votes
2answers
273 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, ...)?
5
votes
1answer
220 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 ...
1
vote
1answer
136 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
984 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?
13
votes
2answers
474 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 ...
1
vote
0answers
77 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 ...
2
votes
1answer
206 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 ...
1
vote
1answer
717 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 ...
3
votes
1answer
103 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_{...
4
votes
2answers
507 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
116 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
165 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: ...
0
votes
1answer
44 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. ...
4
votes
1answer
448 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
64 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?
20
votes
3answers
3k views

Attacks of the MAC construction $\mathcal{H}(m\mathbin\|k)$ for common hashes $\mathcal{H}$?

Consider a common practically-collision-resistant hash function $\mathcal{H}$ (e.g. SHA-1, SHA-256, SHA-512, RIPEMD-160), perhaps based on the Merkle–Damgård construction as are the first three. We ...
2
votes
1answer
254 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 ...
2
votes
1answer
92 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 ...
1
vote
1answer
302 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 ...
3
votes
2answers
8k 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 ...
5
votes
2answers
302 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 ...
4
votes
1answer
280 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'...
6
votes
2answers
672 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 ...
0
votes
1answer
79 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 ...
3
votes
3answers
555 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
3answers
462 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$.
1
vote
2answers
91 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 ...
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 ...
6
votes
1answer
720 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
315 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 ...
0
votes
1answer
132 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 ...
3
votes
1answer
122 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 ...
7
votes
1answer
624 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?
2
votes
1answer
772 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 ...