Proof-of-work with hashcash: Preventing account lockouts

#security #hacking

Translated from Portuguese with AI assistance and reviewed by the author. Read the original (PT)

The news spread fast: “Flaw” in WhatsApp lets anyone lock your account (in Portuguese). It happens because many systems, not just WhatsApp, mitigate brute-force credential attacks by locking an account for “X” amount of time after “N” failed login attempts.

That strategy works reasonably well against brute force, but it has a side effect: it leaves the system open to DoS attacks. A denial-of-service attack? Yes! The account identifier is usually a known email address or phone number. If the system locks accounts after “X” failed attempts, anyone can now lock that account just by submitting invalid logins. It’s not hard to keep a script running every minute so the lock never expires, which denies the service to the legitimate user.

The attack can get more sophisticated and target many other users, or even all of them, which would take the entire system offline. If the system locks by IP address instead, the attack can be distributed to get around that control. And if many users share the same corporate network, locking by IP may not even be an option.

One strategy for mitigating brute-force attacks is to require a “proof-of-work” from whoever is making the attempt. The client has to do some computation, and the server verifies it. Verification is fast for the server, but the work considerably slows down mass attempts for the attacker.

The flow works like this:

PoW flow 1

There’s another possible variation, where the client already knows the server’s difficulty and token. In that case the flow starts at step “3” of the one above, like this:

PoW flow 2

The idea is to use the “hashcash” concept, which is also used in hash mining for cryptocurrencies. It boils down to finding a hash with a desired prefix, for example a hash that starts with “0000” for the content being submitted. Depending on how hard the required prefix is, this takes a certain amount of computation and time.

The difficulty can be defined, for example, by the number of leading “0” (zeros) the hash must start with.

Below is an example implementation for a web environment with a C# back end. The model is simple, and it doesn’t have to be implemented exactly as shown. The goal is to give a starting point and the core concepts to anyone looking for a more detailed implementation or a deeper understanding.

When the user submits a username and password for a login attempt, the client also submits the number that, appended to that data, produced a hash with the desired prefix. The hash itself doesn’t need to be sent, since the server can quickly recompute it from the information it receives.

The suggested structure of the content to be hashed is:

Server-provided token + credentials + mined nonce

Server-provided token: This can be a random string or a fixed GUID, or it can be renewed every “X” amount of time.
Credentials: Usually login + password, but it can include other information depending on each system’s logic.
Mined nonce: The number the function searched for and computed to find the final combination that produces a hash with the expected prefix.

Some implementations also add the date and time of generation. That lets the server enforce an expiration and reject hashes it has already seen. If you need that, just add the extra data to the suggested flow.

In short, you implement a simple hash-mining routine. The content is run through a hash function (SHA256, for example) and the result is checked. As long as the hash doesn’t have the desired prefix, the number stored in the nonce is incremented and a new hash is tested, until the right one turns up.

function getProofOfWorkNonce(login, password) {

	/* 
	* Difficulty fixed at 4.
	* This means we need to find a hash with a prefix
	* of 4 zeros (0000).
	* The difficulty can be variable, increasing with the
	* number of attempts already made.
	*/
	const difficulty = 4;
	const hashPrefix = "0".repeat(difficulty);

	/*
	* Gets the token generated by the server. This value can be
	* fetched dynamically at this point or just read from
	* a hidden field filled in on the previous request.
	*/
	const serverNonce = getServerNonce();

	/*
	* Builds the fixed block of content to be tested
	*/
	const constantInfo = login + password + serverNonce;
	
	/*
	* Starts the nonce at 0 and runs the first check.
	* The 'Sha256.hash' method must be a SHA256 implementation.
	* If you need one, you can get it at:
	* https://www.movable-type.co.uk/scripts/sha256.html
	*/
	let clientNonce = 0;
	let hash = Sha256.hash(constantInfo + clientNonce);
	
	/*
	* The process loops, incrementing the nonce
	* until the condition is met
	*/
	while (!hash.startsWith(hashPrefix)) {
	    clientNonce++;
	    hash = Sha256.hash(constantInfo + clientNonce);
	}
	
	return clientNonce;
};

When the client sends the login and password to the server for verification, it must also send the nonce it found, so the server can validate the mining work. Using the credentials, the nonce and the token it issued earlier, the server recomputes the hash and checks whether the prefix meets the expected condition. That means validation takes just one hash operation, which makes verification very fast.

private bool VerifyProofOfWork(string login, string password, long proofOfWorkNonce)
{
	/*
	* Must be the same token sent to the client
	*/
	var serverNonce = "09c4f6b8-3806-410b-a0f1-593edc98f794";
	
	/*
	* Difficulty fixed at 4 for this example
	*/
	var difficulty = 4;
	
	/*
	* The hash is regenerated from the submitted information,
	* including the nonce found by whoever did the mining.
	* The prefix must meet the expected condition, otherwise the proof of work is invalid.
	* The 'Helper.Sha256Hash' call stands for a SHA256 hashing implementation.
	*/
	var proofOfWorkHash = Helper.Sha256Hash(login + password + serverNonce + proofOfWorkNonce);
	var hashPrefix = new string('0', difficulty);
	
	return proofOfWorkHash.StartsWith(hashPrefix);
}

Making the solution more sophisticated

You can extend the flow, depending on each application’s needs and nature. For example, you could add these checks:

Randomize the server token: issue a new token on every request or every “X” amount of time, with a cache-based control.
Include the date and time in the fixed block.
Raise the difficulty dynamically.
Split the login flow: first submit only the username to get a user-specific token, then do the PoW and send the password attempt afterward. This approach introduces another problem, called user enumeration, so you should study whether it’s viable.

Conclusion

I simulated a brute-force attack against a given system from a home computer and got a rate of 100 login attempts every 5 seconds. Once proof-of-work was required for every attempt, the same 100 attempts took 50 seconds, which is 10x slower.

The main advantage of PoW is that it doesn’t burden the server. The processing cost falls only on whoever is making the requests, unlike throttling/DDoS controls, which require the server to process and store information.

It’s also worth noting that for a legitimate user trying to access their account, a single hashcash mining run for their password won’t cause a noticeable delay, unless the required difficulty is set too high.

On its own, this strategy isn’t the answer to every access management problem. You need to combine it with other measures for adequate mitigation, which means:

Accept only strong passwords, with an adequate minimum length.
Maintain a blocklist of commonly used passwords and check new passwords against it.
Use a proper hash for password storage. I’ve already written a post about it: https://eduardogadotti.com/en/2020/07/05/are-your-users-passwords-secure/.
Apply IP-based anti-throttling, depending on the nature of the application.
Require a CAPTCHA after “X” attempts.
Require another authentication factor after “X” attempts, or whenever the login comes from a source the specific user hasn’t used before. An email confirmation is one option.

Making the solution more sophisticated

Conclusion

References