| 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. |