What are, quantitatively, the pros and cons of fixed versus variable memory access pattern in Password-Based Hashing, Entropy-Stretching Key Derivation functions, and Proof-of-Work applications?

Modern PBH, ESKDF, and PoW techniques all leverage memory as a way to increase the investment cost (perhaps operating cost?) of brute-force search/attack. Some, like Balloon, use a fixed memory access pattern, with that rationale:

Resistant to Cache Attacks. The memory access pattern of the Balloon hash function is independent of the password being hashed. Thus, an adversary who can observe the memory access patterns of a Balloon computation, e.g. via cache side-channels on a multi-user system, learns no information about the password being hashed.

Others, like Scrypt, make the indexes in memory strongly data-dependent. That can be as part of their argument of memory hardness, or/and with the rationale that it makes using cost-effective large but slow memory (or is it SIMD / GPU) less attractive to an attacker.

The winner of the 2013-2015 Password Hashing Competition did not chose:

Argon2 has three variants: Argon2i, Argon2d, and Argon2id. Argon2d is faster and uses data-depending memory access, which makes it highly resistant against GPU cracking attacks and suitable for applications with no threats from side-channel timing attacks (eg. cryptocurrencies). Argon2i instead uses data-independent memory access, which is preferred for password hashing and password-based key derivation, but it is slower as it makes more passes over the memory to protect from tradeoff attacks. Argon2id is a hybrid of Argon2i and Argon2d, using a combination of data-depending and data-independent memory accesses, which gives some of Argon2i's resistance to side-channel cache timing attacks and much of Argon2d's resistance to GPU cracking attacks.

  • $\begingroup$ I'm not quite sure how to phrase it, and need to cite some sources, so using a comment. Data dependence makes SIMD fail, since the instruction varies depending on the data. GPUs are massively SIMD devices. Data independence prevents some side channels from leaking information about the data. The memory access pattern can't leak any information. There's also the whole issue of time-memory-trade offs... $\endgroup$ – SAI Peregrinus Feb 7 '18 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.