Password hashing that is resistant to ASIC-assisted cracking without risking DoS of server

Question

Previously, authentication systems stored passwords in cleartext. This made it trivial for an attacker to log in to an account if he had access to a leaked password file.

Later, passwords were hashed once and the hashed value stored. If the attacker had a leaked password file he could try hashing guesses and if a hash value matched, use that guess to login.

Then passwords were salted and hashed thousands of times on the server and the salt and the resulting hash value was stored. If the attacker had a leaked password file he could use specialized ASICs to hash guesses and if a guess matched use that password to login.

Can we do better than that?

Can we make password cracking so difficult that even if he has the hashed password, he will not get a major advantage (factor of 10) over testing the passwords against the server - even if he has specialized ASICs? And can we avoid this opening an way of DoS'ing the server with many parallel login requests?

We can assume the attacker has access to the hashed password, but that he cannot intercept communication between the server and a client.

Answer 1

There are a few things that can be done, and are done.

One approach is to leverage TPM to create a secret that the server cannot (theoretically) leak. This secret is used upon the password during the hashing process (I believe the term for this is a "pepper," as opposed to a "salt" which is considered public information). The offline attacker could beat on this password file as long as they like, but unless they can guess the server's secret stored in a TPM module, they don't have anything to break. Obviously this can be done with any sort of secret, but I point out TPM because that tends to rely on hardware solutions to provide security for these numbers, and that can make it harder to leak the secrets than losing a password file. This is highly related to the issues the FBI has publicly had when trying to unlock iPhones. The information they need is locked away in a chip that is intentionally difficult to get into.

The other approach is to make ASICs inefficient. The power of ASICs is typically that they can do a massively parallel attack on the password file. You can design the hashing process to consume a large amount of resources which are expensive to parallelize. There are hashing algorithms out there designed to do this. One common approach is to have a very memory intensive hashing routine, forcing the ASIC designer to expend large amounts of chip real estate on banks of memory.

Fundamentally, though, if the attacker can get two computers which are equivalent to your server, they can attack it twice as fast offline. This is a simple information theoretic reality. However, these approaches make it difficult to get an "equivalent" to your server. One approach does so by creating a hard to duplicate secret. The other approach does so by using algorithms that are not trivially parallelizable in hardware.

In response to your comment about your self answer, if you involve the client and have them do the calculations for you, some interesting solutions become options. Consider looking at zero knowledge proofs. They are designed to reveal that you know a number (or password) without revealing any information other than that you know the number. If the server queries the client using one of these zero knowledge protocols to ascertain whether the client knows the password or not, the server doesn't need to know anything about the password at all, so there is no passwords file to leak. At most, there would just be a database of data structures to use in the zero knowledge protocol, which are mathematically proven to contain no information about the password (or at least statistically nothing). An attacker who acquires this file would be able to verify that a client that connects to them(!) is a valid client, but could not crack the password any better than you could -- which is not at all.

Answer 2

Can we make password guessing of an attacker so hard that even if he has the hashed password file, he will not get a major advantage over testing the passwords against the server - even if he has specialized ASICs?

No, we cannot. What you are implying is that somehow is possible to a standard, common server to take the same time to validate a password as another server built only for password breaking.

No matter what you do, how you hash, the algorithms you use, if you encrypt or not, a common server will be slower than a purpose-built one.

The only real defense is to force users to choose good, long passwords. There are services out there that allow you to check offline if the chosen password is on a leak list, so you can ask the user to choose another password. And allow only long passwords (16 chars or more), as this two measures will defeat both dictionary attacks (no leaked passwords) and bruteforce (a 16 byte password properly salted and hashed will survive for millenia).

Answer 3

My boldface:

Can we make password cracking so difficult that even if he has the hashed password, he will not get a major advantage over testing the passwords against the server - even if he has specialized ASICs?

The problem with the way you've formulated the question here is you haven't given us any concrete criterion as to what advantages count as "major." But we can definitely say that even with state-of-the-art memory-hard password hashing functions like Argon2, the attacker definitely still has some advantage. For example in the v.9 draft for the Argon2 RFC, section 8.2 discusses Argon2's security against time-space tradeoff attacks:

