# Memory hard key derivation (password hash) using AES encryption

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).

Pseudocode is:

salt = random (any length between 512bit and several MB)
M[0] = HMAC (sha512, password, salt)

for i=1 to N
hash = HMAC (sha512, M[i-1], M[0] + i)
M[i] = AES-128-CBC (iv = substr(hash,0,128), key = substr(hash,128,128), data = salt + hash) // substr lengths in bit

result = M[N]

for i=0 to N
result = HMAC (SHA512, result XOR M[i], M[N-i])


Because of the second for loop, the entire matrix M needs to be present in memory, which would hopefully make it memory hard. Then one could configure salt size versus N to see what gives the desired results of memory usage and cpu usage within a reasonable amount of time.

I would appear to me that AES related-key attacks are not an issue in this scheme also because of the second for loop which hashes all matrix elements. The purpose of using AES is to obtain a larger randomized text for each array element than a 512 bit hash output would be. Since iv and key are unique and are related only through HMAC hashing, this use of AES would also appear to be secure. Even so, I appreciate your input. Creating one's own crypto is not encouraged, which I understand. Even if I do not end up using this, your feedback would really help me improve my understanding of these matters.

Also, I wonder whether the length of the salt affects the security of the function? I.e. if the salt were to be very long, say several MB, would that make it less safe than if the salt was short such as 512 bit (less reliance of encryption, more HMAC hashes)?

EDIT:

For theoretical purposes and NOT in order to create my own cryptography, based on the comments of otus, it appears that in principle, higher memory-hardness is achieved by a more intense shuffling of the matrix.

Therefore, one could e.g. generate a matrix of a size rounds * x, which is then hashed rounds times, but each hash made up of XOR-ring x*2 matrix values. The example below (PHP code) shows it for x=4 (^ is the PHP XOR operator):

for ($i = 1;$i <= $rounds;$i++) {

$result = hash_hmac ('sha512',$result . ($matrix[$i] ^ $matrix[($rounds+$i)] ^$matrix[($rounds*2+$i)] ^ $matrix[($rounds*3+$i)]), ($matrix[($rounds-$i)] ^ $matrix[($rounds*2-$i)] ^$matrix[($rounds*3-$i)] ^ $matrix[($rounds*4-$i)])); }  For 8 rounds, a matrix size 8*4 = 32 would be created, and then hashed with XOR combinations in the loop shown. The output below shows, which matrix index values (the $i in $matrix[$i]) would be combined in each HMAC round:

Computing 1 ^ 15 ^ 17 ^ 31 AND 7 ^ 9 ^ 23 ^ 25
Computing 2 ^ 14 ^ 18 ^ 30 AND 6 ^ 10 ^ 22 ^ 26
Computing 3 ^ 13 ^ 19 ^ 29 AND 5 ^ 11 ^ 21 ^ 27
Computing 4 ^ 12 ^ 20 ^ 28 AND 4 ^ 12 ^ 20 ^ 28
Computing 5 ^ 11 ^ 21 ^ 27 AND 3 ^ 13 ^ 19 ^ 29
Computing 6 ^ 10 ^ 22 ^ 26 AND 2 ^ 14 ^ 18 ^ 30
Computing 7 ^ 9 ^ 23 ^ 25 AND 1 ^ 15 ^ 17 ^ 31
Computing 8 ^ 8 ^ 24 ^ 24 AND 0 ^ 16 ^ 16 ^ 32


One concern there is the question of whether that many XOR operations would create a lot of of collisions and thus somehow security, even though each result is HMAC hashed. It would be interesting to get people's comments on that, with the reasons behind it.

