Many websites need to allow users to authenticate using passwords, and use an expensive hash function to store the users’ passwords safely. But this approach subjects the website to a simple denial-of-service attack. We propose a solution to mitigate this attack, based on the client including a proof-of-work in each password-based authentication request.
Many websites store only a salted hash of the password, with the hash function
chosen to be an expensive cryptographic hash function. Popular choices include
pbkdf2 and bcrypt with high cost factors.
The problem is that a malicious client can cause a denial of service simply by issuing more authentication requests than the website can handle. The malicious client can issue each authentication request cheaply, while the website must perform an expensive operation to for each authentication request. The higher the cost factor of the hash function, the better the security of the password file, but the longer the website has to work for each authentication request. A single malicious user with minimal computing power and minimal network throughput can bring a website with mighty computing power and mighty throughput to its knees, simply by forcing the website to perform the expensive hash function repeatedly.
There are a few existing solutions.
The website can offload the authentication to a separate set of machines. The majority of the website is served by the main cluster of machines, while the work required to verify a password attempt is performed on a segregated cluster of machines. The denial of service attack will be reduced to an attack against password-based client authentication only. Users will not be able to log in. But the rest of the website will remain operational, including both the unauthenticated and the authenticated portions.
The website can impose a rate-limit scheme on authentications. There are a variety of ways to do it, each with its own costs and benefits.
The website can have a global rate-limit on authentications. The costs and benefits mirror those of authentication offloading.
The website can have a per-client-IP rate-limit on authentication.
The website can have a per-username rate-limit on authentication.
The website can combine multiple of the above approaches.
The website can require the client to produce a proof of work unique to each unique authentication attempt.
The website chooses a hash function $h$ with an output size $|h| \equiv log_2(|cod(h)|)$, a cost factor $c$, a window $w$, and a merge function $m$. The website is configured to use a signed session cookie, and initializes the session with a random nonce $k$.
When the user enters the username $u$ and password $p$ on the sign-in page and submits the form, a JavaScript hook is executed which computes the current time $t$ and looks for a solution $s$ such that $h(m(k,s,t,u,p)) < 2^{(|h| - c)}$ — or, equivalently, has a prefix of zero bits of length at least $c$. Once the hook has found $s$, it includes it in the data sent to the website server alongside $u$, $p$, $t$, and a replay of the signed session cookie.
When the website server receives an authentication request, it first checks that $t$ is recent enough — that is to say, $t$ is within $w$ of the current time. If $t$ is not recent enough, the authentication request is immediately failed. Then the website server checks that the solution $s$ is a correct solution — that is to say, the relation listed above holds. If $s$ is incorrect, the authentication request is immediately failed. The website server then continues as normal, performing the expensive hash function on the password to verify it.
This solution imposes a nontrivial cost to the client for each authentication request it sends to the website, preventing a malicious client from overwhelming the server with a large number of authentication requests (or requiring the malicious client to pay handsomely for the privilege). The website can adjust the cost parameter to suit its needs.
This solution can stand alone, and it can be used in conjunction with any combination of the existing solutions listed above.
This solution is similar to the hashcash system for mitigating email spam and to the RSA connection-depletion defense.
Using a proof-of-work technique, website owners can significantly reduce the exploitability of the attack vector introduced by using an expensive hash function to store and validate user passwords.