This section describes how passwords are implemented inside the Unixoperating system for both locally administered and network-basedsystems.
Traditionally, Unix uses the/etc/passwd file to keep track of every user onthe system. The /etc/passwd file contains theusername, real name, identification information, and basic accountinformation for each user. Each line in the file contains a databaserecord; the record fields are separated by a colon (:).
You can use the cat command to display yoursystem’s /etc/passwd file. Hereare a few sample lines from a typical file:
root:x:0:1:System Operator:/:/bin/kshdaemon:x:1:1::/tmp:uucp:x:4:4::/var/spool/uucppublic:/usr/lib/uucp/uucicorachel:x:181:100:Rachel Cohen:/u/rachel:/bin/ksharlin:x.:182:100:Arlin Steinberg:/u/arlin:/bin/csh
The first three accounts, root,daemon, and uucp, aresystem accounts, while rachel andarlin are accounts for individual users.
The individual fields of the /etc/passwd filehave fairly straightforward meanings. Table 4-1explains a sample line from the file shown above.
Table4-1.Example /etc/passwd fields
Passwords were traditionally stored in the/etc/passwd file in an encrypted format (hencethe file’s name). However, because of advances inprocessor speed, encrypted passwords are now almost universallystored in separate shadow passwordfile s, which are described later.
The meanings of the UID and GID fields are described in Chapter 5.
When Unixrequests your password, it needs some way of determining that thepassword you type is the correct one. Many early computer systems(and quite a few still around today!) kept the passwords for all oftheir accounts plainly visible in a so-called“password file” that containedexactly that—passwords. Under normal circ*mstances, the systemprotected the passwords so that they could be accessed only byprivileged users and operating system utilities. But throughaccident, programming error, or deliberate act, the contents of thepassword file could occasionally become available to unprivilegedusers. This scenario is illustrated in the following remembrance:
Perhaps the most memorable such occasion occurred in the early 1960swhen a system administrator on the CTSS system at MIT was editing thepassword file and another system administrator was editing the dailymessage that is printed on everyone’s terminal onlogin. Due to a software design error, the temporary editor files ofthe two users were interchanged and thus, for a time, the passwordfile was printed on every terminal when it was logged in.
—Robert Morris and Ken Thompson, “Password Security: A CaseHistory” Communications of the ACM, November1979.
The real danger posed by such systems, explainedMorris and Thompson, is not that software problems might somedaycause a recurrence of this event, but that people can make copies ofthe password file and purloin them without the knowledge of thesystem administrator. For example, if the password file is saved onbackup tapes, then those backups must be kept in a physically secureplace. If a backup tape is stolen, theneverybody’s password needs tobe changed.
Unix avoids this problem by not keepingactual passwords anywhere on the system. Instead, Unix stores a valuethat is generated by using the password to encrypt a block of zerobits with a one-way function called crypt( ) ; the result of the calculation wastraditionally stored in the/etc/passwd file.[41]When you try to log in, the program/bin/login does not decrypt the stored password.Instead, /bin/login takes the password that youtyped, uses it to transform another block of zeros, and compares thenewly transformed block with the block stored in the/etc/passwd file. If the two encrypted resultsmatch, the system lets you in.
The security of thisapproach rests upon the strength of the encryption algorithm and thedifficulty of guessing the user’s password. To date,the crypt ( ) algorithm and its successors haveproven highly resistant to attacks. Unfortunately, users have a habitof picking easy-to-guess passwords, which creates the need for shadowpassword files.
The algorithm that traditional crypt( ) uses isbased on the Data Encryption Standard(DES) of the National Institute of Standards and Technology (NIST).In normal operation, DES uses a 56-bit key (8 7-bit ASCII characters,for instance) to encrypt blocks of original text, orcleartext ,that are 64 bits in length. The resulting 64-bit blocks of encryptedtext, orciphertext ,cannot easily be decrypted to the original cleartext without knowingthe original 56-bit key.
The Unix crypt( ) function takes theuser’s password as the encryption key and uses it toencrypt a 64-bit block of zeros. The resulting 64-bit block ofciphertext is then encrypted again with the user’spassword; the process is repeated a total of 25 times. The final 64bits are unpacked into a string of 11 printable characters that arestored in the shadow password file.[42]
Tip
Don’t confuse the crypt( )algorithm with thecrypt encryption program. Thecrypt program uses a different encryption systemfrom crypt( ) and is very easy to break. SeeChapter 7 for more details.
Although the source code to crypt( ) is readilyavailable, no technique has been discovered (or publicized) totranslate the encrypted password back into the original password.Such reverse translation may not even be possible. As a result, theonly known way to defeatUnixpassword security is via a brute-force attack (see the next note), orby a dictionaryattack . A dictionary attack is conducted bychoosing likely passwords—as from a dictionary—encryptingthem, and comparing the results with the value stored in/etc/passwd. This approach to breaking acryptographic cipher is also called a keysearch or password cracking. It is made easier by thefact that DE uses only the first eight characters of the password asits key; dictionaries need only contain passwords of eight charactersor fewer.
Robert Morris and Ken Thompsondesigned crypt( ) to make a key searchcomputationally expensive. The idea was to make a dictionary attacktake too long to be practical. At the time, software implementationsof DES were quite slow; iterating the encryption process 25 timesmade the process of encrypting a single password 25 times slowerstill. On the original PDP-11 processors upon which Unix wasdesigned, nearly a full second of computer time was required toencrypt a single password. To eliminate the possibility of using DEShardware encryption chips, which were a thousand times faster thansoftware running on a PDP-11, Morris and Thompson modified the DEStables used by their software implementation, rendering the twoincompatible. The same modification also served to prevent a bad guyfrom simply pre-encrypting an entire dictionary and storing it.
What was the modification? Morris and Thompson added a bit ofsalt, as we’ll describe inthe next section.
Note
There is no published or known method to easily decrypt DES-encryptedtext without knowing the key. Of course,“easily” has a different meaningfor cryptographers than for mere mortals. To decrypt somethingencrypted with DES is computationally expensive; using the fastestcurrent, general-purpose computers might take hundreds of years.
However, computers have grown so much faster in the past 25 yearsthat it is now possible to test millions of passwords in a relativelyshort amount of time.
As table salt adds zest to popcorn, thesalt that Morris and Thompson sprinkled into the DES algorithm addeda little more spice and variety. The DES salt is a 12-bit number,between 0 and 4,095, which slightly changes the result of the DESfunction. Each of the 4,096 different salts makes a password encrypta different way.
When you change your password, the /bin/passwd program selects a salt based on the time ofday. The salt is converted into a two-character string and is storedin the /etc/passwd file along with the encrypted“password.”[43] In this manner, when youtype your password at login time, the same salt is used again. Unixstores the salt as the first two characters of the encryptedpassword.
Table 4-2 shows how a few different words encryptwith different salts.
Table4-2.Passwords and salts
Notice that the last password, norahs, wasencrypted two different ways with two different salts. As a sideeffect, the salt makes it possible for a user to have the samepassword on a number of different computers and to keep this fact asecret (usually), even from somebody who has access to the/etc/passwd files on all of those computers; twosystems would not likely assign the same salt to the user, thusensuring that the encrypted password field is different.[44]
On the Importance of Encrypted Passwords
Alec Muffett,the author of the Crack program (discussed inTable 19-1), related an entertaining story to usabout the reuse of passwords in more than one place, which weparaphrase here.
A student friend of Alec’s (call him Bob) spent aco-op year at a major computer company site. During his vacations andon holidays, he’d come back to school and playAberMUD (a network-based game) on Alec’s computer.One of Bob’s responsibilities at the companyinvolved system management. The company was concerned about security,so all passwords were random strings of letters with no sensiblepattern or order.
One day, Alec fed the AberMUD passwords into his development versionof the Crack program as a dictionary, becausethey were stored on his machine as plaintext. He then ran this fileagainst his system user-password file, and found a few studentaccount passwords. He had the students change their passwords, and hethen forgot about the matter.
Some time later, Alec posted a revised version of theCrack program and associated files to theUsenet. They ended up in one of the Usenet sources newsgroups andwere distributed quite widely. Eventually, after a trip of thousandsof miles around the world, they came to Bob’scompany. Bob, being a concerned administrator, decided to downloadthe files and check them against his company’spasswords. Imagine Bob’s shock and horror when thewidely distributed Crack promptly churned out amatch for his randomly chosen, super-secret rootpassword!
The moral of the story is that you should teach your usersnever to use their account passwords for otherpurposes—such as games or web sites. They never know when thosepasswords might come back to haunt them! For developers, the moral isthat all programs—even games—should store passwordsencrypted with one-way hash functions.
In recent years the security provided by the salt has diminishedsignificantly. Having a salt means that the same password can encryptin 4,096 different ways. This makes it much harder for an attacker tobuild a reverse dictionary for translated encrypted passwords backinto her unencrypted form: to build a reverse dictionary of 100,000words, an attacker would need to have 409,600,000 entries. But with8-character passwords and 13-character encrypted passwords,409,600,000 entries fit in roughly 8 GBs of storage.
Another problem with the salt was an error in implementation: manysystems selected which salt to use based on the time of day, whichmade some salts more likely than others.
Modern Unix systems have improved the security of thecrypt( ) function by changing the underlyingencryption algorithm. Instead of a modified DES, a variety of otheralgorithms have been adopted, including Blowfish and MD5. Theadvantage of these new algorithms is that more characters of thepassword are significant, and there are many more possible values forthe salt; both of these changes significantly improve the strength ofthe underlying encrypted password system. The disadvantage is thatthe encrypted passwords on these systems will not be compatible withthe encrypted passwords on other systems.
Because of the widespread use of the original Unix passwordencryption algorithm, Unix vendors have gone to great lengths toensure compatibility. Thus, the crypt( )function called with a traditional salt will always use the originalDES-based algorithm. To use one of the newer algorithms you must useeither a different function call (some vendors usebigcrypt( ) or crypt16( ))or a different salt value. Consult your documentation to find outwhat is appropriate for your system.
The DESExtended format is a technique for increasing the number of DESrounds and extending the salt from 212 to224 possible values. This format haslimited use on modern Unix systems but is included on many to providebackwards compatibility.
The Modular Crypt Format (MCF)specifies an extensible scheme for formatting encrypted passwords.MCF is one of the most popular formats for encrypted passwords aroundtoday. Here is an example of an MCF-encrypted password:
$1$EqkVUoQ2$4VLpJuZ.Q2wm6TAiyYt75.
Dollar signs are used to delimit the MCF fields, as described inTable 4-3.
Table4-3.The modular crypt format
| Field | Purpose | Notes |
|---|---|---|
| #1 | Specifies encryption algorithm to use | 1 specifies MD5.2 specifies Blowfish. |
| #2 | Salt | Limited to 16 characters. |
| #3 | Encrypted password | Does not include salt, unlike traditional Unix crypt( ) function. |
Although changes to the encryptedpassword system (as described in the previous section) have improvedthe security of encrypted passwords, they have failed tofundamentally address the weakness exploited by password crackers:people pick passwords that are easy to guess. If an attacker canobtain a copy of the password file, it is a simple matter to guesspasswords, perform the encryption transform, and compare against thefile.
Ultimately, the best way to deal with the problem of poorly-chosenpasswords is to eliminate reusable passwords entirely by usingone-time passwords, some form of biometrics, or a token-basedauthentication system. Because such systems can be awkward orexpensive, modern Unix systems have adopted a second approach calledshadow password files or masterpassword files.
As the name implies, a shadow password file is a secondary passwordfile that shadows the primary password file. On Solaris and Linux systems, the shadowpassword is usually stored in the file /etc/shadow andcontains the encrypted password and a password expiration date. The/etc/shadow file is protected so that it can beread only by the superuser. Thus, an attacker cannot obtain a copy touse in verifying guesses of passwords.
Instead of a shadow password file,FreeBSD uses a master password file. Thisfile, /etc/master.passwd, isa complete password file that includes usernames, passwords, andother account information. The /etc/passwd fileis identical to the /etc/master.passwd file,except that all encrypted passwords have been changed to the letter“x”.
Mac OS X stores all account information in the NetInfo network-basedaccount management system. Mac OS X does this for all computers, evenfor standalone computers that are never placed on a network. Theversion of NetInfo that is supplied in Mac OS 10.0 and 10.1 does notprovide for shadow passwords, although the/etc/master.passwd file is present and is usedduring boot-up.
Themost effective way to minimize the danger of bad passwords is not touse conventional passwords at all. Instead, your site can installsoftware and/or hardware to allow one-timepasswords. A one-time password is exactly that—apassword that is used only once.
There are two popular techniques for implementing one-time passwords:
- Hardware tokens
An exampleis the RSA SecureID card, which displays a new PIN or password foreach login. Some token-based systems display a different code everyminute. Other token-based systems look like little calculators. Whenyou attempt to log in you are presented with a challenge. You typethis challenge into your calculator, type in your personalidentification number, and then type the resulting number that isdisplayed into the computer.
- Codebooks
These list validpasswords. Each password is crossed off the list after it is used.S/Key is a popular codebook system.[45]
One-time passwords can be implemented as a replacement forconventional passwords or in addition to them. In a typical S/Keyenvironment, you enter the S/Key password instead of your standardUnix password. For example:
login: darrelPassword: says rusk wag hut gwen logeLast login: Wed Jul 5 08:11:33 from r2.nitroba.comYou have new mail.%All of these one-time password systems provide an astoundingimprovement in security over the conventional system. Unfortunately,because they require either the installation of special software orthe purchase of additional hardware, they are not as widespread atthis time in the Unix marketplace as they should be. However, manymajor companies and government agencies have moved to using theseone-time methods. (See Table 19-1 for additionaldetails.)
Anotherapproach to solving the problem of passwords is to do away with thementirely and use an alternative authentication system. One popularauthentication system that has been used is recent years is based onpublic key cryptography (described in Chapter 7 ).
In a public key authentication system, each user generates a pair of“keys”—two long numbers withthe interesting property that a message encoded with one of the keyscan be decoded only using the other key. The user keeps one of thekeys private on his local computer (and often protects its privacy byencrypting the key itself with a password), and provides the other,public key to the remote server. When the user wants to log into theserver, the server selects a random number, encodes it with theuser’s public key, and sends it to the user. Bydecrypting the random number using his private key and returning itto the server (possibly re-encrypted with theserver’s public key), the user proves that he is inpossession of the private key and is therefore authentic. In asimilar fashion, the server can authenticate itself to the user, sothat the user is sure that he’s logging into thecorrect machine.
Public key authentication systems have two fundamental problems. Thefirst problem is the management of private keys. Private keys must bekept secure at all costs. Typically, private keys are encrypted witha passphrase to protect them, but all of the caveats about choosing agood password (and not transmitting it where others can eavesdrop)apply.
The second problem is the certification of public keys. If anattacker can substitute his public key for someoneelse’s (or for that of a server to which you wish toconnect) all your communication will be visible to the attacker. Onesolution to this problem is to use a secure channel to exchangepublic keys. With the Secure Shell (ssh), thepublic key is merely copied to the remote system (after logging inwith a password or another non-public key method) and put into a filein the user’s home directory called~/.ssh/authorized_keys.
A more sophisticated technique for distributing public keys involvesthe creation of a public keyinfrastructure (PKI). A group of users and system administratorscould all certify their keys to one another in person, or each couldhave his own key certified by a common person or organization thateveryone trusts to verify the identities associated with the keys.SSL, the Secure Socket Layer, provides transparent support for PKI.
[41] These days, the encrypted password is stored either in theshadow password file or on a network-based server, aswe’ll see in a later section.
[42] Each of the 11characters holds six bits of the result, represented as one of 64characters in the set “.”,“/”, 0-9, A-Z, a-z, in that order.Thus, the value 0 is represented as“.”, and 32 is the letter“U”.
[43] By now,you know that what is stored in the /etc/passwdfile is not really the encrypted password. However, everyone calls itthat, and we will do the same from here on. Otherwise,we’ll need to keep typing “thesuperencrypted block of zeros that is used to verify theuser’s password” everywhere in thebook, filling many extra pages and contributing to the prematuredemise of yet more trees.
[44] This case occurs only when the user actually types in hispassword on the second computer. Unfortunately, in practice, systemadministrators commonly cut and paste/etc/passwd entries from one computer to anotherwhen they build accounts for users on new computers. As a result,others can easily tell when a user has the same password on more thanone system.
Get Practical UNIX and Internet Security, 3rd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
