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.

96 questions
Filter by
Sorted by
Tagged with
1 vote
62 views

• 131
1 vote
134 views

Does Merkle–Damgård construction requires OWF with two inputs?

I'm looking at scheme on Wikipedia: https://en.wikipedia.org/wiki/Merkle–Damgård_construction And it looks like function f takes two inputs. So do we have to use in this scheme OWF which can take two ...
• 1,221
151 views

Merkle–Damgård construction - the bigger input, the longer time to compute hash?

I'm trying to understand Merkle–Damgård construction. We can hash as many blocks of data as we want, if I understand it right. But then it looks like when input is bigger, then also time to compute ...
• 1,221
148 views

Is this implementation of Merkle Trees susceptible to second preimage attack?

I am trying to find a good implementation of Merkle Tree generation in Golang, and I need the tree to be resilient to Second Preimage Attack I have found this standard implementation in the golang ...
756 views

Davies-Meyer block cipher and IV

I have three questions regarding Davies-Meyer construction : What is the name of the underlying block cipher? How is generated the first input hash value (IV) passed to the block cipher? What is ...
78 views

Would changing number of rounds in last compression prevent length extension attack?

Suppose we have some Merkle–Damgård hash function. Assuming compression function supports it and is equally secure with more rounds. Would changing number of rounds (for example doubling them) for ...
• 1,649
1 vote
220 views

Breaking merkle damgård construction that uses bitwise and?

I'm preparing for a exam in crypto course, and i'm doing some practice problems. I'm now playing with this problem: ...
752 views

What is the padding block actually in merkle damgård?

I'm studying up on Merkle Damgård construction for hashing and having some trouble understanding the "padding block", at the end of the message blocks. When you look it up it says that in ...
151 views

Why does Merkle-Damgård hashing involve putting the padding at the end instead of at the start?

Pretty much the title. We have that $x$ is a prefix of $PAD(x)$, instead of being a suffix - was that an arbitrary choice or is there a reason for it? Thank you.
613 views

Why are leaf nodes hashed in merkle tree?

I was reading the following on Wikipedia, it appears that the leaf nodes are hashed. What are the benefits of this? Why is it done?. I fell like they are done so that they can be transferred securely. ...
• 142
476 views

How are SHACAL-2 ciphers calculated?

I am trying to learn about the underlying functionality of the different hash functions (currently SHA) and I'm pretty stuck even after watching a Stanford video about it. One method of hashing is by ...
77 views

Security implications of using the low-order bits for Merkle–Damgård message length

According to RFC 1321 § 3.2 (MD5), the length of the message ($b$) is encoded as $b \bmod 2^{64}$: ...
• 15.3k
1 vote
734 views

Is it possible to generate a hash function that produces similar output to SHA-256?

Is it possible to create a hash function that generates a correlated to SHA-256 when given the same input? In other words, given a fixed input X: ...
• 153
189 views

Which block ciphers are considered staples for constructing hash functions?

I've been looking all over the internet for an answer, and I must not know how to search because I've been really surprised that I haven't been able to find one. I'd also love to know what makes a ...
550 views

Is this modification in Merkle-Damgård collision-resistant?

We modify Merkle-Damgård construction by setting $z_0:=L$ (the length of the message), computing $z_i:=h(z_{i-1}||x_i)$ for $i=1,...,B$ and defining $H(x):=z_B.$ Is this construction collision-...
1 vote
854 views

Does the Blake3 hash have identities, due to its merkle tree structure?

I've read that the Blake3 hash uses a Merkle Tree. Does it follow that there are identities such as: ...
• 938
1 vote
215 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 ...
• 113
1 vote
433 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 ...
• 237
1k 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 ...
• 237
117 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
147 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 ...
• 187
946 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 ...
• 117
191 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 ...
• 9,423
1k 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 ...
• 384
756 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 ...
• 189
3k 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 ...
• 1,267
531 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 ...
• 123
383 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, ...)?
• 6,462
1 vote
263 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 ...
• 141
2k 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?
• 261
1 vote
100 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 ...
• 1,243
154 views

• 71
201 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 ...
• 93.2k
246 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: ...
• 153
484 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 ...
101 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?
101 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 ...
• 123
771 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 ...
59 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
353 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 ...
• 111