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.