The algorithm Argon2i-B of Biryukov, Dinu and Khovratovich is currently
being considered by the IRTF (Internet Research Task Force) as a new
de-facto standard for password hashing. An older version (Argon2i-A)
of the same algorithm was chosen as the winner of the recent Password
Hashing Competition. An important competitor to Argon2i-B is the
recently introduced Balloon Hashing (BH) algorithm of Corrigan-Gibs,
Boneh and Schechter.
A key security desiderata for any such algorithm is that evaluating
it (even using a custom device) requires a large amount of memory
amortized across multiple instances. Alwen and Blocki (CRYPTO 2016)
introduced a class of theoretical attacks against Argon2i-A and BH.
While these attacks yield large asymptotic reductions in the amount of
memory, it was not, a priori, clear if (1) they can be extended to the
newer Argon2i-B, (2) the attacks are effective on any algorithm for
practical parameter ranges (e.g., 1GB of memory) and (3) if they can be
effectively instantiated against any algorithm under realistic hardware
In this work we answer all three of these questions to the affirmative
for all three algorithms. It is also the first work to analyze the
security of Argon2i-B. In more detail, we extend the theoretical attacks
of Alwen and Blocki (CRYPTO 2016) to the recent Argon2i-B proposal
demonstrating severe asymptotic deficiencies in its security. Next we
introduce several novel heuristics for improving the attack's concrete
memory efficiency even when on-chip memory bandwidth is bounded. We
then simulate our attacks on randomly sampled Argon2i-A, Argon2i-B and
BH instances and measure the resulting memory consumption for various
practical parameter ranges and for a variety of upperbounds on the
amount of parallelism available to the attacker. Finally we describe,
implement and test a new heuristic for applying the Alwen-Blocki attack
to functions employing a technique developed by Corrigan-Gibs et al. for
improving concrete security of memory-hard functions.
We analyze the collected data and show the effects various parameters
have on the memory consumption of the attack. In particular, we can draw
several interesting conclusions about the level of security provided by
- For the Alwen-Blocki attack to fail against practical memory
parameters, Argon2i-B must be instantiated with more than 10 passes
on memory. The current IRTF proposal calls even just 6 passes as the
recommended "paranoid" setting.
- More generally, the parameter selection process in the proposal
is flawed in that it tends towards producing parameters for which the
attack is successful (even under realistic constraints on parallelism).
- The technique of Corrigan-Gibs for improving security can also
be overcome by the Alwen-Blocki attack under realistic hardware
- On a positive note, both the asymptotic and concrete security of
Argon2i-B seem to improve on that of Argon2i-A.