Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

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
1 answer
62 views

Necessity of all three MD-Compliant padding conditions

For Merkle-Damgård hashing, MD-compliant padding is defined as any padding scheme satisfying: $M$ is a prefix of $\text{Pad}(M)$ $|M_1|=|M_2|\Rightarrow |\text{Pad}(M_1)|=|\text{Pad}(M_2)|$ $|M_1|\...
hegash's user avatar
  • 113
2 votes
0 answers
38 views

Merkle-Damgård construction without MD compliant padding

Is there an easy example of a Merkle-Damgård constructed hash that does not have Merkle-Damgård compliant padding and is collision resistant? Is there an example that does not have MD-compliant ...
revision's user avatar
1 vote
0 answers
37 views

Suffix-free padding scheme for hash function

I would like an easy to read proof that shows that it is sufficient for a padding scheme to be suffix-free for it to be collision resistant. Whenever I have come across such a proof it always seems to ...
revision's user avatar
1 vote
2 answers
211 views

Sponge construction versus Merkle-Damgard For Hashing based on the very same primitive

I am a bit confused about Sponge construction and Merkle-Damgard-style ones for hashing. The only advantage I see for sponge construction is that they are secure against length extension attacks. So ...
A.Solei's user avatar
  • 405
2 votes
0 answers
105 views

Security of Even-Mansour based Merkle-Damgård

Assuming I have single-key Even-Mansour with single $2n$-bit permutation in wide-pipe Merkle-Damgård specifically with Matyas-Meyer-Oseas mode outputting $n$-bit hash. What security can I expect ...
LightBit's user avatar
  • 1,649
1 vote
1 answer
147 views

modified Merkle-Damgard construction that does not include message length

How to give an example for collision in modified Mekle-Damgard construction that does not include input length, with two message that ARE multiple of the block length? (Assume the resulting hash ...
user1035648's user avatar
2 votes
0 answers
70 views

Is there any standard extension of the Merkle-Damgård transform that handles arbitrary-length inputs?

I have seen multiple sources claim that the Merkle-Damgård transform is able to build a collision-resistant Hash-function $H$ for arbitrary-length inputs from a compression function $h : \{0,1\}^n \to ...
Steven's user avatar
  • 131
1 vote
1 answer
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 ...
Tom's user avatar
  • 1,221
0 votes
1 answer
149 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 ...
Tom's user avatar
  • 1,221
0 votes
0 answers
146 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 ...
Barney Chambers's user avatar
2 votes
1 answer
743 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 ...
Alexandre's user avatar
0 votes
1 answer
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 ...
LightBit's user avatar
  • 1,649
1 vote
1 answer
218 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: ...
partyTuringFriend's user avatar
2 votes
1 answer
749 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 ...
partyTuringFriend's user avatar
3 votes
2 answers
147 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.
sunsetgreen's user avatar
4 votes
2 answers
605 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. ...
m0bi5's user avatar
  • 142
2 votes
1 answer
468 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 ...
Lukas Mittun Alexander Guldstv's user avatar
5 votes
0 answers
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}$: ...
forest's user avatar
  • 15.3k
1 vote
3 answers
727 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: ...
Anonymous's user avatar
  • 153
2 votes
1 answer
187 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 ...
Adar Kahiri's user avatar
2 votes
2 answers
546 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-...
user84987's user avatar
1 vote
2 answers
841 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: ...
fadedbee's user avatar
  • 928
1 vote
1 answer
211 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 ...
AkThao's user avatar
  • 113
1 vote
1 answer
427 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 ...
evernal's user avatar
  • 237
5 votes
1 answer
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 ...
evernal's user avatar
  • 237
0 votes
0 answers
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 ...
user80059's user avatar
1 vote
0 answers
145 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 ...
jhdm's user avatar
  • 187
0 votes
1 answer
942 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 ...
Prime's user avatar
  • 117
0 votes
1 answer
189 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 ...
DannyNiu's user avatar
  • 9,390
4 votes
2 answers
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 ...
Charlie's user avatar
  • 374
2 votes
1 answer
754 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 ...
theantomc's user avatar
  • 189
7 votes
2 answers
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 ...
juhist's user avatar
  • 1,267
0 votes
0 answers
525 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 ...
user1870400's user avatar
3 votes
2 answers
381 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, ...)?
AleksanderCH's user avatar
  • 6,463
1 vote
1 answer
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 ...
SeesSound's user avatar
  • 141
6 votes
2 answers
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?
Zoey's user avatar
  • 261
1 vote
0 answers
99 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 ...
user1868607's user avatar
  • 1,243
3 votes
1 answer
154 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_{...
user1868607's user avatar
  • 1,243
14 votes
2 answers
1k 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 ...
MikeDav77741's user avatar
4 votes
2 answers
2k 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, $...
Hughtwo's user avatar
  • 71
3 votes
1 answer
200 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 ...
Maarten Bodewes's user avatar
2 votes
1 answer
241 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: ...
jdcaballerov's user avatar
4 votes
1 answer
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 ...
Alex Papageorgiou's user avatar
0 votes
1 answer
100 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?
user83024's user avatar
2 votes
1 answer
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 ...
DrDirk's user avatar
  • 123
3 votes
1 answer
767 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 ...
Patrick Hahn's user avatar
0 votes
1 answer
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. ...
Ben Stolman's user avatar
1 vote
1 answer
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 ...
jack klompus's user avatar
2 votes
1 answer
306 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 ...
forest's user avatar
  • 15.3k
5 votes
2 answers
19k 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 ...
Lizz4rd merge me's user avatar