Does the recent Balloon hashing paper and the included attack on
Argon2 effectively negate the result of the Password Hashing
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.