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 &lt;= $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.
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).