Today I’d like to talk about passwords. Yes, I know, passwords are the worst, but why? This is the first of a series of posts about passwords, with this one focusing on the origins of our current password systems starting with log in for multi-user systems.

The conventional story for what’s wrong with passwords goes something like this: Passwords are simultaneously too long for users to memorize and too short to be secure.

It’s easy to see how to get to this conclusion. If we restrict ourselves to just letters and numbers, then there are about 2⁶ one character passwords, 2¹² two character passwords, etc. The fastest password cracking systems can check about 2³⁶ passwords/second, so if you want a password which takes a year to crack, you need a password of 10 characters long or longer.

The situation is actually far worse than this; most people don’t use randomly generated passwords because they are hard to generate and hard to remember. Instead they tend to use words, sometimes adding a number, punctuation, or capitalization here and there. The result is passwords that are easy to crack, hence the need for password managers and the like.

This analysis isn’t wrong, precisely; but if you’ve ever watched a movie where someone tries to break into a computer by typing passwords over and over, you’re probably thinking “nobody is a fast enough typist to try billions of passwords a second”. This is obviously true, so where does password cracking come into it?

How to design a password system

The design of password systems dates back to the UNIX operating system, designed back in the 1970s. This is before personal computers and so most computers were shared, with multiple people having accounts and the operating system being responsible for protecting one user’s data from another. Passwords were used to prevent someone else from logging into your account.

The obvious way to implement a password system is just to store all the passwords on the disk and then when someone types in their password, you just compare what they typed in to what was stored. This has the obvious problem that if the password file is compromised, then every password in the system is also compromised. This means that any operating system vulnerability that allows a user to read the password file can be used to log in as other users. To make matters worse, multiuser systems like UNIX would usually have administrator accounts that had special privileges (the UNIX account is called “root”). Thus, if a user could compromise the password file they could gain root access (this is known as a “privilege escalation” attack).

The UNIX designers realized that a better approach is to use what’s now called password hashing: instead of storing the password itself you store what’s called a one-way function of the password. A one-way function is just a function H that’s easy to compute in one direction but not the other.¹ This is conventionally done with what’s called a hash function, and so the technique is known as “password hashing” and the stored values as “password hashes”

In this case, what that means is you store the pair: (Username, H(Password)). [Technical note: I’m omitting salt which is used to mitigate offline pre-computation attacks against the password file.] When the user tries to log in, you take the password they enter P and compute H(P). If H(P) is the same as the stored password, then you know their password is right (with overwhelming probability) and you allow them to log in, otherwise you return an error. The cool thing about this design is that even if the password file is leaked, the attacker learns only the password hashes.²

Problems and countermeasures

This design is a huge improvement over just having a file with cleartext passwords and it might seem at this point like you didn’t need to stop people from reading the password file at all. In fact, on the original UNIX systems where this design was used, the /etc/passwd file was publicly readable. However, upon further reflection, it has the drawback that it’s cheap to verify a guess for a given password: just compute H(guess) and compare it to what’s been stored. This wouldn’t be much of an issue if people used strong passwords, but because people generally choose bad passwords, it is possible to write password cracking programs which would try out candidate passwords (typically starting with a list of common passwords and then trying variants) to see if any of these matched. Programs to do this task quickly emerged.

The key thing to realize is that the computation of H(guess) can be done offline. Once you have a copy of the password file, you can compare your pre-computed hashes of candidate passwords against the password file without interacting with the system at all. By contrast, in an online attack you have to interact with the system for each guess, which gives it an opportunity to rate limit you in various ways (for instance by taking a long time to return an answer or by locking out the account after some number of failures). In an offline attack, this kind of countermeasure is ineffective.

There are three obvious defenses to this kind of attack:

• Make the password file unreadable: If the attacker can’t read the password, they can’t attack it. It took a while to do this on UNIX systems, because the password file also held a lot of other user-type information that you didn’t want kept secret, but eventually that got split out into another file in what’s called “shadow passwords” (the passwords themselves are stored in /etc/shadow. Of course, this is just the natural design for Web-type applications where people log into a server.
• Make the password hash slower: The cost of cracking is linear in the cost of checking a single password, so if you make the password hash slower, then you make cracking slower. Of course, you also make logging in slower, but as long as you keep that time reasonably short (below a second or so) then users don’t notice. The tricky part here is that attackers can build specialized hardware that is much faster than the commodity hardware running on your machine, and designing hashes which are thought to be slow even on specialized hardware is a whole subfield of cryptography.
• Get people to choose better passwords: In theory this sounds good, but in practice it’s resulted in enormous numbers of conflicting rules about password construction. When you create an account and are told you need to have a password between 8 and 12 characters with one lowercase letter, one capital letter, a number and one special character from this set — but not from this other set — what they’re hoping you will do is create a strong passwords. Experience suggests you are pretty likely to use Passw0rd!, so the situation here has not improved that much unless people use password managers which generate passwords for them.

The modern setting

At this point you’re probably wondering what this has to do with you: almost nobody uses multiuser timesharing systems any more (although a huge fraction of the devices people use are effectively UNIX: MacOS is a straight-up descendent of UNIX and Linux and Android are UNIX clones). The multiuser systems that people do use are mostly Web sites, which of course use usernames and passwords. In future posts I will cover password security for Web sites and personal devices.