18
votes
Accepted
If hash functions append the length, why does length extension attack work?
Let hash be the raw hash function, as you're referring to. You mentioned that the attacker knows hash(message || length), but to ...
- 6,404
17
votes
Attacks of the MAC construction $\mathcal{H}(m\mathbin\|k)$ for common hashes $\mathcal{H}$?
Using $H(m\mathbin\Vert k)$ with hash function $H$, message $m$ and key $k$, is one possible way to build a MAC algorithm. It is not necessarily a good one; it depends on the used hash function. Even ...
- 86.6k
16
votes
Is it accurate to say that SHA-3 (keccak) is based on Merkle-Damgård?
No. That is about as accurate as saying that airplanes are based on motorcycles, because they both have engines.
In MD, the input to the hash is converted to a key, which is used by a block cipher to ...
- 13k
9
votes
What happens if a SHA-256 input is too long (longer than 512 bits)?
If the input message is longer than 512 bits, the input is chopped in “chunks” (read: pieces) with fitting length (512 bits) and those are successively fed to the hash compression function.
See, in ...
- 17.8k
7
votes
Accepted
Forgery attack for Merkle–Damgård MAC scheme with prefix method
A lot of this is explained well on the wikipedia article.
The function $f$ is called the compression function. It is a function $$f:\left\{0,1\right\}^n\times\left\{0,1\right\}^\ell\to\left\{0,1\...
- 3,459
7
votes
Accepted
Would finding a Merkle-Damgård preimage that doesn't change the initial state allow an attacker to prepend it to any hashed message?
Not quite. But it would allow computing ${\rm MD5}(M \,\|\, {\rm pad}_M \,\|\, m \,\|\, {\rm pad}_m \,\|\, {\rm whatever})$, where ${\rm pad}_M$ and ${\rm pad}_m$ are the extra length padding bytes ...
- 45.9k
7
votes
Accepted
What happens if a SHA-256 input is too long (longer than 512 bits)?
Your question essentially is how message length is dealt with in Merkle-Damgård constructions. However, your description is flawed so let's clarify some things:
The whole point of using this kind of ...
- 740
7
votes
Accepted
Compression function is not collision resistant but Merkle-Damgard is collision resistant
Yes, a hash built per the Merkle-Damgård construction can be collision-resistant even if its compression function has a known collision.
Consider SHA-256. Note its round function $F:\{0,1\}^{256}\...
- 138k
6
votes
How does the sponge construction avoid the weaknesses present in Merkle–Damgård hash function?
There's two ways to answer this. One would be to go over the individual M-D weaknesses you list and show why the sponge construction is resistant to them. For example, if you consider length ...
- 14.4k
6
votes
Why does SHA-2 call for doing 10* padding in addition to appending the message length?
As rightly pointed in the question, 0*+length padding would work just as well as 10*+length padding, with the benefit of simplicity and requiring one less block in some cases, like SHA-256 for a ...
- 138k
6
votes
Why was Davies–Meyer chosen over Miyaguchi–Preneel most of the time?
Some ideas (not a definitive answer):
Davies–Meyer is one of the two simplest among the 12 secure methods by which a block cipher and XOR can be turned into an iterative hash with one encryption per ...
- 138k
6
votes
Accepted
Have there been efforts to prevent length extension attacks of hashing algorithms that are based on the Merkle–Damgård construction?
Yes. In this paper, Coron and al. showed that a plain MD construction is secure when it's inputs are prefix-free. They actually proved the indifferentiability of the construction. In other words ...
- 2,848
6
votes
Accepted
Why not use chacha derivatives (BLAKE, rumba) to make an [H]MAC for use with chacha? Why use poly1305?
OK, so the core ChaCha primitive (for any fixed number of rounds) is a function $\operatorname{ChaCha}: \{0,1\}^{256}\times \{0,1\}^{64}\times\{0,1\}^{64}\to \{0,1\}^{512}$ which is believed to be a ...
- 45.7k
6
votes
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?
Performance.
Poly1305 is extremely cheap to compute, and the computation can be essentially ...
- 47.9k
6
votes
Why does Merkle-Damgård hashing involve putting the padding at the end instead of at the start?
I can only provide a programming sense to this;
One may not know the size of the message beforehand (streaming), when finished, the length-padding can be executed nicely at the end. Otherwise, the ...
- 47.6k
5
votes
Can I use M1 straight away and get rid of IV in Merkle–Damgård?
TL;DR: A simple reason why we use the IV is to mitigate second preimage attacks.
This is the typical Merkle–Damgård construction: you split your messages in blocs of $k$ bits (input size of the ...
- 9,969
5
votes
Accepted
Does length-prepending stop length-extension attacks?
Yes, if the length is formatted in a constant-size value (e.g. 64-bit field) or in an otherwise uniquely decodable manner.
With such a length field, no hash input can be the the prefix of another ...
- 32k
5
votes
Accepted
What if using a block cipher as compression function in Merkle–Damgård?
One issue is that it would make finding preimages significantly easier; with $O(2^{n/2})$ time rather than $O(2^n)$ time.
Here's how you would do such a search:
Select $2^{n/2}$ distinct initial ...
- 145k
5
votes
Accepted
What does ChopMD refer to in the default Go ECDSA package?
Let $n$ be the digest length of a hash function $\operatorname{MD}^f:\{0,1\}^*\to\{0,1\}^n$. Now quoting the paper you linked:
chopMD. For $0\leq s<n$ we define $\operatorname{chop}_s(x)=x_R$ ...
- 45.7k
5
votes
Accepted
Which block ciphers are considered staples for constructing hash functions?
Block ciphers used in hash functions built per the Merkle-Damgård structure with a Davies-Meyer compression function (e.g. MD5, SHA-1, and SHA-2) have special requirements:
They must have a wide ...
- 138k
4
votes
Significance of IV in Merkle-Damgård construction
broken up into blocks before it can be (hashed)... Then a fixed IV is used...
In practice, you may not even know the entire message before beginning hashing. So this is incorrect. You divide into ...
- 38.5k
4
votes
Simple compression functions an sponge functions for educational purposes
Many of the designs in the NIST SHA-3 competition came with toy variants for study. For example:
The winner of the competition, Keccak, has parameters for:
word size—the SHA-3 standard is 64-bit, ...
- 47.9k
4
votes
Can someone give me an example of a Merkle–Damgård transformation?
You get it wrong when saying
Since input-output = # of blocks, the 6-bit input should be divided into two blocks, each with the 3-bits
because you have a
…compression function that takes ...
- 17.8k
4
votes
Merkle trees instead of the Sponge or the Merkle-Damgård constructions for the design of cryptorgraphic hash functions
Is there any reason why don't more cryptographic hash functions use a
Merkle tree-like construction directly instead of just adding them as
a way to allow parallelism to existing hash functions on ...
- 239
4
votes
Ease of breaking MD constructions
MD5 and SHA-1 have been broken (from a collision-resistance perspective) due to weaknesses of their compression function, not because they are Merkle–Damgård based.
SHA-2 hashes (SHA-256, SHA-512..) ...
- 138k
4
votes
Why are leaf nodes hashed in merkle tree?
Merkle Tree is based on hashing to the root to provide an efficient digital signature. If the leaves just contain a single data then the parents cannot contain the hash of both children and the ...
- 47.6k
4
votes
Accepted
What is the padding block actually in merkle damgård?
Merke-Damgård construction uses a compression function $C$ that takes two inputs in each iteration. The previous block and a new message block. For example;
In SHA-256, the message is operated in 512-...
- 47.6k
4
votes
Accepted
Merkle–Damgård construction - the bigger input, the longer time to compute hash?
That's right, and you've just stated the obvious. The processing time of Merkle-Damgaard-based hash functions are proportional to the size of the input (unless the input is too small).
That's also ...
- 9,001
3
votes
Accepted
Is it accurate to say that SHA-3 (keccak) is based on Merkle-Damgård?
I have to agree that they are similar aren't they? Block after block with a chain value /state passed along. The two constructions are show below...
If they were substantially different, one would ...
- 15.1k
3
votes
Purpose of hashing last block in Merkle-Damgård?
The purpose of hashing the last block is simply to prevent leaking information like, $L$, the length of the input. It's also important so that if $L\leq \langle 2 \rangle$, then $H$ is still ...
- 31
Only top scored, non community-wiki answers of a minimum length are eligible