found..PPAnother profitable approach for the bad guy is to use the wordlist from a dictionary or to use a list of names.For example, a large commercial dictionary contains typicallly about250,000 words; these words can be checked in about five minutes.Again, a noticeable fraction of any collection of passwordswill be found.Improvements and extensions will be (and have been) found bya determined bad guy.Some ``good'' things to try are:.IP -The dictionary with the words spelled backwards..IP -A list of first names (best obtained from some mailing list).Last names, street names, and city names also work well..IP -The above with initial upper-case letters..IP -All valid license plate numbers in your state.(This takes about five hours in New Jersey.).IP -Room numbers, social security numbers, telephone numbers, andthe like..PPThe authors have conducted experiments to try to determinetypical users' habits in the choice of passwords when noconstraint is put on their choice.The results were disappointing, except to the bad guy.In a collection of 3,289 passwordsgathered from many users over a long period of time;.IP15 were a single ASCII character;.IP72 were strings of two ASCII characters;.IP464 were strings of three ASCII characters;.IP477 were string of four alphamerics;.IP706 were five letters, all upper-case or all lower-case;.IP605 were six letters, all lower-case..LPAn additional 492 passwords appeared in various availabledictionaries, name lists, and the like.A total of 2,831, or 86% of this sample of passwords fell into one ofthese classes..PPThere was, of course, considerable overlap between thedictionary results and the character string searches.The dictionary search alone, which required only fiveminutes to run, produced about one third of the passwords..PPUsers could be urged (or forced) to use either longer passwordsor passwords chosen from a larger character set, or the systemcould itself choose passwords for the users..SHAN ANECDOTE.PPAn entertaining and instructive example isthe attempt made at one installation to force users to use less predictablepasswords.The users did not choose their own passwords; the system suppliedthem.The supplied passwords were eight characters long and were taken from the character set consisting oflower-case letters and digits.They were generated by a pseudo-random number generatorwith only $2 sup 15$ starting values.The time required to search (again on a PDP-11/70) throughall character strings of length 8 from a 36-characteralphabet is 112 years..PPUnfortunately, only $2 sup 15$ of them need be looked at,because that is the number of possible outputs of the randomnumber generator.The bad guy did, in fact, generate and test each of these stringsand found every one of the system-generated passwords usinga total of only about one minute of machine time..SHIMPROVEMENTS TO THE FIRST APPROACH.NHSlower Encryption.PPObviously, the first algorithm used was far too fast.The announcement of the DES encryption algorithm [2]by the National Bureau of Standardswas timely and fortunate.The DES is, by design, hard to invert, but equally valuableis the fact that it is extremely slow when implemented insoftware.The DES was implemented and used in the following way:The first eight characters of the user's password areused as a key for the DES; then the algorithmis used to encrypt a constant.Although this constant is zero at the moment, it is easilyaccessible and can be made installation-dependent.Then the DES algorithm is iterated 25 times and theresulting 64 bits are repacked to become a string of11 printable characters..NHLess Predictable Passwords.PPThe password entry program was modified so as to urgethe user to use more obscure passwords.If the user enters an alphabetic password (all upper-case orall lower-case) shorter than six characters, or apassword from a larger character set shorter than fivecharacters, then the program asks him to enter alonger password.This further reduces the efficacy of key search..PPThese improvements make it exceedingly difficult to findany individual password.The user is warned of the risks and if he cooperates,he is very safe indeed.On the other hand, he is not prevented from usinghis spouse's name if he wants to..NHSalted Passwords.PPThe key search technique is stilllikely to turn up a few passwords when it is usedon a large collection of passwords, and it seemed wise to make thistask as difficult as possible.To this end, when a password is first entered, the password programobtains a 12-bit random number (by reading the real-time clock)and appends this to the password typed in by the user.The concatenated string is encrypted and both the12-bit random quantity (called the $salt$) and the 64-bitresult of the encryption are entered into the passwordfile..PPWhen the user later logs in to the system, the 12-bitquantity is extracted from the password file and appendedto the typed password.The encrypted result is required, as before, to be the same as theremaining 64 bits in the password file.This modification does not increase the task of findingany individualpassword,starting from scratch,but now the work of testing a given character stringagainst a large collection of encrypted passwords hasbeen multiplied by 4096 ($2 sup 12$).The reason for this is that there are 4096 encryptedversions of each password and one of them has been picked moreor less at random by the system..PPWith this modification,it is likely that the bad guy can spend days of computertime trying to find a password on a system with hundredsof passwords, and find none at all.More important is the fact that it becomes impracticalto prepare an encrypted dictionary in advance.Such an encrypted dictionary could be used to cracknew passwords in milliseconds when they appear..PPThere is a (not inadvertent) side effect of thismodification.It becomes nearly impossible to find out whether aperson with passwords on two or more systems has usedthe same password on all of them,unless you already know that..NHThe Threat of the DES Chip.PPChips to perform the DES encryption are already commerciallyavailable and they are very fast.The use of such a chip speeds up the process of passwordhunting by three orders of magnitude.To avert this possibility, one of the internal tablesof the DES algorithm(in particular, the so-called E-table)is changed in a way that depends on the 12-bit randomnumber.The E-table is inseparably wired into the DES chip,so that the commercial chip cannot be used.Obviously, the bad guy could have his own chip designed andbuilt, but the cost would be unthinkable..NHA Subtle Point.PPTo login successfully on the UNIX system, it is necessaryafter dialing in to type a valid user name, and then thecorrect password for that user name.It is poor design to write the login command in such a way that ittells an interloper when he has typed in a invalid user name.The response to an invalid name should be identical tothat for a valid name..PPWhen the slow encryption algorithm was first implemented,the encryption was done only if the user name was valid,because otherwise there was no encrypted password tocompare with the supplied password.The result was that the response was delayedby about one-half second if the name was valid, but wasimmediate if invalid.The bad guy could find outwhether a particular user name was valid.The routine was modified to do the encryption in eithercase..SHCONCLUSIONS.PPOn the issue of password security, UNIX is probablybetter than most systems.The use of encrypted passwords appears reasonablysecure in the absence of serious attention of expertsin the field..PPIt is also worth some effort to conceal even the encryptedpasswords.Some UNIX systems have instituted what is called an``external security code'' that must be typed whendialing into the system, but before logging in.If this code is changed periodically, then someonewith an old password will likely be prevented fromusing it..PPWhenever any security procedure is instituted that attemptsto deny access to unauthorized persons, it is wise tokeep a record of both successful and unsuccessful attemptsto get at the secured resource.Just as an out-of-hours visitor to a computer center normallymust not only identify himself, but a record is usually also kept ofhis entry.Just so, it is a wise precaution to make and keep a recordof all attempts to log into a remote-access time-sharingsystem, and certainly all unsuccessful attempts..PPBad guys fall on a spectrum whose one end is someone withordinary access to a system and whose goal is to findout a particular password (usually that of the super-user)and, at the other end, someone who wishes to collect asmuch password information as possible from as many systemsas possible.Most of the work reported here serves to frustrate the latter type;our experience indicates that the former type of bad guy neverwas very successful..PPWe recognize that a time-sharing system must operate in ahostile environment.We did not attempt to hide the security aspects of the operatingsystem, thereby playing the customary make-believe game inwhich weaknesses of the system are not discussed no matterhow apparent.Rather we advertised the password algorithm and invited attackin the belief that this approach would minimize future trouble.The approach has been successful..SG MH-1271-RM/KT.SHReferences.IP [1]Ritchie, D.M. and Thompson, K.The UNIX Time-Sharing System..IComm. ACM.B17.R(July 1974),pp. 365-375..IP [2].IProposed Federal Information Processing Data Encryption Standard..RFederal Register (40FR12134), March 17, 1975.IP [3]Wilkes, M. V..ITime-Sharing Computer Systems..RAmerican Elsevier,New York, (1968)..IP [4]U. S. Patent Number 2,089,603.