There is a file A and a file B.

If I have only HASH(A) and HASH(B) are there any non-trivial hash functions for which I could calculate both HASH(A ++ B) and HASH(B ++ A) without knowing A and B?

Can this be extended further?

Are there hash functions where, if I know HASH(A ++ B) and HASH(B), I can find HASH(A)?

(By trivial, I mean XOR, etc. "++" is the concatenation operator.)

Are any of these functions "good"? i.e. they have a low chance of collisions for non-malicious data.

Are any of these hash functions cryptographically secure?

  • 2
    $\begingroup$ CRC style hashes would work. They are not cryptographically secure, but are often used in non-malicious settings. The key feature for your question: the "finalize" step is invertible -- you xor the current hash with 0xFFFFFFFF to finalize. To unfinalize, you xor again, and then keep running the "update" step. If this is the only property you require, there are probably lots of candidates for non-cryptographic hashes. -- Oh, CRC is special in that it even works if you only have the hash of B. There are fewer hashes like that. If you only have hash(A), but have all of B, then there are lots. $\endgroup$ – Jack Schmidt Apr 3 at 14:09
  • 1
    $\begingroup$ There are no non-broken cryptographic hashes with the property that Hash(A) and B is enough to compute Hash(A++B). That's called an "extension attack" and is considered a weakness. However, by tweaking/removing the "intiialize" and "finalize" step of some cryptographic hashes (poly1305, i think, for example) you could allow this attack, even with only Hash(B), I believe for poly1305. $\endgroup$ – Jack Schmidt Apr 3 at 14:12
  • 1
    $\begingroup$ @JackSchmidt: even with CRC, to compute HASH(A++B) from HASH(A) and HASH(B), you need to know the length of B $\endgroup$ – poncho Apr 3 at 14:22
  • 2
    $\begingroup$ @JackSchmidt: poly1305 is not a cryptographical hash function. With a secret key, it is a MAC. With a publicly known key, it has similar properties to CRC. $\endgroup$ – poncho Apr 3 at 14:25
  • $\begingroup$ @poncho: thanks, I agree on all counts. I mentioned poly1305 because of its similarities to CRC, its larger tag size, and the ease of finding implementations $\endgroup$ – Jack Schmidt Apr 3 at 14:47

Your Answer

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

Browse other questions tagged or ask your own question.