How password encryption came about

Many know about the main developers of Unix — Ken Thompson and Dennis Ritchie. But a special role belongs to their colleague, cryptographer Robert Morris, whose contribution was significant:

• the first and several subsequent versions of the mathematical library;

• many interesting applications for text processing, such as typo and others;

• a number of programs crypt, which were supplied with early versions of Unix;

• a password encryption scheme that is still fundamentally applied today.

The history of the creation of the password mechanism (with encryption) is particularly interesting because Morris and Thompson laid the foundation for modern information security. They developed and implemented the basic principles of encryption and secret storage.

This story is described in the historical article by Ken Thompson and Robert Morris “Password Security: A Case Study” from 1978, mentioned in the book by Markoff and Hafner “Cyberpunk: Outlaws and Hackers on the Computer Frontier” (1991) and in Dennis Ritchie's memoirs, a direct participant in those events. Dennis Ritchie is known as the co-author of the C programming language and the Unix OS. He also assisted Morris in various cryptographic projects, and the joint decryption of the cipher machine M-209 (also known as CSP-1500 and C-38) he called “one of the most interesting things he did and saw.”

In the scientific article, Thompson and Morris describe the main approaches to developing the password encryption scheme and the architecture of the system that resulted.

Development Principles

Here are some principles that were used in the development.

• Contests. To create a maximally secure system, the authors constantly held contests for new attack methods ("bad guy") as well as for new defense methods against these attacks ("good guy"). The reasons for creating specific mechanisms become clearer when considering potential attacks.

• Usability. The main goal was "to ensure security with minimal inconvenience to users." If a system administrator wants to leave a completely open system without passwords or introduce passwords only for certain users, they can do so.

• Rights. The system must not only prevent unauthorized users from entering but also ensure that users who are already logged in cannot perform actions they are not authorized to do. For example, the "superuser" (root) password is particularly critical because such a user has all types of permissions and unlimited access to all resources.

The creators of Unix concluded that "the security of the password encryption algorithm presents an interesting intellectual and mathematical challenge, but this is just one tiny facet of a very large problem." Practically, physical security of the computer, communication channel, and physical control over the computer itself is much more important. Most importantly, tracking the actions of former employees is crucial, as they are no longer under direct control and may possess insider information about the system, resources, and access methods.

"Good system security implies a realistic assessment of risks not only from intentional attacks but also from accidental authorized access and unintentional disclosure of information."

First Scheme

Initially, Unix was implemented with a passwords file that stored the passwords of all users in plain text. This method developed historically but was extremely insecure.

The obvious solution is to encrypt the passwords, placing only the encrypted form in the passwords file. When a user logs in, the password is encrypted and compared to the encrypted version in the file. If they match, the login attempt is accepted. This scheme was first described in Wilkes' book "Time-Sharing Computer Systems" published in 1968.

It remained to choose an encryption method. At that time, a convenient and high-quality encryption program was accidentally available in the system. It simulated the cipher machine M-209, which was used by the US Army during World War II.

The M-209 program turned out to be quite suitable. In it, the password was used not as text for encryption, but as a key, and with this key, a constant was encrypted. The encrypted result was entered into the password file.

The authors explored the possibilities of brute force and noted that people often choose short and simple passwords that are easy to remember, from a limited set of characters (for example, only lowercase letters), and often choose words or names. This human habit significantly facilitates the search for the key.

A critical factor is the amount of time required to encrypt the password and verify the result: on the PDP-11/70 computer, it took about 1.25 milliseconds. Checking the encrypted test password against all passwords in the file takes no more time.

This historical work by Morris and Thompson published the first table on brute force timing:

Ultimately, protection against unauthorized disclosure of passwords with such a system is impossible, as the disclosure of one password reveals the scheme and the passwords of all other users. The password file is written to magnetic tape for backup, so anyone can read it after the scheme is disclosed.

Improvements

Slower Encryption

Obviously, the first encryption algorithm used was too fast. The emergence of the new DES encryption algorithm from NIST helped significantly. DES ciphers are hard to reverse by design, plus it is extremely slow when implemented in software.

DES was implemented and used as follows: the first eight characters of the user's password are used as the key for DES; then the algorithm is applied to encrypt a constant. Although initially the constant was equal to zero, it is easily accessible and can be tied to the hardware. Then the DES algorithm is iterated 25 times, and the resulting 64 bits are repackaged into a string of 11 characters.

Less Predictable Passwords

The password input program has been modified to encourage users to use more complex passwords. If a user enters a letter-only password shorter than six characters or an alphanumeric password shorter than five characters, the program prompts them to enter a longer password.

Salt

The password program generates a 12-bit random number (using real-time clock) and adds it to the entered password. The combined string is then encrypted, and the 12-bit random number (referred to as salt) and the 64-bit encryption result are written to the password file.

When the user logs in later, the 12-bit number is retrieved from the password file and added to the entered password. The encrypted result is compared with the stored 64 bits in the password file, as before.

With this modification, using a pre-prepared encrypted dictionary, which previously cracked new passwords in milliseconds, has become impractical.

Furthermore, it becomes virtually impossible to determine whether a person has used the same password on two or more systems.

Protection Against Timing Attacks

To successfully log into Unix, a valid username must be entered, followed by the correct password. When the slow DES algorithm was first implemented, encryption was performed only if the username was valid; otherwise, there was no encrypted password to compare with the entered password. As a result, the response was delayed by about half a second for a valid username but was instantaneous for an invalid one. An attacker could learn whether a specific username was valid. The routine was modified to perform encryption in any case.

Conclusions

Experience has shown surprisingly sophisticated attempts to penetrate remote access systems. Therefore, password protection requires special attention.

It is essential to remember that the system operates in a hostile environment. The authors emphasize that it is useless to hide the system's operational features. On the contrary, they made the encryption algorithm public and invited anyone interested to attack, believing that this approach would minimize future problems. The approach turned out to be successful.

More than half a century has passed since then, but the conclusions of the Unix developers remain relevant to this day.