PasswordSecurity:ACaseHistoryEncryptionComputing RobertMorris KenThompson ABSTRACT Thispaperdescribesthehistoryofthedesignofthepasswordsecurity schemeonaremotelyaccessedtime-sharingsystem.Thepresentdesignwasthe resultofcounteringobservedattemptstopenetratethesystem.Theresultisa compromisebetweenextremesecurityandeaseofuse. April3,1978 PasswordSecurity:ACaseHistoryEncryptionComputing RobertMorris KenThompson INTRODUCTION PasswordsecurityontheUNIX◯rtime-sharingsystem[1]isprovidedbyacollectionofpro-gramswhoseelaborateandstrangedesignistheoutgrowthofmanyyearsofexperiencewithear-lierversions.Tohelpdevelopasecuresystem,wehavehadacontinuingcompetitiontodevise newwaystoattackthesecurityofthesystem(thebadguy)and,atthesametime,todevisenew techniquestoresistthenewattacks(thegoodguy).Thiscompetitionhasbeeninthesamevein asthecompetitionoflongstandingbetweenmanufacturersofarmorplateandthoseofarmorpiercingshells.Forthisreason,thedescriptionthatfollowswilltracethehistoryofthepassword systemratherthansimplypresentingtheprograminitscurrentstate.Inthisway,thereasonsfor thedesignwillbemadeclearer,asthedesigncannotbeunderstoodwithoutalsounderstanding thepotentialattacks. Anunderlyinggoalhasbeentoprovidepasswordsecurityatminimalinconveniencetothe usersofthesystem.Forexample,thosewhowanttorunacompletelyopensystemwithoutpasswords,ortohavepasswordsonlyattheoptionoftheindividualusers,areabletodoso,while thosewhorequirealloftheiruserstohavepasswordsgainahighdegreeofsecurityagainstpenetrationofthesystembyunauthorizedusers. Thepasswordsystemmustbeablenotonlytopreventanyaccesstothesystembyunauthorizedusers(i.e.preventthemfromlogginginatall),butitmustalsopreventuserswhoare alreadyloggedinfromdoingthingsthattheyarenotauthorizedtodo.Thesocalled‘‘superuser’’password,forexample,isespeciallycriticalbecausethesuper-userhasallsortsofpermis-sionsandhasessentiallyunlimitedaccesstoallsystemresources. Passwordsecurityisofcourseonlyonecomponentofoverallsystemsecurity,butitisan essentialcomponent.Experiencehasshownthatattemptstopenetrateremote-accesssystems havebeenastonishinglysophisticated. Remote-accesssystemsarepeculiarlyvulnerabletopenetrationbyoutsidersasthereare threatsattheremoteterminal,alongthecommunicationslink,aswellasatthecomputeritself. Althoughthesecurityofapasswordencryptionalgorithmisaninterestingintellectualandmathematicalproblem,itisonlyonetinyfacetofaverylargeproblem.Inpractice,physicalsecurityof thecomputer,communicationssecurityofthecommunicationslink,andphysicalcontrolofthe computeritselfloomasfarmoreimportantissues.Perhapsmostimportantofalliscontrolover theactionsofex-employees,sincetheyarenotunderanydirectcontrolandtheymayhaveinti-mateknowledgeaboutthesystem,itsresources,andmethodsofaccess.Goodsystemsecurity involvesrealisticevaluationoftherisksnotonlyofdeliberateattacksbutalsoofcasualunauthorizedaccessandaccidentaldisclosure. PROLOGUE TheUNIXsystemwasfirstimplementedwithapasswordfilethatcontainedtheactual passwordsofalltheusers,andforthatreasonthepasswordfilehadtobeheavilyprotected againstbeingeitherreadorwritten.Althoughhistorically,thishadbeenthetechniqueusedfor remote-accesssystems,itwascompletelyunsatisfactoryforseveralreasons. Thetechniqueisexcessivelyvulnerabletolapsesinsecurity.Temporarylossofprotection canoccurwhenthepasswordfileisbeingeditedorotherwisemodified.Thereisnowayto -2-preventthemakingofcopiesbyprivilegedusers.Experiencewithseveralearlierremote-access systemsshowedthatsuchlapsesoccurwithfrighteningfrequency.Perhapsthemostmemorable suchoccasionoccurredintheearly60’swhenasystemadministratorontheCTSSsystematMIT waseditingthepasswordfileandanothersystemadministratorwaseditingthedailymessagethat isprintedoneveryone’sterminalonlogin.Duetoasoftwaredesignerror,thetemporaryeditor filesofthetwouserswereinterchangedandthus,foratime,thepasswordfilewasprintedon everyterminalwhenitwasloggedin. Oncesuchalapseinsecurityhasbeendiscovered,everyone’spasswordmustbechanged, usuallysimultaneously,ataconsiderableadministrativecost.Thisisnotagreatmatter,butfar moreseriousisthehighprobabilityofsuchlapsesgoingunnoticedbythesystemadministrators. Securityagainstunauthorizeddisclosureofthepasswordswas,inthelastanalysis,impossiblewiththissystembecause,forexample,ifthecontentsofthefilesystemareputontomagnetic tapeforbackup,astheymustbe,thenanyonewhohasphysicalaccesstothetapecanreadanythingonitwithnorestriction. Manyprogramsmustgetinformationofvariouskindsabouttheusersofthesystem,and theseprogramsingeneralshouldhavenospecialpermissiontoreadthepasswordfile.Theinformationwhichshouldhavebeeninthepasswordfileactuallywasdistributed(orreplicated)intoa numberoffiles,allofwhichhadtobeupdatedwheneverauserwasaddedtoordroppedfromthe system. THEFIRSTSCHEME Theobvioussolutionistoarrangethatthepasswordsnotappearinthesystematall,andit isnotdifficulttodecidethatthiscanbedonebyencryptingeachuser’spassword,puttingonly theencryptedforminthepasswordfile,andthrowingawayhisoriginalpassword(theonethathe typedin).Whentheuserlatertriestologintothesystem,thepasswordthathetypesis encryptedandcomparedwiththeencryptedversioninthepasswordfile.Ifthetwomatch,his loginattemptisaccepted.Suchaschemewasfirstdescribedin[3,p.91ff.].Italsoseemedadvisabletodeviseasysteminwhichneitherthepasswordfilenorthepasswordprogramitselfneeded tobeprotectedagainstbeingreadbyanyone. Allthatwasneededtoimplementtheseideaswastofindameansofencryptionthatwas verydifficulttoinvert,evenwhentheencryptionprogramisavailable.Mostofthestandard encryptionmethodsused(inthepast)forencryptionofmessagesarerathereasytoinvert.A convenientandrathergoodencryptionprogramhappenedtoexistonthesystematthetime;it simulatedtheM-209ciphermachine[4]usedbytheU.S.ArmyduringWorldWarII.Itturned outthattheM-209programwasusable,butwithagivenkey,theciphersproducedbythispro-gramaretrivialtoinvert.Itisamuchmoredifficultmattertofindoutthekeygiventhecleart-extinputandtheencipheredoutputoftheprogram.Therefore,thepasswordwasusednotasthe texttobeencryptedbutasthekey,andaconstantwasencryptedusingthiskey.Theencrypted resultwasenteredintothepasswordfile. ATTACKSONTHEFIRSTAPPROACH Supposethatthebadguyhasavailablethetextofthepasswordencryptionprogramand thecompletepasswordfile.Supposealsothathehassubstantialcomputingcapacityathisdisposal. Oneobviousapproachtopenetratingthepasswordmechanismistoattempttofindageneralmethodofinvertingtheencryptionalgorithm.Verypossiblythiscanbedone,butfewsuccessfulresultshavecometolight,despitesubstantialeffortsextendingoveraperiodofmorethan fiveyears.Theresultshavenotprovedtobeveryusefulinpenetratingsystems. Anotherapproachtopenetrationissimplytokeeptryingpotentialpasswordsuntilonesucceeds;thisisageneralcryptanalyticapproachcalledkeysearch.Humanbeingsbeingwhatthey are,thereisastrongtendencyforpeopletochooserelativelyshortandsimplepasswordsthat theycanremember.Givenfreechoice,mostpeoplewillchoosetheirpasswordsfromarestricted -3-characterset(e.g.alllower-caseletters),andwilloftenchoosewordsornames.Thishumanhabit makesthekeysearchjobagreatdealeasier. Thecriticalfactorinvolvedinkeysearchistheamountoftimeneededtoencryptapotentialpasswordandtochecktheresultagainstanentryinthepasswordfile.Therunningtimeto encryptonetrialpasswordandchecktheresultturnedouttobeapproximately1.25milliseconds onaPDP-11/70whentheencryptionalgorithmwasrecodedformaximumspeed.Itistakes essentiallynomoretimetotesttheencryptedtrialpasswordagainstallthepasswordsinanentire passwordfile,orforthatmatter,againstanycollectionofencryptedpasswords,perhapscollected frommanyinstallations. Ifwewanttocheckallpasswordsoflengthnthatconsistentirelyoflower-caseletters,the numberofsuchpasswordsis26n.Ifwesupposethatthepasswordconsistsofprintablecharacters only,thenthenumberofpossiblepasswordsissomewhatlessthan95n.(Thestandardsystem ‘‘charactererase’’and‘‘linekill’’charactersare,forexample,notprimecandidates.)Wecan immediatelyestimatetherunningtimeofaprogramthatwilltesteverypasswordofagiven lengthwithallofitscharacterschosenfromsomesetofcharacters.ThefollowingtablegivesestimatesoftherunningtimerequiredonaPDP-11/70totestallpossiblecharacterstringsoflength nchosenfromvarioussetsofcharacters:namely,alllower-caseletters,alllower-caselettersplus digits,allalphanumericcharacters,all95printableASCIIcharacters,andfinallyall128ASCII characters. 26lower-case36lower-caseletters62alphanumeric95printableall128ASCII nlettersanddigitscharacterscharacterscharacters 130msec.40msec.80msec.120msec.160msec. 2800msec.2sec.5sec.11sec.20sec. 322sec.58sec.5min.17min.43min. 410min.35min.5hrs.28hrs.93hrs. 54hrs.21hrs.318hrs. 6107hrs. OnehastoconcludethatitisnogreatmatterforsomeonewithaccesstoaPDP-11totestall lower-casealphabeticstringsuptolengthfiveand,givenaccesstothemachinefor,say,several weekends,totestallsuchstringsuptosixcharactersinlength.Byusingsuchaprogramagainst acollectionofactualencryptedpasswords,asubstantialfractionofallthepasswordswillbe found. Anotherprofitableapproachforthebadguyistousethewordlistfromadictionaryorto usealistofnames.Forexample,alargecommercialdictionarycontainstypicalllyabout250,000 words;thesewordscanbecheckedinaboutfiveminutes.Again,anoticeablefractionofanycollectionofpasswordswillbefound.Improvementsandextensionswillbe(andhavebeen)found byadeterminedbadguy.Some‘‘good’’thingstotryare: -Thedictionarywiththewordsspelledbackwards. -Alistoffirstnames(bestobtainedfromsomemailinglist).Lastnames,streetnames,and citynamesalsoworkwell. -Theabovewithinitialupper-caseletters. -Allvalidlicenseplatenumbersinyourstate.(ThistakesaboutfivehoursinNewJersey.) -Roomnumbers,socialsecuritynumbers,telephonenumbers,andthelike. Theauthorshaveconductedexperimentstotrytodeterminetypicalusers’habitsinthe choiceofpasswordswhennoconstraintisputontheirchoice.Theresultsweredisappointing, excepttothebadguy.Inacollectionof3,289passwordsgatheredfrommanyusersoveralong periodoftime; 15wereasingleASCIIcharacter; -4-72werestringsoftwoASCIIcharacters; 464werestringsofthreeASCIIcharacters; 477werestringoffouralphamerics; 706werefiveletters,allupper-caseoralllower-case; 605weresixletters,alllower-case. Anadditional492passwordsappearedinvariousavailabledictionaries,namelists,andthelike. Atotalof2,831,or86%ofthissampleofpasswordsfellintooneoftheseclasses. Therewas,ofcourse,considerableoverlapbetweenthedictionaryresultsandthecharacter stringsearches.Thedictionarysearchalone,whichrequiredonlyfiveminutestorun,produced aboutonethirdofthepasswords. Userscouldbeurged(orforced)touseeitherlongerpasswordsorpasswordschosenfroma largercharacterset,orthesystemcoulditselfchoosepasswordsfortheusers. ANANECDOTE Anentertainingandinstructiveexampleistheattemptmadeatoneinstallationtoforce userstouselesspredictablepasswords.Theusersdidnotchoosetheirownpasswords;thesystem suppliedthem.Thesuppliedpasswordswereeightcharacterslongandweretakenfromthecharactersetconsistingoflower-caselettersanddigits.Theyweregeneratedbyapseudo-random numbergeneratorwithonly215startingvalues.Thetimerequiredtosearch(againona PDP-11/70)throughallcharacterstringsoflength8froma36-characteralphabetis112years. Unfortunately,only215ofthemneedbelookedat,becausethatisthenumberofpossible outputsoftherandomnumbergenerator.Thebadguydid,infact,generateandtesteachof thesestringsandfoundeveryoneofthesystem-generatedpasswordsusingatotalofonlyabout oneminuteofmachinetime. IMPROVEMENTSTOTHEFIRSTAPPROACH 1.SlowerEncryption Obviously,thefirstalgorithmusedwasfartoofast.TheannouncementoftheDESencryptionalgorithm[2]bytheNationalBureauofStandardswastimelyandfortunate.TheDESis,by design,hardtoinvert,butequallyvaluableisthefactthatitisextremelyslowwhenimplemented insoftware.TheDESwasimplementedandusedinthefollowingway:Thefirsteightcharacters oftheuser’spasswordareusedasakeyfortheDES;thenthealgorithmisusedtoencryptaconstant.Althoughthisconstantiszeroatthemoment,itiseasilyaccessibleandcanbemade installation-dependent.ThentheDESalgorithmisiterated25timesandtheresulting64bitsare repackedtobecomeastringof11printablecharacters. 2.LessPredictablePasswords Thepasswordentryprogramwasmodifiedsoastourgetheusertousemoreobscurepasswords.Iftheuserentersanalphabeticpassword(allupper-caseoralllower-case)shorterthansix characters,orapasswordfromalargercharactersetshorterthanfivecharacters,thentheprogramaskshimtoenteralongerpassword.Thisfurtherreducestheefficacyofkeysearch. Theseimprovementsmakeitexceedinglydifficulttofindanyindividualpassword.Theuser iswarnedoftherisksandifhecooperates,heisverysafeindeed.Ontheotherhand,heisnot preventedfromusinghisspouse’snameifhewantsto. 3.SaltedPasswords Thekeysearchtechniqueisstilllikelytoturnupafewpasswordswhenitisusedonalarge collectionofpasswords,anditseemedwisetomakethistaskasdifficultaspossible.Tothisend, whenapasswordisfirstentered,thepasswordprogramobtainsa12-bitrandomnumber(by -5-readingthereal-timeclock)andappendsthistothepasswordtypedinbytheuser.Theconcate-natedstringisencryptedandboththe12-bitrandomquantity(calledthesalt)andthe64-bit resultoftheencryptionareenteredintothepasswordfile. Whentheuserlaterlogsintothesystem,the12-bitquantityisextractedfromthepass-wordfileandappendedtothetypedpassword.Theencryptedresultisrequired,asbefore,tobe thesameastheremaining64bitsinthepasswordfile.Thismodificationdoesnotincreasethe taskoffindinganyindividualpassword,startingfromscratch,butnowtheworkoftestingagiven characterstringagainstalargecollectionofencryptedpasswordshasbeenmultipliedby4096 (212).Thereasonforthisisthatthereare4096encryptedversionsofeachpasswordandoneof themhasbeenpickedmoreorlessatrandombythesystem. Withthismodification,itislikelythatthebadguycanspenddaysofcomputertimetrying tofindapasswordonasystemwithhundredsofpasswords,andfindnoneatall.Moreimportant isthefactthatitbecomesimpracticaltoprepareanencrypteddictionaryinadvance.Suchan encrypteddictionarycouldbeusedtocracknewpasswordsinmillisecondswhentheyappear. Thereisa(notinadvertent)sideeffectofthismodification.Itbecomesnearlyimpossibleto findoutwhetherapersonwithpasswordsontwoormoresystemshasusedthesamepasswordon allofthem,unlessyoualreadyknowthat. 4.TheThreatoftheDESChip ChipstoperformtheDESencryptionarealreadycommerciallyavailableandtheyarevery fast.Theuseofsuchachipspeedsuptheprocessofpasswordhuntingbythreeordersofmagnitude.Toavertthispossibility,oneoftheinternaltablesoftheDESalgorithm(inparticular,the so-calledE-table)ischangedinawaythatdependsonthe12-bitrandomnumber.TheE-tableis inseparablywiredintotheDESchip,sothatthecommercialchipcannotbeused.Obviously,the badguycouldhavehisownchipdesignedandbuilt,butthecostwouldbeunthinkable. 5.ASubtlePoint TologinsuccessfullyontheUNIXsystem,itisnecessaryafterdialingintotypeavaliduser name,andthenthecorrectpasswordforthatusername.Itispoordesigntowritethelogincommandinsuchawaythatittellsaninterloperwhenhehastypedinainvalidusername.The responsetoaninvalidnameshouldbeidenticaltothatforavalidname. Whentheslowencryptionalgorithmwasfirstimplemented,theencryptionwasdoneonlyif theusernamewasvalid,becauseotherwisetherewasnoencryptedpasswordtocomparewiththe suppliedpassword.Theresultwasthattheresponsewasdelayedbyaboutone-halfsecondifthe namewasvalid,butwasimmediateifinvalid.Thebadguycouldfindoutwhetheraparticular usernamewasvalid.Theroutinewasmodifiedtodotheencryptionineithercase. CONCLUSIONS Ontheissueofpasswordsecurity,UNIXisprobablybetterthanmostsystems.Theuseof encryptedpasswordsappearsreasonablysecureintheabsenceofseriousattentionofexpertsin thefield. Itisalsoworthsomeefforttoconcealeventheencryptedpasswords.SomeUNIXsystems haveinstitutedwhatiscalledan‘‘externalsecuritycode’’thatmustbetypedwhendialinginto thesystem,butbeforeloggingin.Ifthiscodeischangedperiodically,thensomeonewithanold passwordwilllikelybepreventedfromusingit. Wheneveranysecurityprocedureisinstitutedthatattemptstodenyaccesstounauthorized persons,itiswisetokeeparecordofbothsuccessfulandunsuccessfulattemptstogetatthe securedresource.Justasanout-of-hoursvisitortoacomputercenternormallymustnotonly identifyhimself,butarecordisusuallyalsokeptofhisentry.Justso,itisawiseprecautionto makeandkeeparecordofallattemptstologintoaremote-accesstime-sharingsystem,andcer-tainlyallunsuccessfulattempts.