• You wrote that " cryptanalysis of script shows time-memory tradeoff ". Any reference? $\;$ Independently: why use a combination of HMAC and AES, when it seems possible to perform something fine with HMAC alone, and that would be much safer (for equivalent CPU time spent) on CPUs without AES-NI? – fgrieu Nov 22 '15 at 20:57
• @fgrieu: 1. There is lots on scrypt, e.g. eprint.iacr.org/2015/227.pdf. 2. The use of AES with a long salt leads to much longer matrix strings (about 7-8 times longer for 4096 bit of salt compared to only HMAC with SHA512), and hence higher memory usage, for the same amount of time needed. – azren Nov 22 '15 at 21:43
• The paper you quote presents itself as a time-memory trade-off applicable to scrypt, not a " cryptanalysis of script ". It trades being able to compute scrypt with slightly less memory against using (significantly) more computations, and does not allow, as far as I can tell, to lower the cost of an attack on scrypt. $\;$ And again, independently, I see no reason to use AES which can be quite slow on some CPUs, rather than HMAC, SHA-512, or SHA-256, which seems to leverage the CPU power much more evenly. – fgrieu Nov 22 '15 at 22:25
• Re scrypt: it means an attacker can greatly reduce memory use if he so chooses to have to use more CPU instead. He can tune the setup to best suit his hardware. The purpose however was to have a setup that MUST require a lot of memory and thus defeat GPU-based attacks. This does not mean that scrypt is broken in any way, but its memory-hardness is not as expected. – azren Nov 22 '15 at 22:52
• Re AES: the point was to create a memory-intensive key-derived matrix. On my server, the AES-based function running for one second manages 700 rounds with 65k salt, with 43.8 million bit total matrix size. The same function running again for one second, but just filling the matrix with 512 bit SHA512 hashes, manages 110.000 rounds, creating 6.7 million bit total matrix size. That matrix requires 6.5 times less memory. The point is to defeat GPU speed hashing through high memory requirements. The alternative to AES would be a hash with a variable and large output size, not just 512 bit. – azren Nov 22 '15 at 22:52

## 3 Answers

Your key derivation function is not particularly memory hard.

The second loop walks the array in order, so an optimized implementation which an attacker would use can avoid the whole array, keeping only some elements in memory at a time.

For example, you can halve the memory use by only storing the second half of M initially. Then for the first N/2 iterations of the loop you only need to calculate the i'th element from the i-1'th. Then you would recalculate the first half of M instead and continue as earlier. You need about twice the computation for half the memory use, and can extend the tradeoff further. This is much worse (better for the attacker) than scrypt's tradeoffs.

If you use a salt length longer than 512 bits, the attacker can reduce the size of M[i] by only storing the hash value at that iteration during the first loop. They can then derive the whole value when needed in the result loop because it only depends on the hash and salt. This means a memory savings factor of salt length/512 bits for a computational overhead of less than 3x (since they need to recompute the AES twice in the second loop, but none of the hashing needs to be repeated).

There is probably a way to fix these, but the main issue is that you are rolling your own algorithm. Normally algorithms need to face years of cryptanalysis before they are trusted, at least unless they have a security proof reducing them to something already known/believed to be secure.

Instead, you should if at all possible use an existing algorithm, preferably an existing implementation because there are things that can go wrong implementing one yourself. If you want memory hardness, scrypt is the most accepted and widely available algorithm (tradeoffs exist, but they are expensive), though Argon2 which recently won a competition for password hashing algorithms might be an option soon (you will not find implementations for most languages yet).

• Thanks but a mistake in your reply: the second loop computes an HMAC based on elements i and N-i (N being total no. of rounds from first loop). Of course it allows an attacker to recompute elements as needed rather than holding them in memory, but at a very high cost (having to recompute almost the entire matrix each time). It appears to me that using 4-8MB salts with low rounds is more likely to force high memory use. It seems to me that I am not rolling my own algorithm, but rather my own implementation, with heavy use of existing algorithms such as AES that are typically used in other ways. – azren Nov 23 '15 at 10:46
• Managed to misread it, but it still allows a trivial time-memory tradeoff. Scrypt's tradeoff is not nearly as cheap. I've updated the answer. – otus Nov 23 '15 at 10:54
• For long salts the tradeoffs become even easier, because you can calculate the whole M[i] on demand from just the hash value in that element. – otus Nov 23 '15 at 11:00
• I guess I wasn't trying to compete with scrypt (edited my original post). But, is my scheme better than just hmac (password + salt)? Why are tradeoffs easier for long salts? – azren Nov 23 '15 at 12:22
• I have done it: crypto.stackexchange.com/questions/30845/… – azren Nov 26 '15 at 10:03

