Brief history of password-based authentication 2 – Entity Authentication
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.