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
0
votes
0answers
30 views

Does Enveloped Merkle-Damgård require last compression to be done in one compression?

Does "Enveloped Merkle-Damgård" require last compression to be done in one compression function call? Since I have compression function with same size of input/output, I would have to make ...
0
votes
0answers
38 views

Second-preimage attack on Streebog

Could attack similar to described in paper "The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function" be applied, if Streebog used Matyas-Meyer-Oseas ...
0
votes
0answers
24 views

Are there any Enveloped Merkle-Damgård implementations?

I'm implementing "Enveloped Merkle-Damgård" and I would like to verify I undestood notation in papers describing it. Is there any hash function using "Enveloped Merkle-Damgård" so ...
0
votes
1answer
40 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
vote
1answer
38 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: ...
2
votes
1answer
48 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 ...
2
votes
1answer
57 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.
4
votes
2answers
387 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. ...
2
votes
1answer
81 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 ...
5
votes
0answers
63 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}$: ...
1
vote
3answers
263 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: ...
2
votes
1answer
155 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 ...
1
vote
0answers
97 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-...
0
votes
2answers
203 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: ...
1
vote
1answer
133 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
148 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 ...
3
votes
1answer
185 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
38 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
44 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 ...
2
votes
1answer
400 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
248 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
125 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 ...
3
votes
2answers
513 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
253 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
206 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 ...
3
votes
2answers
308 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
170 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
1k 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
87 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
117 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_{...
14
votes
2answers
671 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 ...
4
votes
2answers
811 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
123 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
213 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
455 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
66 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
94 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
378 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
50 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
314 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
229 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 ...
5
votes
2answers
11k 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
361 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
90 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
103 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
746 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
2k 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 ...
1
vote
1answer
3k 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
814 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 ...