Can `hash( messageA ) + messageB` be used to determine `hash( concat( messageA, messageB ) )`?

Question

In .NET and other programming platforms all hash functions (such as MD5, SHA256, etc) can be used with streams of bytes, potentially forever - so it isn't necessary to read an entire multigigabyte file into an in-memory buffer to compute the hash of the file, the hash algorithm simply considers new data as it arrives and updates its internal state accordingly.

...it makes me think of the arithmetic Mean function which can work in the same way below, using C# IEnumerable<Byte> to represent a potentially infinite stream of data:

public static int Mean(IEnumerable<Byte> bytes)
{
    UInt64 sum   = 0;
    UInt64 count = 0;

    foreach( Byte b in bytes )
    {
        count++;
        sum += b;
    }

    return (Double)sum / (Double)count;
}

I've long assumed that hash functions might work in the same way as accumulators (warning: considerable over-simplification, I know there's more at work):

public static Byte[] SomeHashFunction(IEnumerable<Byte> bytes)
{
    Byte[] hashState = new Byte[32];

    foreach( Byte b in bytes )
    {
        ConsiderByte( hashState, b );
    }

    return hashState;
}

With arithmetic-mean, provided you know the count and the mean so-far, then you can compute an updated average as new data arrives without needing to see all previous data. E.g. the high-school exam question "If the average height of 20 students is 157cm, and the 21st student is 181cm, what is the new average?" ( ( 157 * 20 ) + 181 ) / 21 == 158cm.

I'm assuming we can do the same for hash functions like SHA256, then SHA256( concat( messageA, messageB ) ) should be computable given SHA256( messageA ) and messageB separately.

But instantly I imagine there's some "final processing step" that non-trivial hash algorithms will do to prevent that (such as not processing individual bytes, but processing blocks of bytes and padding them to some amount if the input data isn't long enough (indeed, in .NET there's the TransformBlock function but also the TransformFinalBlock function so there definitely is special processing when the end of data is reached). This means that provided we can get the internal state of the hash function after processing messageA and persist it then we can compute hashes of concatenated messages. Are there any weaknesses in any algorithms like SHA256 where the internal state can be derived from the output? Is this a weakness at all? What techniques can be used to prevent the internal state being derivable from the output?

Answer 1

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 valid hash(message1 || message2) by running further iterations of the hash algorithm starting with hash(m1).

When a hash of this style is used to generate a Message Authentication Code (MAC), that message is vulnerable to "length-extension attacks". That means an attacker can append the message with their own malicious message and forge a valid tag.

Of course, there are ways to prevent this kind of attack. One easy method is the "wide pipe" strategy -- simply generate your hash with more bits than you need, and truncate your final result! Now the hash code you output no longer represents a valid internal state of the algorithm.

Modern standards for hash functions use this or other such strategies to prevent this from being a problem in practice. For example, HMAC (the standard way to build a MAC from a hash) runs the hash function twice in a way that avoids length extension attacks.

Answer 2

First, this is not generally true of SHA-256 or MD5. What is true is that $$\operatorname{SHA256}(\operatorname{pad}(m) \mathbin\Vert m') = f(\operatorname{SHA256}(m), m')$$ for some easily computed function $f$, where $\operatorname{pad}$ is the padding function of SHA-256.

This length extension property causes trouble for some protocols; with overwhelming probability it is not shared by a uniform random choice of function, so certain protocols whose security is shown with overwhelming probability using a uniform random function may fall apart when instantiated with SHA-256.

For example, if you try to use $m \mapsto \operatorname{SHA256}(k \mathbin\Vert m)$ as a message authentication code, I can forge messages and authenticators without knowing $k$ just by applying the length extension property to a message/authenticator pair I got from you.

Newer designs, such as SHA-3 and all of the SHA-3 candidates and their derivatives like BLAKE2, avoid this property—it was a requirement of the SHA-3 competition. Truncated SHA-2 hashes, like SHA-384 or SHA-512/256, also avoid this property: instead, $$\operatorname{SHA384}(\operatorname{pad}(m) \mathbin\Vert m') = g(\operatorname{SHA384}(m) \mathbin\Vert h, m')$$ where $h$ is a 128-bit part of the 512-bit state discarded by SHA-384, which an adversary would have to guess in order to compute $\operatorname{SHA384}(\operatorname{pad}(m) \mathbin\Vert m')$ from $\operatorname{SHA384}(m)$.