4
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Good point! Do you think that in the second loop, each iteration of i to N would need an HMAC hash computed, or could it be every say 16th or 64th iteration, without compromising security? (Meaning would the XOR-ing of result ^ (matrix... ^ matrix...) with occasional hashing be sufficient)? The reason is that each HMAC computation takes a lot of time, and if one were to iterate several times over the matrix, reducing the number of hashes for each iteration would be very helpful. (BTW all HMAC hash sizes are always 512 bit, per SHA512). $\endgroup$
    – azren
    Nov 27, 2015 at 10:40
  • 1
    $\begingroup$ @azenz, I'm not sure if XOR would be sufficient in that case, it probably depends on the exact order of operations (whether shortcuts remain). However, the slowness of HMAC in generating data is exactly the reason scrypt uses Salsa20/8 core for touching a lot of data quickly. AES hardware could probably be used similarly. I.e. use HMAC and/or AES to build the matrix, then AES to loop over it many times, then finally HMAC to gather it all into one value. $\endgroup$
    – otus
    Nov 27, 2015 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.