MirOS Manual: 17.password(SMM)


Password Security: A Case History                        SMM:17-1

                Password Security: A Case History

                          Robert Morris

                          Ken Thompson

                     AT&T Bell Laboratories
                         Murray Hill, NJ

                            ABSTRACT

          This paper describes the history of the design  of
     the  password  security  scheme  on a remotely accessed
     time-sharing system. The present design was the  result
     of  countering  observed attempts to penetrate the sys-
     tem. The result is a compromise between  extreme  secu-
     rity and ease of use.

INTRODUCTION

     Password security on the UNIX- time-sharing  system  [1]  is
provided  by a collection of programs whose elaborate and strange
design is the outgrowth of many years of experience with  earlier
versions. To help develop a secure system, we have had a continu-
ing competition to devise new ways to attack the security of  the
system  (the  bad guy) and, at the same time, to devise new tech-
niques to resist the new attacks (the good guy). This competition
has  been  in  the  same vein as the competition of long standing
between manufacturers of armor plate and those of  armor-piercing
shells.  For this reason, the description that follows will trace
the history of the password system rather than simply  presenting
the  program  in  its current state. In this way, the reasons for
the design will be made clearer, as the design cannot  be  under-
stood without also understanding the potential attacks.

     An underlying goal has been to provide password security  at
minimal  inconvenience  to  the users of the system. For example,
those who want to run a completely open system without passwords,
or  to have passwords only at the option of the individual users,
are able to do so, while those who require all of their users  to
have passwords gain a high degree of security against penetration
of the system by unauthorized users.

_________________________
- UNIX is a registered trademark of AT&T  Bell  Labora-
tories in the USA and other countries.

SMM:17-2                        Password Security: A Case History

     The password system must be able not  only  to  prevent  any
access  to  the  system  by unauthorized users (i.e. prevent them
from logging in at all), but it must also prevent users  who  are
already  logged in from doing things that they are not authorized
to do. The so called ``super-user''  password,  for  example,  is
especially  critical because the super-user has all sorts of per-
missions and has  essentially  unlimited  access  to  all  system
resources.

     Password security is of course only one component of overall
system security, but it is an essential component. Experience has
shown that attempts to penetrate remote-access systems have  been
astonishingly sophisticated.

     Remote-access systems are peculiarly vulnerable to  penetra-
tion  by  outsiders  as there are threats at the remote terminal,
along the communications link, as well as at the computer itself.
Although  the  security  of a password encryption algorithm is an
interesting intellectual and mathematical problem, it is only one
tiny  facet  of a very large problem. In practice, physical secu-
rity of the computer, communications security of  the  communica-
tions  link,  and physical control of the computer itself loom as
far more important issues. Perhaps most important of all is  con-
trol  over  the actions of ex-employees, since they are not under
any direct control and they may have intimate knowledge about the
system,  its  resources, and methods of access. Good system secu-
rity involves realistic evaluation of the risks not only of deli-
berate  attacks  but  also  of  casual  unauthorized  access  and
accidental disclosure.

PROLOGUE

     The UNIX system was first implemented with a  password  file
that  contained  the  actual  passwords of all the users, and for
that reason the password file had to be heavily protected against
being  either  read  or  written. Although historically, this had
been the technique used for remote-access systems,  it  was  com-
pletely unsatisfactory for several reasons.

     The technique is excessively vulnerable to lapses  in  secu-
rity.  Temporary  loss  of protection can occur when the password
file is being edited or otherwise modified. There is  no  way  to
prevent the making of copies by privileged users. Experience with
several earlier remote-access systems  showed  that  such  lapses
occur with frightening frequency. Perhaps the most memorable such
occasion occurred in the early 60's when a  system  administrator
on  the  CTSS  system  at  MIT  was editing the password file and
another system administrator was editing the daily  message  that
is  printed  on  everyone's  terminal on login. Due to a software
design error, the temporary editor files of the  two  users  were
interchanged  and thus, for a time, the password file was printed
on every terminal when it was logged in.

     Once  such  a  lapse  in  security  has   been   discovered,

Password Security: A Case History                        SMM:17-3

everyone's password must be changed, usually simultaneously, at a
considerable administrative cost. This is not a great matter, but
far  more  serious  is  the high probability of such lapses going
unnoticed by the system administrators.

     Security against unauthorized disclosure  of  the  passwords
was,  in  the last analysis, impossible with this system because,
for example, if the contents of the file system  are  put  on  to
magnetic  tape  for  backup, as they must be, then anyone who has
physical access to the tape can read anything on it with no  res-
triction.

     Many programs must get information of  various  kinds  about
