Password Hashing Methods: A Long Way After Bcrypt

[Man]

The M-209 encryption machine, which was the basis for the first-ever hash function cryptin Unix

It has been 25 years since the hashing algorithm was invented bcrypt(1997), but it is still considered one of the most resistant to brute force hashes.

For several decades now, some experts have been predicting that authentication will be done by keys/certificates. But this has not happened yet. Passwords remain an integral part of information security systems. In fact, they were widely used even before the invention of computers, so such longevity is not surprising.

If we look at history, the concept of computer passwords arose at the dawn of multi-user computing systems, when a way to authenticate and protect data was needed. In the 1960s, the Massachusetts Institute of Technology developed the Compatible Time-Sharing System (CTSS) with password-based account authentication, one of the first such systems in the world. Interestingly, this happened despite the persistent objections of Richard Stallman, who tried to resist the introduction of passwords at MIT in the 1970s. This was recalled by Steven Levy in the documentary book Hackers: Heroes of the Computer Revolution.

However, the true origins of modern password protection can be attributed to the development of Unix and its native hashing function crypt. The original version cryptin Unix (6th Edition) was implemented by Robert Morris and was based on the Hagelin encryption machine (model M-209).

Converter M-209B by Boris Hagelin

The legendary inventor of encryption machines Boris Hagelin was told about on forum. Born in the Russian Empire, this boy studied in Baku and went to further education abroad, where he became famous thanks to the creation of unique encryption machines and the founding of the Swiss company Crypto AG in 1952, for decades the world leader in the cryptographic devices market.

Returning to Unix, specialists in the 70s already realized the problem of too fast execution of the function crypt. In Unix (7th edition), the function was improved by introducing a 12-bit salt and iteration of the Data Encryption Standard (DES) cipher for password hashing. The use of salt resulted in a family of 2¹² different hash functions, and each user randomly selected their password from this family. The purpose of using salt was not only to ensure uniqueness of hashes even for identical passwords, but also to make pre-hash attacks much more difficult. The hashed password with salt was stored in the password file, allowing the system to authenticate users without storing passwords in plain text. It was considered secure

for its time , but the development of computing power and export restrictions on cryptography in the United States paved the way for new password hashing algorithms, such as MD5crypt (1994).

The RSA code, which is prohibited from export from the United States, is printed on a T-shirt as a protest against restrictions on free speech. A citizen dressed in this way had the right to travel abroad and show the T-shirt to foreign citizens.

Concerns about the security of new algorithms led to the developmentcrypt bcryptin 1997. It pioneered the concept of adaptive hashing, making brute-force and dictionary attacks computationally more difficult (the algorithm is secure against future hardware performance gains). Since its introduction in June 1997 as part of OpenBSD 2.1 and its publication by USENIX in 1999, bcrypt it has had a profound impact on the security industry.

The original academic paper describing bcrypt (1999)

Overall, a quarter century of development in hashing functions and the brute-force industry can be summarized in the following table:

	Safety	Adaptable work rate	Memory consumption	Year of release
CRYPT	Not recommended	No	No	1970s
MD5crypt	Not recommended	No	No	1994
BCRYPT	Tall	Yes	No	1999
PBKDF2WithHmacSHA1 (RFC 2898, 2000)	Medium to high	Yes	No	2000
Scrypt (Percival, 2013)	Tall	Yes	Yes	2009
Argon2 (Biryukov and Dinu, 2016)	Tall	Yes	Yes	2015

Comparison of hashing functions and their security. Adaptable coefficient (work factor) means that the CPU load can be increased. Memory-hardness means that in addition to the CPU, the hashing algorithm is scalable in memory

Brute force performance​

Password cracking technologies and hardware have evolved significantly over the past 30 years. Brute force has become much more powerful. It became obvious that password hashing algorithms needed to be adapted to the cost of their work. That is, the algorithm itself should be designed in such a way as to make brute force unprofitable on modern hardware, or even better, with a safety margin for years to come.

To demonstrate this progress, here are approximate estimates of brute force speed on computers of different years, as well as in different programs (Hashcat and John the Ripper). It should be borne in mind that these figures simply demonstrate a general trend; they cannot be directly compared due to differences in hardware and software. For clarity, the figures are published with all digits, without abbreviations to “million” and “billion”.

Year	Hardware, software	Hash format	Brute force speed (passwords per second)
1978	PDP-11/70	crypt in M-209 simulator )	800
1988	VAX 8600	des-crypt in optimization for Morris worm	45
1994	Pentium 60 MHz	MD5 based crypt	29.41
1999	John the Ripper	des-crypt with bit shifting	214,000
1999	John the Ripper	bcrypt with a coefficient of 5	62.5
2018	Hashcat, GPU installation	des-crypt	1,700,000,000
2018	Hashcat, GPU installation	MD5	45,400,000,000
2018	Hashcat, GPU installation	SHA-1	14,600,000
2018	Hashcat, GPU installation	bcrypt with a coefficient of 5	47 200
2018	Hashcat, GPU installation	scrypt	1,400,000
2022	Hashcat, RTX 4090	des-crypt	6,300,000,000
2022	Hashcat, RTX 4090	bcrypt with a coefficient of 5	184,000

It can be noted that over the years, not only the complexity of algorithms has grown, but also the performance of hardware, as well as the efficiency of specialized programs.

For example, over 34 years, the speed of hashing des-crypthas increased from 45 to 6.3 billion per second.

At the same time, the old one bcryptremains one of the most difficult hashes to crack, especially with the maximum complexity coefficient (work factor). Although formally it is considered obsolete, in practice, theoretically, it is quite suitable for use, along with more modern, brute-force-resistant algorithms scryptand Argon2.

Passwords forever​

What's next?

Modern hashing algorithms greatly reduce the effectiveness of brute force. But hash leaks are still a constant threat. On the other hand, the advent of multi-factor authentication (MFA) has shifted the focus to protecting user accounts with additional layers of verification, making passwords less important for security.

In today's world, cloud services are becoming increasingly widespread, where most important data is stored remotely. Simple brute force is ineffective for penetrating such systems, so attackers tend to use vulnerabilities or social engineering.

A quarter of a century later, people still rely on passwords as the main method of protecting computer information. Every year, their complexity (entropy) increases, more complex hashing methods are introduced, but the text passwords/phrases themselves remain.

Source