4
$\begingroup$

Is it possible to have a single hash function output simultaneously verify a compressed block of data as well as its uncompressed counterpart?

Trivially one could just use a hash function twice (once on the uncompressed version and again on the compressed version) and concatenate the outputs, or use a hash function that internally does that, but I wonder if it's possible otherwise.

For example, imagine we've got these functions:

Hash getHash(byte[] data);
byte[] compress(byte[] data);
byte[] decompress(byte[] data);
bool verify(byte[] data, Hash hash);

...then I'm looking for these properties for a nontrivial byte array D (that is uncompressed):

  • verify(compress(D), getHash(D)) == verify(D, getHash(compress(D))) == verify(D, getHash(D)) == true
  • D == decompress(compress(D)) for all D, i.e. lossless compression
  • verify(E, getHash(D)) == false "most of the time" when E != D, i.e. collision "resistant" hashing

This could be useful when verifying persisted compressed data: you could verify the correctness of the compression algorithm and of the uncompressed data both at the same time without having to decompress it or store multiple hashes.

I'm not sure where to start looking for this. I think what I'm describing is some kind of homomorphism but apparently I need to level up my search skills. It seems like a Difficult Problem™; for example, the Deflate algorithm outputs data structures like a Huffman tree/table, and the mathematical relationships of serialized data structures being run through hash functions aren't immediately obvious to this OP.

$\endgroup$
  • $\begingroup$ Wouldn't it be trivial to perform collision attacks on such a hash function? Just keep iteratively compressing the data to get more and more collisions. The cycle length (or divergence) under iterated application becomes very important. $\endgroup$ – Craig Gidney Jul 18 '16 at 15:16
  • $\begingroup$ What kind of hash function? A cryptographic hash function? Why can't the compressed block's hash be verified simply by decompressing it and calculating the hash of the result? $\endgroup$ – Gilles 'SO- stop being evil' Jul 19 '16 at 0:04
  • $\begingroup$ @Evil Thanks for pointing that out. I thought it was fine because of something I must have misread in a meta question, until you said this which made me look harder and find meta.stackexchange.com/a/64069. I deleted my other questions $\endgroup$ – Matt Thomas Jul 21 '16 at 15:00
  • $\begingroup$ Hey, no problem, now everything is fine. Also I thought about your question - some kind of wavelet compression might work, the mix of coefficients would be also hash, another one would be using compression invariant features, like BWT (not compression, preprocessing and point about invariant) - before and after transform location changes but characters not, then RLE - which will give stats. But it is tradeoff - either hash is fast or compression is sophisticated. $\endgroup$ – Evil Jul 21 '16 at 15:13
2
$\begingroup$

In most situations you probably don't want to have D and compress(D) to have the same hash value, as that leads to hash collisions. Usually hash functions are designed to avoid hash collisions -- and this is a good thing. For instance, in cryptographic contexts, any hash scheme that has the properties you ask for would automatically be considered cryptographically insecure.

Therefore, trying to design a hash function with this property is probably a bad idea. Instead, you should probably use the alternative solution: when you verify a hash value, hash both the data D and the compressed version compress(D) and see if either of those hash digests match the expected value. That's probably a much better solution in practice.


If you absolutely must achieve this by artificially introducing collisions into your hash, here is a way you can do it. Disclaimer: This is totally theoretical; it is not useful in practice.

Define the verify procedure as follows:

Verify(D, Y):
1. If Hash(D)==Y or Hash(Compress(D))==Y or Hash(Uncompress(D))==Y, return true; otherwise, return false.

Yes, this is totally trivial.

No, I don't think you'll find anything that is faster than this and that also satisfies the properties to be a good hash function. Hash functions are specifically designed to avoid having any mathematical structure, while at the same time being very fast. Mathematical structure is considered a weakness in a hash function. In contrast, you are asking for a hash function with some structure. Inserting such artificial structure into the hash function might be possible, but the natural ways of doing it probably will either introduce lots of bias into the hash function (e.g., lots of collisions) or slow it down a lot.

To put it another way, right now hash functions are optimized to meet two criteria:

  • Be fast.

  • Be "random-looking" (few collisions, unbiased, etc).

You are proposing to look for a hash function that meets three criteria:

  • Be fast.

  • Be "random-looking" (few collisions, unbiased, etc).

  • Also, satisfy the additional properties you requested that verify(compress(D), getHash(D)) == verify(D, getHash(compress(D))) == verify(D, getHash(D)) == true.

Obviously, it's harder to meet three criteria than to meet two. If you want to meet three criteria, something will have to give: and in your situation, that means the resulting hash function will either be slower or less "random-looking" than standard hash functions (probably significantly so).

So, I don't expect there's any better solution for what you want. Instead, just do the natural solution you mention of hashing twice.

$\endgroup$
  • 1
    $\begingroup$ One thing that might be more feasible is is to devise a hash function and a compression scheme for which it's efficient to compute the hash of the underlying uncompressed file. Say you had a hash function with a fast concatenation operation, and you could use the structure of a LZ77 dictionary to share subcomputations. This would be an interesting research topic. $\endgroup$ – Pseudonym Jul 18 '16 at 22:39
  • $\begingroup$ @Pseudonym, I agree with everything you said. It might be possible to do something. However, from a practical perspective, I'm very skeptical: I don't think it's a promising direction. From an engineering perspective, I would recommend the naive solution (hash twice) and move on with your life. There are some problems where it seems like there's a reasonable chance that research might lead to a practical solution that's useful and significantly better -- but this doesn't feel like one of those to me. I freely admit this is all a matter of judgement, I have no proof, and I could be wrong. $\endgroup$ – D.W. Jul 18 '16 at 22:46
  • $\begingroup$ I completely agree with you from a practical perspective. It would still be interesting, though. $\endgroup$ – Pseudonym Jul 18 '16 at 22:49
  • $\begingroup$ Presuming for a moment that we've got a magic algorithm that satisfies the criteria, wouldn't the number of hash collisions only be doubled? (Since for "good" lossless compression compress(D) usually equals compress(compress(D)) i.e. you can't keep compressing data ad infinitum) $\endgroup$ – Matt Thomas Jul 21 '16 at 15:09
  • 1
    $\begingroup$ @MattThomas, well, my experience is that real lossless compression algorithms don't have that property. Typically compress(compress(D)) is a bit bigger than compress(D), and the sequence D, compress(D), compress(compress(D)), compress(compress(compress(D))) is an infinite sequence that never repeats. Try it! $\endgroup$ – D.W. Jul 21 '16 at 17:44

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.