18

Let hash be the raw hash function, as you're referring to. You mentioned that the attacker knows hash(message || length), but to be more precise, they know hash(message || padding || length). Let full_hash be the proper hash with padding and length, i.e. full_hash(message) = hash(message || padding || length). You're correct that if the attacker knows hash(...


16

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 encrypt the initial value, then the entire encrypted value is the hash. In a sponge based hash, the input is XOR'd into the initial value, then the entire ...


16

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 when it is a good one, that does not preclude the possibility of other, "better" algorithms (e.g. for performance). As an illustration of potential ...


13

A compression function takes two fixed size inputs: a chaining value and a message and returns a fixed size value. So it's essentially a hash function with fixed input size. Merkle-Damgård is a domain extender, which turns that compression function into a hash which supports arbitrarily long messages. MD uses the output of the compression of one block as ...


9

Actually, the Merkle–Damgård construction also specifies a padding bit after the message. The length is there the ensure that a padded message cannot be the suffix of a different longer message. A collision at the prefix leads to a collision in both messages. With a padding bit, a singe byte message 0x30 vs a 2 byte message 0x30 0x00 are padded to 0x30 0x80 ...


9

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 layman’s terms, SHA-256 processes things like this: init SHA-256 while there are input chunks, update hash compression function with the next input chunk (pad ...


7

One reason is convenience: if the IV was variable, it would have to be transmitted to a party verifying the hash, and we'd have to deal with its integrity. Another reason is that it avoids an attack in a Merkle–Damgård variant with padding reduced to appending a single 1 bit and as many zeros as necessary to end the block. With such scheme and common ...


7

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\right\}^n.$$ That is, it takes as input an $n$-bit value and an $\ell$-bit value, and outputs an $n$-bit value. This function is a building block for the function $...


7

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 appended to $M$ and $m$ respectively by the MD5 algorithm, as described in RFC 1321 sections 3.1 and 3.2. To see why, it's worth looking at how the MD5 hash (...


7

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 construction is to build a hash function that maps arbitrary-length inputs to fixed-length outputs, given a compression function (that is hopefully collision-...


7

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}\times\{0,1\}^{512}\to\{0,1\}^{256}$ where the first argument is the state and the second is a message block. Now define $F'$ identical to $F$, except that $F'(0^{...


6

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 extension, the attacker knows: The permutation $F$, capacity $c$, bitrate $r$ and padding rule used in the sponge instance; The length of a message $m$ and its hash ...


6

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 message of 56 bytes. I guess SHA-2 does this because SHA-1 did, and before that SHA, MD5, and Ronald Rivest's MD4 (1990), which is the earliest reference that I can ...


6

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 messages need to be encoded in a prefix-free manner. Quoting the paper: A prefix-free code over the alphabet $\{0, 1\}^κ$is an efficiently computable injective ...


6

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 secure PRF when the first input is the key. So now that we know what ChaCha is, for the three desired functionalities: MAC. Of course a PRF is also immediately ...


5

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 valid input. Thus there is no length-extension attack. (Assumptions include that you reveal no intermediate values, of course.)


5

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 compression function). M1 M2 ... Mn | | | +--|\ +--|\ +--|\ | \ | \ | \ IV ---| |-------| ...


5

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 halves of the message, and determine the intermediate state for the hash after processing each message. Select $2^{n/2}$ distinct final halves of the message, and ...


5

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 block, per the analysis of Bart Preneel, René Govaerts, Joos Vandewalle's Hash functions based on block ciphers: a synthetic approach, in proceedings of Crypto ...


5

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 arbitrarily parallelized, because it's just evaluating a polynomial modulo $2^{130} - 5$. In contrast, functions like BLAKE2 and Rumba20 can't be parallelized ...


5

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 block (data input and output): as wide as the hash, thus twice the security (in bits) if collision-resistance is a consideration. For 128-bit security, we thus need ...


4

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 blocks as more of the message becomes available. before it can be encrypted You are not encrypting. You are hashing. the blocks can be padded if necessary ...


4

The relevant part of Neven et al is this: What this means for practice is that one should not instantiate the hash function with a Merkle-Damgård iteration of an $n$-bit compression function. Instead, one should probably simply truncate the output of a $2n$-bit hash function to $n$ bits. (Such a method would in our situation be reminiscent of Lucks’ wide-...


4

Isn't it still possible to find two different inputs that will be padded to the same value and then deliver the same hash? Well, no, it isn't. Given a padded message (that is, padded by adding a 1 bit, and then as many 0 bits as needed to fill it out to a multiple of the internal block size), we can unambiguously recover the original message -- by ...


4

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 top of the Merkle-Damgård or the Sponge construction? The reason is that a Merkle tree comes with computation overheads that the serial hash functions do ...


4

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..) are Merkle–Damgård based, but use more compute-intensive compression functions, and are so far unbroken. SHA-3 is not Merkle–Damgård based, it uses the sponge ...


4

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$ where $x=x_L\parallel x_R$ and $\left|x_L\right|=s$. In this paper we fix $0<s<n$ and define $\operatorname{chopMD}^f(M)=\operatorname{chop}_s(\...


4

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 combined hash in a simple node design. This can complicate the structure and programming so that the last parents must contain the hash of their children and their ...


4

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-bit and the previous output of the previous compression function is the 256-bit input. The first compression function takes the Initial Values (IV) $$C:\{0,1\}^{...


3

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 look like Or a crocodile. At a certain (reasonable) level of abstraction, they both produce a hash value by successively updating a state passed from message ...


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