2
Mathematical Proof that memory hardness is not reversible? (infosec.pub)
submitted 1 month ago by to c/crypto@infosec.pub
3 comments fedilink hide all child comments
 

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?

all 3 comments

sorted by: hot top controversial new old
[–] [S] 1 point 1 month ago (1 child)

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

  • permalink
  • fedilink
  • source
  • hideshow 1 child comment
    •
  • [–] 1 point 2 weeks ago

    PBKDF2 is almost entirely "linear", you can build an efficient pipeline which runs entirely on-chip without needing to reach out to external memory (a very large RAM requirement needs many more state holding gates than the FPGA has available, so it needs to start using external memory). The FPGA can essentially compose a digital conveyor belt for PBKDF2. This isn't as effective for Argon2id which forces it to stop and start and stop and start, etc.

  • permalink
  • fedilink
  • source
  • parent
    • [–] 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.

  • permalink
  • fedilink
  • source
    •