5.4 Password-based authentication

Password-based authentication is arguably the most common way used to authenticate humans to electronic devices. An average internet user has about 70 to 80 passwords to identify themself to websites they visit and services they use [130].

Most existing password schemes use time-invariant passwords. The user initially chooses a string of characters, typically short enough so they can memorize it. From this point in time onward, that password is associated with the user ID, for instance, the username or the email address entered during registration.

The password is a secret shared between the user and the electronic system. Hence, from a cryptographic perspective, password-based authentication is a symmetric mechanism (it is based on a common secret) that provides unilateral authentication. The authentication is unilateral because the user authenticates themself to the system, but the system – an electronic device or a web service – does not authenticate itself to the user. Note, however, that in most instances of password-based authentication, a secure channel is created between user and server via TLS before the user sends their password, and this includes server authentication.

To access the electronic system, the user enters their user ID and password. The user ID is the claimed identity, and the password is the evidence to prove that claim. The system looks up the given user ID and checks whether the password provided by the user matches the password stored (in whichever form) on the system. The fact that the user knows the password – which is established by the user revealing the password to the system – is accepted by the system as proof of the user’s identity. As a result, the system grants the user access to certain system resources, such as a computer account or web service.

In its most basic form, password-based authentication therefore takes the form depicted in Figure 5.3. The claimant sends their identity to the verifying system, along with a matching password. The system then checks whether the provided password indeed belongs to the claimed identity. Based on the result of this check, the system grants certain rights to the claimant. For example, after a successful login at amazon.com, you get the right to inspect your previous orders. This is called authorization and can be seen as an advanced kind of security service built on top of entity authentication.

Figure 5.3: Working principle of password-based authentication

Note, however, that there are important questions left open in this scheme: how do we protect the password on its way from the user to system? How is the password stored at the system’s site in a secure way? We will return to these questions shortly, but first, a bit of history.

5.4.1 Brief history of password-based authentication

Password-based authentication was introduced in the early 1960s when the first time-sharing systems, such as the famous Compatible Time-Sharing System (CTSS) and, later on, Multics, were developed at the Massachusetts Institute of Technology.

A key problem the designers of these systems faced is that they – unlike earlier mainframe computers – were used by multiple people, each having their own private files. To protect access to these files, an authentication mechanism had to be added, and passwords were chosen for their simplicity and low usage of computing resources [116].

From these early time-sharing systems, passwords found their way into operating systems such as Unix, BSD, and Xenix as well as their many derivatives, such as SunOS, AIX, FreeBSD, Solaris, and Linux. Eventually, password-based authentication established itself as the main authentication method in IT systems.

Although passwords have many well-known, serious security problems (see the Disadvantages of password-based authentication section later in this chapter), they remain the dominant authentication mechanism on the internet and, in general, in IT systems [81] since they are easy to implement and have relatively good usability.

The diversity of technical systems and the usability of authentication, especially for non-technically-savvy users, are prime examples of the many barriers preventing the move beyond alphanumeric passwords [81].

IT systems that require user authentication are very heterogeneous, ranging from embedded smart home appliances to personal computers, tablets, and smartphones to web services and social media sites. To date, no other alternative authentication solution covers all these systems and services.

Moreover, passwords are conceptually simple and therefore usable even for people without a significant technical background. Stronger authentication mechanisms, such as two-factor authentication or the use of dedicated hardware keys, require much higher technical proficiency and put additional effort on the user.

5.4.2 Storing passwords

As early as 1977, the Multics Security Evaluation report by US Airforce’s Electronic Systems Division [54] identified the login password file of any operating system as an attractive target because the information contained in this file enables undetected impersonation attacks and, as a result, a long-term exploitation of the system.

This attack vector was deemed especially critical if exposed to attackers who are not always authorized users of the system. For such attackers, obtaining a legitimate user’s password provides an entry into the system that would not exist otherwise. The report [54] also considered the possibility of passwords appearing in memory dumps and concluded that password files must be protected.

In the early 1970s, Needham [202] was the first to note this security weakness and therefore proposed to store encrypted passwords together with the user ID. Needham’s proposal included the use of a one-way function as there was no need to decrypt the passwords since the password supplied by the user must only be encrypted and compared to the ciphertext of the password stored for that user on the system.

The rationale for this approach was that even if an attacker could get hold of the file with encrypted passwords and their user IDs, it would be impossible for her to compute the plaintext passwords from the ciphertexts.

In Chapter 4, Encryption and Decryption, we briefly introduced the concept of one-way functions. These functions are also referred to as hash functions, and we are going to cover them in detail in Chapter 11, Hash Functions and Message Authentication Codes. For now, it is sufficient to recall that these functions are easy to compute but computationally infeasible to revert. Roughly speaking, this means that given some input x and a hash function f, it is easy to compute the hash value y = f(x), but it is impossible to efficiently obtain the original input x given the hash value y.

Modern operating systems such as Linux use hash functions to store the hash values of passwords rather than the passwords themselves. The rationale is that even if an attacker gets hold of a hashed password, they cannot use it to log in as the victim because the password system requires the plaintext password. Moreover, because a hash function is a one-way function, the attacker should not be capable of obtaining the original password from its hash value.