Unless a fast AES is available on the combination of CPU and PHP instance being used (that is, something built with AES-NI), I strongly advise against using AES as the basis of entropy stretching. Number-1 rule in designing an entropy-stretching function is that it should put to the best possible use the computational resources available to the legitimate user, and software AES is far from that. In scrypt, which used to be state of the art, that is achieved by using the Salsa core, because it comes much closer to optimally using the CPU(s).

Among what's used of PHP built-ins in the question's code, HMAC-SHA-512 is likely to put a CPU without AES-NI to much better use than AES-128-CBC. It could be used as the basis of a decent entropy-stretching function, in pure PHP, making intensive and near-optimal use of significant memory and a (single) CPU. I do not know if/how it could be possible to leverage multiple CPUs in pure PHP.

Update: on the other hand, with AES-NI put to good use (as stated in comment), it could be part of an effective strategy. I can't have an informed opinion on the question's pseudocode since I don't fully understand it; in particular what's the length of M[i] when i>0 (in which case M[i] is defined as the AES-128-CBC encryption of some long string); which parameter is the key in e.g. HMAC (sha512, password, salt)(PHP's hash_hmac and the usual definition of HMAC differ in their order of key and text), and as an aside if that's hex or binary.

If sticking to PHP built-in security functions rather than rolling one's own, we could do much worse than using the built-in crypt with CRYPT_BLOWFISH (also known as bcrypt). That's simple to use, relatively foolproof, and makes at least some significant use of memory (though much less than desirable to optimize the protection achieved).

At least, that's likely to be much better than PBKDF2, which in the context cumulates all sins:

• it does not require significant memory, making attack using (existing!) ASICs extremely efficient;
• it can't use multiple CPUs, if available to the legitimate users;
• it is not built into PHP, thus it is easy to make an implementation error;
• any implementation in PHP will make far from optimal use of the CPU (PHP being an interpreted language).
• I use an Intel i7 server with AES-NI cores and PHP uses openssl which has AES-NI support. My previous reply to your comments under my question states that on that machine, AES runs a lot faster than HMAC (about 6.5 times more data can be encrypted than hashed in the same time) - at least using my implementation shown above. I agree though what you say about bcrypt vs. PBKDF2. – azren Nov 24 '15 at 12:38
• @azenz: that makes using AES quite reasonable. Answer (now) updated accordingly. – fgrieu Nov 24 '15 at 13:23
• Pseudocode: the iv is the first 128 bits of the 512 bit HMAC of (password, salt), and the key the second 128 bits of the same HMAC. – azren Nov 26 '15 at 8:17
• see also my edit of my original question, I wonder whether you might have any insights on that. Thanks. – azren Nov 26 '15 at 8:34

It's normally the best advice to use something proven and well established, such as scrypt or PBKDF2. You say you can't use scrypt, but you could use PBKDF2 and make it run long enough until you feel secure. So you decide that every time you need the password, it must take n seconds on the current system. You store the number of rounds along with the salt. This becomes self-tuning, as the CPU gets faster you'll update to a larger number of rounds when the password is changed. (And obviously you can also set a configurable minimum number of rounds, in case you want to jack it up despite how long it would (or, more likely, would not) otherwise take.)

• PBKDF2 does not require significant memory, making attack using (existing!) ASICs extremely efficient. And it can't use multiple CPUs, if available to the legitimate users. In the question's context, it cumulates others sins: it is not built into PHP, thus it is easy to make an implementation error, and any implementation in PHP will make far from optimal use of the CPU (PHP being an interpreted language). – fgrieu Nov 24 '15 at 3:52