Time-space tradeoffs allow computing a memory-hard function storing fewer memory blocks at the cost of more calls to the internal compression function. The advantage of tradeoff attacks is measured in the reduction factor to the time-area product, where memory and extra compression function cores contribute to the area, and time is increased to accomodate the recomputation of missed blocks. A high reduction factor may potentially speed up preimage search.

The idea here is:

• There are strategies to reduce the memory usage needed to compute the function but at the cost of slowing down the computation. This is called a time-memory tradeoff (TMTO).
• We use a time-area product metric as a proxy for the cost of computing the password hash.
• A time-memory tradeoff is advantageous to the attacker if it allows them to compute the function at a lower cost (measured by time-area product) than the canonical algorithm that the defender uses.

And the answer for Argon2 and similar algorithms is that there are definitely time-memory tradeoffs advantageous to the attacker, but their size is bounded:

The best tradeoff attack on t-pass Argon2d is the ranking tradeoff attack, which reduces the time-area product by the factor of 1.33.

The best attack on Argon2id can be obtained by complementing the best attack on the 1-pass Argon2i with the best attack on a multi-pass Argon2d. Thus the best tradeoff attack on 1-pass Argon2id is the combined low-storage attack (for the first half of the memory) and the ranking attack (for the second half), which bring together the factor of about 2.1. The best tradeoff attack on t-pass Argon2id is the ranking tradeoff attack, which reduces the time-area product by the factor of 1.33.

So actually, we expect that an ASCI attacker could compute Argon2d or multi-pass Argon2id at something like half the cost to the defender, and one-pass Argon2d for some 75% of the cost. Whether that counts as "major" is up to you, but functions such as scrypt and Argon2 are seen as major improvement in this field.

And can we avoid this opening a way of DoS'ing the server with many parallel login requests?

There's a few server relief techniques that have been proposed for shifting the computation of the costly function over to the clients, but none has really caught on. See, for example:

• https://www.rfc-editor.org/rfc/rfc5802
• https://openwall.info/wiki/people/solar/algorithms/challenge-response-authentication

The downside to these compared to server-side hashing is that the server discloses the userside salt to any attacker who probes for that user ID. Which means that an attacker can start precomputing hashes for users of interest before they manage to steal the password hash stored on the server.

Beyond that there's password-authenticated key exchange protocols that use asymmetric cryptography, and are rather more complicated.

Answer 4

