Bcrypt and a Short History of Password Hashing
As the creator of the widely-used bcrypt password hashing library, Niels Provos finds it surprising that we, the people on the internet, still rely heavily on passwords. This was the first time I even considered something better could exist.
The following article is a brief history of password hashing and the password cracking software keeping pace with the algorithms. Before password hashing, passwords were just stored in plaintext in password databases. We’ve come a long way, yet there are many miles still cover. Niels Provos, creator of bcrypt, wrote a fascinating blog post for Usenix which included his expertise, advice, and predictions for the future.
Password hashing started with Unix, like most things do. Crypt is Unix’s hashing function. Robert Morris released Crypt in Unix’s sixth edition. Crypt was based on the Hagelin cipher machine (M-209). Crypt was never without issues. Developers re-released crypt in the seventh edition with a 12-bit salt and an iterated on Data Encryption Standard (DES) cipher to create a hash from the user’s password. Salt created a family of 2^12 distinct hash functions, with each user randomly drawing from this pool for their password.
With the introduction of salt, which prepends a has with a random string, passwords were always unique even in the case of identical original passwords and precomputed hash attacks were impeded. This was the end of plaintext password storage. Now the salt and hashed passwords were stored in the password file for user authentication. Though Crypt was groundbreaking at the time, it eventually became obsolete.
Bcrypt
Password hashing back in 1997 wasn’t cutting it. The internet was starting to take flight, home computer rooms were springing up everywhere, and data breaches followed suit. In response, Provos wanted to create, “an algorithm designed to resist the rapid advancements in computational power.” It worked. We still use bcrypt.
A key contribution to bcrypt came from David Mazieres’, who introduced the adjustable cost factor. The adaptive hashing that makes brute force and dictionary attacks increasingly resource-intensive was the result of the adjustable cost factor.
This means bcrypt can keep pace with computing power advancements. Memory-hardness and adjustable parallelism were created to counter password guessing on specialized hardware such as GPUs. Memory hardness increases the password guessing because it requires a substantial amount of memory for each guess. Adjustable parallelism allows the algorithms to make use of multiple processing cores, further increasing the computation cost and reducing the efficiency gains through guessing passwords in parallel.
Comparison table of password hashing functions and their security over time (Usenix)
Today’s Hashing Landscape
We’re a long way away from the days of plaintext password storage. Now, with all this fancy new tech, hacking requires a few more steps. For someone to steal a password, they have to guess the password, hash it correctly, and compare it against the encrypted password database. But to the surprise of probably no one, humans are predictable. Predictable password slightly decreases the complexity in password guessing. There are password-guessing tools that bank on the predictability by marketing their ability to guess common passwords and compare them with hashed passwords. For those of you using pas$w0rd for multiple sites, this is for you.
And sure, hashing is getting better, but so is cracking. And we’re not taking about some guy in his mom’s basement, although I’m sure there are many. These tools are nothing to scoff at. Password cracking tools are growing exponentially. What was once 45 passwords per second is now 6.3 billion passwords per second.
- 1978: PDP-11/70 (M-209 simulated crypt) → 800 passwords/second
- 1988: VAX 8600 (Morris-worm optimized des-crypt) → 45 passwords/second
- 1994: 60MHz Pentium (MD5-based crypt) → 29.41 passwords/second
- 1999: John the Ripper (bitsliced DES-crypt) → 214,000 passwords/second
- 1999: John the Ripper (bcrypt with work factor 5) → 62.5 passwords/second
- 2018: Hashcat (des-crypt on a GPU-based rig) → 1.7 billion passwords/second
- 2018: Hashcat (MD5 hashes on a GPU-based rig) → 45.4 billion passwords/second
- 2018: Hashcat (SHA-1 hashes on a GPU-based rig) → 14.6 billion passwords/second
- 2018: Hashcat (bcrypt with work factor 5 on a GPU-based rig) → 47.2 thousand passwords/second
- 2018: Hashcat (scrypt on a GPU-based rig) → 1.4 million passwords/second
- 2022: Hashcat (des-crypt on an RTX 4090 GPU) → 6.3 billion passwords/second
- 2022: Hashcat (bcrypt with work factor 5 on an RTX 4090 GPU) → 184 thousand passwords/second
Where Are We Going?
The cat-and-mouse game continues on. Modern password hashing reduced the effectiveness of brute-force password guessing but it doesn’t end there. Now there’s password stuffing, where attackers use previously leaked credentials to gain entry. Tools such as rate-limiting, captchas (wow, they do serve a purpose), and multifactor authentication (MFA) help greatly in deterring attacks. Cloud services now mean there’s much critical data stored and processed remotely. It’s as important as ever to keep secured entry secure.
What now? Why are there still breaches and what can we do? It’s time to take a look inward. Provos says the problem is us. Well, he elegantly stated, “most security challenges have technological solitons to sufficiently address them and the main problem when it comes to reducing data breaches boils down to human factors and the cost of adopting existing security technologies.” Different people play different roles. There’s the company that cheaps out on top-notch security in favor of more bells and whistles elsewhere. Insider risk was the other category. This included social engineering, disgruntled employees, and ignorance. Lastly, there’s a skills gap.
Conclusion
Passwords are an integral part of our digital lives. Their ease of deployment, creation, and revocability make them a convenient choice. But they’re risky. Be smart, use at your own risk, and for the love of all things good in this world, don’t use any password that has the word password in it.