However, it turns out that this is still not sufficient to protect passwords against practical attacks. While it is impossible to invert a hash function, Eve can employ a method known as dictionary attack. She can simply compute hash values for all words (or word combinations) in a dictionary – which can also be a list of compromised or common passwords – and compare them to the stolen hash value of a password.

However, simply computing the hash values of all possible words of a given length formed of 64 characters (a-z, A-Z, 0-9) and storing the hash values along with the words would result in huge files that are difficult to handle. But in a so-called rainbow table [134], only the results of repeatedly hashing the most common passwords are stored in so-called hash chains (actually, it is enough to store only the starting value s and end value e for each chain, as the intermediate values can be easily re-computed if needed).

We will discuss the details of an attack based on rainbow tables a bit later in Section 19.7 of Chapter 19, Attacks on Cryptography. But basically, the attack works like this.

Suppose Eve has found the value y = hash(x) in a stolen database and wants to find a matching preimage x. She creates a hash chain of her own starting with y and checks whether one of the resulting hash values coincides with one of the end values e stored in the rainbow table. This means that there is a high probability that y = hash(x) is contained in the hash chain belonging to e.

Suppose that the hash chain ending with e starts with s. Eve then re-computes the hash chain, starting with s until she reaches the value y. The preceding value x in the chain has y as its hash value and will therefore be accepted as the password, even though it may not be the same as the original password.

This technique is known as a time-memory tradeoff. In this case, we are saving storage space by sacrificing some computation time that is needed to re-create the hash chains. In any case, it seems that by using rainbow tables, Eve would be able to break short or simple passwords that can be found in dictionaries.

There is, however, a relatively simple remedy against pre-computed hash tables: password systems used in practice employ a so-called salt, a random string that is freshly generated for each new password. The salt is hashed together with the password and stored in cleartext, together with the resulting hash value and the corresponding user ID. Salting does not make dictionary attacks impossible, but it makes them much harder because for every password, the attacker has to go through the hashing effort anew and cannot rely on pre-computed tables.

The Linux operating system stores the hashed passwords along with their salts and the user IDs in the /etc/shadow file. There are various algorithm options for the hash algorithm. The hash algorithm used is indicated numerically after the user ID (see Figure 5.4).

Figure 5.4: The etc/shadow file in Ubuntu Linux

In Figure 5.4, the alice entry 6 means that the SHA-512 algorithm was used for hashing. The value elkQzDDD is the salt. The 512-bit hash value follows thereafter.

Meanwhile, there are also other schemes, such as PBKDF2 [96], which were originally invented to derive a symmetric key from a password, but which may also be used to verify a password in a secure way.

5.4.3 Disadvantages of password-based authentication

In the previous section, we learned of several disadvantages of password-based authentication related to password storage. It turns out that passwords have even more drawbacks related to usability, time invariance, and human psychology.

From a usability perspective, the user must be able to correctly enter the password and, thus, successfully authenticate themselves on the system with high probability. This is, of course, easy to achieve if the user chooses a short and easy-to-remember password such as iloveyou or 1234.

However, as the Have I Been Pwned (HIBP) online service [83] will tell you, iloveyou has appeared 2,330,348 times in past data breaches and is therefore an utterly insecure password; it is certainly in every password dictionary, and its hash value is in every rainbow table you can download from the internet.

Choosing a strong password, such as 0(a<*ZS>jBUvNLym?oIp8d!PN4, increases security but also makes it much more likely for the user to mistype while entering their password. This – as well as the time needed to enter a complicated character string – turns password-based authentication using strong passwords into a hassle for the user.

Moreover, strong passwords are not only error-prone and time-consuming to enter, but also difficult for humans to memorize. As a result, users either choose a short but insecure password or a complicated, secure one that they write down, preferably in an easily accessible place such as on a sticky note. This way, passwords get exposed to potential attackers in physical proximity, for example, in a co-working space.

Users also tend to choose passwords based on everyday words or popular phrases that they can easily remember. Many passwords therefore have low entropy and can be easily cracked using dictionary attacks, which we discussed earlier in this chapter [7].

Passwords can also be stolen using social engineering attacks, phishing emails, malware, key loggers, and man-in-the-middle attacks. According to recent statistics from the cybersecurity industry [142], nearly 98% of cybersecurity attacks rely on social engineering, the most popular method being to deliver phishing emails.

On a more fundamental level, many of the security weaknesses of passwords result from them being time-invariant. If Eve can trick Alice into disclosing her password – whether by using a social engineering attack, by eavesdropping on Alice while she enters it, or by cracking a leaked password file – there is nothing Alice can do to restore her security. Eventually, Alice might, of course, try and change her password. But even this might fail because Eve already has changed the password to something Alice does not know. In the instance of time when a password is compromised, its time-invariant nature immediately allows Eve repeated unauthorized access to Alice’s account [81].

Taken together, these drawbacks make passwords a form of weak authentication. The good news is that instead of relying on passwords, we can use cryptographic protocols for entity authentication that avoid most of these drawbacks and, as a result, offer strong authentication.