Password-based authentication seems simple. You whisper a code word to a gatekeeper with good memory (a website or application’s login page), he matches it to your identity after just a moment’s thinking time and opens the gate to the castle (your data). Yet the secure handling of such sensitive information requires much more complex design.

Directly storing the password in a database won’t guarantee security because the consequences of a data breach are just too high: attackers will be able to log in as users if even a few leaks out. Using a function to transform the password seems like a good fix. Due to its purpose, the function should not be reversible; to make storage and transmission easier, it should have a fixed length return value; and because a password will be authenticated many times, it should return the same value for the same input. A family of functions, called hash functions, fits all three requirements. They return hashes, pseudorandom-looking binary numbers of pre-determined size. It is infeasible to recover the original input from its hash value alone. Instead of raw passwords, the user database can store their hashes instead. To make sure identical passwords don’t produce the same hashes, a randomly generated string unique to each user (a “salt”) is combined before hashing and stored with the hash in the database. This means an attacker can’t precompute the hash values of common passwords and simply match them to database entries.

Hashing algorithms have many uses other than protecting passwords, from detecting file corruption to building efficient lookup tables. While each has the same input (data of any length) and requires the same type of output (a fixed length binary number), the desired performance characteristics are vastly different. Programmers who use general-purpose hash functions want to take advantage of multiple CPU cores or a GPU, if available, and calculate the hash as fast as possible with minimal computational resources. So do attackers brute-forcing passwords.

Therefore, password hashing functions must be designed with the opposite goal to nearly every other algorithm: use as much processing power and memory as possible and be hard to speed up with parallel processing.

Earlier algorithms increase computational requirements by applying a hash function to the input many times. PBKDF2 (Password-based Key Derivation Function 2) passes the password to a hash function, combines the output with the original password, then hashes it again. The process can be repeated for as many times as required, and each result is combined with bitwise XOR (for two series of binary digits, output 1 if corresponding bits differ, 0 if they are the same) to obtain the final output.

While this takes a lot of processing resources (which the user can easily increase through iteration count), the algorithm uses a constant, small amount of memory, as each iteration only depends on the original password and the immediately preceding hash. Algorithms such as PBKDF2 are now vulnerable to brute-force attacks by GPUs, which can allocate a small amount of memory and a trial password for each of its thousands of cores to compute simultaneously.

Security experts have been actively mitigating this threat. More recently, a common strategy is to initialise a large amount of RAM, divide it into blocks, then fill each block in a way that depends on a previous block. This limits the effectiveness of using multiple processor cores to fill blocks simultaneously and means every block must be kept in memory, because a future block may need its content. RAM is expensive, so an attacker is forced to spend more on hardware if they want to test multiple passwords at the same time.

After the memory is filled, two blocks can be mixed to one with bitwise XOR or by arithmetic operations such as addition. The order in which blocks are mixed is also determined by the content of other blocks. In scrypt, a widely used password hashing algorithm, the index of the block to be mixed is the remainder of the current block value divided by the block count. These complex dependency chains make the process hard to parallelise. The mixing function is often the crux of the entire algorithm, as most of the computational resources go towards mixing blocks, which is a process that is difficult to optimise.

Password hashing functions are often based on a general-purpose hashing algorithm. For example, Argon2id, the winner of the Password Hashing Competition held in 2015, generates the first blocks of its initial state by passing its inputs through the BLAKE2b hash function. Although BLAKE2b is considered secure, it was not designed to be excessively hard to compute. By iteratively applying components of BLAKE2b and mixing the outputs, Argon2id makes it so.

Computers increase in power and memory capacity every year, while a user may use the same password for decades, so password hashing algorithms should stay computationally expensive with regards to new hardware. To do this, they have additional inputs specifying time and memory usage, tied to number of mixing operations and size of allocated RAM respectively. To deter attackers, users should set these as high as possible while still processing legitimate authentication requests in reasonable time. The requirements of password hashing algorithms represent a unique challenge in computational complexity. It is not a case of simply minimising resource use and execution time; instead, it’s about hitting the sweet spot where legitimate users can quickly obtain hashes, yet attackers cannot efficiently do this in bulk. The best solution is to make the algorithm flexible and trust the user to specify suitable parameters for their security needs.

Sources

Reading is open to everyone. Log in only to take part.

Reader discussion

Join the conversation.

0 comments

No comments yet. Start the discussion.