# Tag Info

## Hot answers tagged length-extension

58

SHA-1 processes data by 512-bit blocks (64 bytes). For a given input message m, it first appends some bits (at least 65, at most 576) so that the total length is a multiple of 512. Let's call p the added bits (that's the padding). The padding bits depend only on the length of m (these bits include an encoding of that length, but they do not depend on the ...

28

You're missing the most important strength of HMAC: it comes with a proof of security (under some plausible assumptions). The outer key plays an important role in the proofs. The best place to learn more is to read the HMAC papers: Message authentication using hash functions: The HMAC construction, Mihir Bellare, Ran Canetti, Hugo Kawczyk, CryptoBytes ...

26

The key to understanding hash extension attacks is to understand that the hash output isn't just the output of the machine generating the hash, it's also the state of the machine up till that point. In other words, just the hash output alone contains enough information for you to keep going and append more content to the hashed input. The catch is that since ...

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(...

13

Contrary to your assumption, this is done, and it is secure: For instance, the hash functions SHA-224 and SHA-384 are basically the same algorithms as SHA-256 and SHA-512! The only differences are in the initial values for the Merkle-Damgård construction used internally and, of course, in that only the first $224$ or $384$ bits of the resulting hash are ...

11

The archetypal situation where the length-extension property becomes problematic is when ones builds a Message Authentication Code from a hash function as $$\textrm{BadMAC}(K,M)=\textrm{Hash}(K||M)$$ where $K||M$ is the concatenation of the Key and the Message. The length extension property then translates directly into the capability to forge a different ...

9

As a Skein co-author, one of the properties of the UBI chaining mode is to give you HMAC-like properties in one pass. Skein itself consists of the Threefish tweakable block cipher, the UBI chaining mode, and some proofs that extend tweakable block cipher theory into a tweakable hash function theory that reduces the security of the hash function to the ...

8

To attack a MAC in general, the attacker needs to find a valid MAC of a message that they do not have the MAC for (or find a message collision that allows a different message to have the same MAC digest). In this case, the attacker would be appending data to the original message, not the MAC itself, and trying to obtain a valid MAC for the new message. In ...

8

The short answer is no. I'll assume $SHA256_d(M)$ is $SHA256(M)$ when $d=0$, else $SHA256(SHA256_{d-1}(M))$. $SHA256_1$ is protected against length extension attacks. The only sizable benefit that I see in parameterizing $d$ is that it allows tuning a slow down of the computation intended as a protection against brute force attacks. However there are more ...

8

How does the length extension attack against $H(k||m)$ work? For Merkle-Damgård hashes, if you know $H(x)$ but not $x$ you can still choose an $e$ and then compute $H(x||p||e)$. With $x=k||m$ you can compute $H((k||m||p)||e)=H(k||(m||p||e))$ which is a valid authentication tag for $m||p||e$. Why doesn't it work against $H(m||k)$? With a length extension ...

7

No, the length extension attack/property is not considered a collision. It does not allow to build a collision. The length extension property is that given the hash of a bitstring $M$ of given length $l$ (but arbitrary and unknown content), it is possible to compute the hash of $M\mathbin\|F(l)\mathbin\|E$ with $F(l)$ a short bitstring deduced from the ...

6

The objective of the construction $H'(m)=H(H(0^b\mathbin\|m))$ is not to strengthen $H$ against collision attacks; as noted in the question, that does not work. The objective is preventing a length-extension attack. In such attack, an adversary knows the hash $h=H(m_0)$ of some unknown $m_0$, and the length $l$ of $m_0$. Then from $h$ and $l$ s/he ...

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 ...

5

Let's split your question into two parts: first the length extension attack problem with Whirlpool, and next your HMAC tool idea. 1. Is whirlpool vulnerable to length extension attack? Yes, Whirlpool by itself (as a plain hash, not HMAC) is indeed vulnerable to length extension attacks. Besides Crypto.SE Q&As like “Understanding the length extension ...

5

If $H(x) = x$, $x$ is a fixed point. If for a value the output of the function is the same as the input, it is called a fixed point. A length extension attack is unrelated to the concept of fixed points. There is a good question about understanding length extension attacks here.

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

A length extension attack doesn't let you find a collision. It lets you predict the hash for an input with an unknown component in the prefix. If you have $h = H(x)$ for unknown (or partially unknown) $x$, you can generate $h_y = H(x \vert\vert y)$ for arbitrary $y$ (this is not strictly correct; I've ignored padding, but for the purposes of this discussion ...

5

First of all, let us explore what a "length extension attack" is; it might not be exactly what you assumed it was. Suppose we were given the MD5 hash of a bytestring we'll call $A$; we may have no idea what the string $A$ consists of, but we do know its length. Then, we can create a bytestring $B$ (which depends on the length of $A$, but not any of its ...

4

AFAIK the d stands for double, and simply means that the input gets hashed twice. i.e. SHA-256d = SHA-256(SHA-256(m)). It's not a configurable parameter, since hashing more often has no benefit, unless you want a slow down, but there are better constructions for that case. Hashing twice prevents length-extension attacks, but reduces performance, especially ...

4

This is not possible in general, or for the specific case of SHA1 and SHA512. Length extension works because MD-hashes iterate the same function, so knowing the output you also know the intermediate state for some related longer inputs. Now there are some cases with "different" hashes where it could be possible. That its when the hashes are related. Like ...

4

BLAKE2 is not open-source. BLAKE2 is a specification. The state is shuffled one last time after having set the final bit, ensuring that a small change, even a single bit, yields a completely different output, that cannot be reverted. A length extension attack means that knowing M and Hk(M), you may be able to compute Hk(M||E) without knowing the key k. ...

3

OK, lets go through this step by step: the message size of http://example.com/downloadfile=report.pdf is 10 bytes, as only the filename (report.pdf) is hashed according to the article; the key size is usually known and was explicitly set in the article to 11 bytes, not 15 (11 bytes is a bit short for a key size, by the way); so the length of the message is ...

3

I don't understand why you are talking about a 1-1 property; a pseudorandom function is not 1-1. As such, you can always just truncate in order to reduce the output size, and you can just truncate by taking the first $t$ bits that you want (you don't need to apply any other function). In order to extend, if $\ell$ is long enough to be the length of a seed in ...

3

But is it necessary to use these bytes? Yes, it is, at least for most messages that you'll see in practice. MD5 works by taking the message, and applying a fixed padding to it. This fixed padding involves, for messages which are a number of bytes (as opposed to, say, a message of 119 bits) an 0x80 byte, and for not huge messages, 0x00 bytes (in the length ...

3

The short answer is: No, there is no known practical attack in the setup given. But we do not have an argument/proof that there is not one, and we should be less confident in that than we are in HMAC-MD5, for which we have such an argument.

3

I'm putting another answer in because as good as D.W.'s answer is (I up-voted it), it doesn't really answer your question. You said: But the simple construction Hash(Hash(key|message)) would offer those properties too. But the construction you gave -- Hash(Hash(key|message)) -- has a weakness that HMAC does not. One of those properties was resistance ...

3

No, there is no known way. It would actually be rather surprising if there were even a theoretical way; the SHA-256 and the SHA-512 compression functions are rather different (for one, one works with 32 bit words and the other works with 64 bit words); one wouldn't expect them to share any sort of relation.

3

I understand, that this approach is more secure and eliminate length extension attack Actually, just be processing the blocks backwards doesn't actually eliminate any attacks. Instead of 'length extension' attacks, we have 'prepend attacks' (where we add the extra blocks to the beginning rather than the end), which yield the same vulnerability. Now, this '...

3

Actually, GOST R 34.11-2012 hash function doesn't work from the end. It defines M as a binary vector to be hashed. The binary number is usually printed with the least significant bit printed last. When they say M = M'||m, it means that m is a binary sub-vector containing 512 least significant bits of M. And since GOST standard uses big endian everywhere, it ...

3

With a little more information, an attacker can indeed get up to some funny business by abusing this "internal state-revealing" property of Merkle-Damgard style hash functions (this includes MD5 and SHA-1 and SHA-2 but not SHA-3). With hash(message1) and len(message1) but not message1 itself, there is one specific message2 such that an attacker can forge a ...

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