5
$\begingroup$

bscrypt is a cache-hard password hashing algorithm/KDF from Steve Thomas (aka Sc00bz/TobTu), who was on the Password Hashing Competition (PHC) panel. He argues it is better than the alternative algorithms on his minimum password hashing parameters page. There are two talks for further information, but it's not thoroughly documented currently.

Pufferfish2 is another cache-hard, but not memory-hard, password hashing algorithm by Jeremi Gosney (aka epixoip), another member of the PHC panel. It's designed to be an improvement on bcrypt and is based on Pufferfish, a finalist in the PHC.

The idea is that cache-hard algorithms are better than memory-hard algorithms at shorter run times since memory bandwidth/small CPU caches are more of a bottleneck than the amount of memory required.

Searching 'cache-hard' on the Cryptology ePrint Archive comes up with no results compared to 36 results at the time of writing for 'memory-hard', suggesting this has not been academically studied. However, this seems to be supported by claims that bcrypt, a 'minimally' cache-hard algorithm, is better than Argon2 for short run times, which is now on the Wikipedia page. There was also apparently an Argon2 variant called Argon2ds that's cache-hard, although I have no idea where information about this variant is unless it's hidden in the PHC mailing list archive.

This information leads to several interesting questions worthy of discussion:

  1. What are the pros and cons of cache-hardness vs memory-hardness?
  2. Should we recommend algorithms like bcrypt/hmac-bcrypt (and eventually newer algorithms like bscrypt after further analysis) for password hashing instead of memory-hard algorithms like Argon2?
  3. Should cache-hard algorithms be used for key derivation or only password hashing?
  4. If cache-hard algorithms are so good, why were they not more of a thing/more successful in the PHC and why are they still not being researched? The PHC final report is quite vague.

Thanks to @fgrieu for inspiring this question; sorry it took so long to ask.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

You have a lot to unpack in that question, but basically memory-hard is the way to go.

From a hardware point of view, there's a few things here that you need to consider. I'm going to assume that you have commodity hardware. In the x86 model, you generally have cache and memory so that you do not have to wait for the memory, which is slower than the cache. What Apple did with their silicon was have the memory on the die next to the CPU, and this is what people who make custom hardware have done forever in the non-commodity hardware space. If you have some of these custom CPUs, the cache and the memory run at the same speed. This means that there's not an advantage to cache vs. memory. This is also why cache/memory seemed to disappear as a discussion (my opinion) is because the through-die vias that you need for this architecture became, or are becoming, a commodity item; however, very few people use them (Apple via TSMC, and POWER via GF). I expect that we'll see more of these used in 2nm via buried power rails and such, so that we'll have more ICs with memory on the same die via bonding or chiplet as a CPU.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So there's not a case for switching to/recommending cache-hard algorithms like bcrypt for short run times? $\endgroup$
    – samuel-lucas6
    Jun 9 at 12:38
  • 1
    $\begingroup$ @samuel-lucas6 in my opinion, no, but I'm a hardware designer and not a proper cryptographer. $\endgroup$
    – b degnan
    Jun 9 at 16:59
  • $\begingroup$ Regardless, I appreciate your input. Argon2 certainly has less pitfalls than bcrypt, and it doesn't seem like these new cache-hard schemes are going anywhere anytime soon unless they get implemented in a library like libsodium. $\endgroup$
    – samuel-lucas6
    Jun 9 at 19:33
2
$\begingroup$

What are the pros and cons of cache-hardness vs memory-hardness?

cache-hard algorithms' authors argue that memory-hard algorithm isn't suitable for password hashing, because the password hashing progress should take < 500ms, while "argon2 is weaker than bcrypt for run time < 1000ms". They are better for KDFs, which you may wait more than 1000ms when decrypting luks2-encrypted partition. cache-hard algos are more resistance to GPU and custom hardware than memory hard, while taking little time. Yeah with run time > 1000ms (acceptable time) when you open luks2-encrypted disk "argon2 is better than bcrypt".

Should we recommend algorithms like bcrypt/hmac-bcrypt (and eventually newer algorithms like bscrypt after further analysis) for password hashing instead of memory-hard algorithms like Argon2?

maybe. algorithm like argon2 are better for KDF, not password hashing.

Should cache-hard algorithms be used for key derivation or only password hashing?

cache-hard algorithms are designed for password hashing, which have a good resistance against GPU/custom hardware while have run time < 500ms.

I cannot speak the 4th question.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Hiya & welcome :-) It might be useful to our gentle readers if you could explain the significance of your timing thresholds. They seem 'out of the blue'. I've built my own KDF that runs in (Java) approximately 2000mS/256MB. How would that fit in? $\endgroup$
    – Paul Uszak
    Sep 10 at 20:55
  • $\begingroup$ Yes, I was aware of these details, and those figures are linked in my question from memory. The thing is the authors of cache-hard algorithms are the main people recommending them, and the concept doesn't seem to be being discussed by many other people, which is a bit odd. I suppose password hashing in general is an area of cryptography that's received less study despite blatant limitations with algorithms like bcrypt and PBKDF2. $\endgroup$
    – samuel-lucas6
    Sep 11 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.