Memory hardness of key derivation function through XOR-ring multiple matrix values

Question

For theoretical purposes in order to enhance my own understanding, and NOT in order to create my own cryptography, I am asking a question about the memory-hardness of a key derivation function achieved by a more intense shuffling of the matrix.

If I were to create a matrix with N elements with pseudorandom values:

for i=1 to N
    matrix[i] = HASH (some input)

and then hash over all elements of the matrix:

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

It was pointed out to me here that this was not especially memory-hard, since an attacker can trade twice the computation for half the memory use. This is done by only storing the second half of M. Then for the first N/2 iterations of the loop, one only calculates the i'th element from the i-1'th, then recalculate the first half of M instead and continue as earlier.

Greater memory-hardness would therefore seem to be achievable through a more intensive XOR-ring of matrix values in the second loop.

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

for i=1 to N*4
    matrix[i] = HASH (some input)

for i=1 to N
    result = HMAC (SHA512, result +
            (matrix[$i] ^ matrix[(N*2-$i)] ^ matrix[N*2+i] ^ matrix[N*4-i]), 
            (matrix[N-i)] ^ matrix[N+i)] ^ matrix[N*3-i] ^ matrix[N*3+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 collisions and thus compromise security, even though each result is HMAC hashed. The lines "computing 4/8" show same matrix values being XOR-ed, although one could remove these lines (only two in total) from the second loop or alternate the respective values. It would be interesting to get people's comments on that, with the reasons behind it.

Answer 1

Collisions are not much of a concern, since you have to compute them to know they happen, and assuming your values are a typical hash size (256+ bits) they will never happen randomly anyway. But yes, having identical computation that use the same data is wasteful if you don't store the intermediate values.

However, the main problem your function has is that the XORs can be computed ahead of time for multiple iterations of the second loop. For example, here:

Computing 1 ^ 15 ^ 17 ^ 31 AND 7 ^ 9 ^ 23 ^ 25
Computing 2 ^ 14 ^ 18 ^ 30 AND 6 ^ 10 ^ 22 ^ 26

The attacker can compute both of these by going through the matrix once and only maintain four values where they XOR the appropriate elements of the matrix. In fact, they can choose exactly the amount of memory they do have and calculate that many iterations' worth of XORs in one go. (Concatenation would be better than XOR since it would take more space. But it would still be less than the whole matrix, so trade-offs would be possible.)

The way scrypt and other memory hard hashes accomplish their memory-hardness is by having a large state that they update instead of just reading. Your two loops where one generates and one "collects" the data will always let the attacker store only parts of the matrix and recalculate as needed. If the second loop took many passes over the data while also changing the matrix, it would no longer be as easy since calculating any dropped values again would take longer and longer the further along the algorithm is.