By using memory hard algorithms the advantage of ASICs is limited: RAM costs around the same in an ASIC as it does in consumer hardware (https://www.youtube.com/watch?v=8QxFsWszbyI). A memory hard function that requires 1 GB RAM will require 1 GB RAM no matter the design of the ASIC. E.g. if you have a GPU with 2688 cores and 6 GB RAM (like Tesla K20X), then you can at most run 6 jobs in parallel due to the memory requirements - the remaining 2682 cores will have to sit idle.

So a solution would be to pass the password through a memory hard function, hash the result twice and store the result.

1. Derive a random looking value from the password in a way that is expensive to do on ASIC (memory hard, ASIC unfriendly algorithm)
2. Hash this value using a normal hash function to make the size small
3. (Transmit this to the server)
4. Hash this value using a normal hash function
5. Store this in the password file

E.g. store this result: salt,sha512(sha512(Argon2id(1 GB RAM, 1 G instructions, salt, password)))

As long as SHA512 and Argon2id are not broken then this should make the advantage of using ASICs very small: Guessing a random looking input value from a SHA512 value is infeasible - even with dedicated hardware. The best pre-image attack on SHA512 is 2^511.5 (https://en.wikipedia.org/wiki/SHA-2). If Argon2id is proven to be ASIC friendly replace that with another hashing function that is ASIC unfriendly.

Unfortunately, if the computation is run on the server, then the server can be DoS'ed by starting many logins simultaneously, because if the server has to run Argon2id(1 GB RAM), it will be using 1 GB RAM for each simultaneous login. This can be avoided by moving that part of the computation to the client:

Client: Please login in user A
Server: Here is the salt for user A
Client: computes `sha512(Argon2id(1 GB RAM, 1 G instructions, salt, password))`
Client: Return result to Server
Server: Compare `sha512(result from client)` with password file.

The communication is of course encrypted, so an attacker cannot get the answer being sent from the Client. This would otherwise make a replay attack possible.

Even for modern smartphones (that have 8 GB RAM) using 1 GB RAM for 1 G instructions is feasible, and for laptops it has not been a problem for a long time.

In practice the client program would need native support for this to be fast enough (e.g. JavaScript would not be fast enough), but for browsers this ought to be possible to do using native plug-ins/extensions/add-ons/modules.

By doing a single hashing on the server, a leaked password file cannot be used directly, as computing the reverse of a hash should be very hard (it basically corresponds to the user having a 512-bit random password). An added advantage is that the password is never accessible on the server in cleartext. If the site is completely taken over by an attacker, the attacker will thus not know the password, which the user might be using on other sites.

For clients that do not support this (e.g. if they have less than 1 GB RAM free), we can give the user the option to do a CAPTCHA, and if he completes that, then the server will do the computation for the client. Here the password will be on the server in clear text when starting the computation.

So all in all an attacker will have to buy 1 GB RAM for each parallel guess he wants to run, and spend 1 G instructions for each guess, while the server only needs a few MB for a few milliseconds to verify a user that runs the computation himself.

Arguments against

An attacker does not need to guess the password. He can just take the hash value from the password file and compute a value that would result in this hash value, and use this value to login. In other words: Find x where sha512(x)=value.

This is called finding the pre-image. If x is in a small search space (say, all 10 word combinations of 1000 English words = 1000^10 = 1000000000000000000000000000000) then this may be doable. If x is a random number in a 512-bit search space, then this requires 2^511.5 operations according to https://en.wikipedia.org/wiki/SHA-2 This is not doable no matter the hardware: 2^512 = 13407807929942597099574024998205846127479365820592393377723561443721\ 76403007354697680187429816690342769003185818648605085375388281194656\ 9946433649006084096.

Recall that the server stores: salt,sha512(sha512(Argon2id(1 GB RAM, 1 G instructions, salt, password)))

So an attacker would have to find sha512(Argon2id(1 GB RAM, 1 G instructions, salt, password)) or another value that gives the same sha512.

In this case the search space is 512-bit. This is because the output from Argon2id(1 GB RAM, 1 G instructions, salt, password) is indistinguishable from random data, and thus the output from the sha512 will also be indistinguishable from random data: You cannot rule out values like, say, aaaa...a, because given random input SHA512 may result in that value.

An attacker can just design an ASIC so efficiently that he can run many thousands of guesses in parallel.

It is important to understand the difference between memory hard functions and a simple hash function like SHA512.

By definition of a memory hard function the function requires the defined amount of memory to run (1 GB in the example here). So the ASIC would have to include 1 GB of RAM for each compute core. This makes a specialized ASIC with RAM prohibitively expensive: The attacker would have to have at least 8 G transistors on the chip for a single thread. More realistically he could buy the RAM in sticks like the rest of us. He would thus need to buy 1 GB of RAM for each thread he wants to run in parallel.

If the attacker has to buy 1 GB RAM for each thread and each thread has to run for 1 G instructions for each guess, it pushes the bar way higher than for the server which has to do a single SHA512 for each login.

Will this run on small clients?

It will require 1 GB of free memory on the client, so very small machines (think IOT) will not be able to do this. They may use digital certificates instead, but that is outside the scope of this question.

It may, however, be interesting that it can run on small servers (if the run-the-computation-on-the-server solution described below is not included), so if the IOT-device acts like a server, this may be a secure way to login.

Will it run on slow clients (e.g. in JavaScript)?

The 1 G instructions will most likely make this impossible. So for browsers you would need a plugin/extension/module that is written for the native CPU.

If it is important to support slow clients, the server could also offer a secondary login, where the server does the memory hard computation after the user solves a CAPTCHA.

What is the difference between a memory hard function and, say, SHA512?

SHA512 can be run in less than 1 MB. A memory hard function requires a certain amount of RAM to run.

A simple example (probably not cryptographically safe) would be:

tablesize = 1 GB / length(SHA512(0))
table[0] = SHA512(password)
table[1] = SHA512(salt)
for i = 2 .. tablesize:
  table[i] = SHA512(table[i-1] xor table[i-2])

j,k,l = 0,1,2
for i = 1 .. 1 G instructions:
  table[j] = SHA512(table[k] xor table[l])
  l = k
  k = j
  j = table[j] % tablesize

return table[j]