6
$\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.

$\endgroup$

1 Answer 1

4
$\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.

$\endgroup$
4
  • $\begingroup$ So there's not a case for switching to/recommending cache-hard algorithms like bcrypt for short run times? $\endgroup$ Jun 9, 2023 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, 2023 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$ Jun 9, 2023 at 19:33
  • 3
    $\begingroup$ This means that there's not an advantage to cache vs. memory - This is wildly over-optimistic. Apple M1 CPUs still have big fast L1i/L1d caches, and shared L2. Putting the DRAM inside the same package as the CPU allows a wider bus for better bandwidth, but only a bit lower latency. anandtech.com/show/16252/mac-mini-apple-m1-tested shows memory latency at about 96 ns, which is nothing amazing. reddit.com/r/hardware/comments/k5zjwy/m1_memory_and_performance . DRAM bandwidth is about 242 GB/s on M1 Max (which is high), but L2 B/W is about 800 GB/s and better latency $\endgroup$ Feb 2 at 13:15

Your Answer

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

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