the  users  of  the  system, and these programs in general should
have no special permission to read the password file. The  infor-
mation  which  should have been in the password file actually was
distributed (or replicated) into a number of files, all of  which
had  to  be  updated whenever a user was added to or dropped from
the system.

THE FIRST SCHEME

     The obvious solution is to arrange that  the  passwords  not
appear  in  the  system at all, and it is not difficult to decide
that this can be done by encrypting each user's password, putting
only  the  encrypted form in the password file, and throwing away
his original password (the one that he typed in). When  the  user
later  tries  to log in to the system, the password that he types
is encrypted and compared with the encrypted version in the pass-
word  file. If the two match, his login attempt is accepted. Such
a scheme was first described in  [3,  p.91ff.].  It  also  seemed
advisable  to  devise a system in which neither the password file
nor the password program itself needed to  be  protected  against
being read by anyone.

     All that was needed to implement these ideas was to  find  a
means  of encryption that was very difficult to invert, even when
the encryption program is available. Most of the standard encryp-
tion  methods  used  (in the past) for encryption of messages are
rather easy to invert. A convenient and  rather  good  encryption
program happened to exist on the system at the time; it simulated
the M-209 cipher machine [4] used by the U.S. Army  during  World
War II. It turned out that the M-209 program was usable, but with
a given key, the ciphers produced by this program are trivial  to
invert.  It  is  a much more difficult matter to find out the key
given the cleartext input and the enciphered output of  the  pro-
gram.  Therefore,  the  password  was  used not as the text to be
encrypted but as the key, and a constant was encrypted using this
key. The encrypted result was entered into the password file.

ATTACKS ON THE FIRST APPROACH

     Suppose that the bad guy has available the text of the pass-
word  encryption  program and the complete password file. Suppose

SMM:17-4                        Password Security: A Case History

also that he has substantial computing capacity at his disposal.

     One obvious approach to penetrating the  password  mechanism
is  to  attempt to find a general method of inverting the encryp-
tion algorithm. Very possibly this can be done, but few  success-
ful  results  have  come  to  light,  despite substantial efforts
extending over a period of more than five years. The results have
not proved to be very useful in penetrating systems.

     Another approach to penetration is  simply  to  keep  trying
potential passwords until one succeeds; this is a general crypta-
nalytic approach called key search. Human beings being what  they
are,  there  is a strong tendency for people to choose relatively
short and simple passwords that they  can  remember.  Given  free
choice, most people will choose their passwords from a restricted
character set (e.g.  all  lower-case  letters),  and  will  often
choose  words or names. This human habit makes the key search job
a great deal easier.

     The critical factor involved in key search is the amount  of
time  needed  to  encrypt  a  potential password and to check the
result against an entry in the password file. The running time to
encrypt  one trial password and check the result turned out to be
approximately 1.25 milliseconds on a PDP-11/70 when  the  encryp-
tion  algorithm was recoded for maximum speed. It is takes essen-
tially no more time to test the encrypted trial password  against
all the passwords in an entire password file, or for that matter,
against any collection of encrypted passwords, perhaps  collected
from many installations.

     If we want to check all passwords of length n  that  consist
entirely  of  lower-case letters, the number of such passwords is
26n. If we suppose that the password consists of printable  char-
acters  only,  then  the number of possible passwords is somewhat
less than 95n.  (The  standard  system  ``character  erase''  and
``line kill'' characters are, for example, not prime candidates.)
We can immediately estimate the running time of  a  program  that
will  test every password of a given length with all of its char-
acters chosen from some set of characters.  The  following  table
gives  estimates  of  the running time required on a PDP-11/70 to
test all possible character strings of length n chosen from vari-
ous  sets  of  characters:  namely,  all  lower-case letters, all
lower-case letters plus digits, all alphanumeric characters,  all
95  printable ASCII characters, and finally all 128 ASCII charac-
ters.

    26 lower-case   36 lower-case letters   62 alphanumeric   95 printable   all 128 ASCII
n      letters           and digits           characters       characters     characters
1      30 msec.           40 msec.              80 msec.       120 msec.       160 msec.
2     800 msec.            2 sec.                5 sec.         11 sec.         20 sec.
3      22 sec.            58 sec.                5 min.         17 min.         43 min.
4      10 min.            35 min.                5 hrs.         28 hrs.         93 hrs.
5       4 hrs.            21 hrs.              318 hrs.
6     107 hrs.

Password Security: A Case History                        SMM:17-5

One has to conclude that it is no great matter for  someone  with
access  to  a PDP-11 to test all lower-case alphabetic strings up
to length five and, given access to the machine for, say, several
weekends,  to  test  all  such  strings  up  to six characters in
length. By using such a program against a  collection  of  actual
encrypted  passwords, a substantial fraction of all the passwords
will be found.

     Another profitable approach for the bad guy is  to  use  the
