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.
94
questions
1
vote
2
answers
124
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 ...
- 385
2
votes
0
answers
101
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 ...
- 1,649
1
vote
1
answer
95
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 ...
- 363
2
votes
0
answers
66
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 ...
- 131
1
vote
1
answer
132
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,211
0
votes
1
answer
142
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,211
0
votes
0
answers
131
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 ...
- 103
2
votes
1
answer
628
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 ...
- 23
0
votes
1
answer
73
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
1
answer
205
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
1
answer
619
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 ...
3
votes
2
answers
130
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.
- 73
4
votes
2
answers
565
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
2
votes
1
answer
403
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
0
answers
74
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.1k
1
vote
3
answers
677
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:
...
- 143
2
votes
1
answer
185
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 ...
- 23
2
votes
1
answer
456
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-...
- 31
1
vote
2
answers
728
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:
...
- 897
1
vote
1
answer
201
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
1
answer
373
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
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 ...
- 237
0
votes
0
answers
110
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
0
answers
132
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
3
votes
1
answer
2k
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)...
- 187
0
votes
1
answer
865
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
0
votes
1
answer
179
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,001
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 ...
- 344
2
votes
1
answer
711
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
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 ...
- 1,247
0
votes
0
answers
493
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
3
votes
2
answers
366
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,405
1
vote
1
answer
256
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
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?
- 259
1
vote
0
answers
98
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
3
votes
1
answer
148
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_{...
- 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 ...
- 173
4
votes
2
answers
1k
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, $...
- 71
3
votes
1
answer
178
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 ...
- 91.9k
2
votes
1
answer
232
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
4
votes
1
answer
481
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
1
answer
90
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
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 ...
- 123
3
votes
1
answer
729
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 ...
- 31
0
votes
1
answer
58
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. ...
- 11
1
vote
1
answer
344
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
2
votes
1
answer
296
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 ...
- 15.1k
5
votes
2
answers
18k
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
2
answers
536
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 ...
- 17.8k
0
votes
1
answer
104
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 ...
- 17.8k