Alex Davicenko · Follow
5 min read · Jan 7, 2024
--
A popular tool for implementing password hashing in applications with a need for authentication is the bcrypt hash function. It is available in numerous programming languages, most notably Java Script, Python, C#, and C++, and can easily be included in your application in a matter of seconds via pip or npm.
Recalling that a hash function is a function that aims to scramble data in a way such that small variations in the input data result in huge changes in the output, bcrypt is an example of such a hash function. Often, hash functions are used to securely store passwords in server databases, as they, in theory, are impossible to reverse without checking every single possible input. Passwords are hashed and stored in the database with the idea that if the database is stolen, i.e., the data is copied onto a device belonging to an attacker, they would not be able to read the client passwords in plain text. This would result in the attacker not being able to attempt to use those credentials to access other platforms and services that the client is signed up for. For example, if you use the same password for every service you sign up for, if each of those services stores your password in plain text, an attacker could gain access to the database of one of them and, in turn, be able to access all of your other accounts.
On top of being a hash function, bcrypt incorporates a vital procedure, formally known as password salting, as part of the algorithm. This intriguingly named concept revolves around the idea of preventing rainbow table attacks. In essence, rainbow table attacks are when the attacker precomputes a table of many different passwords together with their hashes allowing to quickly identify multiple users with the same password. This is can be combated by adding a small ‘salt’ to every password making the hash different for every password, yet consistent for every password, salt combination. However, now the salt needs to be stored in the database as well. The bcrypt algorithm takes in as parameters a 72 byte password, a 16 byte salt and a cost.
In the event of an attacker gaining access to the database records, if our passwords are hashed, no matter what sophisticated method is used, a large number of hashes will have to be computed by the attacker. Therefore, making the hashing algorithm slow and require as much computation as possible is optimal for decreasing the chance of clients being negatively affected by a data breach. However, slow hashing algorithms with a constant speed of execution run the risk of becoming too fast over the course of decades as advances in hardware become more pronounced. The way bcrypt implements its slow, sometimes referred to as expensive, step is through the cost parameter. As we will later see, the cost parameter has an exponential effect on the time it takes to hash a password, meaning that increasing the cost by 1 roughly doubles the number of execution steps.
The mechanism that allows this to happen is best understood when looking deeper into the principles of operation of the bcrypt algorithm. Most commonly, bcrypt can be broken down into two parts. During the first part, the password and salt are mixed into what are known as the S and P boxes. In the second stage, the blowfish encryption algorithm encrypts an arbitrary string (predefined in the source code) using those S and P boxes. This process is referred to as key expansion.
The structure of the S boxes consists of a 256x4 2D array of 32-bit integers, and the structure of the P boxes is an 18-length array of 32-bit integers. In summary, the first phase of bcrypt goes as follows:
- Salt is randomly generated using the language’s standard library.
- S and P boxes are randomly filled with consistent arbitrary data, such as hexadecimal pi digits.
- The password and salt are mixed into the S and P boxes, 2 raised to the power of the cost times.
I am intentionally leaving the idea of’mixing’ in the password and salt into the S and P boxes vague, as the code itself for this step is quite involved. Interestingly, the same encrypt function will help us with the mixing stage as well as the second phase of the bcrypt algorithm. In the second phase, we simply:
- Encrypt an arbitrary string (that is kept consistent and defined in the source code) using blowfish encryption in ECB mode. ECB mode simply means that the blowfish encryption is only defined to take a certain amount of bits, referred to as blocks. For a large input to be encrypted, it must be split into blocks and encrypted separately. In this case, the arbitrary string is 24 bytes long and needs to be split into 8-byte blocks.
- Concatenate the information about the hash and return it.
Annoyingly for the developer, bcrypt uses the following base-64 encoding:
./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789
Meaning our 16-byte salt is stored as 22 (21.33) base-64 characters and our 24-byte hash is stored as 31 base-64 characters. At the beginning of the bcrypt hash, we can see information about the type of algorithm (e.g., blowfish of SHA-512) used and the cost. This storage format is convenient as, over time, the value of the cost parameter will need to go up. Similarly, the algorithm used to encrypt the arbitrary string may change, and all of this is simply reflected in this one string.
There is a lot to look at in the world of bcrypt and, more generally, cryptography and hashing. For those of you looking to implement bcrypt for a personal project, some good resources are:
