The BLAKE3 version does indeed seem to be faster. The question now is if would be worth the effort to integrate it into ccache? One problem, beside it being new and perhaps not yet battle-tested, is that there is no official C-API, so the sources would have to be included directly in ccache.

Yes, sounds interesting. I would be OK with bundling the source code. Would you like to prepare a PR so that we can try it out a bit more?

issues in misc/performance

Thanks for the notice, fixed in dcd4efc.

Yes, I can look into creating a PR for this.

If speed really matters, I suggest to have a look at KangarooTwelve, based on a primitive that has been cryptanalysed since 2008, unlike all other new fancy stuff. But do this only if you care about peer-reviewed algorithms, you know the kind of thing you should look at when dealing with crypto...

Otherwise I suggest to wait for Blake4, probably going to be out next year or so.

I agree that one should probably not pick BLAKE3 just yet for anything security related, but for ccache's usage I don't see a big problem with it.

Maybe K12 is faster (even though the latest numbers in the Python issue to add BLAKE3 support seems to have BLAKE3 as the leader), but my primary motivation for suggesting BLAKE3 instead of anything else was that it seemed to be an easy upgrade from BLAKE2.

Security should be a primary concern of ccache because many users just deploy binaries built somewhere else, and hence there is a need to protect the integrity of these binaries, not only in the way you distribute them but also up to the tool chain that produces them. If you use a hash function that is not secure against collision, it would be trivial to inject trojan objects in the cache, and it would be quite difficult to detect the infection.

Now you may discuss on the relevance of that attack model, or even point out that old ccache was using the very weak MD4 as hash function, but in my opinion given the speed gain of ccache, I consider now that security is more a concern than any potential speed benefit. Taking my project and PC as an example, a standard single thread build (make -j1) takes 2 minutes without ccache, and down to 3 seconds with ccache. With parallel built (make -j64) it goes from 34 secs to 2 secs. Is there any point in making it faster?

Security should be a primary concern of ccache because many users just deploy binaries built somewhere else, and hence there is a need to protect the integrity of these binaries, not only in the way you distribute them but also up to the tool chain that produces them. If you use a hash function that is not secure against collision, it would be trivial to inject trojan objects in the cache, and it would be quite difficult to detect the infection.

Now you may discuss on the relevance of that attack model, or even point out that old ccache was using the very weak MD4 as hash function, but in my opinion given the speed gain of ccache, I consider now that security is more a concern than any potential speed benefit. Taking my project and PC as an example, a standard single thread build (make -j1) takes 2 minutes without ccache, and down to 3 seconds with ccache. With parallel built (make -j64) it goes from 34 secs to 2 secs. Is there any point in making it faster?

Just bringing another data point: Ccache brings my project from hours to half an hour. But if it can get any faster, that would be lovely. I (and I suspect many of the current users) do no really care about security at the level of ccache.

