Return to password.ms CVS log

Up to [CSRG BSD Unix] / 43BSDReno / share / doc / smm / 18.password

Annotation of 43BSDReno/share/doc/smm/18.password/password.ms, revision 1.1

1.1     ! root        1: .\"    @(#)password    6.1 (Berkeley) 5/14/86
        !             2: .\"
        !             3: .\" tbl mm ^ eqn ^ troff -ms
        !             4: .EH 'SMM:18-%''Password Security: A Case History'
        !             5: .OH 'Password Security: A Case History''SMM:18-%'
        !             6: .EQ
        !             7: delim $$
        !             8: .EN
        !             9: .\".RP
        !            10: ....TM 78-1271-5 39199 39199-11
        !            11: .ND April 3, 1978
        !            12: .TL
        !            13: Password Security:
        !            14: A Case History
        !            15: .OK
        !            16: .\"Encryption
        !            17: .\"Computing
        !            18: .AU "MH 2C-524" 3878
        !            19: Robert Morris
        !            20: .AU "MH 2C-523" 2394
        !            21: Ken Thompson
        !            22: .AI
        !            23: .MH
        !            24: .AB
        !            25: This paper describes the history of the design of the
        !            26: password security scheme on a remotely accessed time-sharing
        !            27: system.
        !            28: The present design was the result of countering
        !            29: observed attempts to penetrate the system.
        !            30: The result is a compromise between extreme security and
        !            31: ease of use.
        !            32: .AE
        !            33: .CS 6 0 6 0 0 4
        !            34: .SH
        !            35: INTRODUCTION
        !            36: .PP
        !            37: Password security on the
        !            38: .UX
        !            39: time-sharing system [1] is provided by a
        !            40: collection of programs
        !            41: whose elaborate and strange design is the outgrowth of
        !            42: many years of experience with earlier versions.
        !            43: To help develop a secure system, we have had a continuing
        !            44: competition to devise new ways to
        !            45: attack the security of the system (the bad guy) and, at the same time, to
        !            46: devise new techniques to resist the new attacks (the good guy).
        !            47: This competition has been in the same vein as the
        !            48: competition of long standing between manufacturers of armor
        !            49: plate and those of armor-piercing shells.
        !            50: For this reason, the description that follows will
        !            51: trace the history of the password system rather than simply
        !            52: presenting the program in its current state.
        !            53: In this way, the reasons for the design will be made clearer,
        !            54: as the design cannot be understood without also
        !            55: understanding the potential attacks.
        !            56: .PP
        !            57: An underlying goal has been to provide password security
        !            58: at minimal inconvenience to the users of the system.
        !            59: For example, those who want to run a completely open
        !            60: system without passwords, or to have passwords only at the
        !            61: option of the individual users, are able to do so, while
        !            62: those who require all of their users to have passwords
        !            63: gain a high degree of security
        !            64: against penetration of the system by unauthorized
        !            65: users.
        !            66: .PP
        !            67: The password system must be able not only to prevent
        !            68: any access to the system by unauthorized users
        !            69: (i.e. prevent them from logging in at all),
        !            70: but it must also
        !            71: prevent users who are already logged in from doing
        !            72: things that they are not authorized to do.
        !            73: The so called ``super-user'' password, for example, is especially
        !            74: critical because the super-user has all sorts of
        !            75: permissions and has essentially unlimited access to
        !            76: all system resources.
        !            77: .PP
        !            78: Password security is of course only one component of
        !            79: overall system security, but it is an essential component.
        !            80: Experience has shown that attempts to penetrate
        !            81: remote-access systems have been astonishingly
        !            82: sophisticated.
        !            83: .PP
        !            84: Remote-access systems are peculiarly vulnerable to
        !            85: penetration by outsiders as there are threats at the
        !            86: remote terminal, along the communications link, as well
        !            87: as at the computer itself.
        !            88: Although the security of a password encryption algorithm
        !            89: is an interesting intellectual and mathematical problem,
        !            90: it is only one tiny facet of a very large problem.
        !            91: In practice, physical security of the computer, communications
        !            92: security of the communications link, and physical control
        !            93: of the computer itself loom as far more important issues.
        !            94: Perhaps most important of all is control over the actions
        !            95: of ex-employees, since they are not under any direct control
        !            96: and they may have intimate
        !            97: knowledge about the system, its resources, and
        !            98: methods of access.
        !            99: Good system security involves realistic
        !           100: evaluation of the risks not only of deliberate
        !           101: attacks but also of casual unauthorized access
        !           102: and accidental disclosure.
        !           103: .SH
        !           104: PROLOGUE
        !           105: .PP
        !           106: The UNIX system was first implemented with a password file that contained
        !           107: the actual passwords of all the users, and for that reason
        !           108: the password file had to
        !           109: be heavily protected against being either read or written.
        !           110: Although historically, this had been the technique used
        !           111: for remote-access systems,
        !           112: it was completely unsatisfactory for several reasons.
        !           113: .PP
        !           114: The technique is excessively vulnerable to lapses in
        !           115: security.
        !           116: Temporary loss of protection can occur when
        !           117: the password file is being edited or otherwise modified.
        !           118: There is no way to prevent the making of copies by
        !           119: privileged users.
        !           120: Experience with several earlier remote-access systems
        !           121: showed that such lapses occur with frightening frequency.
        !           122: Perhaps the most memorable such occasion occurred
        !           123: in the early 60's when
        !           124: a system administrator on the CTSS system at MIT
        !           125: was editing the
        !           126: password file and another system administrator was editing
        !           127: the daily message that is printed on everyone's terminal
        !           128: on login.
        !           129: Due to a software design error, the temporary editor files
        !           130: of the two users were interchanged and thus, for a time, the password
        !           131: file was printed on every terminal when it was logged in.
        !           132: .PP
        !           133: Once such a lapse in security has been discovered, everyone's
        !           134: password must be changed, usually simultaneously, at a considerable
        !           135: administrative cost.
        !           136: This is not a great matter, but
        !           137: far more serious is the high probability of such lapses
        !           138: going unnoticed by the system administrators.
        !           139: .PP
        !           140: Security against unauthorized disclosure of the passwords was,
        !           141: in the last analysis, impossible with this system because,
        !           142: for example, if the
        !           143: contents of the file system are put on to magnetic tape for
        !           144: backup, as they must be, then anyone who has physical
        !           145: access to the tape
        !           146: can read anything on it with no restriction.
        !           147: .PP
        !           148: Many programs must get information of various kinds
        !           149: about the users of the system, and these programs in general
        !           150: should have no special permission to read the password file.
        !           151: The information which should have been in the password file actually was
        !           152: distributed (or replicated) into a number of files, all of
        !           153: which had to be updated whenever a user was added to or
        !           154: dropped from the system.
        !           155: .SH
        !           156: THE FIRST SCHEME
        !           157: .PP
        !           158: The obvious solution is to arrange that the passwords not
        !           159: appear in the system at all, and it is not difficult to decide
        !           160: that this can be done by encrypting each user's password,
        !           161: putting only the encrypted form in the password file, and
        !           162: throwing away his original password (the one that
        !           163: he typed in).
        !           164: When the user later tries to log in to the system, the password
        !           165: that he types is encrypted and compared with the encrypted
        !           166: version in the password file.
        !           167: If the two match, his login attempt is accepted.
        !           168: Such a scheme was first described
        !           169: in [3, p.91ff.].
        !           170: It also seemed advisable to devise
        !           171: a system in which neither the password file nor the
        !           172: password program itself needed to be
        !           173: protected against being read by anyone.
        !           174: .PP
        !           175: All that was needed to implement these ideas
        !           176: was to find a means of encryption that was very difficult
        !           177: to invert, even when the encryption program
        !           178: is available.
        !           179: Most of the standard encryption methods used (in the past)
        !           180: for encryption of messages are rather easy to invert.
        !           181: A convenient and rather good encryption program happened
        !           182: to exist on the system at the time; it simulated the
        !           183: M-209 cipher machine [4]
        !           184: used by the U.S. Army during World War II.
        !           185: It turned out that the M-209 program was usable, but with
        !           186: a given key, the ciphers produced by this program are
        !           187: trivial to invert.
        !           188: It is a much more difficult matter to find out the key
        !           189: given the cleartext input and the enciphered output of the program.
        !           190: Therefore,
        !           191: the password was used not as the text to be encrypted but as the
        !           192: key, and a constant was encrypted using this key.
        !           193: The encrypted result was entered into the password file.
        !           194: .SH
        !           195: ATTACKS ON THE FIRST APPROACH
        !           196: .PP
        !           197: Suppose that the bad guy has available
        !           198: the text of the password encryption program and
        !           199: the complete password file.
        !           200: Suppose also that he has substantial computing
        !           201: capacity at his disposal.
        !           202: .PP
        !           203: One obvious approach to penetrating the password
        !           204: mechanism is to attempt to find a general method of inverting
        !           205: the encryption algorithm.
        !           206: Very possibly this can be done, but few
        !           207: successful results
        !           208: have come to light, despite substantial efforts extending
        !           209: over a period of more than five years.
        !           210: The results have not proved to be very useful
        !           211: in penetrating systems.
        !           212: .PP
        !           213: Another approach to penetration is simply to keep trying
        !           214: potential
        !           215: passwords until one succeeds; this is a general cryptanalytic
        !           216: approach called
        !           217: .I
        !           218: key search.
        !           219: .R
        !           220: Human beings being what they are, there is a strong tendency
        !           221: for people to choose relatively short and simple passwords that
        !           222: they can remember.
        !           223: Given free choice, most people will choose their passwords
        !           224: from a restricted character set (e.g. all lower-case letters),
        !           225: and will often choose words or names.
        !           226: This human habit makes the key search job a great deal easier.
        !           227: .PP
        !           228: The critical factor involved in key search is the amount of
        !           229: time needed to encrypt a potential password and to check the result
        !           230: against an entry in the password file.
        !           231: The running time to encrypt one trial password and check
        !           232: the result turned out to be approximately 1.25 milliseconds on
        !           233: a PDP-11/70 when the encryption algorithm was recoded for
        !           234: maximum speed.
        !           235: It is takes essentially no more time to test the encrypted
        !           236: trial password against all the passwords in
        !           237: an entire password file, or for that matter, against
        !           238: any collection of encrypted passwords, perhaps collected
        !           239: from many installations.
        !           240: .PP
        !           241: If we want to check all passwords of length
        !           242: .I
        !           243: n
        !           244: .R
        !           245: that consist entirely of lower-case letters, the number
        !           246: of such passwords is $26 sup n$.
        !           247: If we suppose that the password consists of
        !           248: printable characters only, then the number of possible passwords
        !           249: is somewhat less than $95 sup n$.
        !           250: (The standard system ``character erase'' and ``line kill''
        !           251: characters are, for example, not prime
        !           252: candidates.)
        !           253: We can immediately estimate the running time of a program that
        !           254: will test every password of a given length with all of its
        !           255: characters chosen from some set of characters.
        !           256: The following table gives estimates of the running time
        !           257: required on a PDP-11/70
        !           258: to test all possible character strings of length $n$
        !           259: chosen from various sets of characters: namely, all lower-case
        !           260: letters, all lower-case letters plus digits,
        !           261: all alphanumeric characters, all 95 printable
        !           262: ASCII characters, and finally all 128 ASCII characters.
        !           263: .TS
        !           264: cccccc
        !           265: cccccc
        !           266: nnnnnn.
        !           267:        26 lower-case   36 lower-case letters   62 alphanumeric 95 printable    all 128 ASCII
        !           268: n      letters and digits      characters      characters      characters
        !           269: .sp .5
        !           270: 1      30 msec.        40 msec.        80 msec.        120 msec.       160 msec.
        !           271: 2      800 msec.       2 sec.  5 sec.  11 sec. 20 sec.
        !           272: 3      22 sec. 58 sec. 5 min.  17 min. 43 min.
        !           273: 4      10 min. 35 min. 5 hrs.  28 hrs. 93 hrs.
        !           274: 5      4 hrs.  21 hrs. 318 hrs.
        !           275: 6      107 hrs.
        !           276: .TE
        !           277: .LP
        !           278: One has to conclude that it is no great matter for someone with
        !           279: access to a PDP-11 to test all lower-case alphabetic strings up
        !           280: to length five
        !           281: and, given access to the machine for, say, several weekends, to test
        !           282: all such strings up to six characters in length.
        !           283: By using such a program against a collection of actual encrypted
        !           284: passwords, a substantial fraction of all the passwords will be
        !           285: found.
        !           286: .PP
        !           287: Another profitable approach for the bad guy is to use the word
        !           288: list from a dictionary or to use a list of names.
        !           289: For example, a large commercial dictionary contains typicallly about
        !           290: 250,000 words; these words can be checked in about five minutes.
        !           291: Again, a noticeable fraction of any collection of passwords
        !           292: will be found.
        !           293: Improvements and extensions will be (and have been) found by
        !           294: a determined bad guy.
        !           295: Some ``good'' things to try are:
        !           296: .IP -
        !           297: The dictionary with the words spelled backwards.
        !           298: .IP -
        !           299: A list of first names (best obtained from some mailing list).
        !           300: Last names, street names, and city names also work well.
        !           301: .IP -
        !           302: The above with initial upper-case letters.
        !           303: .IP -
        !           304: All valid license plate numbers in your state.
        !           305: (This takes about five hours in New Jersey.)
        !           306: .IP -
        !           307: Room numbers, social security numbers, telephone numbers, and
        !           308: the like.
        !           309: .PP
        !           310: The authors have conducted experiments to try to determine
        !           311: typical users' habits in the choice of passwords when no
        !           312: constraint is put on their choice.
        !           313: The results were disappointing, except to the bad guy.
        !           314: In a collection of 3,289 passwords
        !           315: gathered from many users over a long period of time;
        !           316: .IP
        !           317: 15 were a single ASCII character;
        !           318: .IP
        !           319: 72 were strings of two ASCII characters;
        !           320: .IP
        !           321: 464 were strings of three ASCII characters;
        !           322: .IP
        !           323: 477 were string of four alphamerics;
        !           324: .IP
        !           325: 706 were five letters, all upper-case or all lower-case;
        !           326: .IP
        !           327: 605 were six letters, all lower-case.
        !           328: .LP
        !           329: An additional 492 passwords appeared in various available
        !           330: dictionaries, name lists, and the like.
        !           331: A total of 2,831, or 86% of this sample of passwords fell into one of
        !           332: these classes.
        !           333: .PP
        !           334: There was, of course, considerable overlap between the
        !           335: dictionary results and the character string searches.
        !           336: The dictionary search alone, which required only five
        !           337: minutes to run, produced about one third of the passwords.
        !           338: .PP
        !           339: Users could be urged (or forced) to use either longer passwords
        !           340: or passwords chosen from a larger character set, or the system
        !           341: could itself choose passwords for the users.
        !           342: .SH
        !           343: AN ANECDOTE
        !           344: .PP
        !           345: An entertaining and instructive example is
        !           346: the attempt made at one installation to force users to use less predictable
        !           347: passwords.
        !           348: The users did not choose their own passwords; the system supplied
        !           349: them.
        !           350: The supplied passwords were eight characters long and 
        !           351: were taken from the character set consisting of
        !           352: lower-case letters and digits.
        !           353: They were generated by a pseudo-random number generator
        !           354: with only $2 sup 15$ starting values.
        !           355: The time required to search (again on a PDP-11/70) through
        !           356: all character strings of length 8 from a 36-character
        !           357: alphabet is 112 years.
        !           358: .PP
        !           359: Unfortunately, only $2 sup 15$ of them need be looked at,
        !           360: because that is the number of possible outputs of the random
        !           361: number generator.
        !           362: The bad guy did, in fact, generate and test each of these strings
        !           363: and found every one of the system-generated passwords using
        !           364: a total of only about one minute of machine time.
        !           365: .SH
        !           366: IMPROVEMENTS TO THE FIRST APPROACH
        !           367: .NH
        !           368: Slower Encryption
        !           369: .PP
        !           370: Obviously, the first algorithm used was far too fast.
        !           371: The announcement of the DES encryption algorithm [2]
        !           372: by the National Bureau of Standards
        !           373: was timely and fortunate.
        !           374: The DES is, by design, hard to invert, but equally valuable
        !           375: is the fact that it is extremely slow when implemented in
        !           376: software.
        !           377: The DES was implemented and used in the following way:
        !           378: The first eight characters of the user's password are
        !           379: used as a key for the DES; then the algorithm
        !           380: is used to encrypt a constant.
        !           381: Although this constant is zero at the moment, it is easily
        !           382: accessible and can be made installation-dependent.
        !           383: Then the DES algorithm is iterated 25 times and the
        !           384: resulting 64 bits are repacked to become a string of
        !           385: 11 printable characters.
        !           386: .NH
        !           387: Less Predictable Passwords
        !           388: .PP
        !           389: The password entry program was modified so as to urge
        !           390: the user to use more obscure passwords.
        !           391: If the user enters an alphabetic password (all upper-case or
        !           392: all lower-case) shorter than six characters, or a
        !           393: password from a larger character set shorter than five
        !           394: characters, then the program asks him to enter a
        !           395: longer password.
        !           396: This further reduces the efficacy of key search.
        !           397: .PP
        !           398: These improvements make it exceedingly difficult to find
        !           399: any individual password.
        !           400: The user is warned of the risks and if he cooperates,
        !           401: he is very safe indeed.
        !           402: On the other hand, he is not prevented from using
        !           403: his spouse's name if he wants to.
        !           404: .NH
        !           405: Salted Passwords
        !           406: .PP
        !           407: The key search technique is still
        !           408: likely to turn up a few passwords when it is used
        !           409: on a large collection of passwords, and it seemed wise to make this
        !           410: task as difficult as possible.
        !           411: To this end, when a password is first entered, the password program
        !           412: obtains a 12-bit random number (by reading the real-time clock)
        !           413: and appends this to the password typed in by the user.
        !           414: The concatenated string is encrypted and both the
        !           415: 12-bit random quantity (called the $salt$) and the 64-bit
        !           416: result of the encryption are entered into the password
        !           417: file.
        !           418: .PP
        !           419: When the user later logs in to the system, the 12-bit
        !           420: quantity is extracted from the password file and appended
        !           421: to the typed password.
        !           422: The encrypted result is required, as before, to be the same as the
        !           423: remaining 64 bits in the password file.
        !           424: This modification does not increase the task of finding
        !           425: any individual
        !           426: password,
        !           427: starting from scratch,
        !           428: but now the work of testing a given character string
        !           429: against a large collection of encrypted passwords has
        !           430: been multiplied by 4096 ($2 sup 12$).
        !           431: The reason for this is that there are 4096 encrypted
        !           432: versions of each password and one of them has been picked more
        !           433: or less at random by the system.
        !           434: .PP
        !           435: With this modification,
        !           436: it is likely that the bad guy can spend days of computer
        !           437: time trying to find a password on a system with hundreds
        !           438: of passwords, and find none at all.
        !           439: More important is the fact that it becomes impractical
        !           440: to prepare an encrypted dictionary in advance.
        !           441: Such an encrypted dictionary could be used to crack
        !           442: new passwords in milliseconds when they appear.
        !           443: .PP
        !           444: There is a (not inadvertent) side effect of this
        !           445: modification.
        !           446: It becomes nearly impossible to find out whether a
        !           447: person with passwords on two or more systems has used
        !           448: the same password on all of them,
        !           449: unless you already know that.
        !           450: .NH
        !           451: The Threat of the DES Chip
        !           452: .PP
        !           453: Chips to perform the DES encryption are already commercially
        !           454: available and they are very fast.
        !           455: The use of such a chip speeds up the process of password
        !           456: hunting by three orders of magnitude.
        !           457: To avert this possibility, one of the internal tables
        !           458: of the DES algorithm
        !           459: (in particular, the so-called E-table)
        !           460: is changed in a way that depends on the 12-bit random
        !           461: number.
        !           462: The E-table is inseparably wired into the DES chip,
        !           463: so that the commercial chip cannot be used.
        !           464: Obviously, the bad guy could have his own chip designed and
        !           465: built, but the cost would be unthinkable.
        !           466: .NH
        !           467: A Subtle Point
        !           468: .PP
        !           469: To login successfully on the UNIX system, it is necessary
        !           470: after dialing in to type a valid user name, and then the
        !           471: correct password for that user name.
        !           472: It is poor design to write the login command in such a way that it
        !           473: tells an interloper when he has typed in a invalid user name.
        !           474: The response to an invalid name should be identical to
        !           475: that for a valid name.
        !           476: .PP
        !           477: When the slow encryption algorithm was first implemented,
        !           478: the encryption was done only if the user name was valid,
        !           479: because otherwise there was no encrypted password to
        !           480: compare with the supplied password.
        !           481: The result was that the response was delayed
        !           482: by about one-half second if the name was valid, but was
        !           483: immediate if invalid.
        !           484: The bad guy could find out
        !           485: whether a particular user name was valid.
        !           486: The routine was modified to do the encryption in either
        !           487: case.
        !           488: .SH
        !           489: CONCLUSIONS
        !           490: .PP
        !           491: On the issue of password security, UNIX is probably
        !           492: better than most systems.
        !           493: The use of encrypted passwords appears reasonably
        !           494: secure in the absence of serious attention of experts
        !           495: in the field.
        !           496: .PP
        !           497: It is also worth some effort to conceal even the encrypted
        !           498: passwords.
        !           499: Some UNIX systems have instituted what is called an
        !           500: ``external security code'' that must be typed when
        !           501: dialing into the system, but before logging in.
        !           502: If this code is changed periodically, then someone
        !           503: with an old password will likely be prevented from
        !           504: using it.
        !           505: .PP
        !           506: Whenever any security procedure is instituted that attempts
        !           507: to deny access to unauthorized persons, it is wise to
        !           508: keep a record of both successful and unsuccessful attempts
        !           509: to get at the secured resource.
        !           510: Just as an out-of-hours visitor to a computer center normally
        !           511: must not only identify himself, but a record is usually also kept of
        !           512: his entry.
        !           513: Just so, it is a wise precaution to make and keep a record
        !           514: of all attempts to log into a remote-access time-sharing
        !           515: system, and certainly all unsuccessful attempts.
        !           516: .PP
        !           517: Bad guys fall on a spectrum whose one end is someone with
        !           518: ordinary access to a system and whose goal is to find
        !           519: out a particular password (usually that of the super-user)
        !           520: and, at the other end, someone who wishes to collect as
        !           521: much password information as possible from as many systems
        !           522: as possible.
        !           523: Most of the work reported here serves to frustrate the latter type;
        !           524: our experience indicates that the former type of bad guy never
        !           525: was very successful.
        !           526: .PP
        !           527: We recognize that a time-sharing system must operate in a
        !           528: hostile environment.
        !           529: We did not attempt to hide the security aspects of the operating
        !           530: system, thereby playing the customary make-believe game in
        !           531: which weaknesses of the system are not discussed no matter
        !           532: how apparent.
        !           533: Rather we advertised the password algorithm and invited attack
        !           534: in the belief that this approach would minimize future trouble.
        !           535: The approach has been successful.
        !           536: .SG MH-1271-RM/KT
        !           537: .SH
        !           538: References
        !           539: .IP [1]
        !           540: Ritchie, D.M. and Thompson, K.
        !           541: The UNIX Time-Sharing System.
        !           542: .I
        !           543: Comm. ACM
        !           544: .B
        !           545: 17
        !           546: .R
        !           547: (July 1974),
        !           548: pp. 365-375.
        !           549: .IP [2]
        !           550: .I
        !           551: Proposed Federal Information Processing Data Encryption Standard.
        !           552: .R
        !           553: Federal Register (40FR12134), March 17, 1975
        !           554: .IP [3]
        !           555: Wilkes, M. V.
        !           556: .I
        !           557: Time-Sharing Computer Systems.
        !           558: .R
        !           559: American Elsevier,
        !           560: New York, (1968).
        !           561: .IP [4]
        !           562: U. S. Patent Number 2,089,603.

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.