3
$\begingroup$

Assume I have two data fragments: $Frag_1$ and $Frag_2$.

I can build sha512 hashes the usual way with $SHA512(Frag_1)$ and $SHA512(Frag_2)$ and then hash the two fragments appended to each other:

$$SHA512(Frag_1 | Frag_2)$$

My question is, is there any way to combine the hashes of those two fragments so that it would be possible to compute the hash of their appended version?

More precise: Is there an operation (denoted here with a red question mark “$\color{red} ?$”), so that

$$SHA512(Frag_1)\ \color{red} ?\ SHA512(Frag_2) == SHA512(Frag_1 | Frag_2)$$

It is possible to create the data fragments with a length of a multiple of the block size of sha512?

$\endgroup$
  • $\begingroup$ I don't have a proof (maybe someone else has), but I think this is impossible without inverting SHA-512. $\endgroup$ – SEJPM Aug 21 '15 at 16:15
  • $\begingroup$ en.wikipedia.org/wiki/Length_extension_attack $\endgroup$ – Henrick Hellström Aug 21 '15 at 17:13
  • $\begingroup$ @HenrickHellström That extends a hash using additional data. Combining the state of one hash with another hash, which started off with the usual initial state seems another matter to me entirely. $\endgroup$ – Maarten Bodewes Aug 21 '15 at 21:04
  • $\begingroup$ As nicely explained in the answers, if this was possible for any Hash function, it would lead to a recursive attack and a break. $\endgroup$ – kodlu Aug 22 '15 at 9:47
8
$\begingroup$

Most standard-use iterative hash functions (including SHA-512) are build in a way that these types of operation are not possible (without breaking the hash function).

They work generally in this way:

  • The message is split in same-size blocks (usually with some padding at the end to fill the last block): $pad(M) = M_0 || M_1 || M_2 ... || M_n$.
  • There is some internal "state" $S$, initialized to a fixed value $S_0$ at the start
  • For each block, some internal function $C$ (usually called a "compression function") is applied to the old state and a message block to produce a new state: $S_{i+1} = C(S_i, M_i)$
  • At the end, either the last state is output directly, or (in more modern hash functions) another function $O$ is applied on that state to produce the final hash output: $h(M) = O(S_{n+1})$

So for example with a 4-block message (after padding) we have $$h(M) = O(C(C(C(C(S_0, M_0), M_1), M_2), M_3)).$$

The compression functions are usually build in a way that even a minor change in one of the inputs produces a totally different output, and such that there is no easy way to go back from the output to the input. (This is usually formalized as "$C$ is a one-way function".) (Sometimes parts of the state are treated specially and can be easily tracked back, like in Skein, where they contain a counter. This is not the case for SHA-256, and also in Skein this doesn't hurt anything, as the output doesn't include them.)

Even assuming there is no padding, O is the identity and our fragments have both the size of only one block, we get $h(F_1) = C(S_0, F_1)$, $h(F_2) = C(S_0, F_2)$ and $h(F_1||F_2)) = C(C(S_0, F_1), F_2)$. While we can write the latter also as $h(F_1||F_2)) = C(h(F1), F_2)$, the one-way property of the compression function doesn't allow us to get any information about this from $C(S_0, F_2)$.

But if you have $F_2$ actually given, not just its hash, you can use this to create the hash of $F_1||F_2$, even without knowing $F_1$. This is known as the length-extension property of iterative hashes with the identity as its output transformation.
In reality it is complicated by the presence of a padding, but you still get to create the hash for something like $F_1 || P || F_2$, where you know $h(F_1)$ (but not $F_1$ itself), $P$ is some padding depending on the length of $F_1$ (and not actually needed to be known by you), and $F_2$ is a string chosen by you).

Using a non-trivial output transformation blocks this – possible ways are to apply some simple truncation (like SHA-384, which is essentially SHA-512 with a different initial state and a truncation of the result), or some other compression-function-like transformation. Or simply apply the whole hash function again on the result (this is used e.g. as SHA-256d in the Bitcoin protocol).


On the other hand, there are hash functions which are specifically designed to allow stuff like that: hashing two (or more) parts of the message separately and create the final hash from the partial hashes.

Have a look at the Merkle tree article in Wikipedia, it explains the basic principles. When used as a simple message hash algorithm (and not a complex structure), for it to have a deterministic result, the size of $F_1$ needs to be one of some few specific values (e.g. powers of two), so the limit between $F_1$ and $F_2$ falls exactly on a border between two subtrees.

$\endgroup$
  • $\begingroup$ I suspected as much, thank you for the very detailed and well understandable explanation! $\endgroup$ – Cybran Aug 22 '15 at 7:39
  • $\begingroup$ Is there a common name for the "hash functions which are specifically designed to allow stuff like that"? $\endgroup$ – Alexei Osipov Dec 23 '15 at 18:53
2
$\begingroup$

No, that's not possible, as you calculate sha512(F2) without the state of sha512(F1). What you require is compress(mix(compress(mix(IH, F1)), F2)) while what you have is compress(mix(IH, F1)) and compress(mix(IH, F2)). So you would have to undo that last compression, which is obviously not possible.

Here IH is the initial state (the values of $h_1$ etc.) for SHA-1 or SHA-2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.