Of course nobody cares about security (until it's too late). But at least you should get your requirements straight.

• "I don't care about security. I want every nanosec of possible improvement"
  Okay... but then why use a cryptographic hash function at the first place? There are much faster non-cryptographic alternatives.

• "I only care about speed but please tag me with some crypto"
  Use AES-NI instructions.

• "It's 2020. State-of-the-art security becomes a must. I want the best security-speed trade-off"
  Use KangarooTwelve.

Security should be a primary concern of ccache [...] Now you may discuss on the relevance of that attack model

Since you make this to be about security, then yes, relevance needs to be part of the discussion. There's a reason why MD4 (+ input length) is still used in the latest released ccache version even though MD4 has been cryptographically broken for decades, and that's simply because the ccache maintainers have not considered being resistant to attacks to be a concern. That may be a mistake and you are welcome to contribute with insights. Talking down to us from a high pedestal is however not welcome.

If you use a hash function that is not secure against collision, it would be trivial to inject trojan objects in the cache

Say that you want to inject into my cache a trojan object file whose source code is crafted to collide with a source code file that I will compile in the future. To do that you have to make me compile source code I got from you, for instance via some third party library I downloaded from the Internet. Additionally, you need to make me compile it without using any bundled build scripts, Makefiles or similar (since there otherwise is a much easier way to poison my cache: just write the trojan object file directly to the cache; no collision needed). Is this the scenario you mean is trivial or is there another one?

• "I don't care about security. I want every nanosec of possible improvement"
  Okay... but then why use a cryptographic hash function at the first place? There are much faster non-cryptographic alternatives.

The answer is simple: We (or at least I) are not aware of any non-cryptographic alternatives with suitable properties.

• "I only care about speed but please tag me with some crypto"

I don't even know what that means. Please stop creating straw men.

[...] Use KangarooTwelve.
[...] Otherwise I suggest to wait for Blake4, probably going to be out next year or so.

I see that you are one of the authors of SHA-3 and KangarooTwelve. If you are angry about crypto competitors in some way then please bark up another tree.

I don't see any pedestal around, so you must clearly misinterpret something. I could misinterpret your tone as well, but I prefer to assume your good faith.

I'm perfectly fine with ccache using MD4. My main point was that I don't see any good reason to use BLAKE3 instead. Either you value speed, but then I doubt that BLAKE3 will bring you any benefit compared to better alternatives or even MD4. Or you value security, but then why pick a cryptographic primitive that is only a few weeks old?!?

Regarding suitable hash functions, and if you only focus on speed, then AES-CBC implemented with intel AES-NI instructions seems a good candidate. This would produce a 128-bit digest like MD4 does. You don't need a key, so you can drop the key part, and since you "only" get 2^64 resistance against collision (because of the "small" 128-bit digest size), it means that you can reduce the number of rounds to get even more speed. Reducing to 6 (or even 4 rounds might be acceptable) would give you a significant speed up. Of course, you would then have a hash function that is no longer cryptographically secure (like MD4), but this is out-of-scope.

I don't know much about dedicated non-cryptographic hash functions. Your main requirement is the size of the digest, so one candidate might be MurmurHash2_160. Otherwise, collision and pre-image resistance always comes with a cost, so if you don't need that, then you can turn most cryptographic hash functions into a faster (non-cryptographic) one simply by reducing their number of rounds (as I proposed above).

Finally, if you would know a bit the history around SHA-3 and follow-up, you would know that we are not the ones with anger issues. Some of the "competitors" (as you put it) did admit publicly they do have some though. My comment was only meant to say that K12 is faster than Blake2 (fact) and more secure (opinion, but based on 12 years public review), and a (possibly bad) joke that is usually bad practice to propose to include the very latest crypto in designs without a time of public review.

Regarding attack scenario, here an example.

Say that you have a project hosted on GitHub with continuous integration. This CI runs your tests at each commit and also provides some release packages at tagging points. Dev gets notification when tests fail, and users can download new releases from this project. To accelerate the build process and reporting, the build tool chain uses ccache.

if I have write access to that repository, I could push a commit that would update a source file that would contain some trojan code, and wait the CI to start building this new commit. When done, the ccache would contain the trojan code in its cache. Then I push another commit, updating the very same file, and such that this new version of the file collides with the previous version when being hashed by ccache. The CI would then produce a binary containing my trojan code although this code disappeared from the sources. If history rewrite is allowed, this new commit could replace the previous commit, hence removing any traces from the repository itself. Depending on the CI setup, injection could even occur through a pull request (so even without write access to the repository itself).

@xeyownt: Thanks for showing and assuming good faith. What triggered my (maybe overly harsh) reply was the IMO lecturing and ironic tone in #503 (comment) and #503 (comment) (and probably also a dose of tiredness due to 👶). When coming as an outsider and giving unasked-for but well-meaning advice I think that it is a good idea to be a bit careful to not come off as ironic or sarcastic since that will only risk backfiring. I hope this makes sense to you.

So the background here, if you're not aware, is that the next still unreleased ccache version currently uses 160 bits of BLAKE2b for an increased sleep-well-at-night factor compared to 128 bits MD4 + length. Regardless of which algorithm is used, how large of a digest size would you say is appropriate for ccache's use case? (The reason for not using too many bits is mainly to keep filenames reasonably small.)

I guess that if you wanted to prevent such a public CI system, you could add some salt using CCACHE_EXTRAFILES ? Including a secret value in the hash, would make it harder to predict.

I think it would be interesting to compare MD4 and K12, so I will set up such a comparison for myself. Would be nice to have something embeddable, similar to "mdfour.c". But that is probably just me.

Here it is, in normal C: 3.7-maint...afbjorklund:kangaroo

Everyone else would probably just use generic64/libK12.a

@jrosdahl Yes, make total sense. I apologize for sounding imperative and indeed sarcasm was not the best choice ^^. Very busy as we all are and so I cut corners a bit too much I guess. Btw, congrats for your forked-yourself ;-)

Regarding digest size, 160 bits seems indeed a very good choice. It's certainly an upper bound if you take Git as reference SCM, since it is the digest size used in Git and it makes no sense to use a larger one. But if you use a strong hash function like Blake2 (or our beloved animal...), sticking to 128-bit hashes is still a vaiid option. In that case you can assume the function is ideal, and assuming you would have 10^9 users that would have at most 10^9 files, then the chance of one of these users seeing a collision is less than 1/10^12. With 160-bit hashes, this chance drops to 1/10^22.

