⟦ca6cfc5f3⟧

TextFile

%!PS-Adobe-2.1
%%Creator: groff version 0.6
%%DocumentFonts: Times-Roman Times-Italic Times-Bold
%%DocumentSuppliedFonts:
%%DocumentNeededFonts: Times-Roman Times-Italic Times-Bold
%%Pages: 6
%%EndComments
/grops 100 dict def grops begin
%!
% If you add definitions here, be sure to check that MAX_PROLOGUE_DEFS
% in ps.c is large enough.

% The ASCII code of the space character.
/SC 32 def

/A /show load def
/B { 0 SC 3 -1 roll widthshow } bind def
/C { 0 exch ashow } bind def
/D { 0 exch 0 SC 5 2 roll awidthshow } bind def
/E { 0 rmoveto show } bind def
/F { 0 rmoveto 0 SC 3 -1 roll widthshow } bind def
/G { 0 rmoveto 0 exch ashow } bind def
/H { 0 rmoveto 0 exch 0 SC 5 2 roll awidthshow } bind def
/I { 0 exch rmoveto show } bind def
/J { 0 exch rmoveto 0 SC 3 -1 roll widthshow } bind def
/K { 0 exch rmoveto 0 exch ashow } bind def
/L { 0 exch rmoveto 0 exch 0 SC 5 2 roll awidthshow } bind def
/M { rmoveto show } bind def
/N { rmoveto 0 SC 3 -1 roll widthshow } bind def
/O { rmoveto 0 exch ashow } bind def
/P { rmoveto 0 exch 0 SC 5 2 roll awidthshow } bind def
/Q { moveto show } bind def 
/R { moveto 0 SC 3 -1 roll widthshow } bind def
/S { moveto 0 exch ashow } bind def
/T { moveto 0 exch 0 SC 5 2 roll awidthshow } bind def

% name size font SF -

/SF {
	findfont exch
	[ exch dup 0 exch 0 exch neg 0 0 ] makefont
	dup setfont
	[ exch /setfont cvx ] cvx bind def
} bind def

% name a c d font MF

/MF {
	findfont
	[ 5 2 roll
	0 3 1 roll % b
	neg 0 0 ] makefont
	dup setfont
	[ exch /setfont cvx ] cvx bind def
} bind def

	
% BP -

/BP {
	/level0 save def
	1 setlinecap
	1 setlinejoin
	72 RES div dup scale
	LS {
		90 rotate
	} {
		0 PL translate
	} ifelse
	1 -1 scale
} bind def

/EP {
	level0 restore
	showpage
} bind def


% centerx centery radius startangle endangle DA -

/DA {
	newpath arcn stroke
} bind def

% x y SN - x' y'
% round a position to nearest (pixel + (.25,.25))

/SN {
	transform 
	.25 sub exch .25 sub exch
	round .25 add exch round .25 add exch
	itransform
} bind def
	
% endx endy startx starty DL -
% we round the endpoints of the line, so that parallel horizontal
% and vertical lines will appear even

/DL {
	SN
	moveto
	SN
	lineto stroke
} bind def

% centerx centery radius DC -

/DC {
	newpath 0 360 arc closepath
} bind def


/TM matrix def

%  width height centerx centery DE -

/DE {
	TM currentmatrix pop
	translate scale newpath 0 0 .5 0 360 arc closepath
	TM setmatrix
} bind def

% these are for splines

/RC /rcurveto load def
/RL /rlineto load def
/ST /stroke load def
/MT /moveto load def
/CL /closepath load def

% fill the last path

% amount FL -

/FL {
	currentgray exch setgray fill setgray
} bind def

% fill with the ``current color''

/BL /fill load def

/LW /setlinewidth load def
% new_font_name encoding_vector old_font_name RE -

/RE {
	findfont
	dup maxlength dict begin
	{
		1 index /FID ne { def } { pop pop } ifelse
	} forall
	/Encoding exch def
	dup /FontName exch def
	currentdict end definefont pop
} bind def

% hpos vpos EBEGIN -

/EBEGIN {
	moveto
	DEFS begin
} bind def

/EEND /end load def

% llx lly newwid wid newht ht newllx newlly -

