24
$\begingroup$

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.

$\endgroup$
8
  • 3
    $\begingroup$ @Elias: Scrypt is nice, but does not exhibit property (ii), and that's a serious concern with respect to cache-related side channel leakage (e.g. timing). $\endgroup$
    – fgrieu
    Jun 30, 2017 at 11:57
  • 1
    $\begingroup$ Please note that Argon2i has been tweaked in response to the Balloon hashing paper (now version 1.3, previously 1.2), however I do not know (yet) how it now compares to Balloon Hash. $\endgroup$
    – SEJPM
    Jun 30, 2017 at 19:02
  • 4
    $\begingroup$ There has been a lot of activity on the iMHF front, not just from the balloon hashing paper, but also from papers by Alwen and Blocki with attacks on Argon2i and balloon hashing. There's been much discussion and substantial revisions to the Argon2 RFC to account for this. The latest draft RFC mainlines Argon2id, a hybrid of the original Argon2i and Argon2d, as the primary variant of the algorithm, because of resistance to the A&B attacks. An optimal answer to this question, in my view, would recapitulate this in detail. $\endgroup$ Jun 30, 2017 at 21:22
  • 2
    $\begingroup$ These two papers are relevant. One shows that Argon2i is "better" than Balloon hashing, the other one presents an optimal graph that is better, in terms of cumulative cost, than all of the alternatives. $\endgroup$ Jul 1, 2017 at 15:29
  • 2
    $\begingroup$ Not sure I agree scrypt is seldom used. For one its use in cryptocurrencies means it's likely been run orders of magnitude more, in terms or computing time, than alternatives. Even in its intended use as a password hash it is used in various "brain wallet" systems. $\endgroup$
    – otus
    Dec 5, 2017 at 16:37

1 Answer 1

1
$\begingroup$

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 password hashing competition (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.

$\endgroup$

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.