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.
- Derive a random looking value from the password in a way that is expensive to do on ASIC (memory hard, ASIC unfriendly algorithm)
- Hash this value using a normal hash function to make the size small
- (Transmit this to the server)
- Hash this value using a normal hash function
- 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.
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.
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\
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.
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 = SHA512(password)
table = 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