Concatenation of multiple shorter hashes vs a single long hash

Question

I permanently need to hash lots of data quickly, but the result only needs to be collision resistant.

Is there any negative side-effect of using multiple (say 2) algorithms providing a shorter digest (e.g. RIPE-MD-128 and Tiger128) versus using an algorithm providing a digest of the added length (e.g. SHA256).

I want to explicitly highlight that I only need high performance and collision resistance. Other properties (avalanching, etc.) are irrelevant, I do not even care if it is possible to go back from digest to input. So I do not even need to really use "cryptographic" hashing algorithms (CRC32 is perfectly fine here I guess).

More specifically my idea is to use multiple REALLY FAST algorithms (clhash performing at over 4 gigabyte per second on my testsetup, xxhash performing at over 6GB/s, ...) and simply concatenate them to improve collision resistance: $$ Digest(Input) = XXH64(input)\ |\ CLhash(input)\ |\ CRC32(input)\ |\ Farsh(input) $$

This results in a digest with $64+64+32+32=192$ bits length, but is faster than an algorithms providing a digest with 192 bits. The important question for me is: is the collision resistance comparable to an algorithm providing 192 bits?

---

I benchmarked a lot of different hashing algorithms and the fastest performing hash, that is also reviewed and provides a long digest (which can be an indicator of better collision resistance), is Blake2b performing slightly above 1500 megabytes per second and provides a 512 bit digest. A combination of different algorithms would be even faster, and for my use case performance is key.

Answer 1

TL;DR: We don't know how secure your construction is with regards to collision resistance. We do however know that it isn't a cryptographically secure hash.

I permanently need to hash lots of data quickly, but the result only needs to be collision resistant ... So I do not even need to really use "cryptographic" hashing algorithms (CRC32 is perfectly fine here I guess).

If you require collision resistance you generally require a hash with large output. CRC32 would certainly not be fine. You would normally use a cryptographic hash to achieve this; you definitely need a large output size of the hash (i.e. 160 bits or over).

Is there any negative side-effect of using multiple (say 2) algorithms providing a shorter digest (e.g. RIPE-MD-128 and Tiger128) versus using an algorithm providing a digest of the added length (e.g. SHA256).

Well, yes, it won't provide as much security. How much less may be tricky to calculate though. MD5 and SHA-1 concatenation was used by SSL for a while. However, a paper by Antoine Joux: Multicollisions in Iterated Hash Functions has shown that these constructions aren't very secure when it comes to finding collisions. If the input cannot be manipulated then the chance of a collision happening should still be high though (i.e. finding collisions implies an active attack).

More specifically my idea is to use multiple REALLY FAST algorithms (clhash performing at over 4 gigabyte per second on my testsetup, xxhash performing at over 6GB/s, ...) and simply concatenate them to improve collision resistance.

You don't use any cryptographically secure algorithms, so the result is unlikely to be secure as well. At the very least it is probably impossible to prove security as the algorithms may be mathematically linked somehow.

With regards to collision resistance: it is likely that it will provide about 192 / 2 = 96 bits of resistance in case active attacks are not considered. It would be very hard to provide that it does because the algorithms may be somehow related.

It could be equally hard to find a way of showing that it does not provide 96 bits of resistance as proving that the algorithms are related may be hard as well.

---

A method of speeding up hash calculations is to use a Merkle- or hash tree. This will enable parallel processing to calculate the hash values.

Answer 2

If end users of your system supply the data being hashed in any way (e.g. as an string input or a object key in an API call) you absolutely need to use a cryptographic hash function to get collision resistance. None of the "fast hashes" you mention are collision resistant when faced with malicious input. Concatenation of a few such weak hashes does not magically create a collision-resistant cryptographic hash function.

Note that "malicious hash collisions" is not a theoretical attack; there have been many documented attacks against the "fast but weak" hashes used in hash tables by web frameworks, because they failed to recognize they were dealing with potentially malicious inputs. Also, the Google SHA-1 test documents corrupted Subversion repositories because of the assumption that user inputs could never collide; a stonger cryptographic hash function would have prevented this attack.

The hardware assist instructions for SHA2-256 on modern x64 chips probably makes this your best choice; SHA2-256 may even be faster than your "multiple weak hashes" scheme on common x64 hardware.

If after, implementation of the system with a cryptographic hash, real measurements reveal that hashing is actually the real bottleneck in your whole system, you could consider using a reduced-round variant that still offers practical collision resistance against malicious input. The research papers out there can be a guide as to what is considered safe, but in general real crypto hashes like SHA2/SHA3/Blake2b have high security margins.