Understanding Hash Functions and Keeping Passwords Safe

From time to time, servers and databases are stolen or compromised. With this in mind, it is important to ensure that some crucial user data, such as passwords, cannot be recovered. Today, we are going to learn the basics of hashing and what it takes to protect passwords in your web applications.

If you just want to learn the best way to hash passwords in PHP, scroll to the bottom for the password_hash() function.

Disclaimer

Cryptology is a complicated subject, and I am by no means an expert. There is constant research happening in this area, in many universities and security agencies.

In this article, I will try to keep things as simple as possible, while presenting to you a reasonably secure method of storing passwords in a web application.

What Does "Hashing" Do?

Hashing converts a piece of data (either small or large) into a relatively short piece of data such as a string or an integer.

This is accomplished by using a one-way hash function. "One-way" means that it is very difficult (or practically impossible) to reverse it.

A common example of a hash function is md5(), which is quite popular.

With md5(), the result will always be a 32-character string. But it contains only hexadecimal characters; technically it can also be represented as a 128-bit (16-byte) integer. You may md5() much longer strings and data, and you will still end up with a hash of this length. This fact alone might give you a hint as to why this is considered a "one-way" function.

1	$data = "Hello World";
2	$hash = md5($data);
3	echo $hash; // b10a8db164e0754105b7a99be72e3fe5

Using a Hash Function for Storing Passwords

Here's the usual process during a user registration:

The user fills out a registration form, including the password field.
The web script stores all of the information in a database.
However, the password is run through a hash function before being stored.
The original version of the password has not been stored anywhere, so it is technically discarded.

And the login process:

The user enters a username (or e-mail) and password.
The script runs the password through the same hashing function.
The script finds the user record from the database and reads the stored hashed password.
Both of these values are compared, and access is granted if they match.

Once we decide on a decent method for hashing the password, we are going to implement this process later in this article.

Note that the original password has never been stored anywhere. If the database is stolen, the user logins can not be compromised, right? Well, the answer is: "It depends." Let's look at some potential problems.

Problem #1: Hash Collision

A hash "collision" occurs when two different data inputs generate the same resulting hash. The likelihood of this happening depends on which function you use.

How Can This Be Exploited?

As an example, I have seen some older scripts which used crc32() to hash passwords. This function generates a 32-bit integer as the result. This means there are only 2^32 (i.e. 4,294,967,296) possible outcomes.

Let's hash a password:

1	echo crc32('supersecretpassword');
2	// outputs: 323322056

Now, let's assume the role of a person who has stolen a database and has the hash value. We may not be able to convert 323322056 into 'supersecretpassword', but we can figure out another password that will convert to the same hash value, with a simple script:

set_time_limit(0);
$i = 0;
while (true) {
    if (crc32(base64_encode($i)) == 323322056) {
		echo base64_encode($i);
		exit;
	}
	$i++;
}

This may run for a while, but eventually it should return a string. We can use this returned string—instead of 'supersecretpassword'—and it will allow us to successfully log in to that person's account.

For example, after running this exact script for a few moments on my computer, I was given 'MTIxMjY5MTAwNg=='. Let's test it out:

echo crc32('supersecretpassword');
// outputs: 323322056 

echo crc32('MTIxMjY5MTAwNg==');
// outputs: 323322056

How Can This Be Prevented?

Nowadays, a powerful home PC can be used to run a hash function almost a billion times per second. So we need a hash function that has a very big range.

For example, md5() might be suitable, as it generates 128-bit hashes. This translates into 340,282,366,920,938,463,463,374,607,431,768,211,456 possible outcomes. It is impossible to run through so many iterations to find a collision for an arbitrary hash. However, some people have still found ways to create collisions.

Sha1

Sha1() is a better alternative, and it generates an even longer 160-bit hash value.

Problem #2: Rainbow Tables

Even if we fix the collision issue, we're still not safe yet.

A rainbow table is built by calculating the hash values of commonly used words and their combinations.

These tables can have as many as millions or even billions of rows.

For example, you can go through a dictionary and generate hash values for every word. You can also combine words and generate hashes for those too. That's not all; you can even start adding digits before, after, or between words, and store them in the table as well.

Considering how cheap storage is nowadays, gigantic rainbow tables can be produced and used.

How Can This Be Exploited?

Let's imagine that a large database is stolen, along with 10 million password hashes. It is fairly easy to search the rainbow table for each of them. Not all of them will be found, certainly, but nonetheless... some of them will!

How Can This Be Prevented?

We can try adding a "salt". Here is an example:

$password = "easypassword";

// this may be found in a rainbow table 
// because the password contains 2 common words 
echo sha1($password); // 6c94d3b42518febd4ad747801d50a8972022f956 

// use a bunch of random characters, and it can be longer than this 
$salt = "f#@V)Hu^%Hgfds

// this will NOT be found in any pre-built rainbow table 
echo sha1($salt . $password); // cd56a16759623378628c0d9336af69b74d9d71a5

