# Are there any high level memory-hard PBKDF constructions?

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.

• @MaartenBodewes: As far as I understand, the difficult part in trying to implement scrypt from scratch in a high-level language is the SMix function, which uses the Salsa20/8 core in (what I believe is) a non-standard manner. Even if one happened to have a Salsa20/8 implementation available (which is far from universal), one would still have to implement the ROMix and BlockMix functions (which involve a lot of data shuffling and hash calls) in the high-level language. That said, I'm not really familiar enough with scrypt to tell whether the high-level parts of it could somehow be adapted. – Ilmari Karonen Jun 18 '16 at 13:57
• @MaartenBodewes: ... As for Argon2, it seems to depend on another uncommon hash function (Blake2b), and indeed appears to require access to its internals. What I'm really looking for is something that could be instantiated with nothing more exotic than, say, AES and SHA-256 (and, ideally, even these should be pluggable components that could be easily replaced with some other block cipher and/or hash without requiring non-trivial modifications or reanalysis). – Ilmari Karonen Jun 18 '16 at 14:07
• Ah, I see you've already included those inside your question. But I'm sure that neither of them require implementing your own algorithm. I'm not sure if there is a PBKDF that just uses NIST compatible algorithms, maybe that could be an objective benchmark? Hmm, a generic framework that just requires explicit properties of the configured primitives would indeed be another. – Maarten Bodewes Jun 18 '16 at 14:09
• @MaartenBodewes: Yes, that kind of a generic framework is basically what I'm looking for. PBKDF2 (from PKCS #5) is one example of just such a generic framework, but it's not (and doesn't make any attempt to be) memory-hard. – Ilmari Karonen Jun 18 '16 at 17:31
• I can't look it up properly right now, but Lyra2 and Catena look exactly like what you're asking for. – SEJPM Jun 18 '16 at 21:31

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.

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.