r/cryptography • u/foonoxous • 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
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.
2
Nov 22 '21
Why though
0
u/foonoxous Nov 22 '21
This was discussed in the previous thread, and also on the page I linked. Because all existing password hashers suck in browsers. PBKDF2 is fast but not memory-hard, while Argon2 and Scrypt run so much slower that password crackers get a 100-fold speed advantage even on a single desktop PC. That is unacceptable.
With this scheme, cracking with native code using all CPU cores is not much faster than verifying a password in a browser is, so that is why.
1
u/ivm83 Nov 22 '21
Interesting idea. Might be ok, might be completely broken. I wouldn’t use this for anything that actually needs to be secure unless it goes through a password hashing competition and either wins, or at least gets to be a finalist :)
-3
u/foonoxous Nov 22 '21 edited Nov 22 '21
Woah, THREE downvotes and no comments yet. Must be a touchy subject.
2
u/parabirb_ Nov 22 '21
if i had to guess, you're being downvoted because you're rolling your own password hashing algorithm with literally no prior experience. just use argon2 if you're able to.
1
u/foonoxous Nov 22 '21
I have been using Argon2 for the past years and Bcrypt before that. You should not assume that someone has no experience when you know nothing about the person.
Even though I understand the sentiment quite well, because these kind of forums are flooded with people inventing their own crappy cipher algorithms, missing all the basic principles.
This uses proven standard crypto and is extremely simple. That's two principles to start with. Now, go and find a flaw on it instead of raging on the Internet.
P.S. Obviously I am not claiming that this is secure, that is well stated on the page. As another comment mentioned, much scrutiny is needed before we get there, and in all likelyhood this does have some fundamental shortcomings.
2
u/parabirb_ Nov 22 '21
sorry for the hyperbole, i mean that i highly doubt you have the experience required to create your own secure password hashing algorithm.
4
u/Natanael_L Nov 22 '21
What are you doing with that key variable inside the loop? If you're trying to say you're using the the first half then the second of SHA512 then don't do that when you retrieve the bits, split it first so you get clean separation between the halves. Or if that's what you use to retrieve the GCM tag from the buffer as the comment implies, use a different variable so you don't use the same one for multiple purposes!