4

The common advice of benchmarking a password hashing algorithm and choosing the slowest acceptable cost factor doesn't work for algorithms with more than one parameter: adding a lot of iterations at the expense of memory hardness makes the benchmark time go up, but if the attacker can still grab off-the-shelf hardware (like a regular gaming graphics card) then I might as well have used pbkdf2 instead of Argon2id. There must be some minimum amount of memory that makes Argon2id safer than a well-configured algorithm from the 90s, otherwise we could have saved ourselves the effort of developing it.

I would run benchmarks and just see for myself at what point hashing isn't faster anymore on a GPU than on a CPU, but Hashcat lacks Argon2 support altogether. (Though any software I choose isn't necessarily going to be the fastest possible implementation to give me a correct answer anyway.)

Even my old graphics card from 2008 had 1GB of video memory and 2020 cards seem to commonly have 4-8GB. Nevertheless, the default Argon2id setting in PHP is to use 64MiB of memory.

If you set the parallelism of Argon2id to your number of CPU cores (say, 4) and use this default memory limit, is either of the following (roughly) true?

  • A GPU with 8192MB of memory can still use 8192/64 = 128 of its cores, getting a 32× speed boost compared to your CPU. The slowdown on GPUs due to increased memory requirements is a linear scale. The only way to thwart GPU cracking effectively, is to make Argon2id use more RAM than a high-end GPU has when divided by the number of parallelism you configure in Argon2id (i.e. in this example with 4 cores, Argon2id needs to be set to use 8192/4 = 2048MB).

or

  • This amount, 64MiB, already makes a common consumer GPU completely ineffective for cracking because it is simply too big to efficiently use from a simple GPU core (because if the core has to access the card's main memory then it's not worth it, or something).
3
  • 1
    GPUs work to speed certain tasks because they do the same thing to different data in parallel. Iterated key derivation systems (bcrypt, Argon2, PBKDF2, etc.) require the data be worked on in serial. A GPU might be able to speed up cracking several passwords at a time, but they won't speed of cracking a single password. Using a new password for every site, generated from a random source, with at least 12 characters means that they won't brute force your password for a few decades, no matter what off-the-shelf hardware they buy. – Ghedipunk Apr 5 at 3:45
  • 1
    @Ghedipunk "[A GPU] won't speed of cracking a single password" From first-hand experience, that's not true. Have you ever tried cracking a password? Each of those GPU cores can do a section of the search space, so also for a single password, the parallelism speeds it up massively compared to a CPU with only a handful of (albeit faster) cores. – Luc Apr 5 at 12:02
  • @Ghedipunk: When an attacker is brute-forcing a single password, many different passwords are tried. Usage of GPUs can speed up brute-forcing, because for many operations GPUs are more efficient than CPUs. – mentallurg Apr 5 at 16:50
2

There are different ways to make brute-forcing of Argon2id harder. Two of them are following:

  • Make passwords longer, and of course make passwords randomly generated, not generated by humans
  • Increase work factor, i.e. use more iterations

It makes sense to consider memory factor only then, when increasing computing power in 1-2 orders of magnitude can really lead to successful brute-forcing.

Let's consider 2 cases.

1. Passwords of 20 chars from 62-char set, password hashing takes 1s on a single core of 8-cores CPU

How many passwords need to be tried? Supposing that a half of all possible passwords is sufficient, we get: 62^20/2 ~= 10^35.

How many passwords can test such a CPU per year? 8 cores * 60 seconds/minute * 60 minutes/hour * 24 hours/day * 365 days/year ~= 10^8.

Thus 10^35 / 10^8 = 10^27 CPU-years are needed.

Suppose, some GPU is 1 000 times faster than such CPU. Suppose some organization can afford 1 000 000 000 such GPUs (only a few countries in the World can afford it). Then still it will take 10^27 / (1 000 * 1 000 000 000) = 10^15 years to brute-force such password.

What will we gain from using bigger memory factor and reducing the effective GPU power? Is the duration of 10^15 years not huge enough? In this case it makes no sense to spend time analyzing what memory factor how much can slow down GPUs. Even the small memory factors like 10K will be sufficient, because duration of 10^15 years makes brute-forcing impossible.

2. Passwords of 10 chars from 62-char set, password hashing takes 0.000001s on a single core of 8-cores CPU, or 10^6 per second

How many passwords need to be tried? Supposing that a half of all possible passwords is sufficient, we get: 62^10/2 ~= 10^17.

How many passwords can test such a CPU per year? 10^6 * 8 cores * 60 seconds/minute * 60 minutes/hour * 24 hours/day * 365 days/year ~= 10^14.

Thus 10^17 / 10^14 = 10^3 = 1000 CPU-years are needed.

If some GPU is 1 000 time faster than such CPU (which is way too optimistic), then such single GPU can brute-force the password within 1 year. 10 such GPUs can brute-force the password within 36,5 days. Many can hackers can afford even 100 GPUs. Then password will be brute-forced within 0,365 days or within 9 hours.

In such case restricting the number of cores used for brute-forcing can really slow brute-forcing down and for some attackers this can be prohibiting (too expensive), or time needed for brute-forcing can become much longer, so that when the password is brute-forced and information decrypted, this information is not secret any more and is freely available.

TLDR

Big memory factor can be not necessary in case password entropy and work factor are relatively big. A 20-char password and hash generation of 1s makes brute-forcing impossible. It is up to you to calculate and decide what smaller values are acceptable to you.

Big memory factor makes sense only in cases when the risk of brute-forcing is high and slowing the brute-forcing down in 1-3 orders of magnitude reduces the brute-forcing risk to the acceptable level.

To your question

does Argon2id need to use gigabytes of memory as well in order to effectively thwart GPU cracking?

If you use relatively long passwords, e.g. 20-char passwords, and if work factor in Argon2id is big enough, e.g. hashing of a single password takes 1s, then no, you don't need to use Gigabytes of memory per password, any small memory factor will be sufficient.

If you use relatively short passwords, e.g. 8-10 characters length, and if work factor is relatively small, e.g. hashing of single password takes 0.000001s, then yes, using of Gigabytes of memory per password can slow brute-forcing down. For instance, some Nvidia GPUs have ~6000 cores with 12 GB RAM. If you use e.g. 64MB per password, it will effectively reduce the number cores to 192 instead of ~6000, thus the brute-forcing will be ~30 times slower. After you decided how much memory you want to use, check that the number of iterations is not too small, see the comment of brynk.

Why use Argon2id at all?

Then why use Argon2id at all, why not PBKDF2? Because it has for instance a better side-channel resistance. See more details here:

4
  • This question is about limiting the attacker; specifically, how to ensure I exceed effective memory limits of typical cracking hardware (i.e. graphics cards). The answer only speaks of the defense side, recommending to set parameters as high as possible for my situation. Choosing the best possible parameters indeed goes without saying, but that doesn't tell me whether setting it to your example of 16MB "effectively thwart[s] GPU cracking". – Luc Apr 5 at 12:30
  • @Luc: I have updated the answer. – mentallurg Apr 5 at 19:20
  • 1
    I will also add that the Argon2id spec informs the number of iterations in relation to the amount of RAM. There is a tangentially related discussion about hardness parameters, specifically in this comment. – brynk Apr 5 at 20:25
  • @brynk: Thank you, it is a good point. I have updated the answer. – mentallurg Apr 5 at 21:34

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.