Are there any high level memory-hard PBKDF constructions?

Question

The PBKDF2 construction from PKCS #5 v2 has the convenient feature that it can be implemented using only standard interchangeable cryptographic primitives. Specifically, it only requires the availability of a suitable PRF, typically implemented using a standard cryptographic hash function via HMAC (another high level crypto construction). Thus, PBKDF2 can be easily implemented on top of any crypto library that provides access to a suitable hash function, even if the library does not directly implement PBKDF2 (or even HMAC) itself.

However, while PBKDF2 implements an adjustable work factor (in the form of an iteration count) to thwart brute-force password cracking attempts, it uses only a fairly small amount of memory. This leaves it vulnerable to attacks using parallel computing hardware such as GPUs, FPGAs or dedicated ASICs.

In recent years, several "memory-hard" password-based key derivation functions, such as scrypt and Argon2, have been developed to address this issue. These functions, however, all tend to use specific non-standard primitives that are not (yet) implemented by many crypto libraries, and which would be hard if not impossible to implement securely and efficiently from scratch in a high-level programming language.

Thus, my question would be: Are there any memory-hard PBKDF constructions that can be implemented using only common standard crypto primitives, like (generic) hash functions and/or block ciphers?

Ideally, the security of the construction should be easily reducible to reasonable security assumptions on the underlying primitives. I do suspect that for some aspects (particularly, the memory-hardness) this reduction may be non-trivial, but hopefully still provable.

Also, to be well suited for implementation in high-level languages, the construction should ideally be implementable using only a relatively small number of high-level calls to the underlying crypto library. For example, a construction based on a block cipher should ideally spend most of its time running the cipher on bulk data in a widely implemented mode of operation like (bulk) ECB or CBC, instead of requiring repeated high-level calls to encrypt individual blocks. Similarly, for hash-based constructions, it would be ideal for most of the hash invocations to be on fairly long input strings. (Note that PBKDF2-HMAC fails this additional requirement, invoking the hash repeatedly on short strings.)

---

Ps. This earlier question is a good example of the kind of use case for which such a construction would be useful for:

"I am restricted on a certain environment involving PHP and am currently unable to implement new memory hard hashes such as scrypt (and I am not trying to compete with the likes of scrypt).

My current key derivation is simply an iteration of HMAC (password + salt). But it seems that using AES or other encryption ciphers, one could construct a fairly simple, memory-hard key derivation function using build-in PHP capabilities such as HMAC and AES encryption (assuming PHP is compiled with openssl support)."

Alas, their proposed construction does not actually seem to be memory-hard. I've been thinking about possible alternative constructions to achieve the same goal, but before investing a lot of time and effort on analyzing their security and memory-hardness, I thought I'd first ask whether this is already a solved problem.

Answer 1

Are there any memory-hard PBKDF constructions that can be implemented using only common standard crypto primitives, like (generic) hash functions and/or block ciphers?

Of course there is one, and it even got a "special recognition" at PHC: Catena.

I won't go into the details of Catena here (the paper does it much better on its 50+ pages), but it comes with pebble-game-based security reductions, rigorous security proofs, default instances and a alot of customizable parameters (namely four):

• It uses a cryptographic primitive, the paper suggests Blake2b, but really any hash will do, which you can compute quickly
• It uses a round-reduced cryptographic primitive, although a full-rounded version will also work
• It takes an optional randomziation layer, to harden memory initialization
• It takes some "memory-hard" function

Finally it uses all these parameters and a clever graph driven data flow to achieve basically all desirable properties being expected from a modern password hash.

Note: Default parameters for the latter two choices are provided, so that the user basically has the choice between two Catena variants based on their favorite hash.

Answer 2

An alternative which appeared after the password hashing competition is Balloon hashing. It can use any standard cryptographic hash function as it's only crypto primitive; all other operations are simple concatenations or XOR which can be done in almost any high level language. I've even implemented it in Microsoft T-SQL using the HASHBYTES() function with SHA-256.

The Balloon hashing paper includes an attack on Argon2 as a bonus.