word  list from a dictionary or to use a list of names. For exam-
ple, a large  commercial  dictionary  contains  typicallly  about
250,000  words; these words can be checked in about five minutes.
Again, a noticeable fraction of any collection of passwords  will
be  found.  Improvements  and  extensions will be (and have been)
found by a determined bad guy. Some ``good'' things to try are:

-    The dictionary with the words spelled backwards.

-    A list of first  names  (best  obtained  from  some  mailing
     list).  Last  names,  street names, and city names also work
     well.

-    The above with initial upper-case letters.

-    All valid license plate numbers in your state.  (This  takes
     about five hours in New Jersey.)

-    Room numbers, social security  numbers,  telephone  numbers,
     and the like.

     The authors have conducted experiments to try  to  determine
typical  users'  habits  in  the choice of passwords when no con-
straint is put on their choice. The results  were  disappointing,
except  to  the bad guy. In a collection of 3,289 passwords gath-
ered from many users over a long period of time;

     15 were a single ASCII character;

     72 were strings of two ASCII characters;

     464 were strings of three ASCII characters;

     477 were string of four alphamerics;

     706 were five letters, all upper-case or all lower-case;

     605 were six letters, all lower-case.

An additional 492 passwords appeared in  various  available  dic-
tionaries,  name lists, and the like. A total of 2,831, or 86% of
this sample of passwords fell into one of these classes.

     There was, of course, considerable overlap between the  dic-
tionary results and the character string searches. The dictionary

SMM:17-6                        Password Security: A Case History

search alone, which required only five minutes to  run,  produced
about one third of the passwords.

     Users could be urged (or forced) to use either longer  pass-
words  or  passwords  chosen  from a larger character set, or the
system could itself choose passwords for the users.

AN ANECDOTE

     An entertaining and instructive example is the attempt  made
at  one installation to force users to use less predictable pass-
words. The users did not choose their own passwords;  the  system
supplied  them. The supplied passwords were eight characters long
and were taken from the character set  consisting  of  lower-case
letters and digits. They were generated by a pseudo-random number
generator with only 215 starting values.  The  time  required  to
search  (again  on  a PDP-11/70) through all character strings of
length 8 from a 36-character alphabet is 112 years.

     Unfortunately, only 215 of them need be looked  at,  because
that  is the number of possible outputs of the random number gen-
erator. The bad guy did, in fact, generate and test each of these
strings  and  found  every  one of the system-generated passwords
using a total of only about one minute of machine time.

IMPROVEMENTS TO THE FIRST APPROACH

1. Slower Encryption

     Obviously, the first algorithm used was far  too  fast.  The
announcement  of the DES encryption algorithm [2] by the National
Bureau of Standards was timely and  fortunate.  The  DES  is,  by
design,  hard to invert, but equally valuable is the fact that it
is extremely slow when  implemented  in  software.  The  DES  was
implemented  and used in the following way: The first eight char-
acters of the user's password are used as a key for the DES; then
the  algorithm  is used to encrypt a constant. Although this con-
stant is zero at the moment, it is easily accessible and  can  be
made  installation-dependent.  Then the DES algorithm is iterated
25 times and the resulting 64  bits  are  repacked  to  become  a
string of 11 printable characters.

2. Less Predictable Passwords

     The password entry program was modified so as  to  urge  the
user  to use more obscure passwords. If the user enters an alpha-
betic password (all upper-case or all  lower-case)  shorter  than
six characters, or a password from a larger character set shorter
than five characters, then the program asks him to enter a longer
password. This further reduces the efficacy of key search.

     These improvements make it exceedingly difficult to find any
individual  password.  The  user is warned of the risks and if he
cooperates, he is very safe indeed. On the other hand, he is  not

Password Security: A Case History                        SMM:17-7

prevented from using his spouse's name if he wants to.

3. Salted Passwords

     The key search technique is still likely to turn  up  a  few
passwords when it is used on a large collection of passwords, and
it seemed wise to make this task as  difficult  as  possible.  To
this  end, when a password is first entered, the password program
obtains a 12-bit random number (by reading the  real-time  clock)
and  appends  this to the password typed in by the user. The con-
catenated string is encrypted and both the 12-bit random quantity
(called  the  salt)  and  the 64-bit result of the encryption are
entered into the password file.

     When the user later logs in to the system, the 12-bit  quan-
tity  is  extracted  from  the  password file and appended to the
typed password. The encrypted result is required, as  before,  to
be  the  same as the remaining 64 bits in the password file. This
modification does not increase the task of finding any individual
password,  starting  from  scratch, but now the work of testing a
given character string against a large  collection  of  encrypted
passwords  has been multiplied by 4096 (212). The reason for this
is that there are 4096 encrypted versions of  each  password  and
one of them has been picked more or less at random by the system.

     With this modification, it is likely that the  bad  guy  can
