2
$\begingroup$

Let $b_1, b_2, \dots, b_n$ be blocks of a fixed size. We take our hash function to be $H(x)$, for example SHA1.

What is the result of $H(b_1 || b_2 || \dots || b_n)$?

Edit:

Let me formulate it more clearly. So I want to know if the following properties (or any other similar property) hold:

  • $H(b_1 || b_2) = H(H(b_1) || H(b_2))$
  • $H(b_1 || b_2) = H(b_1 || H(b_2))$
  • $H(b_1 || b_2) = H(H(b_1 || H(b_2)))$
  • Associativity (I assume it's not the case)
  • Commutativity (clearly not the case)

For any hash function like MD5, SHA1, etc.

Edit 2:

Okay, so how are large inputs treated by decent hash functions? Will the blocks be xored, then hashed. Is there a pattern or is it completely different from function to function?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What do you mean, "what is the result"? Hash functions generally "mess up" the input to random-looking output, so the output will not have any visible relation with the individual blocks, if that's what you're asking. $\endgroup$
    – TMM
    Feb 5, 2017 at 1:01
  • 1
    $\begingroup$ For any decent hash none of these properties should hold. I'll answer what is asked in your question soon, until then: The two major construction methods for hashes are Merkle-Damgard and the Sponge-Construction or something custom (which is quite rare) $\endgroup$
    – SEJPM
    Feb 5, 2017 at 11:38
  • 1
    $\begingroup$ I could be wrong, but chances are it may help to prevent downvotes if you'ld describe what research you've done. See, sharing your research efforts helps everyone! Tell us what research you did, what you found, and why it didn’t meet your needs. That shows answerers you took time trying to help yourself, it saves us from reiterating obvious answers, and – most important – it helps you to get more relevant, on-point answers. Hope that helps… (I've dropped a motivational upvote, assuming you think about what I just hinted at.) $\endgroup$
    – e-sushi
    Feb 5, 2017 at 12:11

1 Answer 1

Reset to default
4
$\begingroup$

The old hash functions you mention (MD5, SHA-1) are based on the Merkle-Damgård construction. SHA-3 uses a sponge construction instead. There are certainly more variations possible, but these are the popular ones.

There are multiple constructions possible but for most hash functions the input is indeed split in blocks. These blocks are directly put in some kind of compression / sponge function which is used to update the state of the hash function. A hash function also has an initial state provided for when zero blocks have been processed.

Generally the last block is padded and a length of the input is included to create the final state. In the case of MD5 and SHA-1 the state is directly output as the hash value, but in more modern hash constructions there may be more processing before the final output is produced. This happens for instance for SHA-3.

A hash function is required to always produce a different output for any different input. As they may process a virtually unlimited amount of input while producing a small amount of output there must of course be many messages that produce the same output; this is called the pigeon hole principle.

It is however computationally infeasible to find those input.at least when the hash function is not broken. MD5 is such a broken hash function for which this property is clearly not true anymore.

So lets visit your questions with this knowledge:

  • $H(b_1 || b_2) = H(H(b_1) || H(b_2))$ - clearly different inputs
  • $H(b_1 || b_2) = H(b_1 || H(b_2))$ - clearly different inputs
  • $H(b_1 || b_2) = H(H(b_1 || H(b_2)))$ - clearly different inputs
  • Associativity (I assume it's not the case) - clearly different inputs
  • Commutativity (clearly not the case) - clearly different inputs

So, no, hash functions do not possess any of these mathematical properties, which is not surprising if you consider that it should be infeasible to reverse a hash value.

It's much more interesting to have a look at how the internal compression function or sponge function behaves.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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