The M-209B encryption machine became the prototype of the first Unix utility for encrypting passwordscrypt
Stealing password databases from hacked systems is a common problem. It was especially acute in the early years of Unix development, when passwords were stored in clear text. A leak of such a database meant a complete compromise of the system.
The problem was solved by the world's first hashing utility, crypt, in the 70s. Since then, passwords have ceased to be stored in clear text; hashes were stored in the database. According to official documentation,crypt(3)up to the sixth edition, the utility used code from an emulator of the M-209 encryption machine, which the American army used during World War II. In this system, the password was used not as a ciphertext, but as a key that encrypted a constant. Ken Thompson, Dennis Ritchie, and other creators of Unix thought that this was a reliable approach. It turned out otherwise.
It soon became clear that checking an encrypted password against all passwords in the database was performed at the speed of hashing one password (1.25 ms on a PDP 11/70), which was a clear architectural flaw in the system. Therefore, in the late 1970s, starting with the seventh edition crypt(3), they switched to a one-way cryptographic function based on the DES block cipher.
It also quickly became clear that people are extremely predictable in choosing passwords. And various tools appeared that allowed you to guess common passwords and compare them with hashed values in the database. As a rule, these tools use a combination of dictionary attacks, brute force, and other methods to guess potential passwords and compare them with stored hashes.
The creators of Unix tried in every possible way to make it more difficult to crack passwords. Already in the late 1970s, they modified the password entry program in such a way as to encourage users to choose more complex passwords. In addition, salt was first used in hashing: the first time a password was entered, the program generated a 12-bit random value and added it to the password. The next time the password was entered, this value was retrieved from the database along with the password and automatically added to it in the input field.
File fragment /etc/passwd(1983). The first two characters are the salt (12-bit), then 11 characters of the hash (64-bit), source
Then, in the late 70s, the first chips for hardware acceleration of DES appeared.
First software for brute force
The first password cracking programs appeared immediately after system administrators started hashing them with the aforementioned Unix utility cryptin the 70s. It is known that already in 1978, emulators were launched on PDP-11/70 computers cryptto try various hash options at a speed of about 800 passwords (hashes) per second.The first information security tools with a password cracking or verification function were:
- COPS (Local Unix System Audit with Weak Password Detection)
- Crack
- Cracker Jack
- goodpass.c and CrackLib (later included in passwd, yppasswd, etc.)
- npasswd
Over time, the tools became more efficient. Soon, John the Ripper, developed by Solar Designer, became the leader in technological innovation . But with the advent of powerful GPUs, Hashcat took over the leadership, managing to use the capabilities of graphics processors more effectively. Interestingly, the first brute force on GPUs was implemented by the Russian company Elcomsoft (Andrey Belenko).
In addition to them, popular tools include L0phtCrack and Hydra.
Over thirty years, brute force methods and hardware have evolved significantly, which has led to a significant increase in productivity , as can be seen in the table below.
| Year | Platform | Software | Heshi | Performance (hashes per second) |
|---|---|---|---|---|
| 1978 | PDP-11/70 | emulator | crypt | 800 |
| 1988 | VAX 8600 | emulator | DES-crypt | 45 |
| 1994 | Pentium 60 MHz | emulator | DES-crypt с MD5 | 29,41 |
| 1999 | John the Ripper | DES-crypt | 214 out. | |
| 1999 | John the Ripper | bcrypt with working factor 5 | 62,5 | |
| 2018 | GPU rig | hashcat | DES-crypt | 1.7 billion |
| 2018 | GPU rig | hashcat | MD5 hash | 45.4 billion |
| 2018 | GPU rig | hashcat | SHA-1 hashes | 14.6 billion |
| 2018 | GPU rig | hashcat | bcrypt with working factor 5 | 47.2 thousand. |
| 2018 | GPU rig | hashcat | script | 1.4 million |
| 2022 | RTX 4090 | hashcat | DES-crypt | 6.3 billion |
| 2022 | RTX 4090 | hashcat | bcrypt | 184 thousand. |
md5()With the increase in CPU and GPU performance, it has become clear that it is important to choose a specific hashing algorithm to make brute force attacks more difficult (slower). Many web developers used the unsalted built-in PHP function in the 90s , but since 2007, support has been added phpass(bcrypt), so the industry has been gradually switching to stronger hashing algorithms automatically. The average password length has also been gradually increasing. According to statistics, it increased from 4.4 characters in 1989 to 7.9 characters in 2009 (see "The Science of Guessing: Analyzing an Anonymized Corpus of 70 Million Passwords", 2012 IEEE Symposium on Security and Privacy).
It can be assumed that with the widespread use of password managers in the second half of the 2010s, password lengths have increased even more.
New hashing algorithms are being developed to be as CPU, GPU, and memory-unfriendly as possible, to slow down the computation on any device, including FPGA and ASIC.
However, password cracking programs are also not stopping their development and are introducing new methods to improve their efficiency. Cloud platforms with the ability to scale the load almost indefinitely within a data center have become a great help. Some organizations that specialize in brute force have even built their own data centers so as not to rely on third-party clouds.
Source
