Why does the GPU get a comparatively bigger advantage to the CPU when using higher parallelism in Argon2id?

Question

My understanding is that the memory bandwidth of CPUs and GPUs is roughly one order of magnitude difference⁴, unlike cores which a GPU has many of and a CPU a handful. That is why PBKDF2-HMAC-SHA1 parallelizes very well (which needs 164 bytes of memory¹, fitting inside the registers of a GPU's streaming processors) whereas bcrypt, scrypt, or Argon2² don't necessarily—not without a relatively large amount of independently accessible RAM per core.

The purpose of the parallelization parameter of Argon2 seems to be to fill the memory faster, i.e. to make it faster when running on a CPU as compared to cracking hardware⁶. The most common cracking hardware continues to be GPUs, and they have gigabytes of RAM, just that this big chunk is shared between all cores and therefore you lose the big advantage you had with non-memory-hard algorithms.

I've been able to partially confirm this experimentally: the speedup for PBKDF2, i.e. the number of hashes you can do per second on a CPU vs. on a GPU, is much greater than for bcrypt, scrypt, or Argon2. However, the comparative speedup when setting a higher L (lanes) value in Argon2 actually gets worse for the CPU. Setting L=2 might halve the time compared to L=1 when all else is equal, but on a GPU it might quarter the time instead, giving your attacker an advantage.³

The following two graphs show the number of hashes per second for the GPU and CPU with different parameters.

The CPU speed increases until roughly the number of cores available. The 4 MiB (second) graph is a bit less accurate because it runs very fast.

The next graph shows the speedup factor achieved with different parameters.

The speedup you get on CPU from using more lanes allows you to use more memory without taking more time (thus not annoying users more but getting a should-be-stronger hash). This should protecting better against a potential ASIC⁵, but it seems to weaken the protection from GPUs which typical attackers would actually use in practice.

Why is that? Should the GPU not be running into the same memory bandwidth issue as your CPU is, at least as soon as the CPU saturates the available memory bandwidth (and I assume the GPU always does due to the plentiful cores)? (Of course, this assumes the memory requirements are beyond the caches local to the streaming processor or streaming multiprocessor.)

The results do not seem to match the theory and intended goals as I understood them. Must the implementations I used be flawed, do I understand the theory wrong, the intended effect or the use of the lanes, is this hardware an outlier, or something else?

---

The raw data is available in this content-containing link.

Implementations and hardware used:

• To run on the RX 5700 GPU: Ondrej Mosnáček's argon2-gpu-bench

  $ ./argon2-gpu-bench -m opencl -M $((16*1024)) -T 32 -L 4 -t id | grep -a Mean\ com | grep -a per
  // outputs a value with a unit like "3.91383 us"
  

• To run on the Ryzen 7 3700X CPU: the PHP function password_hash which uses libsodium under the hood if I am not mistaken.

  $ php -r '$t=microtime(true); password_hash("test", PASSWORD_ARGON2ID, ["memory_cost"=>1024*4, "time_cost"=>32, "threads"=>4]); print(microtime(true) - $t) . "\n";'
  // outputs the time taken in seconds
  

  I also tried doing multiple calls (the way argon2-gpu-bench does by default) but I think the function call overhead defeats any benefits because the results did not seem to be any different or significantly more stable.

It might be worth noting that the highest amount of memory tested with is 256 MiB and not multiple gigabytes as the CFRG recommends because with as little as 512 MiB:

$ ./argon2-gpu-bench -m opencl -M $((512*1024))
terminate called after throwing an instance of ‘cl::Error’
    what():  clCreateBuffer
Aborted

(And scrypt is no better, hashcat's implementation errored out at 16 MiB until last week and now 64 MiB is the maximum. The GPU reports having >4000 MB allocateable on both Windows and Linux. PHP has no issues computing Argon2 with e.g. 13 GiB.)

---

¹ Ondrej Mosnáček "Key derivation functions and their GPU implementations" https://is.muni.cz/th/409879/fi_b/

² Whenever I say just Argon2, I assume it goes for all variants, but Argon2id is the one I am specifically looking into.

³ This should also go for scrypt and its p (parallelism) parameter, but neither hashcat nor Python (using OpenSSL's implementation) seem to implement it. p=2 simply takes twice as long as p=1 and so on (linearly). There is a JavaScript implementation that claims to be able to do parallelism, but in Edge (i.e. Chromium) it doesn't work, in Firefox on Windows it only works for p>2 (namely p=1 is twice as fast as p=2, but p=4 is equally fast as p=2), and in Firefox on Linux it only works for p<4 (namely p=1 is as fast as p=2, but p=4 is twice as slow as p=2). Because Argon2 seems like the more modern option, I haven't investigated further. This includes the recent commits (late April 2021) that improve scrypt in hashcat.

⁴ "The CUDA implementation can reach about 40-60 GiB/s [...] on an NVIDIA Tesla K20X. For comparison, a fast Intel Xeon processor can only reach about 10 GiB/s."

⁵ The Argon2 paper writes: "We aim to maximize the cost of password cracking on ASICs. There can be different approaches to measure this cost, but we turn to one of the most popular – the time-area product [4, 16]. [...] The 50-nm DRAM implementation [10] takes 550 mm² per GByte; The Blake2b implementation in the 65-nm process should take about 0.1 mm²". I conclude from this that using more memory (M) increases the manufacturing cost of an ASIC more than more passes over said memory (T) do while the time it takes can be kept unchanged.

⁵ "The parallelism was probably one reason why Argon2 won the Password Hashing Competition. The use of processor cores allows for greater memory hardness (security) without increasing the execution time accordingly." and "Parallelism is actually used to fill memory more quickly. The more hardware threads you use, the faster the memory can be filled and operated on."

Answer 1

Must the implementations I used be flawed, do I understand the theory wrong, the intended effect or the use of the lanes, is this hardware an outlier, or something else?

You misunderstood the intended effect of the use of lanes.

The reason memory-hard KDFs use a large amount of memory is not to slow down computations by making memory bus bandwidth a bottleneck, but to make the computations impossible to perform on hardware that doesn't have sufficient memory. Once you exceed the amount of memory that the cracking hardware has (whether system RAM, VRAM, or memory attached to an ASIC), it becomes necessary for the attacker to perform a TMTO (Time-Memory Tradeoff) attack. This involves running a modified version of the algorithm which requires less memory, but involves significantly more computations. Since the amount of memory you are using does not appear to have exceeded either your CPU or GPU's memory capacity, you aren't running into this limit.

A large amount of memory does not cause an ASIC to run slower intrinsically, but since high-speed memory for ASICs is very expensive, it forces an attacker to either increase the amount of memory, or to run a horribly inefficient TMTO attack. All else equal, if a CPU, a GPU, and an ASIC can fit all the state of Argon2 in memory, then ASIC will be fasted, followed by GPU, followed by CPU.

If you want to see the effect of lanes, increase them until it physically will not run on your GPU. Now you'll see that you'll have to modify the algorithm to require less memory, but in doing so, the hash rate will go way, way, way down. One of the parameters given to Argon2, the number of passes, affects just how much slower this modified algorithm will need to be.