Memory-hard password hash in practice?

Question

Dan Boneh, Henry Corrigan-Gibbs, and Stuart Schechter have proposed Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks (in proceedings of AsiaCrypt 2016). Taking the abstract at face value, it is a blow (pun intended) to Argon2, the winner of the (first) password hashing competition, in particular as Balloon hashing boasts

the first practical cryptographic hash function that:
(i) has proven memory-hardness properties in the random-oracle model,
(ii) uses a password-independent access pattern, and
(iii) meets or exceeds the performance of the best heuristically secure password-hashing algorithms.

and further claims

a practical attack against Argon2i that successfully evaluates the function with less space than was previously claimed possible

---

Is Balloon hashing, or any of the contenders with properties (i) and (ii), ready for practical use (possibly including some Argon2 variant)? With what parametrization (underlying hash, etc..)?

Can we roughly guestimate the security improvement (at equal computing effort, for some definition of that) compared to competitors like the still very ubiquitous PBKDF2-HMAC-SHAx? Bcrypt, which has some traction in servers? Scrypt, which better leverages multiple CPUs and ample memory, but does not exhibit property (ii) and is seldom used?

^{Note: After Luis Casillas's comment, I have expanded the scope of this question beyond Balloon Hashing.}

Answer 1

Update 20/07/24: I'm working on an Internet-Draft for a new algorithm called Balloon Key Derivation Function (BKDF), which is a redesign of Balloon to address its limitations and make it a usable algorithm. I'm currently collaborating with Henry Corrigan-Gibbs, one of the Balloon authors, and Steve Thomas, one of the Password Hashing Competition (PHC) judges.

Any feedback is welcome. It won't be published to the IETF Datatracker until the design has been finalised and everything has been fully proofread. I will try to contact some more cryptographers/cryptographic engineers as time goes on.

---

I'm surprised this has been left unanswered. I'll give it a go.

Is Balloon hashing ready for practical use?

As of 2022, I would strongly argue no.

There's no standard, no standard is planned, there are no official test vectors, there's no real guidance on parameters, and the few implementations have generally not been interoperable. This is not surprising given there are apparently differences between the paper and the prototype implementation.

To make matters worse, the prototype implementation is now unmaintained, and notice how I say prototype instead of reference implementation. There's literally a warning in the README saying to not use the code in production.

The main third-party implementation is by Rust Crypto, who have a solid rep and have tried to make things more interoperable. However, I don't consider this enough for the algorithm to be worth recommending.

Even if the problems above were fixed, I doubt it's received as much analysis as the algorithms in the PHC. Furthermore, it's less resistant to the attacks against Argon2i, and Argon2i is more depth-robust.

It's rather baffling that NIST mentions it given these facts. It feels like the authors became busy with other work or simply gave up because they thought it wouldn't get much attention given the existence of Argon2. It's a shame because the simplicity makes it a great alternative to PBKDF2.

Are any of the contenders with properties (i) and (ii) ready for practical use (possibly including some Argon2 variant)?

In contrast to Balloon, Argon2 has an RFC, went through the PHC, has received more and more use, and is available in more mainstream libraries. It's ready for practical use. The real problem is which mode to use.

Because of attacks on Argon2i and some side-channel attack protection (more than Argon2d), Argon2id is the recommended mode. It's meant be supported by every implementation of the RFC, whereas support for Argon2d and Argon2i is optional. Argon2i is now barely mentioned in the RFC.

The trouble is, protection against side channels (provided by data-independent functions like Argon2i) results in a less memory-hard construction. So, you either lose some memory hardness or use a hybrid scheme (data-independent + data-dependent like Argon2id) to get a bit of side-channel protection as well as greater bruteforce protection. The latter doesn't fully satisfy a threat model involving protection from side-channel attacks though, so what's the threat model?

For example, Argon2id uses Argon2i for the first half of the first pass and then Argon2d from then on, making it worse than Argon2i against side-channel attacks. A side-channel attack against Argon2id reduces security to using Argon2i with m=m/2, t=1, and p=p. However, Argon2i is meant to be used with at least 3 iterations due to attacks.

Can we roughly guestimate the security improvement (at equal computing effort, for some definition of that) compared to competitors like the still very ubiquitous PBKDF2-HMAC-SHAx?

The scrypt paper contains a nice table for the estimated cost of hardware to crack a password in 1 year. It includes DES CRYPT, MD5, MD5 CRYPT, PBKDF2, bcrypt, and scrypt. The difference between PBKDF2 and scrypt is night and day, although this is now out of date.

Then the Argon2 paper discusses the time-area product, which is one, albeit less intuitive, approach of measuring the cost of password cracking.

Bcrypt, which has some traction in servers? Scrypt, which better leverages multiple CPUs and ample memory, but does not exhibit property (ii) and is seldom used?

It was actually claimed that Argon2 is worse than bcrypt with certain amounts of delay/low memory sizes. I'm not entirely sure whether this is accurate, but Argon2 should be used with a sizeable amount of memory and multiple iterations anyway.

Lastly, I would agree with @otus that scrypt has been used quite a lot. I don't think there's much point using it now Argon2 has come along though.