What we basically do is concatenate the "salt" string with the passwords before hashing them. The resulting string obviously will not be in any pre-built rainbow table. But we're still not safe just yet!

Problem #3: Rainbow Tables (Again)

Remember that a rainbow table may be created from scratch, after the database has been stolen.

How Can This Be Exploited?

Even if a salt was used, the salt might have been stolen along with the database. All the attacker then has to do is generate a new rainbow table from scratch, but this time they concatenate the salt to every word that they are putting in the table.

For example, in a generic Rainbow Table, "easypassword" may exist. But in this new Rainbow Table, they have "f#@V)Hu^%Hgfdseasypassword" as well. When they run all of the 10 million stolen salted hashes against this table, they will again be able to find some matches.

How Can This Be Prevented?

We can use a "unique salt" instead, which changes for each user.

A candidate for this kind of salt is the user's id value from the database:

1	$hash = sha1($user_id . $password);

This is assuming that a user's id number never changes, which is typically the case.

We may also generate a random string for each user and use that as the unique salt. But we would need to ensure that we store that in the user record somewhere.

// generates a 22 character long random string 
function unique_salt() {
    return substr(sha1(mt_rand()),0,22);
}


$unique_salt = unique_salt();
$hash = sha1($unique_salt . $password);

// and save the $unique_salt with the user record 
// ...

This method protects us against Rainbow Tables, because now every single password has been salted with a different value. The attacker would have to generate 10 million separate rainbow tables, which would be completely impractical.

Problem #4: Hash Speed

Most hashing functions have been designed with speed in mind because they are often used to calculate checksum values for large data sets and files to check for data integrity.

How Can This Be Exploited?

As I mentioned before, a modern PC with powerful GPUs (yes, video cards) can be programmed to calculate roughly a billion hashes per second. This way, they can use a brute force attack to try every single possible password.

You may think that requiring a minimum 8-character password might keep it safe from a brute force attack, but let's determine if that is indeed the case:

If the password can contain lowercase and uppercase letters and numbers, that is 62 (26+26+10) possible characters.
An 8-character string has 62^8 possible versions. That is a little over 218 trillion.
At a rate of 1 billion hashes per second, that can be solved in about 60 hours.

And for 6-character passwords, which are also quite common, it would take under a minute.

Feel free to require 9- or 10-character passwords, but you might start annoying some of your users.

How Can This Be Prevented?

Use a slower hash function.

Imagine that you use a hash function that can only run 1 million times per second on the same hardware, instead of 1 billion times per second. It would then take the attacker 1000 times longer to brute force a hash. 60 hours would turn into nearly 7 years!

One way to do that would be to implement it yourself:

function myhash($password, $unique_salt) {
    $salt = "f#@V)Hu^%Hgfds";
	$hash = sha1($unique_salt . $password);
	// make it take 1000 times longer 
	for ($i = 0; $i < 1000; $i++) {
		$hash = sha1($hash);
	}
	return $hash;
}

Or you may use an algorithm that supports a "cost parameter," such as BLOWFISH. In PHP, this can be done using the crypt() function.

1	function myhash($password, $unique_salt) {
2	// the salt for blowfish should be 22 characters long
3	return crypt($password, '$2a$10$'.$unique_salt);
4	}

The second parameter to the crypt() function contains some values separated by the dollar sign ($).

The first value is '$2a', which indicates that we will be using the BLOWFISH algorithm.

The second value, '$10' in this case, is the "cost parameter". This is the base-2 logarithm of how many iterations it will run (10 => 2^10 = 1024 iterations.) This number can range between 04 and 31.

Let's run an example:

function myhash($password, $unique_salt) {
    return crypt($password, '$2a$10$'.$unique_salt);
}
function unique_salt() {
	return substr(sha1(mt_rand()),0,22);
}

$password = "verysecret";
echo myhash($password, unique_salt());
// result: $2a$10$dfda807d832b094184faeu1elwhtR2Xhtuvs3R9J1nfRGBCudCCzC

The resulting hash contains the algorithm ($2a), the cost parameter ($10), and the 22-character salt that was used. The rest of it is the calculated hash. Let's run a test:

// assume this was pulled from the database 
$hash = '$2a$10$dfda807d832b094184faeu1elwhtR2Xhtuvs3R9J1nfRGBCudCCzC';

// assume this is the password the user entered to log back in 
$password = "verysecret";

if (check_password($hash, $password)) {
    echo "Access Granted!";
} else {
	echo "Access Denied!";
}

function check_password($hash, $password) {
	// first 29 characters include algorithm, cost and salt 
	// let's call it $full_salt 
	$full_salt = substr($hash, 0, 29);
	// run the hash function on $password 
	$new_hash = crypt($password, $full_salt);
	// returns true or false 
	return ($hash == $new_hash);
}

When we run this, we see "Access Granted!"

Putting It Together

With all of the above in mind, let's write a utility class based on what we've learned so far:

