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.

  • 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 '17 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 '17 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$ – Luis Casillas Jun 30 '17 at 21:22
  • 1
    $\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$ – Samuel Neves Jul 1 '17 at 15:29
  • 1
    $\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 '17 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.