We will describe our password database in a historical manner, starting by telling about the standard Unix password database that came with SunOS 4.1.3, then describing the JFH shadow package that we replaced it with, and finally describing our own modifications to that package.
janc:DIBU7epiSd4xs:100:100:Jan Wolter:/home/janc:/bin/cshThis contains seven fields, separated by colons:
Passwords are encrypted using a version of the US National Bureau of Standard's DES (Data Encryption Standard) algorithm. The Unix password encryption algorithm takes the lowest 7 bits of each of the first 8 characters of your password to construct a 56-bit key which is used to repeatedly encrypt a constant string (usually a string of all zeros) into a 14 character string like the one in the example above.
The first two characters of the encrypted password aren't really part of the encryption. They are a randomly selected "salt" which is different for each user and is used to permute the algorithm in small ways, resulting in the encrypted password that is stored as the other twelve characters. Thus, if two different users set their password to the same thing, you won't be able to tell because with different salts, their entire encrypted passwords will be different.
The /etc/passwd file, which normally contain these encrypted passwords, is always publicly readable on Unix systems, so any user can see any other user's encrypted password. Back in the seventies this wasn't a real problem. Knowing someone's encrypted password couldn't get you access to their account, and decrypting a password was simply too hard. However, computers have gotten much, much faster, and there exist programs these days that can do a pretty decent job of cracking passwords these days. With 56-bit keys, there are 2**56 or 72,057,594,037,927,936 different possible passwords. Modern parallel computers can search that in reasonable amounts of time, and widely available programs like crack can do a pretty good job of searching the portion of that key space usually used by humans. (That's why Grex's password programs are pretty picky about encouraging "non-obvious" passwords - it lengthens the list crackers have to search.)
The other problem with the traditional Unix password system is one of access time. The original designers of Unix didn't expect Unix systems with tens of thousands of users. Grex has about 15,000 accounts, which means that the passwd file is about 15,000 lines long. Every time the system needs to know any of the information stored in there, it has to search that huge file. This can be very slow.
Newer versions of Unix deal with both of these problems. Encrypted passwords are no longer stored in /etc/passwd, though all the other information will still be there, and there may be an alternate hashed password database that can be searched much more efficiently. Unfortunately, Grex runs SunOS 4.1, which is not a newer version of Unix and doesn't support do either of these things. So we had to fix it.
First, encrypted passwords are no longer stored in /etc/passwd. If you look at that file, you will see that the lines look like:
janc:x:100:100:Jan Wolter:/home/janc:/bin/cshHere the encrypted password has been replaced by an x. (Some Unix systems put fake passwords here instead of an x, but we don't want to encourage hopeful hackers to download the whole useless /etc/passwd file over our overburdened internet connection - though plenty of people try it anyway. Duh.) The actual encrypted passwords are stored in a different file, called /etc/shadow, which, unlike /etc/passwd, is not readable. If you could read it, you would see that it contains lines that look like this:
janc:ytx9yoTz0xTiYv3eIkk9XOpF:10008:0:365:30:::The fields are:
The alert reader will have noticed another difference. In the sample shadow line above, the encrypted password is 26 characters long, rather than the standard 14. You guessed it - there have been changes to the password encryption algorithm.
As we mentioned, the DES algorithm uses a 56 bit key, constructed by taking 7 bits from the first 8 characters of your password. But what happens if your password is longer than 8 characters? On standard Unix systems, the extra characters aren't used. That's a waste of perfectly good password.
So in the JFH system, if your password is more than 8 characters long, the next eight characters are also encrypted by the same algorithm. So So the result is 2 bytes of salt, 12 bytes encrypted from the first 8 characters of your password, and 12 more bytes encrypted from the rest of your password with the same salt. String them all together and you have 26 bytes of encrypted password, like the sample above.
The JFH password system also addresses the speed question. In addition to the the standard /etc/passwd file, there are the /etc/passwd.pag and /etc/passwd.dir files. These contain exactly the same data as the /etc/passwd file, and, in fact, are generated from the /etc/passwd file, but they comprise a hashed database, which can be searched very rapidly. (To search a hashed file, you take what you are searching for, in this case the name "janc", and use some fixed algorithm to turn it into a number (e.g., you might add up all the letters). Then you use this number to index straight into the database to find the object you want. This can be very fast, but requires that the database be properly structured to make it work.) There are similar /etc/shadow.pag and /etc/shadow.dir files to enable fast searching of the shadow database.
The catch, of course, is that none of the Unix programs that come with SunOS know that the hashed database exists. We have rebuilt the most commonly used programs to use the hashed database for password file lookups, but some programs still search straight through the flat /etc/passwd file. In most cases, this is just a matter of recompiling them with the -lshadow flag on the compile command to link in the shadow library, which includes new versions of the getpwnam() and getpwuid() calls that use the hashed database.
The first change was related to the maintenance of the hash files. In the JFH shadow system, and in many other Unix versions with a hashed password database, the entire hash file has to be rebuilt every time there is any change. If your password file is big enough to need a hashed database, then rebuilding that database is going to be a slow process. So while the hash system makes accesses very fast, updates become very slow.
The general presumption is that it doesn't matter so much because updates are rare. You only need to rebuild the hash files when you create or delete an account, or when there is a change to a user's name, password, or login shell. However, on Grex we typically have about a hundred new accounts created through the newuser program every day. With Grex as slow as it sometimes is, it could take as long as an fifteen minutes to do each rebuild, and only one can be running at a time, so it could take about 25 hours a day to do all the account creations. This is definitely a problem.
The solution, of course, is not to rebuild the entire database every time one thing changes. Instead, you modify the existing database to make only the necessary changes. This is much, much faster, but difficult to do correctly. Marcus has developed versions of the newuser, passwd, chsh and chfn commands that do this, as well as a program to allow staff members to modify, create and destroy accounts.
The other change we have made is to the password encryption algorithm. The method used by the JFH software to handle long passwords isn't really all that good. Those 26-character long encryptions aren't as formidable as they look. Though many users have passwords longer than 8 characters, they usually aren't more than a few characters longer. That means the second half of the password is usually an encryption of a one, two, or three-character long string. It's really easy to crack passwords that short, so the second halves of the long encryptions tend to add little extra security.
This isn't really that big a problem for Grex. After all, since the encrypted passwords are in a file readable only to root, we don't expect many people to ever see them. People can still try to guess passwords without having access to the encrypted strings. All they have to do is try their guesses at Grex's login prompt, but then they can't attack long passwords half at a time (so, in fact, passwords longer than eight characters are a lot more secure), and they can't run huge number of them very fast because, well, they'd be on Grex and Grex isn't fast.
But there was another reason we wanted to change the password encryption algorithm. Currently Grex is all one computer, but in the future we hope to use different machines for different services, for example, there might be a separate machine to handle E-mail. In such an environment, we'd want users' accounts to work on multiple machines. That means we'd need to use some form of distributed password system, like Kerberos.
So Marcus Watts formulated the following requirements for a new encryption algorithm:
To replace the DES encryption, Marcus Watts has developed a new encryption algorithm based on the SHA (Secure Encryption Algorithm). The one tricky part in this is that password lengths vary, and SHA requires wants a constant length input. So the basic algorithm is:
The reason for tagging the passwords generated by this algorithm with a %! sequence is that, for a while at least, the password file will contain a mixture of DES passwords and new passwords, and we need to be able to distinguish them. The reason for this is to smooth the transition from the old encryption to the new encryption. We can't easily convert existing passwords from the old scheme to the new scheme. You'd have to decrypt the old passwords before you could re-encrypt them with the new scheme. It's doubtful whether such a project could be considered practical or ethical.
So we are making the change gradually. For people with DES passwords, the lines in the /etc/shadow file look like the example above. For people with new passwords, the encryption string always starts with the three characters %!, like this:
janc:%!!@Tpf4)X^Pes@Xms8tq(M).U+#:10008:0:365:30:::If the login program doesn't see the %!! in your encrypted password, it uses the DES encryption algorithm, if it does, it uses the new algorithm. All new accounts are now being created using the new encryption, and whenever an older user makes a password change, the password encryption is changed over to the new algorithm. So within a year (since passwords expire after a year), all Grex users will be using the new algorithm, and we will be ready to change over to a distributed password system.
Marcus's actual source for the kg_pwhash() routine that does the encryption is available on a separate page.