/PICTURE {
	translate
	div 3 1 roll div exch scale
	neg exch neg exch translate
	% set the graphics state to default values
	0 setgray
	0 setlinecap
	1 setlinewidth
	0 setlinejoin
	10 setmiterlimit
	[] 0 setdash
	newpath
} bind def
/DEFS 1 dict def DEFS begin/u{.001 mul}bind def end end
%%EndProlog
%%IncludeFont: Times-Roman
%%IncludeFont: Times-Italic
%%IncludeFont: Times-Bold
%%BeginSetup
grops begin/#copies 1 def/RES 72 def/PL 792 def/LS false def/ENC0[/asciicircum
/asciitilde/Scaron/Zcaron/scaron/zcaron/Ydieresis/trademark/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef
/.notdef/.notdef/.notdef/.notdef/space/exclam/quotedbl/numbersign/dollar
/percent/ampersand/quoteright/parenleft/parenright/asterisk/plus/comma/hyphen
/period/slash/zero/one/two/three/four/five/six/seven/eight/nine/colon/semicolon
/less/equal/greater/question/at/A/B/C/D/E/F/G/H/I/J/K/L/M/N/O/P/Q/R/S/T/U/V/W/X
/Y/Z/bracketleft/backslash/bracketright/circumflex/underscore/quoteleft/a/b/c/d
/e/f/g/h/i/j/k/l/m/n/o/p/q/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/tilde
/.notdef/quotesinglbase/guillemotleft/guillemotright/bullet/florin/fraction
/perthousand/dagger/daggerdbl/endash/emdash/ff/fi/fl/ffi/ffl/dotlessi/dotlessj
/grave/hungarumlaut/dotaccent/breve/caron/ring/ogonek/quotedblleft
/quotedblright/oe/lslash/quotedblbase/OE/Lslash/.notdef/exclamdown/cent
/sterling/currency/yen/brokenbar/section/dieresis/copyright/ordfeminine
/guilsinglleft/logicalnot/minus/registered/macron/degree/plusminus/twosuperior
/threesuperior/acute/mu/paragraph/periodcentered/cedilla/onesuperior
/ordmasculine/guilsinglright/onequarter/onehalf/threequarters/questiondown
/Agrave/Aacute/Acircumflex/Atilde/Adieresis/Aring/AE/Ccedilla/Egrave/Eacute
/Ecircumflex/Edieresis/Igrave/Iacute/Icircumflex/Idieresis/Eth/Ntilde/Ograve
/Oacute/Ocircumflex/Otilde/Odieresis/multiply/Oslash/Ugrave/Uacute/Ucircumflex
/Udieresis/Yacute/Thorn/germandbls/agrave/aacute/acircumflex/atilde/adieresis
/aring/ae/ccedilla/egrave/eacute/ecircumflex/edieresis/igrave/iacute
/icircumflex/idieresis/eth/ntilde/ograve/oacute/ocircumflex/otilde/odieresis
/divide/oslash/ugrave/uacute/ucircumflex/udieresis/yacute/thorn/ydieresis]def
/Times-Roman@0 ENC0/Times-Roman RE/Times-Italic@0 ENC0/Times-Italic RE
/Times-Bold@0 ENC0/Times-Bold RE
%%EndSetup
%%Page: 1 1
BP/F0 12/Times-Bold@0 SF(Password Security: A Case History)198.012 123 Q/F1 10
/Times-Italic@0 SF(Robert Morris)259.25 147 Q(Ken Thompson)257.86 165 Q
(ABSTRACT)264.385 207 Q/F2 10/Times-Roman@0 SF .124(This paper describes the h\
istory of the design of the password security scheme on a)133 231 R .637
(remotely accessed time-sharing system.)108 243 R .637
(The present design was the result of countering)5.637 F .561
(observed attempts to penetrate the system.)108 255 R .561
(The result is a compromise between extreme)5.561 F(security and ease of use.)
108 267 Q/F3 10/Times-Bold@0 SF(INTRODUCTION)72 303 Q F2 1.436
(Password security on the)97 318.6 R/F4 9/Times-Roman@0 SF(UNIX)3.936 E F2
3.936<8774>C 1.437
(ime-sharing system [1] is provided by a collection of programs)239.161 318.6 R
.314(whose elaborate and strange design is the outgrowth of many years of expe\
rience with earlier versions.)72 330.6 R -.7(To)5.313 G .131(help develop a se\
cure system, we have had a continuing competition to devise new ways to attack\
 the secu-)72 342.6 R .798(rity of the system \(the bad guy\) and, at the same\
 time, to devise new techniques to resist the new attacks)72 354.6 R .79
(\(the good guy\).)72 366.6 R .79(This competition has been in the same vein a\
s the competition of long standing between)5.79 F .745
(manufacturers of armor plate and those of armor)72 378.6 R .745
(-piercing shells.)-.2 F .744(For this reason, the description that fol-)5.745
F .496(lows will trace the history of the password system rather than simply p\
resenting the program in its current)72 390.6 R 2.68(state. In)72 402.6 R .18
(this way)2.68 F 2.68(,t)-.65 G .18
(he reasons for the design will be made clearer)150.12 402.6 R 2.679(,a)-.4 G
2.679(st)344.056 402.6 S .179(he design cannot be understood with-)353.405
402.6 R(out also understanding the potential attacks.)72 414.6 Q .637(An under\
lying goal has been to provide password security at minimal inconvenience to t\
he users of)97 430.2 R .562(the system.)72 442.2 R .561(For example, those who\
 want to run a completely open system without passwords, or to have)5.562 F
.491(passwords only at the option of the individual users, are able to do so, \
while those who require all of their)72 454.2 R .824(users to have passwords g\
ain a high degree of security against penetration of the system by unauthorize\
d)72 466.2 R(users.)72 478.2 Q 1.378(The password system must be able not only\
 to prevent any access to the system by unauthorized)97 493.8 R 1.015(users \(\
i.e. prevent them from logging in at all\), but it must also prevent users who\
 are already logged in)72 505.8 R .216
