18 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 ...
Thomas Pornin's user avatar
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 ...
Conrado's user avatar
  • 6,424
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 ...
Richie Frame's user avatar
  • 13.1k
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 ...
e-sushi's user avatar
  • 17.9k
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 ...
Ilmari Karonen's user avatar
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\...
CurveEnthusiast's user avatar
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 ...
indiscreteLog's user avatar
7 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 ...
fgrieu's user avatar
  • 141k
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}\...
fgrieu's user avatar
  • 141k
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 ...
Luis Casillas's user avatar
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 ...
fgrieu's user avatar
  • 141k
6 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 ...
otus's user avatar
  • 32.1k
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 ...
Marc Ilunga's user avatar
  • 3,188
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 ...
SEJPM's user avatar
  • 46k
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 ...
Squeamish Ossifrage's user avatar
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 ...
kelalaka's user avatar
  • 48.5k
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 ...
Biv's user avatar
  • 9,989
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 ...
poncho's user avatar
  • 147k
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$ ...
SEJPM's user avatar
  • 46k
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 ...
fgrieu's user avatar
  • 141k
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 ...
mikeazo's user avatar
  • 38.6k
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, ...
Squeamish Ossifrage's user avatar
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 ...
e-sushi's user avatar
  • 17.9k
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 ...
Adam54's user avatar
  • 261
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..) ...
fgrieu's user avatar
  • 141k
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 ...
kelalaka's user avatar
  • 48.5k
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-...
kelalaka's user avatar
  • 48.5k
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 ...
DannyNiu's user avatar
  • 9,207
3 votes
Accepted

Why are theoretical hash constructions based on the hardness of the discrete logarithm problem not really used in practice?

I would say it is largely due to the fact that discrete log functionalities tend to be computationally expensive and harder to implement on specific hardware (compared to constructions like SHA-2) ...
indiscreteLog's user avatar
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 ...
Paul Uszak's user avatar
  • 15.4k

Only top scored, non community-wiki answers of a minimum length are eligible