3
$\begingroup$

Assuming our fixed compression function $h$ works for inputs of length $i(n)$ and output strings of length $o(n)$, if $2o(n) < i(n)$, why do we need to calculate $h(z_B||L)$ where L is the input's length instead of just concatenating $z_B ||L$? What do we gain from hashing the length?

$\endgroup$
3
$\begingroup$

I am making the assumption you are asking why not just append the length to the output of the hash, the question is not quite clear on that. Take a very simple example of SHA-1 modified to do what I think you are asking. The results here are fake, but the example stands.

If we hash a byte stream of 0xFE25B6A1C8, we may receive the digest a9993e364706816aba3e25717850c26c9cd0d89d0000000000000028.

If we hash a byte stream of 0xFE25B6A1C800, we may receive the digest a9993e364706816aba3e25717850c26c9cd0d89d0000000000000030.

It should be clear that this is not a desirable property.

The same property applies to other inputs where there are trailing 0 bits within the same compression function call and the same total number of compression calls, the bits have no effect on the hash function without the length because of how they are used to generate the message word array.

$\endgroup$
  • $\begingroup$ Deterministic bit padding would make this answer incorrect (currently there is only padding when required because of the length but that's easily fixed). $\endgroup$ – Maarten Bodewes Jan 29 '17 at 12:39
  • $\begingroup$ Rereading that last comment: it should be preceded with "Note that" as it doesn't invalidate the answer; I've actually voted up this answer in Januari '17. $\endgroup$ – Maarten Bodewes Nov 26 '17 at 14:25
2
$\begingroup$

Well, there are two immediate reasons, besides the points given by the answer linked to by CodesInChaos about the harder security proof:

  1. the size of the hash value would grow by 64 bits to encode the length;
  2. the size of the message would be directly leaked.

The second property is not good at all; think of hashing passwords, or even hashing a message using HMAC while the size of the input is always leaked. That would certainly leak information that you do not want to be leaked.

$\endgroup$
0
$\begingroup$

From theoretical point of view, we CAN, if the underlying hash is collision resistant than using the modified version you suggested would create collision resistant hash, BUT, the size of the output will grow, instead of size $o(n)$ we would get output of size $o(n)+i(n)$. Note that hash function does not need to hide anything, it just needs to have the collision resistance property.

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