(from doing things that they are not authorized to do.)72 517.8 R .216
(The so called `)5.216 F(`super)-.74 E -2.13(-user ')-.2 F 2.716('p)-.74 G .216
(assword, for example, is)405.872 517.8 R .096
(especially critical because the super)72 529.8 R .096
(-user has all sorts of permissions and has essentially unlimited access to)-.2
F(all system resources.)72 541.8 Q .81
(Password security is of course only one component of overall system security)
97 557.4 R 3.311(,b)-.65 G .811(ut it is an essential)426.866 557.4 R 3.554
(component. Experience)72 569.4 R 1.053(has shown that attempts to penetrate r\
emote-access systems have been astonish-)3.554 F(ingly sophisticated.)72 581.4
Q .031(Remote-access systems are peculiarly vulnerable to penetration by outsi\
ders as there are threats at the)97 597 R .232(remote terminal, along the comm\
unications link, as well as at the computer itself.)72 609 R .231
(Although the security of)5.232 F 2.746(ap)72 621 S .247(assword encryption al\
gorithm is an interesting intellectual and mathematical problem, it is only on\
e tiny)84.186 621 R .827(facet of a very lar)72 633 R .827(ge problem.)-.18 F
.827(In practice, physical security of the computer)5.827 F 3.326(,c)-.4 G .826
(ommunications security of)395.688 633 R 1.191(the communications link, and ph\
ysical control of the computer itself loom as far more important issues.)72 645
R 1.265(Perhaps most important of all is control over the actions of ex-employ\
ees, since they are not under any)72 657 R 1.859(direct control and they may h\
ave intimate knowledge about the system, its resources, and methods of)72 669 R
3.619(access. Good)72 681 R 1.119(system security involves realistic evaluatio\
n of the risks not only of deliberate attacks but)3.619 F
(also of casual unauthorized access and accidental disclosure.)72 693 Q .32 LW
76 703 72 703 DL 80 703 76 703 DL 84 703 80 703 DL 88 703 84 703 DL 92 703 88
703 DL 96 703 92 703 DL 100 703 96 703 DL 104 703 100 703 DL 108 703 104 703 DL
112 703 108 703 DL 116 703 112 703 DL 120 703 116 703 DL 124 703 120 703 DL 128
703 124 703 DL 132 703 128 703 DL 136 703 132 703 DL 140 703 136 703 DL 144 703
140 703 DL/F5 8/Times-Roman@0 SF<87>72 713 Q/F6 7/Times-Roman@0 SF(UNIX)2 E F5
(is a trademark of Bell Laboratories.)2 E EP
%%Page: 2 2
BP/F0 10/Times-Roman@0 SF 243.95(SMM:18-2 Password)72 48 R
(Security: A Case History)2.5 E/F1 10/Times-Bold@0 SF(PROLOGUE)72 84 Q F0 .341
(The UNIX system was \214rst implemented with a password \214le that contained\
 the actual passwords of)97 99.6 R .636(all the users, and for that reason the\
 password \214le had to be heavily protected against being either read or)72
