1
$\begingroup$

When people talk about hash functions, they usually say that they accept arbitrary-length input, but if you actually look at the padding (eg MD-strengthening padding), you see it's like M100.000||length where length is the binary representation in bytes or bits. But what if the length is so large that you can't represent it in a single block?

Obviously you can get around this problem by just using the most significant bits, but doesn't this destroy the MD-compliant padding property (which you need in proofs of one-wayness and collision resistance etc, assuming properties of the compression function)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

It depends on the exact Merkle-Damgaard hash.

MD5 will literally take an arbitrary length; that's because the value placed in the padding is actually computed modulo $2^{64}$.

For SHA-1 and the SHA-2 hashes, yes, you are correct; there is an upper bound on the length of the preimages that could potentially be hashed; for SHA-1, SHA-224 and SHA-256, it's $2^{64}-1$ bits; for SHA-384, SHA-512, SHA-512/224 and SHA-512/256, it's $2^{128}-1$ bits.

On the other hand, for all practical purposes, these limits are effectively infinite. For example, with SHA-1, the limit of $2^{64}-1$ bits, that's $2^{55}$ blocks; even if we were able to the compression function in 10nsec, that means it'd take us over 10 years to hash a single value that size. It's unlikely that anyone would actually attempt that.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Makes sense, thanks. With regards to MD5, does the padding satisfy the conditions of being MD-compliant (en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction)? I think not? And I think it's impossible to truly take arbitrary length input and still satisfy MD-compliancy isn't it? $\endgroup$
    – Mark
    Commented Dec 8, 2014 at 11:17
  • $\begingroup$ I think it won't scale that high on the list of MD5 deficiencies if it's not MD-compliant with regards to this. It would be fun though if you could generate a collision after 2^64 cycles, some kind of MD5 "time bomb" :) $\endgroup$
    – Maarten Bodewes ♦
    Commented Dec 9, 2014 at 10:37

Your Answer

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

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