spend days of computer time trying to find a password on a system
with hundreds of passwords, and find none at all. More  important
is  the  fact that it becomes impractical to prepare an encrypted
dictionary in advance. Such an encrypted dictionary could be used
to crack new passwords in milliseconds when they appear.

     There is a (not inadvertent) side effect of  this  modifica-
tion.  It  becomes nearly impossible to find out whether a person
with passwords on two or more systems has used the same  password
on all of them, unless you already know that.

4. The Threat of the DES Chip

     Chips to perform the DES encryption are already commercially
available  and  they are very fast. The use of such a chip speeds
up the process of password hunting by three orders of  magnitude.
To  avert this possibility, one of the internal tables of the DES
algorithm (in particular, the so-called E-table) is changed in  a
way  that  depends  on  the  12-bit random number. The E-table is
inseparably wired into the DES chip, so that the commercial  chip
cannot  be  used.  Obviously, the bad guy could have his own chip
designed and built, but the cost would be unthinkable.

5. A Subtle Point

     To login successfully on the UNIX system,  it  is  necessary
after  dialing in to type a valid user name, and then the correct
password for that user name. It is poor design to write the login

SMM:17-8                        Password Security: A Case History

command  in  such  a  way that it tells an interloper when he has
typed in a invalid user name. The response  to  an  invalid  name
should be identical to that for a valid name.

     When the slow encryption algorithm  was  first  implemented,
the  encryption was done only if the user name was valid, because
otherwise there was no encrypted password  to  compare  with  the
supplied  password.  The result was that the response was delayed
by about one-half second if the name was valid, but was immediate
if  invalid. The bad guy could find out whether a particular user
name was valid. The routine was modified to do the encryption  in
either case.

CONCLUSIONS

     On the issue of password security, UNIX is  probably  better
than most systems. The use of encrypted passwords appears reason-
ably secure in the absence of serious attention of experts in the
field.

     It is also worth some effort to conceal even  the  encrypted
passwords.  Some  UNIX  systems have instituted what is called an
``external security code'' that must be typed when  dialing  into
the  system,  but  before  logging  in.  If  this code is changed
periodically, then someone with an old password  will  likely  be
prevented from using it.

     Whenever any security procedure is instituted that  attempts
to  deny  access  to  unauthorized  persons, it is wise to keep a
record of both successful and unsuccessful attempts to get at the
secured  resource.  Just as an out-of-hours visitor to a computer
center normally must not only identify himself, but a  record  is
usually  also kept of his entry. Just so, it is a wise precaution
to make and keep a record of all attempts to log into  a  remote-
access   time-sharing  system,  and  certainly  all  unsuccessful
attempts.

     Bad guys fall on a spectrum whose one end  is  someone  with
ordinary  access to a system and whose goal is to find out a par-
ticular password (usually that of the  super-user)  and,  at  the
other  end, someone who wishes to collect as much password infor-
mation as possible from as many systems as possible. Most of  the
work  reported  here  serves  to  frustrate  the latter type; our
experience indicates that the former type of bad  guy  never  was
very successful.

     We recognize that a time-sharing system must  operate  in  a
hostile  environment.  We  did  not  attempt to hide the security
aspects of the operating system, thereby  playing  the  customary
make-believe  game in which weaknesses of the system are not dis-
cussed no matter how apparent. Rather we advertised the  password
algorithm  and  invited  attack  in the belief that this approach
would minimize future trouble. The approach has been successful.

Password Security: A Case History                        SMM:17-9

References

[1]  Ritchie, D.M. and Thompson, K. The UNIX Time-Sharing System.
     Comm. ACM 17 (July 1974), pp. 365-375.

[2]  Proposed  Federal  Information  Processing  Data  Encryption
     Standard. Federal Register (40FR12134), March 17, 1975

[3]  Wilkes,  M.  V.  Time-Sharing  Computer  Systems.   American
     Elsevier, New York, (1968).

[4]  U. S. Patent Number 2,089,603.

Generated on 2014-07-04 21:17:45 by $MirOS: src/scripts/roff2htm,v 1.79 2014/02/10 00:36:11 tg Exp $

These manual pages and other documentation are copyrighted by their respective writers; their source is available at our CVSweb, AnonCVS, and other mirrors. The rest is Copyright © 2002‒2014 The MirOS Project, Germany.
This product includes material provided by Thorsten Glaser.

This manual page’s HTML representation is supposed to be valid XHTML/1.1; if not, please send a bug report – diffs preferred.