Is it better to maximize memory usage or number of passes with Argon2i 1.3?

Question

I wrote a small application that uses Argon2i for deriving symmetric keys for encryption of local files and secret Curve25519 keys. Argon2i v1.3 is susceptible to TMTO attacks if the number of passes is below 10, according to the most recent paper I could find: https://eprint.iacr.org/2016/759.pdf

Ideally, of course, I would increase both. However, I am trying to find parameters that maximize security on a variety of machines, some of which are limited by CPU much more so than by RAM, such as old laptops. Let's say I am aiming for a computation time of around 10 seconds. I can use much more RAM if the number of passes is 3, which is the minimum recommended for Argon2i. However, this appears to allow a TMTO attack that reduces that RAM usage according to the paper above. If I increase the number of passes to > 10, I must use much less RAM to achieve the same computation time, however, the TMTO attack above does not apply.

On fast CPUs, increasing the number of passes is not a big problem because I can still use a lot of RAM. On slow CPUs, it can be much more significant. As a practical example, I tried this on a T23 ThinkPad. The results are below.

Tcost=3 Mcost=128 MiB Parallelism=1 Computation time: 10 seconds

Tcost=11 Mcost=40 MiB Parallelism=1 Computation time: 10 seconds

Given the most recent TMTO attacks in the Alwen-Blocki paper above, does an attacker with a GPU gain more of an advantage attacking the first example or the second? What about an ASIC?

For reference, here's Argon2d with only 1 pass and a target of 10 seconds

Tcost=1 Mcost=448 MiB Parallelism=1 Computation time: 10 seconds

(I am strongly considering going to Argon2d)

Answer 1

As of October 2017, the resource I've found most useful for getting a quick, practical sense of how pick parameters for Argon2 is the (still draft) RFC, in particular section 9, which gives this guidance (in 9.2):

The best attacks on the 1-pass and 2-pass Argon2i is the low-storage attack described in [CBS16], which reduces the time-area product (using the peak memory value) by the factor of 5. The best attack on 3-pass and more Argon2i is [AB16] with reduction factor being a function of memory size and the number of passes. For 1 gibibyte of memory: 3 for 3 passes, 2.5 for 4 passes, 2 for 6 passes. The reduction factor grows by about 0.5 with every doubling the memory size. To completely prevent time-space tradeoffs from [AB16], the number of passes must exceed binary logarithm of memory minus 26.

Since $\log_2(128\ \mathrm{MiB}) = 27$, this actually suggests that you should be able to use $t = 3$, $m = 128\ \mathrm{MiB}$ as your first alternative proposes. (Yes, $27 - 26 = 1$, but you need at least three passes to defeat the [CBS16] attacks.)

It's also worth quoting section 9.3 in full:

9.3. Security for time-bounded defenders

A bottleneck in a system employing the password-hashing function is often the function latency rather than memory costs. A rational defender would then maximize the bruteforce costs for the attacker equipped with a list of hashes, salts, and timing information, for fixed computing time on the defender’s machine. The attack cost estimates from [AB16] imply that for Argon2i, 3 passes is almost optimal for the most of reasonable memory sizes, and that for Argon2d and Argon2id, 1 pass maximizes the attack costs for the constant defender time.

The draft RFC doesn't say which memory sizes they consider reasonable, but they do repeatedly use 1 GiB throughout the draft as a reference figure. For example the reduction factors given in the first quote are based on 1 GiB, and the quote notes that these increase with more memory—but you're proposing to use less memory than that.

---

Or, as your question proposes and comments concur, you might consider not using Argon2i. The draft RFC in fact recommends Argon2id over either 2i or 2d. Then you just need one pass, because the advantage of tradeoff attacks on 2d and 2id doesn't depend on the number of passes (section 9.2):

The best tradeoff attack on $t$-pass Argon2d is the ranking tradeoff attack, which reduces the time-area product by the factor of 1.33.

The best attack on Argon2id can be obtained by complementing the best attack on the 1-pass Argon2i with the best attack on a multi-pass Argon2d. Thus The best tradeoff attack on 1-pass Argon2id is the combined low-storage attack (for the first half of the memory) and the ranking attack (for the second half), which bring together the factor of about 2.1. The best tradeoff attack on t-pass Argon2id is the ranking tradeoff attack, which reduces the time-area product by the factor of 1.33.

So for 1 GiB memory size, you need six passes of Argon2i to reduce attacker advantage to a similar level as one-pass Argon2id (2 vs. 2.1), and both are still behind Argon2d (1.33). This speaks strongly in favor of Argon2id, and is presumably the reason the draft RFC recommends it.

Answer 2

You should use as much time as the user will tolerate, and as much memory as the user has available for the computation. That maximizes the cost to the attacker, subject to your constraints. The more resources available to the user, the harder it is to attack.

Answer 3

Generally speaking it would probably be better if you just move to Argon2id, which came into the whole IETF draft quite a while after the question but it goes with some protection against TMTO and side channels so you can use as much memory as you want with only one pass.

on the other hand if side channels are absolutely no problem you could also go for Argon2d instead which probably does have an even better protection against TMTO but instead has side channel problems, while argon2id tries to balance it nicely.