![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to password.ms CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / share / doc / smm / 18.password|
Return to password.ms CVS log | Up to [CSRG BSD Unix] / 43BSDReno / share / doc / smm / 18.password |
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.