As GNU/Linux system administrators, we are often confronted with adding user accounts on the system, deleting user accounts, and modifying existing user accounts. At times, this can be a time consuming process. Further, keeping user accounts synchronized between machines, if not using a directory service, can be a bit of a pain. Have you ever looked at, or spent some time pouring over the /etc/shadow file? Curious what that hashed password is all about? I've got your answer.
Before I begin, however, let make take a couple seconds to explain what this post is and is not about. This post is all about learning about shadowed passwords on GNU/Linux. This post is not about learning how to implement different shadowed algorithms on your distribution, the pros and cons of each algorithm, or the mathematical details behind them. This post serves mainly as an informative post regarding the shadowed password itself.
Also, I need to declare a couple of definitions:
- shadowed password: A password stored in a database that is only readable by the root user on a Unix or Linux machine. Unix didn't implement shadowed passwords until 1988 with AT&T SystemV R3.2 and BSD 4.3 Reno in 1990.
- salt: A random string of text that is used as a seed to build an encrypted hash. Passwords on Unix and Linux are hashed with this salt as a seed. The salt is passed to the hashing algorithm as an argument.
Let's familiarize ourselves with the entire syntax, start to end, of the /etc/shadow file. Then, we'll get dirty digging into the nitty-gritty of the actual password, and how authentication on the machine works. So, first the overall syntax.
As you've probably noticed, the /etc/passwd and /etc/shadow as well as /etc/group and /etc/shadow (if that exists) are colon-delimited files. This means, that columns exist by using the colon as a separator, exactly the same way commas would describe columns in a comma separated file. Between each column, in the /etc/shadow file, exists a value describing aging information regarding the account. Let's look at it in more detail:
Looking at each of these fields one by one:
- username: The username of the account as specified in the /etc/passwd file
- password: The password is in encrypted hash format, meaning that it has been hashed using a salt as the seed. The rest of the post is on this very topic.
- last_change: The number of days, since January 1, 1970, when the password was last changed.
- may_change: The number of days since the last password change before a new password change is allowed.
- must_change: The number of days since the last password change when a new password change is required.
- warn_days: The number of days before must_change when the user begins receiving warning about changing their password.
- expire_date: The number of days after the password expires when the account is disabled.
- disable: The number of days since January 1, 1970, when the account will be disabled.
- reserved: A reserved field for the system.
All of this information can be found in section 5 of the shadow man page.
Knowing the locations and valid values of each is crucial as a system administrator. However, I won't be covering each of these in any detail other than what has been described above. Also, I'll only be discussing the password field. The password field is interesting to me, as I enjoy mathematics and cryptography. Hopefully, you'll find this interesting as well.
As you are probably already aware, the password field is required in order to use the account, however, a password doesn't have to exist for the account to be active. When a new account is created on the system, before a password is applied, take a look at the contents of the password in the shadow file. On my Ubuntu system, there is a single exclamation point in the password field. As it sits, the password is invalid, as the system is looking for a hash. Removing the exclamation point from the password field would mean that the user can log into the system without a password. It should be noted, however, that there are unexpected behaviors logging into the system without a password with regards to PAM properly cleaning up the login.
This brings up another point: the authentication mechanisms that exist on your machine are attempting to validate your password against a valid hash that exists in that password field. Keeping a user from logging in is as simple as producing an invalid hash. This means simply changing a single character in the password, or as above with newly created accounts, putting an exclamation point or two in the password field. In other words, unless a hash can be produced that matches a hash in that field, the user won't be able to log in. Fairly simple, no?
If you check the permissions of the /etc/shadow file, you'll notice that only root has access to the file. This is intentional, for one main reason: rainbow table attacks. The concept of a rainbow table is simple. Take some text, retrieve the hash value then store it in a table. As hash algorithms are one way cryptographic functions, this means that taking a hash value, and reversing it to its text value is extremely time consuming and highly improbable. So, rather than brute force the hash value, all you have to do is simply look up a hash in the table for a match. If a match is found, you have the text to the hash. Spending some time on Google, there are plenty of rather large rainbow tables in existence. Salting the hash means that access to the salt would be needed, otherwise, the hash will change infinitely for a single password.
A little history note: passwords have not always existed in the shadow file, as they used to exist in the /etc/passwd file. After all, where do you think the name came from? In the second field of that file is where the password used to exist. Now, you'll notice that an 'x' exists in its place instead, with the password moved to the shadow file. The reason is explained above, with rainbow tables. The /etc/passwd permissions allow any account on the system to read the file. This is needed for applications to know if accounts exists on the system for various routines. Keeping the password, even if it's hashed, in a file world-readable made system administrators uneasy, and eventually, the shadow system was created. FYI- on FreeBSD, and other Unixes, the shadow file is /etc/master.passwd rather than /etc/shadow.
To bring security up on the front lines, hashes aren't difficult to brute force. When Unix was created in 1969, computing resources were severely limited. We couldn't use massive mathematical algorithms to process hashed passwords and see if they matched what was in the password database. As such, we stuck with small bit rates for generating the hash. As time progressed, and computing power got more powerful, the need for changing that bit rate to higher values on creating the hash increased. Unfortunately, the rate of change wasn't linear to the rate of change in computing power, and brute forcing hashed passwords became more and more of a realization. The need for stronger algorithms became a necessity.
As already noted, the password was stored in the /etc/passwd file. However, because the threat of brute forcing password hashes was becoming real, the need to rethink passwords on a Unix system was eventually realized, and the password moved into its current location, the /etc/shadow file. The reason for "shadow" comes from the idea that rather than just storing the password hash in a world-readable file, we move it to a separate file that only root has access (as defined above). Further, to add strength to the hashed password, we create a seed, which we'll refer to as a "salt", and use that salt, combined with the hashing algorithm, to result in a much stronger encrypted password (security experts actually will call the encrypted password encoded rather than encrypted, as the text is set to null, and the password is the key). Shadowing and salting your password has been implemented in GNU/Linux for some time, and came as a result of first appearing in FreeBSD. Most, if not all, GNU/Linux distributions now shadow and salt their passwords by default.
So, now that we've learned what is contained in the /etc/shadow file, and a little history of the password itself, let's look at the structure of the encrypted password in the file. You will probably notice that it has a very patterned format. The format is simple to understand:
There are 3 dollar signs which act as separators in the shadowed password field. Within the first two dollar signs exists the type of algorithm used to hash the password. Within the next two dollar signs is a random salt that is used with the hashing algorithm to create the encrypted password. After the third dollar sign, before the next colon, is the encrypted password itself.
For the supported hash types, this is generally MD5, however, new computing power is beginning to show the age of MD5 hashes, which has an output of 128-bits. As such, new hashing algorithms are coming onto the scene to strengthen the password itself, such as 160-bit, 256-bit and 512-bit algorithms. The question is, however, how do know which algorithm you are using? I've outlined a list of the common, currently in use hash types.
- missing: If the dollar signs are missing, but a hash exists, then the DES algorithm or the crypt() function was called. This has been implemented on Unix since the early days, and still exists on a few GNU/Linux distributions. DES has shown severe cryptanalysis attacks, and should not be used.
- $1$: The MD5 hashing algorithm, as originally started with FreeBSD, developed by Poul-Henning Kamp. This is the default on Ubuntu, and other Debian-based distributions. The resulting output is 128-bits in size..
- $2$ and $2a$: Two different versions of the blowfish encryption cipher, originally developed by Bruce Schneier, and implemented by Niels Provos and David Mazieres for OpenBSD. This is the default in openSUSE 11, as well as the forthcoming SUSE Linux Enterprise Server and Desktop, version 11. The resulting output is 128-bits, where $2$ appends a NUL to the password, and $2a$ does not.
- $5$: The next two come from Ulrich Drepper at Red Hat for GNU/Linux. This one is a SHA-256 hashing algorithm implementation with a 32 byte output, and the resulting output is 256-bits.
- $6$: This is a SHA-512 hashing algorithm implementation with a 64 byte output. This is the default on Fedora 9 and soon to be released Red Hat Enterprise Linux 6. The resulting output is 512-bits in size.
Others exist, but aren't worth mentioning, in my opinion. However, for reference, there is a CPAN Perl module for working with shadowed passwords, and documentation exists for handling all the supported shadow types.
I won't be covering the mathematical algorithm used on each function, as that could make for an exceptionally lengthy post (you're probably bored already). As such, may I recommend spending some time on Google and Wikipedia, learning each algorithm, their strengths and weaknesses, as well as their implementations? It really makes for fascinating reading, if you are into mathematics and cryptography.
Now, what's up with the salt? What does it actually provide? Why should I care? Isn't a straight hash strong enough? Actually, no- it's not. A straight hash, albeit strong, is not strong enough, due to rainbow tables. So, the salt steps in, and adds strength to the hash. Here's how. First, a string is chosen at random with the following valid characters: a-z, A-Z, 0-9, "." and "/". In other words, all 26 uppercase and lowercase letters of the English alphabet, all ten single digits, the period and forward slash.
Let's say that only 2 characters where chosen from that pick to form our salt string. Because there are 64 possible combinations when choosing just one character, and another 64 combinations for the other, this makes the possible combinations from just 2 characters 4096 (64 squared). Adding that to the hash, means there are 4096+1, or 4097 possible hashes that could result from my single password. This makes the rainbow table 4096 times larger, and it also makes the hash literally 4096 times more difficult to break. Now, on my Ubuntu installation, the salt is used with 8 characters from the above list. So, 64 to the 8th power means 281,474,976,710,656 possible combinations in the salt alone. Which, as discovered above, means 281.4 quadrillion possible hashes from a single password, and a rainbow table size of 281.4 quadrillion times larger! To put this number in perspective, 281,474,976,710,656 seconds would be approximately 8,925,513 years. Yeah. Salting the password just makes sense, don't you think?
To take advantage of a specific algorithm in the shadow file, we need to modify the pluggable authentication modules, known as PAM. Of course, you will need to have an understanding of PAM before hacking away. I'm not going to cover how to setup your box to take advantage of the different algorithms. The would lengthen the post, and potentially render your system unbootable if you were to make a mistake, forcing you into a rescue environment, then I get blamed. However, check your GNU/Linux vendor documentation, as well as Google, and support forums for enabling different algorithms on your distribution.
So, there you have it! Shadowed password information on GNU/Linux. As you can tell, there is much to discuss in relation to this topic. I could probably spend a couple of posts describing how to implement each algorithm on your box, the algorithms of each, testing their strengths and weaknesses, and much more. Encryption, especially when it comes to passwords, is a broad, but intriguing and enlightening topic.