@afbjorklund Adding some (secret) salt would indeed make the attack much more difficult!

Thanks for looking into K12. As you probably noticed, we have different optimized versions but these must be selected at build time (make Haswell/libk12.a or make SkylakeX/libk12.a). Ideally, we could provide a library that would detect at runtime the platform and run the best implementation. If this happens, I'll create a separate issue, to avoid polluting this one any further ^^.

@xeyownt wrote:

if I have write access to that repository, I could push a commit that would update a source file that would contain some trojan code, and wait the CI to start building this new commit. When done, the ccache would contain the trojan code in its cache. Then I push another commit, updating the very same file, and such that this new version of the file collides with the previous version when being hashed by ccache. The CI would then produce a binary containing my trojan code although this code disappeared from the sources. If history rewrite is allowed, this new commit could replace the previous commit, hence removing any traces from the repository itself. Depending on the CI setup, injection could even occur through a pull request (so even without write access to the repository itself).

Thanks for the example attack scenario. I certainly don't have knowledge about all differents CI setups out there, but in my mind it's very common for CI builds to use build scripts (e.g. a Makefile) that lie next to the source code itself. And if so there's an easier way to put trojan code into the cache: just calculate the hash for the file you want to replace and (in some obfuscated way) change the build rules to copy your wanted data directly to the known cache file. This works since ccache just writes to the local file system. To make ccache's hash algorithm the weakest link in the chain I think that at least one of the following must be true:

1. The CI build doesn't execute any build scripts in the repository to which the user has write access (or pull request rights), or
2. The build enviroment used for the CI build has some kind of audit hooks which check that writing to files in the ccache directory can only be made by a known-good ccache binary, or
3. It's considered to be easier to create a colliding unsuspicious source code file than an unsuspicious change to a build script.

Well, maybe the third one has some merit, but it feels unlikely to me. 🙂 Regardless, it of course wouldn't hurt if ccache's hash would be cryptographically stronger.

I'm personally OK with the speed of BLAKE2b, but on the other hand it would be kind of nice to be able to say that we haven't slowed down hashing in ccache 4. BLAKE2b is ≈35% slower than MD4 on my system. The generic K12 implementation from XKCP/K12 that @afbjorklund tried out in 398d9f3 (thanks, Anders!) seems to be ≈65% slower than MD4 for me. So yes, for K12 to be of interest there needs to be runtime detection of microarchitecture and the library needs to be easy to find, configure and use.

As you probably noticed, we have different optimized versions but these must be selected at build time (make Haswell/libk12.a or make SkylakeX/libk12.a).

I can't find those targets, neither in XKCP/K12 nor in XKCP/XKCP. XKCP/K12 only has generic{32,64}/libk12.a targets, it seems. Where should I look?

Either you value speed, but then I doubt that BLAKE3 will bring you any benefit compared to better alternatives or even MD4.

@erijo's BLAKE3 PR is ≈48% faster than MD4 on my system. I would be very surprised if BLAKE3 turns out to be so bad that it doesn't provide MD4 levels of collision resistance. If it turns out to have stronger security properties then that's a nice bonus. And if something better (K12?) comes along we can just change to that; ccache doesn't have to be backward compatible for cache data.

Regarding digest size, 160 bits seems indeed a very good choice. [...]

Thanks, sounds like your reasoning is in line with mine here.

@jrosdahl wrote:

I can't find those targets, neither in XKCP/K12 nor in XKCP/XKCP. XKCP/K12 only has generic{32,64}/libk12.a targets, it seems. Where should I look?

Last week, I changed XKCP/K12 so that the right implementation (plain, SSE2, AVX2 or AVX512) is chosen at compile time when doing make generic64/*. If you make make generic64/K12Tests then bin/generic64/K12Tests -s, you should be able to see what are the selected implementations.

I am working on making this selection runtime.

@gvanas wrote:

I am working on making this selection runtime.

Nice!

I just pushed to XKCP/K12 a version that does the implementation selection at run-time. Sorry it took a long time, but it required more refactoring and cleanup than I expected.

I just pushed to XKCP/K12 a version that does the implementation selection at run-time. Sorry it took a long time, but it required more refactoring and cleanup than I expected.

Thanks.

I don't have bandwidth to try out and evaluate K12. Does anybody with time and possibility like to do it (work on a pull request and motivate why it would be better fit for ccache than BLAKE3)? Otherwise I'm inclined to just go with @erijo's #519 since it's a) already available and b) in all likelihood more than good enough for ccache's needs of collision resistance.

Note that #577 makes hash performance less critical by eliminating about 99% of the hashing when building a larger project. If we go that way, focus could be on which hash algorithm is preferred by other reasons than pure performance.