.\" tbl mm ^ eqn ^ troff -ms.EQdelim $$.EN.RP....TM 78-1271-5 39199 39199-11.ND April 3, 1978.TLPassword Security:A Case History.OKEncryptionComputing.AU "MH 2C-524" 3878Robert Morris.AU "MH 2C-523" 2394Ken Thompson.AI.MH.ABThis paper describes the history of the design of thepassword security scheme on a remotely accessed time-sharingsystem.The present design was the result of counteringobserved attempts to penetrate the system.The result is a compromise between extreme security andease of use..AE.CS 6 0 6 0 0 4.SHINTRODUCTION.PPPassword security on the.UXtime-sharing system [1] is provided by acollection of programswhose elaborate and strange design is the outgrowth ofmany years of experience with earlier versions.To help develop a secure system, we have had a continuingcompetition to devise new ways toattack the security of the system (the bad guy) and, at the same time, todevise new techniques to resist the new attacks (the good guy).This competition has been in the same vein as thecompetition of long standing between manufacturers of armorplate and those of armor-piercing shells.For this reason, the description that follows willtrace the history of the password system rather than simplypresenting the program in its current state.In this way, the reasons for the design will be made clearer,as the design cannot be understood without alsounderstanding the potential attacks..PPAn underlying goal has been to provide password securityat minimal inconvenience to the users of the system.For example, those who want to run a completely opensystem without passwords, or to have passwords only at theoption of the individual users, are able to do so, whilethose who require all of their users to have passwordsgain a high degree of securityagainst penetration of the system by unauthorizedusers..PPThe password system must be able not only to preventany access to the system by unauthorized users(i.e. prevent them from logging in at all),but it must alsoprevent users who are already logged in from doingthings that they are not authorized to do.The so called ``super-user'' password, for example, is especiallycritical because the super-user has all sorts ofpermissions and has essentially unlimited access toall system resources..PPPassword security is of course only one component ofoverall system security, but it is an essential component.Experience has shown that attempts to penetrateremote-access systems have been astonishinglysophisticated..PPRemote-access systems are peculiarly vulnerable topenetration by outsiders as there are threats at theremote terminal, along the communications link, as wellas at the computer itself.Although the security of a password encryption algorithmis an interesting intellectual and mathematical problem,it is only one tiny facet of a very large problem.In practice, physical security of the computer, communicationssecurity of the communications link, and physical controlof the computer itself loom as far more important issues.Perhaps most important of all is control over the actionsof ex-employees, since they are not under any direct controland they may have intimateknowledge about the system, its resources, andmethods of access.Good system security involves realisticevaluation of the risks not only of deliberateattacks but also of casual unauthorized accessand accidental disclosure..SHPROLOGUE.PPThe UNIX system was first implemented with a password file that containedthe actual passwords of all the users, and for that reasonthe password file had tobe heavily protected against being either read or written.Although historically, this had been the technique usedfor remote-access systems,it was completely unsatisfactory for several reasons..PPThe technique is excessively vulnerable to lapses insecurity.Temporary loss of protection can occur whenthe password file is being edited or otherwise modified.There is no way to prevent the making of copies byprivileged users.Experience with several earlier remote-access systemsshowed that such lapses occur with frightening frequency.Perhaps the most memorable such occasion occurredin the early 60's whena system administrator on the CTSS system at MITwas editing thepassword file and another system administrator was editingthe daily message that is printed on everyone's terminalon login.Due to a software design error, the temporary editor filesof the two users were interchanged and thus, for a time, the passwordfile was printed on every terminal when it was logged in..PPOnce such a lapse in security has been discovered, everyone'spassword must be changed, usually simultaneously, at a considerableadministrative cost.This is not a great matter, butfar more serious is the high probability of such lapsesgoing unnoticed by the system administrators..PPSecurity against unauthorized disclosure of the passwords was,in the last analysis, impossible with this system because,for example, if thecontents of the file system are put on to magnetic tape forbackup, as they must be, then anyone who has physicalaccess to the tapecan read anything on it with no restriction..PPMany programs must get information of various kindsabout the users of the system, and these programs in generalshould have no special permission to read the password file.The information which should have been in the password file actually wasdistributed (or replicated) into a number of files, all ofwhich had to be updated whenever a user was added to ordropped from the system..SHTHE FIRST SCHEME.PPThe obvious solution is to arrange that the passwords notappear in the system at all, and it is not difficult to decidethat this can be done by encrypting each user's password,putting only the encrypted form in the password file, andthrowing away his original password (the one thathe typed in).When the user later tries to log in to the system, the passwordthat he types is encrypted and compared with the encryptedversion in the password file.If the two match, his login attempt is accepted.Such a scheme was first describedin [3, p.91ff.].It also seemed advisable to devisea system in which neither the password file nor thepassword program itself needed to beprotected against being read by anyone..PPAll that was needed to implement these ideaswas to find a means of encryption that was very difficultto invert, even when the encryption programis available.Most of the standard encryption methods used (in the past)for encryption of messages are rather easy to invert.A convenient and rather good encryption program happenedto exist on the system at the time; it simulated theM-209 cipher machine [4]used by the U.S. Army during World War II.It turned out that the M-209 program was usable, but witha given key, the ciphers produced by this program aretrivial to invert.It is a much more difficult matter to find out the keygiven the cleartext input and the enciphered output of the program.Therefore,the password was used not as the text to be encrypted but as thekey, and a constant was encrypted using this key.The encrypted result was entered into the password file..SHATTACKS ON THE FIRST APPROACH.PPSuppose that the bad guy has availablethe text of the password encryption program andthe complete password file.Suppose also that he has substantial computingcapacity at his disposal..PPOne obvious approach to penetrating the passwordmechanism is to attempt to find a general method of invertingthe encryption algorithm.Very possibly this can be done, but fewsuccessful resultshave come to light, despite substantial efforts extendingover a period of more than five years.The results have not proved to be very usefulin penetrating systems..PPAnother approach to penetration is simply to keep tryingpotentialpasswords until one succeeds; this is a general cryptanalyticapproach called.Ikey search..RHuman beings being what they are, there is a strong tendencyfor people to choose relatively short and simple passwords thatthey can remember.Given free choice, most people will choose their passwordsfrom a restricted character set (e.g. all lower-case letters),and will often choose words or names.This human habit makes the key search job a great deal easier..PPThe critical factor involved in key search is the amount oftime needed to encrypt a potential password and to check the resultagainst an entry in the password file.The running time to encrypt one trial password and checkthe result turned out to be approximately 1.25 milliseconds ona PDP-11/70 when the encryption algorithm was recoded formaximum speed.It is takes essentially no more time to test the encryptedtrial password against all the passwords inan entire password file, or for that matter, againstany collection of encrypted passwords, perhaps collectedfrom many installations..PPIf we want to check all passwords of length.In.Rthat consist entirely of lower-case letters, the numberof such passwords is $26 sup n$.If we suppose that the password consists ofprintable characters only, then the number of possible passwordsis somewhat less than $95 sup n$.(The standard system ``character erase'' and ``line kill''characters are, for example, not primecandidates.)We can immediately estimate the running time of a program thatwill test every password of a given length with all of itscharacters chosen from some set of characters.The following table gives estimates of the running timerequired on a PDP-11/70to test all possible character strings of length $n$chosen from various sets of characters: namely, all lower-caseletters, all lower-case letters plus digits,all alphanumeric characters, all 95 printableASCII characters, and finally all 128 ASCII characters..TSccccccccccccnnnnnn.	26 lower-case	36 lower-case letters	62 alphanumeric	95 printable	all 128 ASCIIn	letters	and digits	characters	characters	characters.sp .51	30 msec.	40 msec.	80 msec.	120 msec.	160 msec.2	800 msec.	2 sec.	5 sec.	11 sec.	20 sec.3	22 sec.	58 sec.	5 min.	17 min.	43 min.4	10 min.	35 min.	5 hrs.	28 hrs.	93 hrs.5	4 hrs.	21 hrs.	318 hrs.6	107 hrs..TE.LPOne has to conclude that it is no great matter for someone withaccess to a PDP-11 to test all lower-case alphabetic strings upto length fiveand, given access to the machine for, say, several weekends, to testall such strings up to six characters in length.By using such a program against a collection of actual encryptedpasswords, a substantial fraction of all the passwords will be