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

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!

1

u/foonoxous Nov 22 '21

First of all, the key variable is what is used as AES encryption key, and it is always 32 bytes, thus I see little confusion here. Assigning variables with new values is a very normal thing in programming, even if not in mathematics.

Initially it comes from the SHA-512 hash of the password, but after each round it uses encrypted data and its tag, no SHA hashing in between. Since AEAD schemes append that 16-byte tag at the end, the final 32 bytes of the buffer are 16 bytes ciphertext and 16 byte tag.

Using the tag ensures that the entire buffer must be calculated. A password cracker cannot skip processing of any byte even on the final round, and must store all the ciphertext between rounds (to actually be memory-hard, ops needs to be >= 2, because for the initial round the buffer is all zeroes and after the final round the data can be thrown away).

2

u/Natanael_L Nov 22 '21

In cryptography, this is most certainly a very weird chaining mode, and it is absolutely not recommended to reuse variables this way in the context of cryptography. There should be absolutely no ambiguity regarding what's going on to avoid accidentally undoing your own security measures. At the very least, use a separate variable inside the loop to maintain state

1

u/foonoxous Nov 22 '21

Thanks for your comment. What do you recommend?

1

u/foonoxous Nov 22 '21

Here is the pseudo code of Balloon hashing, which is considered better than Argon2 and which has a fairly simple construct, considering that Argon2 and Scrypt use hundreds of lines of code.

func Balloon(block_t passwd, block_t salt,
    int s_cost,         // Space cost (main buffer size)
    int t_cost):        // Time cost (number of rounds)
  int delta = 3         // Number of dependencies per block
  int cnt = 0           // A counter (used in security proof)
  block_t buf[s_cost]): // The main buffer

  // Step 1. Expand input into buffer.
  buf[0] = hash(cnt++, passwd, salt)
  for m from 1 to s_cost-1:
    buf[m] = hash(cnt++, buf[m-1])

  // Step 2. Mix buffer contents.
  for t from 0 to t_cost-1:
    for m from 0 to s_cost-1:
      // Step 2a. Hash last and current blocks.
      block_t prev = buf[(m-1) mod s_cost]
      buf[m] = hash(cnt++, prev, buf[m])

      // Step 2b. Hash in pseudorandomly chosen blocks.
      for i from 0 to delta-1:
        block_t idx_block = ints_to_block(t, m, i)
        int other = to_int(hash(cnt++, salt, idx_block)) mod s_cost
        buf[m] = hash(cnt++, buf[m], buf[other])

    // Step 3. Extract output from buffer.
    return buf[s_cost-1]

There are many variables that keep changing, defined all over the function. It is genuinely hard to keep track of all the nested loops and of all the variables.

1

u/Natanael_L Nov 22 '21

It's one thing for an optimized implementation written by experts and tested against the spec and test vectors to do weird things for performance. But if you're proposing something new, that's very far from an ideal way to introduce it.

And to be clear, in the code above the purpose of the buffer doesn't change midway.

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

u/[deleted] 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.