5

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?

3

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.

9

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.

  • Indeed. Just because a cryptographic hash is no longer useful as a cryptographic hash doesn't necessarily mean it's bad as a hash where cryptographic level guarantees are not needed. (Same issue as with SHA-1 today; SHA-1, despite being sunset for specific uses is still perfectly usable and useful in many other situations. Not everything needs to be SHA-512.) – a CVn Feb 26 '16 at 15:46
  • 1
    I wish git used SHA-256... It uses SHA-1... – Bruno Rohée Feb 26 '16 at 17:40
  • 1
    +1, this happened to us. Our old source repository used CRC32 digests, and the system admin thought he could save space by deleting files with identical digests. That made the next build really interesting! – John Deters Feb 26 '16 at 20:32
  • @BrunoRohée Corrected. But I don't see what advantage SHA-256 would have in that scenario, except for creating revision ID's which are twice as unwieldy as they already are. – Philipp Feb 27 '16 at 12:07
  • When SHA-1 preimage collisions will be doable, there will be lots of funny attacks on git... Hopefully we'll have moved on by then... – Bruno Rohée Feb 27 '16 at 12:10

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.