home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / doc / password < prev    next >
Encoding:
Text File  |  1979-01-10  |  20.2 KB  |  559 lines

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