Hello, i have a question. I understand that government institutions probably do not want to certify memoryhard KDFs like argon* (because government agencies cannot bruteforce for clandestine or forensic purporses) but sometimes i wonder, if there is actual mathematical proof, that memory hardness like done for argon, scrypt and co. cannot be reverse into more bruteforce with a timetradeoff.

Can anyone explain this to me, because i feel like i do not understand something?

you are viewing a single comment's thread
view the rest of the comments
[–] 1 point 2 weeks ago

Look up Kolgomorov time bounded complexity. The absolute minimum memory requirement is defined by the compression limit which is bounded by the total entropy in the algorithm. Entropy is defined by the input values (the password, random salt).

But computationally limited attackers often can't wait long enough to solve the compressed variant because CPU time explodes, so they can not reach high degrees of compression. Using a certain amount of minimum RAM is effectively optimal for resource usage if you can't break the underlying cryptographic function in password hashing algorithms.

We don't have an absolute proof what the minimum is, but Argon2id is very solid and there's little reason to believe there's some major hidden shortcut.

  • source