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