111.6 R 3.765(written. Although)72 123.6 R(historically)3.765 E 3.765(,t)-.65 G
1.265(his had been the technique used for remote-access systems, it was com-)
204.035 123.6 R(pletely unsatisfactory for several reasons.)72 135.6 Q .166
(The technique is excessively vulnerable to lapses in security)97 151.2 R 5.166
(.T)-.65 G .165(emporary loss of protection can occur)351.824 151.2 R .916
(when the password \214le is being edited or otherwise modi\214ed.)72 163.2 R
.917(There is no way to prevent the making of)5.917 F .354
(copies by privileged users.)72 175.2 R .354
(Experience with several earlier remote-access systems showed that such lapses)
5.354 F 1.068(occur with frightening frequency)72 187.2 R 6.068(.P)-.65 G 1.069
(erhaps the most memorable such occasion occurred in the early 60')220.592
187.2 R(s)-.55 E .266(when a system administrator on the CTSS system at MIT wa\
s editing the password \214le and another system)72 199.2 R .43
(administrator was editing the daily message that is printed on everyone')72
211.2 R 2.931(st)-.55 G .431(erminal on login.)373.094 211.2 R .431
(Due to a soft-)5.431 F .957(ware design error)72 223.2 R 3.457(,t)-.4 G .957(\
he temporary editor \214les of the two users were interchanged and thus, for a\
 time, the)152.221 223.2 R
(password \214le was printed on every terminal when it was logged in.)72 235.2
Q 1.101(Once such a lapse in security has been discovered, everyone')97 250.8 R
3.602(sp)-.55 G 1.102(assword must be changed, usually)363.222 250.8 R
(simultaneously)72 262.8 Q 2.83(,a)-.65 G 2.83(tac)141.68 262.8 S .33
(onsiderable administrative cost.)159 262.8 R .329(This is not a great matter)
5.33 F 2.829(,b)-.4 G .329(ut far more serious is the)403.205 262.8 R
(high probability of such lapses going unnoticed by the system administrators.)
72 274.8 Q .776(Security against unauthorized disclosure of the passwords was,\
 in the last analysis, impossible with)97 290.4 R .431(this system because, fo\
r example, if the contents of the \214le system are put on to magnetic tape fo\
r backup,)72 302.4 R .02(as they must be, then anyone who has physical access \
to the tape can read anything on it with no restriction.)72 314.4 R .631(Many \
programs must get information of various kinds about the users of the system, \
and these pro-)97 330 R 1.711(grams in general should have no special permissi\
on to read the password \214le.)72 342 R 1.712(The information which)6.712 F
.624(should have been in the password \214le actually was distributed \(or rep\
licated\) into a number of \214les, all of)72 354 R(which had to be updated wh\
enever a user was added to or dropped from the system.)72 366 Q F1
(THE FIRST SCHEME)72 390 Q F0 .171(The obvious solution is to arrange that the\
 passwords not appear in the system at all, and it is not dif-)97 405.6 R .017
(\214cult to decide that this can be done by encrypting each user)72 417.6 R
1.117 -.55('s p).37 H .016(assword, putting only the encrypted form in).55 F
.347(the password \214le, and throwing away his original password \(the one th\
at he typed in\).)72 429.6 R .347(When the user later)5.347 F .412(tries to lo\
g in to the system, the password that he types is encrypted and compared with \
the encrypted ver)72 441.6 R(-)-.2 E 2.196(sion in the password \214le.)72
453.6 R 2.197(If the two match, his login attempt is accepted.)7.196 F 2.197
(Such a scheme was \214rst)7.197 F .203(described in [3, p.91f)72 465.6 R 2.703
(f.]. It)-.18 F .202(also seemed advisable to devise a system in which neither\
 the password \214le nor)2.702 F(the password program itself needed to be prot\
ected against being read by anyone.)72 477.6 Q .587(All that was needed to imp\
lement these ideas was to \214nd a means of encryption that was very dif)97
493.2 R<8c2d>-.18 E 1.138
(cult to invert, even when the encryption program is available.)72 505.2 R
1.137(Most of the standard encryption methods)6.137 F 1.741
(used \(in the past\) for encryption of messages are rather easy to invert.)72
517.2 R 4.241(Ac)6.741 G 1.742(onvenient and rather good)394.074 517.2 R .202(\
encryption program happened to exist on the system at the time; it simulated t\
he M-209 cipher machine [4])72 529.2 R .502(used by the U.S. Army during W)72
541.2 R .502(orld W)-.8 F .502(ar II.)-.8 F .503
(It turned out that the M-209 program was usable, but with a)5.502 F .649
(given key)72 553.2 R 3.149(,t)-.65 G .649
(he ciphers produced by this program are trivial to invert.)119.588 553.2 R
.649(It is a much more dif)5.649 F .649(\214cult matter to)-.18 F .874(\214nd \
out the key given the cleartext input and the enciphered output of the program\
.)72 565.2 R .875(Therefore, the pass-)5.874 F .518
(word was used not as the text to be encrypted but as the key)72 577.2 R 3.017
(,a)-.65 G .517(nd a constant was encrypted using this key)327.721 577.2 R(.)
-.65 E(The encrypted result was entered into the password \214le.)72 589.2 Q F1
-.74(AT)72 613.2 S -.74(TA).74 G(CKS ON THE FIRST APPROACH).74 E F0 .094(Suppo\
se that the bad guy has available the text of the password encryption program \
and the complete)97 628.8 R(password \214le.)72 640.8 Q
(Suppose also that he has substantial computing capacity at his disposal.)5 E
.303(One obvious approach to penetrating the password mechanism is to attempt \
to \214nd a general method)97 656.4 R .076
(of inverting the encryption algorithm.)72 668.4 R -1.11(Ve)5.077 G .077
(ry possibly this can be done, but few successful results have come)1.11 F .949
(to light, despite substantial ef)72 680.4 R .949
(forts extending over a period of more than \214ve years.)-.18 F .948
(The results have not)5.949 F(proved to be very useful in penetrating systems.)
72 692.4 Q .225(Another approach to penetration is simply to keep trying poten\
tial passwords until one succeeds; this)97 708 R .375
(is a general cryptanalytic approach called)72 720 R/F2 10/Times-Italic@0 SF
.375(key sear)2.875 F(ch.)-.37 E F0 .374
(Human beings being what they are, there is a strong)5.375 F EP
%%Page: 3 3
BP/F0 10/Times-Roman@0 SF(Password Security: A Case History)72 48 Q(SMM:18-3)
459.55 48 Q .861(tendency for people to choose relatively short and simple pas\
swords that they can remember)72 84 R 5.862(.G)-.55 G .862(iven free)467.878 84
R .432(choice, most people will choose their passwords from a restricted chara\
cter set \(e.g. all lower)72 96 R .432(-case letters\),)-.2 F
(and will often choose words or names.)72 108 Q
(This human habit makes the key search job a great deal easier)5 E(.)-.55 E
.825(The critical factor involved in key search is the amount of time needed t\
o encrypt a potential pass-)97 123.6 R .913
(word and to check the result against an entry in the password \214le.)72 135.6
R .912(The running time to encrypt one trial)5.912 F .516(password and check t\
he result turned out to be approximately 1.25 milliseconds on a PDP-1)72 147.6
R .516(1/70 when the)-.37 F 1.587
(encryption algorithm was recoded for maximum speed.)72 159.6 R 1.586
(It is takes essentially no more time to test the)6.586 F .325(encrypted trial\
 password against all the passwords in an entire password \214le, or for that \
matter)72 171.6 R 2.826(,a)-.4 G .326(gainst any)462.844 171.6 R
(collection of encrypted passwords, perhaps collected from many installations.)
72 183.6 Q .019(If we want to check all passwords of length)97 199.2 R/F1 10
/Times-Italic@0 SF(n)2.519 E F0 .019(that consist entirely of lower)2.519 F
.019(-case letters, the number of)-.2 F .1(such passwords is 26)72 211.2 R/F2 7
/Times-Italic@0 SF(n)156.649 207 Q F0 5.101(.I)160.796 211.2 S 2.601(fw)171.727
211.2 S 2.601(es)184.878 211.2 S .101
(uppose that the password consists of printable characters only)195.809 211.2 R
2.601(,t)-.65 G .101(hen the num-)451.028 211.2 R 1.018
(ber of possible passwords is somewhat less than 95)72 223.2 R F2(n)285.313 219
Q F0 6.018(.\()289.46 223.2 S 1.017(The standard system `)301.308 223.2 R 1.017
(`character erase')-.74 F 3.517('a)-.74 G 1.017(nd `)469.563 223.2 R(`line)-.74
E(kill')72 235.2 Q 2.872('c)-.74 G .372
(haracters are, for example, not prime candidates.\))98.572 235.2 R 1.972 -.8
(We c)5.372 H .372(an immediately estimate the running time of).8 F 2.771(ap)72
247.2 S .27(rogram that will test every password of a given length with all of\
 its characters chosen from some set of)84.211 247.2 R 2.593(characters. The)72
259.2 R .093
(following table gives estimates of the running time required on a PDP-1)2.593
F .094(1/70 to test all pos-)-.37 F .398(sible character strings of length)72
271.2 R F1(n)3.168 E F0 .397(chosen from various sets of characters: namely)
3.108 F 2.897(,a)-.65 G .397(ll lower)409.699 271.2 R .397(-case letters, all)
-.2 F(lower)72 283.2 Q .421(-case letters plus digits, all alphanumeric charac\
ters, all 95 printable ASCII characters, and \214nally all)-.2 F
(128 ASCII characters.)72 295.2 Q(26 lower)92 313.2 Q 12.5(-case 36)-.2 F
(lower)2.5 E(-case letters)-.2 E(62 alphanumeric)260.16 313.2 Q(95 printable)
342.09 313.2 Q(all 128 ASCII)405.14 313.2 Q 30.585(nl)72 325.2 S 49.775
(etters and)110.365 325.2 R 47.39(digits characters)2.5 F 24.05
(characters characters)345.85 325.2 R 27.53(13)72 343.2 S 2.5(0m)109.53 343.2 S
43.53(sec. 40)124.81 343.2 R 54.19(msec. 80)2.5 F 29.44(msec. 120)2.5 F 24.03
(msec. 160)2.5 F(msec.)2.5 E 22.53(28)72 355.2 S(00 msec.)104.53 355.2 Q 2.5
(2s)191.11 355.2 S 66.97(ec. 5)202.5 355.2 R 42.59(sec. 1)2.5 F 2.5(1s)-.37 G
36.81(ec. 20)367.23 355.2 R(sec.)2.5 E 27.53(32)72 367.2 S 2.5(2s)109.53 367.2
S 51.31(ec. 58)120.92 367.2 R 66.97(sec. 5)2.5 F 39.43(min. 17)2.5 F 34.02
(min. 43)2.5 F(min.)2.5 E 27.53(41)72 379.2 S 2.5(0m)109.53 379.2 S 48.52
(in. 35)124.81 379.2 R 64.18(min. 5)2.5 F 42.77(hrs. 28)2.5 F 37.36(hrs. 93)2.5
F(hrs.)2.5 E 32.53(54)72 391.2 S 51.86(hrs. 21)117.03 391.2 R 57.52(hrs. 318)
2.5 F(hrs.)2.5 E 22.53(61)72 403.2 S(07 hrs.)104.53 403.2 Q .826(One has to co\
nclude that it is no great matter for someone with access to a PDP-1)72 424.8 R
3.327(1t)-.37 G 3.327(ot)422.019 424.8 S .827(est all lower)433.126 424.8 R
(-case)-.2 E .667
(alphabetic strings up to length \214ve and, given access to the machine for)72
436.8 R 3.167(,s)-.4 G(ay)374.955 436.8 Q 3.167(,s)-.65 G .667
(everal weekends, to test all)393.302 436.8 R .022
(such strings up to six characters in length.)72 448.8 R .022
(By using such a program against a collection of actual encrypted)5.022 F
(passwords, a substantial fraction of all the passwords will be found.)72 460.8
Q .085(Another pro\214table approach for the bad guy is to use the word list f\
rom a dictionary or to use a list of)97 476.4 R 3.163(names. For)72 488.4 R
.664(example, a lar)3.163 F .664
(ge commercial dictionary contains typicallly about 250,000 words; these words)
-.18 F .646(can be checked in about \214ve minutes.)72 500.4 R .645
(Again, a noticeable fraction of any collection of passwords will be)5.645 F
4.403(found. Improvements)72 512.4 R 1.903
(and extensions will be \(and have been\) found by a determined bad guy)4.403 F
6.904(.S)-.65 G(ome)486.78 512.4 Q -.74(``)72 524.4 S(good').74 E 2.5('t)-.74 G
(hings to try are:)109.12 524.4 Q 21.67(-T)72 540 S
(he dictionary with the words spelled backwards.)103.11 540 Q 21.67(-A)72 555.6
S .005(list of \214rst names \(best obtained from some mailing list\).)106.726
555.6 R .005(Last names, street names, and city names)5.005 F(also work well.)
97 567.6 Q 21.67(-T)72 583.2 S(he above with initial upper)103.11 583.2 Q
(-case letters.)-.2 E 21.67(-A)72 598.8 S
(ll valid license plate numbers in your state.)104.22 598.8 Q
(\(This takes about \214ve hours in New Jersey)5 E(.\))-.65 E 21.67(-R)72 614.4
S(oom numbers, social security numbers, telephone numbers, and the like.)103.67
614.4 Q 1.305(The authors have conducted experiments to try to determine typic\
al users' habits in the choice of)97 630 R .143
(passwords when no constraint is put on their choice.)72 642 R .143
(The results were disappointing, except to the bad guy)5.143 F(.)-.65 E(In a c\
ollection of 3,289 passwords gathered from many users over a long period of ti\
me;)72 654 Q(15 were a single ASCII character;)97 669.6 Q
(72 were strings of two ASCII characters;)97 685.2 Q
(464 were strings of three ASCII characters;)97 700.8 Q
(477 were string of four alphamerics;)97 716.4 Q EP
%%Page: 4 4
BP/F0 10/Times-Roman@0 SF 243.95(SMM:18-4 Password)72 48 R
(Security: A Case History)2.5 E(706 were \214ve letters, all upper)97 84 Q
(-case or all lower)-.2 E(-case;)-.2 E(605 were six letters, all lower)97 99.6
Q(-case.)-.2 E .267(An additional 492 passwords appeared in various available \
dictionaries, name lists, and the like.)72 115.2 R 2.768(At)5.268 G .268
(otal of)477.902 115.2 R
(2,831, or 86% of this sample of passwords fell into one of these classes.)72
127.2 Q 1.338(There was, of course, considerable overlap between the dictionar\
y results and the character string)97 142.8 R 2.526(searches. The)72 154.8 R
.026(dictionary search alone, which required only \214ve minutes to run, produ\
ced about one third of)2.526 F(the passwords.)72 166.8 Q .849
(Users could be ur)97 182.4 R .849(ged \(or forced\) to use either longer pass\
words or passwords chosen from a lar)-.18 F(ger)-.18 E
(character set, or the system could itself choose passwords for the users.)72
194.4 Q/F1 10/Times-Bold@0 SF(AN ANECDOTE)72 218.4 Q F0 .614(An entertaining a\
nd instructive example is the attempt made at one installation to force users \
to use)97 234 R .304(less predictable passwords.)72 246 R .303
(The users did not choose their own passwords; the system supplied them.)5.304
F(The)5.303 E .765(supplied passwords were eight characters long and were take\
n from the character set consisting of lower)72 258 R(-)-.2 E .621
(case letters and digits.)72 271.516 R .621
(They were generated by a pseudo-random number generator with only 2)5.621 F/F2
7/Times-Roman@0 SF(15)463.38 267.316 Q F0(starting)474 271.516 Q 2.667
(values. The)72 283.516 R .167(time required to search \(again on a PDP-1)2.667
F .167(1/70\) through all character strings of length 8 from a)-.37 F
(36-character alphabet is 1)72 295.516 Q(12 years.)-.37 E(Unfortunately)97
312.632 Q 2.953(,o)-.65 G .453(nly 2)162.903 312.632 R F2(15)183.636 308.432 Q
F0 .453
(of them need be looked at, because that is the number of possible outputs of)
194.089 312.632 R .671(the random number generator)72 324.632 R 5.671(.T)-.55 G
.672
(he bad guy did, in fact, generate and test each of these strings and found)
206.324 324.632 R(every one of the system-generated passwords using a total of\
 only about one minute of machine time.)72 336.632 Q F1(IMPROVEMENTS T)72
360.632 Q 2.5(OT)-.18 G(HE FIRST APPROACH)181.83 360.632 Q 2.5(1. Slower)72
384.632 R(Encryption)2.5 E F0(Obviously)97 400.232 Q 2.866(,t)-.65 G .366
(he \214rst algorithm used was far too fast.)146.166 400.232 R .365
(The announcement of the DES encryption algo-)5.365 F .885
(rithm [2] by the National Bureau of Standards was timely and fortunate.)72
412.232 R .886(The DES is, by design, hard to)5.886 F .709(invert, but equally\
 valuable is the fact that it is extremely slow when implemented in software.)
72 424.232 R .708(The DES)5.708 F .378(was implemented and used in the followi\
ng way: The \214rst eight characters of the user)72 436.232 R 1.479 -.55('s p)
.37 H .379(assword are used).55 F .19
(as a key for the DES; then the algorithm is used to encrypt a constant.)72
448.232 R .19(Although this constant is zero at the)5.19 F .174
(moment, it is easily accessible and can be made installation-dependent.)72
460.232 R .174(Then the DES algorithm is iterated)5.174 F
(25 times and the resulting 64 bits are repacked to become a string of 1)72
472.232 Q 2.5(1p)-.37 G(rintable characters.)364.64 472.232 Q F1 2.5(2. Less)72
496.232 R(Pr)2.5 E(edictable Passwords)-.18 E F0 .476
(The password entry program was modi\214ed so as to ur)97 511.832 R .476
(ge the user to use more obscure passwords.)-.18 F(If)5.475 E 1.078
(the user enters an alphabetic password \(all upper)72 523.832 R 1.079
(-case or all lower)-.2 F 1.079(-case\) shorter than six characters, or a)-.2 F
1.508(password from a lar)72 535.832 R 1.508(ger character set shorter than \
\214ve characters, then the program asks him to enter a)-.18 F
(longer password.)72 547.832 Q(This further reduces the ef)5 E
(\214cacy of key search.)-.18 E 2.029
(These improvements make it exceedingly dif)97 563.432 R 2.029
(\214cult to \214nd any individual password.)-.18 F 2.03(The user is)7.03 F
1.05(warned of the risks and if he cooperates, he is very safe indeed.)72
575.432 R 1.049(On the other hand, he is not prevented)6.049 F
(from using his spouse')72 587.432 Q 2.5(sn)-.55 G(ame if he wants to.)173.67
587.432 Q F1 2.5(3. Salted)72 611.432 R(Passwords)2.5 E F0 .473(The key search\
 technique is still likely to turn up a few passwords when it is used on a lar)
97 627.032 R .474(ge collec-)-.18 F .563
(tion of passwords, and it seemed wise to make this task as dif)72 639.032 R
.562(\214cult as possible.)-.18 F 1.962 -.7(To t)5.562 H .562
(his end, when a pass-).7 F 1.731(word is \214rst entered, the password progra\
m obtains a 12-bit random number \(by reading the real-time)72 651.032 R .022
(clock\) and appends this to the password typed in by the user)72 663.032 R
5.022(.T)-.55 G .022(he concatenated string is encrypted and both)326.128
663.032 R .186(the 12-bit random quantity \(called the)72 675.032 R/F3 10
/Times-Italic@0 SF(salt)3.026 E F0 2.686(\)a).6 G .186
(nd the 64-bit result of the encryption are entered into the pass-)252.832
675.032 R(word \214le.)72 687.032 Q .438(When the user later logs in to the sy\
stem, the 12-bit quantity is extracted from the password \214le and)97 702.632
R .332(appended to the typed password.)72 714.632 R .333
(The encrypted result is required, as before, to be the same as the remain-)
5.333 F 1.442(ing 64 bits in the password \214le.)72 726.632 R 1.442
(This modi\214cation does not increase the task of \214nding any individual)
6.442 F EP
%%Page: 5 5
BP/F0 10/Times-Roman@0 SF(Password Security: A Case History)72 48 Q(SMM:18-5)
459.55 48 Q .313(password, starting from scratch, but now the work of testing \
a given character string against a lar)72 84 R .314(ge collec-)-.18 F .717
(tion of encrypted passwords has been multiplied by 4096 \(2)72 97.432 R/F1 7
/Times-Roman@0 SF(12)317.593 93.232 Q F0 3.217(\). The)325.093 97.432 R .716
(reason for this is that there are 4096)3.217 F .593(encrypted versions of eac\
h password and one of them has been picked more or less at random by the sys-)
72 109.432 R(tem.)72 121.432 Q -.4(Wi)97 137.032 S .507(th this modi\214cation\
, it is likely that the bad guy can spend days of computer time trying to \214\
nd a).4 F .575
(password on a system with hundreds of passwords, and \214nd none at all.)72
149.032 R .576(More important is the fact that it)5.575 F .23
(becomes impractical to prepare an encrypted dictionary in advance.)72 161.032
R .23(Such an encrypted dictionary could be)5.23 F
(used to crack new passwords in milliseconds when they appear)72 173.032 Q(.)
-.55 E .347(There is a \(not inadvertent\) side ef)97 188.632 R .347
(fect of this modi\214cation.)-.18 F .348
(It becomes nearly impossible to \214nd out)5.348 F 1.426(whether a person wit\
h passwords on two or more systems has used the same password on all of them,)
72 200.632 R(unless you already know that.)72 212.632 Q/F2 10/Times-Bold@0 SF
2.5(4. The)72 236.632 R(Thr)2.5 E(eat of the DES Chip)-.18 E F0 .195(Chips to \
perform the DES encryption are already commercially available and they are ver\
y fast.)97 252.232 R(The)5.196 E .629(use of such a chip speeds up the process\
 of password hunting by three orders of magnitude.)72 264.232 R 2.028 -.7(To a)
5.628 H .628(vert this).7 F(possibility)72 276.232 Q 3.076(,o)-.65 G .576
(ne of the internal tables of the DES algorithm \(in particular)123.606 276.232
R 3.076(,t)-.4 G .577(he so-called E-table\) is changed)373.952 276.232 R .05
(in a way that depends on the 12-bit random number)72 288.232 R 5.049(.T)-.55 G
.049(he E-table is inseparably wired into the DES chip, so)291.919 288.232 R
.943(that the commercial chip cannot be used.)72 300.232 R(Obviously)5.943 E
3.443(,t)-.65 G .944(he bad guy could have his own chip designed and)296.924
300.232 R(built, but the cost would be unthinkable.)72 312.232 Q F2 2.5(5. A)72
336.232 R(Subtle Point)2.5 E F0 1.924 -.7(To l)97 351.832 T .523(ogin successf\
ully on the UNIX system, it is necessary after dialing in to type a valid user\
 name,).7 F .714(and then the correct password for that user name.)72 363.832 R
.715(It is poor design to write the login command in such a)5.714 F .631
(way that it tells an interloper when he has typed in a invalid user name.)72
375.832 R .631(The response to an invalid name)5.631 F
(should be identical to that for a valid name.)72 387.832 Q .285(When the slow\
 encryption algorithm was \214rst implemented, the encryption was done only if\
 the user)97 403.432 R .991(name was valid, because otherwise there was no enc\
rypted password to compare with the supplied pass-)72 415.432 R 3.341
(word. The)72 427.432 R .841(result was that the response was delayed by about\
 one-half second if the name was valid, but)3.341 F .486
(was immediate if invalid.)72 439.432 R .486
(The bad guy could \214nd out whether a particular user name was valid.)5.486 F
.485(The rou-)5.485 F(tine was modi\214ed to do the encryption in either case.)
72 451.432 Q F2(CONCLUSIONS)72 475.432 Q F0 .187
(On the issue of password security)97 491.032 R 2.687(,U)-.65 G .187
(NIX is probably better than most systems.)244.39 491.032 R .187
(The use of encrypted)5.187 F(passwords appears reasonably secure in the absen\
ce of serious attention of experts in the \214eld.)72 503.032 Q 1.354
(It is also worth some ef)97 518.632 R 1.354
(fort to conceal even the encrypted passwords.)-.18 F 1.354
(Some UNIX systems have)6.354 F .697(instituted what is called an `)72 530.632
R .697(`external security code')-.74 F 3.198('t)-.74 G .698
(hat must be typed when dialing into the system, but)291.608 530.632 R .748
(before logging in.)72 542.632 R .747(If this code is changed periodically)
5.747 F 3.247(,t)-.65 G .747(hen someone with an old password will likely be)
302.484 542.632 R(prevented from using it.)72 554.632 Q .049(Whenever any secu\
rity procedure is instituted that attempts to deny access to unauthorized pers\
ons, it)97 570.232 R .183(is wise to keep a record of both successful and unsu\
ccessful attempts to get at the secured resource.)72 582.232 R .183(Just as)
5.183 F .12(an out-of-hours visitor to a computer center normally must not onl\
y identify himself, but a record is usually)72 594.232 R .171
(also kept of his entry)72 606.232 R 5.171(.J)-.65 G .17(ust so, it is a wise \
precaution to make and keep a record of all attempts to log into a)167.475
606.232 R
(remote-access time-sharing system, and certainly all unsuccessful attempts.)72
618.232 Q .485(Bad guys fall on a spectrum whose one end is someone with ordin\
ary access to a system and whose)97 633.832 R .251
(goal is to \214nd out a particular password \(usually that of the super)72
645.832 R .251(-user\) and, at the other end, someone who)-.2 F .136(wishes to\
 collect as much password information as possible from as many systems as poss\
ible.)72 657.832 R .136(Most of the)5.136 F .762(work reported here serves to \
frustrate the latter type; our experience indicates that the former type of ba\
d)72 669.832 R(guy never was very successful.)72 681.832 Q 2.121 -.8(We r)97
697.432 T .521
(ecognize that a time-sharing system must operate in a hostile environment.).8
F 2.122 -.8(We d)5.522 H .522(id not attempt).8 F .731(to hide the security as\
pects of the operating system, thereby playing the customary make-believe game\
 in)72 709.432 R 1.861
(which weaknesses of the system are not discussed no matter how apparent.)72
721.432 R 1.862(Rather we advertised the)6.862 F EP
%%Page: 6 6
BP/F0 10/Times-Roman@0 SF 243.95(SMM:18-6 Password)72 48 R
(Security: A Case History)2.5 E .489(password algorithm and invited attack in \
the belief that this approach would minimize future trouble.)72 84 R(The)5.488
E(approach has been successful.)72 96 Q/F1 10/Times-Bold@0 SF(Refer)72 120 Q
(ences)-.18 E F0 10.84([1] Ritchie,)72 135.6 R 1.101(D.M. and Thompson, K.)
3.601 F 1.101(The UNIX T)6.101 F 1.102(ime-Sharing System.)-.35 F/F2 10
/Times-Italic@0 SF 1.102(Comm. ACM)6.102 F F1(17)3.602 E F0 1.102
(\(July 1974\),)3.602 F(pp. 365-375.)97 147.6 Q([2])72 163.2 Q F2(Pr)97 163.2 Q
7.059(oposed Federal Information Pr)-.37 F 7.059
(ocessing Data Encryption Standar)-.37 F(d.)-.37 E F0 7.058(Federal Register)
431.122 163.2 R(\(40FR12134\), March 17, 1975)97 175.2 Q 10.84([3] W)72 190.8 R
(ilkes, M. V)-.4 E(.)-1.29 E F2 -.55(Ti)5 G(me-Sharing Computer Systems.).55 E
F0(American Elsevier)5 E 2.5(,N)-.4 G(ew Y)382.38 190.8 Q(ork, \(1968\).)-1 E
10.84([4] U.)72 206.4 R(S. Patent Number 2,089,603.)2.5 E EP
%%Trailer
end
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦ca6cfc5f3⟧ TextFile

Derivation

TextFile
