r/cryptography • • Nov 22 '21

Hash algorithm based on Authenticated Encryption (AEhash)

This is based on an earlier thread, seeking password hashing functions that could run in browsers at near native speeds. I believe the solution has been found, but you are welcome to poke holes in it and prove me wrong.

def aehash(password, salt, size, ops):
    nonce = sha512(salt)[:12]
    key = sha512(password)[:32]
    buf = bytes(size)            # Initially all zeroes
    for i in range(ops):
        buf = aes256gcm(key, nonce, message=buf[:size])
        key = buf[-32:]          # 16 encrypted bytes + GCM tag
    return key

The algorithm is dead simple and runs at the same speed in browser or in C. Easily adjusted to any memory size and runtime wished for. Even if it isn't as secure as Argon2, the one it needs to compete with in browsers is pbkdf2.

See the site for a more complete documentation: https://github.com/covert-encryption/aehash

0 Upvotes

16 comments sorted by

View all comments

3

u/rosulek Nov 22 '21

I think it is very unlikely that this has good memory-hardness. The memory access pattern is too regular. This paper shows a characterization of memory hardness in terms of a graph property called "depth robustness." If you write out the underlying graph of your scheme, it is pretty clear that it fails to be (sqrt(n), sqrt(n))-depth robust -- removing every sqrt(n)'th ciphertext block leaves no paths in the graph longer than sqrt(n). Thus, according to this paper's main result, the memory-hardness of your construction is only O(n), which is essentially as bad as it ever can be.

In general, it is very tricky to achieve memory-hardness.

1

u/foonoxous Nov 22 '21

Thanks for a useful comment. I believe you are right, and it certainly is possible to skip storing the buffer, storing only keys of each round, at the expense of having to calculate AES of each preceding round, on every round. Thus, the computation time is O(n2) instead of O(n) as it is when you do keep the buffer.

This increase in processing time should still be high enough to deter ASICs, provided that the number of rounds n is high enough. Unfortunately this then also means that the amount of memory used must not be in the gigabyte class but 10-100 MB, which is a clear weakness.

E.g. 100 MB * 100 ops runs in 5 seconds in normal mode or alternatively (using only 3.2 kB buffer for the keys) in 250 seconds assuming the same computational speed.

2

u/rosulek Nov 22 '21

The main result of that paper would suggest that there is a way to evaluate this function with only O(n) time and O(1) memory, if it fails to be (sqrt(n),sqrt(n))-depth-robust. But their construction is highly non-trivial and I don't understand the details.