class PassHash {
    // blowfish 
	private static $algo = '$2a';
	// cost parameter 
	private static $cost = '$10';
	// mainly for internal use 
	public static function unique_salt() {
		return substr(sha1(mt_rand()),0,22);
	}
	// this will be used to generate a hash 
	public static function hash($password) {
		return crypt($password,
					self::$algo .
					self::$cost .
					'$' . self::unique_salt());
	}
	// this will be used to compare a password against a hash 
	public static function check_password($hash, $password) {
		$full_salt = substr($hash, 0, 29);
		$new_hash = crypt($password, $full_salt);
		return ($hash == $new_hash);
	}
}

Here is the usage during user registration:

// include the class 
require ("PassHash.php");

// read all form input from $_POST 
// ... 

// do your regular form validation stuff 
// ... 

// hash the password 
$pass_hash = PassHash::hash($_POST['password']);

// store all user info in the DB, excluding $_POST['password'] 
// store $pass_hash instead 
// ...

And here is the usage during a user login process:

// include the class 
require ("PassHash.php");

// read all form input from $_POST 
// ... 

// fetch the user record based on $_POST['username'] or similar 
// ... 

// check the password the user tried to login with 
if (PassHash::check_password($user['pass_hash'], $_POST['password']) {
    // grant access 
	// ... 
} else {
	// deny access 
	// ... 
}

Using the `password_hash()` Function

Now that we understand the basics of hashing in PHP and how we can use hashes to keep user passwords safe, it's time to learn about the built-in password_hash() function. This function was introduced in PHP 5.5 and serves as a good alternative to crypt().

The password_hash() function has been specifically designed to create secure password hashes. As such, it automatically creates a cryptographically secure salt for all your password hash calls.

This function returns the hashed password as a string. The return value contains information about the algorithm used, the cost, and the salt used for hashing the password. This makes the hash fully self-contained, so it can be read by the password_verify() function to determine if the hash matches a given password.

The password_hash() function accepts three parameters.

The first parameter is the original password string.

The second parameter is the hashing algorithm. There are four possible values:

PASSWORD_DEFAULT which uses the bcrypt algorithm for now. The value of this constant will change over time as newer and stronger algorithms are introduced.
PASSWORD_BCRYPT which uses the CRYPT_BLOWFISH algorithm to generate the hash. The final value is a crypt() compatible hash with the $2y$ identifier.
PASSWORD_ARGON2I which uses the Argon2i algorithm to generate the hash.
PASSWORD_ARGON2ID which uses the Argon2id algorithm to generate the hash.

The last two algorithms are only available if you compile PHP with Argon2 support.

The third parameter is optional and allows you to provide some options such as cost for different algorithms.

Here is an example of using the password_hash() function:

<?php

for($i = 0; $i <= 5; $i++) {
 echo password_hash("1qkjxg2!bxhjwWQJH", PASSWORD_DEFAULT)."\n";
}

/* Outputs:

$2y$10$vCBUBr18IQ.SrckFPbZC/uPN90UUutrw6b9H8T1LYMelMTswGJgty
$2y$10$RoM0MQDrvcDfzeNYb3HnGOn7ISyz5ry8vl/dqbaWJCQhcXJdgXK8y
$2y$10$/osX.LrLn7Jce3szr5wCJOkra74KB0zOQzKVXyzGA6WXncraJqo1W
$2y$10$/t5Hi2QjoMWck9NGMTed7e1RBpAKjUtA4kcJHJoz7qQClj6Yo8Yvm
$2y$10$6knmUnls3lXnDlBVF2hYZOogEnl2pgjrhrcvdg9Obt3c5X/WFnbra
$2y$10$k4ooJoLXzHlL/aA/WCm/9uH1eljb7g/w0Urfla4pVrNmgsYAOXCp.

*/

?>

As you can see, a unique hash is generated even if the same password is fed to the function each time. This is because a unique salt is generated before processing every hashing request.

Another advantage of using the password_hash() function is that it will automatically take care of algorithm upgrades for you. Returning a single string that contains information about the algorithm, its cost, the salt, and the actual hash also simplifies the storage and verification of the hashed passwords.

Conclusion

This method of hashing passwords should be solid enough for most web applications. That said, don't forget: you can also require that your members use stronger passwords by enforcing minimum lengths, mixed characters, digits, and special characters.

This post has been updated with contributions from Monty Shokeen. Monty is a full-stack developer who also loves to write tutorials and learn about new JavaScript libraries.

Understanding Hash Functions and Keeping Passwords Safe

Disclaimer

What Does "Hashing" Do?

Using a Hash Function for Storing Passwords

Problem #1: Hash Collision

How Can This Be Exploited?

How Can This Be Prevented?

Sha1

Problem #2: Rainbow Tables

How Can This Be Exploited?

How Can This Be Prevented?

Problem #3: Rainbow Tables (Again)

How Can This Be Exploited?

How Can This Be Prevented?

Problem #4: Hash Speed

How Can This Be Exploited?

How Can This Be Prevented?

Putting It Together

Using the password_hash() Function

Conclusion

Using the `password_hash()` Function