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?
huh, i think i know understand it better. it works that hashing steps builds on multiple hashing steps together from previous rounds, which increase storage consumption. but i still do not understand, why less storage consumption makes pbkdf2 for example faster to crack in fpga
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.