Why use MD4 for caching?

Question

ccache is a popular tool for speeding recompilation with GCC and other compilers. It works by caching previous compilations and detecting when the same compilation is done again. The detection is done using MD4 hashes.

I am curious as to (a) why such a caching tool would use any cryptographic hash function, and (b) of all the cryptographic hash functions available, why MD4 in particular would be used.

Regarding (a), what's the benefit of using a cryptographic hash function, as opposed to some hash function not designed with cryptography in mind? For example, Java's built-in hash functions don't seem to correspond to known ones used (or formerly used) in cryptography. Why not use one of these non-cryptographic hash functions instead? Given MD4's known weaknesses, I can't imagine that it would be chosen out of a desire for greater security.

Regarding (b), assuming that there is some basis for using a cryptographic hash, why MD4 in particular? I understand that it wouldn't make sense to use a modern cryptographic hash function, since these are generally computationally intensive, which defeats a caching tool's purpose of speeding up access times. So MD4 must be used at least in part for speed. But is it absolutely the fastest cryptographic hash function, or are there others that are faster? If it's not the fastest, what other advantages would MD4 have (over, for example, MD5) for use in caching?

Answer 1

Usual non-cryptographic hashes such as CRC-32 are statistically good, but here what the cache wants to avoid is false positives -- recompilations that are declared identical to a previous one, but are not. A usual non-crypto hash that produces only 32 bits has too high a risk of false positive, simply from its output size, and regardless of its statistical qualities. A cryptographic hash has a much larger output, which makes risks of false positives negligible.

This is not a security question: all the inputs are from the user, so if the user makes a collision on purpose he is only fighting against himself. Thus, a cryptographically broken hash function can be used.

Now for the specific choice of MD4 over a more common function (such as MD5 or SHA-1), one can only speculate, but my guess is that it is about performance; after all, ccache is all about making compilations faster. MD4 is devilishly fast (even faster than CRC-32 on some platforms). Of course, hashing is faster than any compilation process or even simply reading files, so chances are that using MD5 instead of MD4 would have make no significant difference in the overall performance of ccache. Many performance-related decisions are in practice taken on a hunch, without bothering with actual measures to see if there is a performance issue that must be solved.

From work on this library, there are very few cryptographic hash functions that are at least as fast as MD4. BLAKE2, a recent derivative of the BLAKE SHA-3 candidate, may be your best bet for a cryptographically secure hash function that approaches MD4-levels of performance. But, as I wrote above, it is highly probable that performance is not a real issue in the case of ccache.

Answer 2

Cryptographic hash functions usually have the property that slightly different inputs generate vastly different outputs. Any collisions should usually have very different input.

This property does not apply to most non-cryptographic checksums. Small changes can result in similar checksums, and in some corner cases some small changes can cancel each other out in a way that the same checksum is generated.

Changes in sourcecode are often quite small, so in the context of checking sourcecode changes the risk of collisions is quite high with non-cryptographic checksums. The version control tool git, for example, uses SHA-1 hashes as unique identifier for code revisions.

Why MD4 in particular? Well, you got to ask the ccache developers about this. It is a quite old tool, and MD5 wasn't standardized until 1992. It might be possible that MD4 was simply the most obvious choice which was available at the time this feature was developed, and later on nobody felt the need to replace the algorithm, because it did what it was supposed to be doing.