24
$\begingroup$

Does the recent Balloon hashing paper and the included attack on Argon2 effectively negate the result of the Password Hashing Competition? On one hand it seems that only a constant-factor improvement has been achieved, which is rarely critical in cryptography. On the other hand, the entire point of password hashing is to increase the constant factors of brute-force search.

I'm building a new authentication service at the time of this writing; should one use Argon2 or Balloon hashing in new development given this result? (I love the simplicity of Balloon hashing and it comes with a proof, but it hasn't been "selected as a standard").

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I suggest that answers to this question might also want to address Alwen & Blocki's recent papers: "Efficiently Computing Data-Independent Memory-Hard Functions" and "Towards Practical Attacks on Argon2i and Balloon Hashing". $\endgroup$
    – Luis Casillas
    Commented Sep 15, 2016 at 8:10
  • 2
    $\begingroup$ I would go with bcrypt or scrypt instead of those new algorithms for now. $\endgroup$
    – CodesInChaos
    Commented Sep 15, 2016 at 10:42
  • 2
    $\begingroup$ IIRC this was discussed on the PHC mailing list a while ago and they said that you can't get really good time-memory trade-off penalties with the data-independent Argon2i. If you can (and don't mind theoretical cache-timing attacks) use Argon2d which is safe against these attacks (because it's data-dependent). $\endgroup$
    – SEJPM
    Commented Sep 15, 2016 at 12:10

2 Answers 2

Reset to default
19
$\begingroup$

Does the recent Balloon hashing paper and the included attack on Argon2 effectively negate the result of the Password Hashing Competition?

No.
The main result of the PHC was not a single new fancy password hashing function (i.e. Argon2), but a massive advancement in the research of password hashing. We understand password hashing and how to do it much better after the competition than we did before it. That's the most important and main result.
Examples of this include new security reductions for time-memory trade-offs (Catena) and completely new ideas like workload delegation (Makwa).

Now for the actual attack. It appears that the attack reduces the time-memory product of one- and two-pass Argon2i (as of v1.2.1) by a factor of 5 (or less). While this is certainly not good, it doesn't completely destroy Argon2i either. So you can still use it, but have to keep in mind that there may be trade-offs against it.

Now for the mitigations:

  • After this very paper was released, there was an update to the Argon2 specification, adding the paragraph 5.2 to the security analysis, they documented the TL;DR of the attack and how they mitigated it in version 1.3. With Argon2 v1.3 you only need to avoid single-pass Argon2i, with two-passes and more the attack shouldn't apply anymore.
  • The idea of Argon2i originally was to allow for data-independent memory-hard password hashing, especially to avoid side-channel attacks like cache-timing attacks. However, if your threat model doesn't include attackers sitting on your machine while you're doing the password hashing, you should use Argon2d anyways, which uses data-dependent operations (similar to scrypt) and is not affected by these recent attacks.
  • The last mitigation of course is to use other password hashing functions. Either the special recognitions from PHC (i.e. Lyra2, Catena, yescrypt and Makwa) or the good old ones like scrypt and bcrypt. Of course you should note that while the old ones have probably seen more scrutiny, they have their own respective weaknesses (e.g. bcrypt doesn't help much against FPGAs and scrypt also has some weaknesses and doesn't protect against side-channel attacks too well either).

In the comments to the question were also two other papers mentioned. "Efficiently Computing Data-Independent Memory-Hard Functions" by Alwen and Blocki which provides asymptotic bounds on the time-memory-product for a variety of password hashing constructs (including Argon2i, Catena and Balloon Hashing).
The other paper mentioned, "Towards Practical Attacks on Argon2i and Balloon Hashing" by Alwen and Blocki improves on the result of the previous paper, focusing on the old and the new Argon2i version and on Balloon Hashing, again reporting successful (conretely instantiated) attacks on both schemes and noting that 10 passes would be required to regain (full) security for Argon2i.

TL;DR: Use Argon2d if you don't mind with side-channel attacks and use high-pass-counted (e.g. 10 passes) Argon2i if you do mind.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Won't 10-pass Argon2i be way slower? $\endgroup$
    – pg1989
    Commented Sep 15, 2016 at 16:45
  • $\begingroup$ Unless I misunderstand the paper, the constant factor speed up against reduced-memory (approx n/3) Argon 2i is a factor of 16000+ better than the security claim in the PHC version of Argon 2i using recommended parameters. That's not trivial.. Also, cache timing attacks do matter: nearly all apps including this one can or will be deployed on shared cloud infrastructure. Cache timing attacks have even been demonstrated as successful over high latency networks. $\endgroup$
    – rmalayter
    Commented Sep 15, 2016 at 18:44
  • $\begingroup$ @pg1989 the number of passes is the linear workload adjusting parameter and as such, with the same set of other parameters, 10-pass Argon2i should take 10x the time of single-pass Argon2i. Of course you could adjust the other parameters accordingly. $\endgroup$
    – SEJPM
    Commented Sep 15, 2016 at 19:20
  • $\begingroup$ @rmalayter To the best of my (and the bear's, yes I asked him) knowledge, nobody ever observed a cache timing attack in the wild, so this is a relatively minor threat to worry about. At most there were some fancy lab demonstrations. Also, to which paper are you referring to? The original (kinda fixed) balloon one or the last one? $\endgroup$
    – SEJPM
    Commented Sep 15, 2016 at 19:30
  • 4
    $\begingroup$ @rmalayter Additional thought about why cache timing attacks aren't that bad: Consider the threat scenario: An attacker has your database of pw hashes (which he needs to verify his guesses) and is in a position to measure cache-timings on your server (e.g. sitting on the same physical server) and he's not able to just plainly fetch the passwords before they're feeded into the hash function. That doesn't sound like a likely scenario (more like a conspiracy theory) and thus using something like Argon2d brings you much more than using the worse data-independent schemes. (credit: codesinchaos) $\endgroup$
    – SEJPM
    Commented Sep 15, 2016 at 20:09
1
$\begingroup$

You should probably use provably secure schemes, and BH is such a scheme. Not only they provide a proof of memory complexity, but also show attacks on Argon that achieve a 4x speedup. Winning a competition shouldn't on its own make Argon a standard, especially given that Balloon appeared after the PHC.

Improve this answer
$\endgroup$

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.