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.