-6-Badguysfallonaspectrumwhoseoneendissomeonewithordinaryaccesstoasystemand whosegoalistofindoutaparticularpassword(usuallythatofthesuper-user)and,attheother end,someonewhowishestocollectasmuchpasswordinformationaspossiblefromasmanysystemsaspossible.Mostoftheworkreportedhereservestofrustratethelattertype;ourexperienceindicatesthattheformertypeofbadguyneverwasverysuccessful. Werecognizethatatime-sharingsystemmustoperateinahostileenvironment.Wedidnot attempttohidethesecurityaspectsoftheoperatingsystem,therebyplayingthecustomary make-believegameinwhichweaknessesofthesystemarenotdiscussednomatterhowapparent. Ratherweadvertisedthepasswordalgorithmandinvitedattackinthebeliefthatthisapproach wouldminimizefuturetrouble.Theapproachhasbeensuccessful. References [1]Ritchie,D.M.andThompson,K.TheUNIXTime-SharingSystem.Comm.ACM17(July 1974),pp.365-375. [2]ProposedFederalInformationProcessingDataEncryptionStandard.FederalRegister (40FR12134),March17,1975 [3]Wilkes,M.V.Time-SharingComputerSystems.AmericanElsevier,NewYork,(1968). [4]U.S.PatentNumber2,089,603.