3
$\begingroup$

My understanding is that the memory bandwidth of CPUs and GPUs is roughly one order of magnitude difference4, 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 memory1, fitting inside the registers of a GPU's streaming processors) whereas bcrypt, scrypt, or Argon22 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 hardware6. 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.3

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

1

2

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.

3

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 ASIC5, 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.)


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

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

3 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.

4 "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."

5 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.

5 "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."

$\endgroup$
3
  • 1
    $\begingroup$ Not an answer, but once you have a certain number of parallel hardware threads, you saturate the memory bus. If you keep adding threads, performance improvements actually start to reverse. For GPUs, even if they have a lot of cores, many of the cores are locked together and have to share the same memory bus. A GPU with a thousand cores won't be able to run a thousand truly independent computations. $\endgroup$
    – forest
    May 18 '21 at 0:26
  • $\begingroup$ Also, what parameters are different between your two figures? They both have M=4, T=1. $\endgroup$
    – forest
    May 18 '21 at 0:39
  • $\begingroup$ @forest ah darn it, good point, one should have been labeled M=256 MiB (I think the first one). Will edit after work. $\endgroup$
    – Luc
    May 18 '21 at 7:26
2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ "to make the computations impossible to perform [without] sufficient memory" Maybe I'm in denial but... GPUs used for password cracking have more than 2 GiB (the CFRG-recommended hardness), not because people use MHFs (I wish they did) but because all the fast cards come with a ton of VRAM. Or one can just use a cloud GPU with 24+ GiB at <$1/h. You'd need an expensive and dedicated login server to beat merely opportunistic attackers, let alone a serious one. By this definition, it sounds like nobody in the world would realistically do memory-hard hashing yet that's what we say Argon2 does. $\endgroup$
    – Luc
    May 18 '21 at 8:25
  • 1
    $\begingroup$ @Luc Memory hardness is useful because it prevents massively-parallel attacks (or makes them significantly more expensive to pull off). With memory hardness, maybe only 10 cores in a 1000 core GPU will be processing data at any one time (the rest will be blocked waiting on memory access, or won't have enough memory dedicated to them to operate). Without memory hardness, all 1000 cores can independently run the hashes. So you don't have to use 2 GiB of memory to cripple a 2 GiB GPU. You just need to use enough memory that it exceeds 2 GiB divided by the number of cores. $\endgroup$
    – forest
    May 18 '21 at 22:57
  • 1
    $\begingroup$ @Luc So pretending memory contention doesn't exist for a moment, if you had 1000 cores and 2 GB (not GiB, just to make the math simpler) of GPU memory, then a GPU will be efficient against Argon2 up to 2 MB. If you up it to 4 MB, now only 500 cores can run concurrently. If you up it to 2 GB, you can literally only utilize one GPU core (at that point, a CPU is significantly faster than a GPU, as a CPU core is both run at a higher clock rate and has faster vectorized intsructions). If you exceed 2 GB, now you have to modify the hashing algorithm to perform an extremely inefficient TMTO attack. $\endgroup$
    – forest
    May 18 '21 at 23:01
  • 1
    $\begingroup$ @Luc The overall reason for this is that each independent compute unit (whether it's a CPU core, a GPU core, or an ASIC "core") needs 100% of the memory you set for Argon2. They won't benefit from sharing any memory. This makes it useful against GPUs, but really, really useful against ASICs. Whereas cracking SHA-1 is simple enough that an ASIC could have 100,000 compute units all running in parallel, Argon2 using 2 MiB would require each compute unit to have its own 2 MiB of fast memory, totaling 200 GiB. That much money could have been used for 10,000,000 more compute units if it was SHA-1! $\endgroup$
    – forest
    May 18 '21 at 23:08
  • 1
    $\begingroup$ @Luc Now, an n-core GPU is actually going to be less efficient than an idealized n-core processor due to the fact that, even if there is enough total memory to utilize each core, memory contention becomes a problem. But Argon2 is designed to work against even an ASIC where each "core" is given access to its own, independent high-speed memory bus connected to its own, independent memory (for example, by using high-speed TSVs, which can give cache-like bandwidth and latency with RAM-like capacity). So focusing on GPUs is a bit of a red herring. It's better to think about the price of ASICs. $\endgroup$
    – forest
    May 18 '21 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.