Since GPUs have gigabytes of memory, does Argon2id need to use gigabytes of memory as well in order?



  • 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).


  • 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:



Suggested Topics

  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2