The following paper was originally published in the
`Proceedings of the 8th USENIX Security Symposium
`Washington, D.C., USA, August 23–26, 1999
`
`T H E D E S I G N A N D A N A L Y S I S
`O F G R A P H I C A L P A S S W O R D S
`
`Ian Jermyn, Alain Mayer, Fabian Monrose,
`Michael K. Reiter, and Aviel D. Rubin
`
`THE ADVANCED COMPUTING SYSTEMS ASSOCIATION
`
`© 1999 by The USENIX Association
`All Rights Reserved
`For more information about the USENIX Association:
`Phone: 1 510 528 8649
`FAX: 1 510 548 5738
`Email: office@usenix.org WWW: http://www.usenix.org
`Rights to individual papers remain with the author or the author's employer. Permission is granted for noncommercial
`reproduction of the work for educational or research purposes. This copyright notice must be included in the reproduced paper.
`USENIX acknowledges all trademarks herein.
`
`1
`
`APPLE 1014
`
`

`

`ATE averd Diem] VonroseaMichcelAR citer}
`Labs @Lucent
`
`
`{alainreiten}@rescarchbellgabsicom|fabian
`
`AvielfD FRubin,
`ATE T Labs
`
`
`
`authorization [to faccessEt
`
`Ror meorion offouly|
`ifthepasswords iverefound[by Bearching[ou
`eet(02L-
`graphical
`
`popudesprethemeena— wore
`ande bettergsecurity[than [textepasswoudsggGLaphical finputfidevicesfenable|a user1decouple theDOsittonOl|eofromthe|roame
`tfexploit}featuresforferaphical
`d
`ara ho" ge
`passwordspconsistinefo
`ig
`andUPpergandlowercase letterspulone.}
`ene WweJexplorefan approach[tofuser
`thentication[that]theTotionof ee
`OCCULma[we]it aapasswordie:rypassword Spacesmglnjorder] ottthe se-
`reerthatTeenaerd
`renee
`—,
`tpextiralrerATRREN Pne by|theJusergto
`curity folfone offotrpschemesmwe deviseanovel [way
`eePEATE hntertace. MA Ke
`captureaBubsetfol[the memorable?
`mrebelicve§spitscl!|Tnthispwork|
`_
`SytheBate[purposejasfe[vextall
`aescet
`offhandwrits
`arepuinanilymotivated[by devi cespsuchfsyp cg
`ratyry Rrhich JorWwefarefpriinarily
`SMT TNEDAN pepeee
`.uesiiginatiiiionioniod
`Input
`Via[aBtylus andfwe|describé our
`prototype pimplementationJorfoeT peau
`iCre PAS) Buchpope
`
`Schemesjonpuch@PDABmamelythePalinPilOtgam
`PalinPiloteM ple NewtonwuiCasio
`cn andfothershiwhichaon SgtoJprovide|
`
`BraphicspnputstothedeviceViaastylus
`graphical canJbeused[whenever |
`
`| Melontroduction
`fiffputfidévice,suchfsfa mouse,tis}
`ical
`Peep Of ffo
`the Fnotion|ioa
`is eosony (Ae ChatAeeaeeetaaeae
`PorgtheWastfimajority pf icomputcrsystcrst—pass,
`Wwordspare|thefmethod fot] amlee
`
`USerSeam tMispwell sknowiMhowevermgt
`isppresentedwith&predeterminedimageonvisual}
`pineeeeoneJorn
`aresusceptibletoattack: Jusersgtend[tochoosepass
`words}
`areJeasy [to emembersgand foften this}
`
`thatfithey pare also Jeasy forgan fattackerpito|
`obtain [by pearching forficandidate JpasswordsBMELn
`one Jcase Btudy Jofmlt,000 [Unix Jpasswordsmgalmost
`
`gain Fngeefo| natgtroinFe] hisfor —
`
`2
`
`

`

`
`PLoposal Mhowevermy 4 iidid frotpftrtherpexplore thé
`thatypasswordsiidescribableby Bhort
`Powergotferaphical
`BrgSCCULty[fOr
`memorableWweshow]thatfeven[hissubset}ofimemn
`
`rableDASpasswordshisflargerthanthedictionaries
`itspparticular|
`offiextual fpasswords§towhich fihigh[percentageof]
`passwordsitypicallyjbelong.§
`in
`[thisspaper
`advance[ihe[iheory
`and [practiCeofferaphical fpasswordsagWetakeBsa
`Wwefocusfon.aemaneol
`Mann euiteronthe Mead[tOevaltiateBraphical [pass
`WordsfthateSem
`We design eepasswordBchemes
`wordspsecurityrelativetothatfofftextualfpasswords™
`ourgworkfrommfall fworksfou.eet
`believe [to Jbaedatextual fpasswords
`ee offwhichWweareaware[See SeC-
`(andfinoreBecure[than[theSchemejot} HeEnid[we|employmovelfanalysisto make thigh
`tion 4) Mawhere jitsuificesstorgthedevice [to Fecos-
`mizeaiinputgaspbeing pesutficientlypimilargstOpgput
`mOtapreviouslystorediy
`Tecra
`implementationOf]
`ya. EBecausepatterna require|theBtoragejoffsome ayeeton theJplaing
`oneOfpasswordBchemesponithePalin]
`= passwordfon[the\device, ttheJpasswordfisfvuly
`Pilock
`‘The merabletofanattacker—whocapturcsfand[probespassword Bchernes
`
`
`derive their aaaaeeefrom the following observation.
`device GincontrastMbecause graphica.
`repeatable,tour]acanderive a secret, on
`a Praphical jintertace fOrgproviding iiput
`toenctyptfand|decrypt]ane oe
`usergto |decouple }the[posiionspot™the finputstron|
`and[thejencrypted content ere
`
`thepasswordfon|thedeviceJUhisfprotects
`Thciprermmpord Peder impor opente)
`
`peererpeTy
`baernoremnen)
`Ser Toeeeeae
`IthTheeepeeheeyeeeles
`tackertheattackersphandsEinto
`
`
`
`in fajeraphical dsCem akai lof [several|
`
`[Therestfoffthis outlinedfas) deltouss InSecs
`drawn Jliftesmathé[final position Joffeach fline fcan Jbe|
`tion 2,4 WweJpresent) textual passwords)
`erap!hig
`cal fassistatice. WL poection 3 we[proceed |toPpurely|
`determined findependently joffthe temporal forder fit|
`ee With faschemeJcalled Bidraw™
`Which [thejlinessare\drawt agWeShow that[t
`hissing
`dependence Joctween EIputgposition Fand Jorden
`BSection 3.2showspourpdesign fand|
`PeepsSection.3Proposessrovelways)ReneereeST
`——
`belised|tojbuildjinterestingmew spasswordBchemcs™
`
`and inBomeCasespobtainatthentigationthathis)
`eninJgeneraSeee
`ern Leet
`ot
`significantly uardergtoremembers
`eel ar cin
`to Re
`passwordsmbut]ane OurWwOrkilalargerfcontext™
`firstferaphical[p
`Oe
`ee eTpassword|- offtextualfpasswordsjusing graphical =md
`aeSection(concludesl
`IM thisfcase,hitfwe assuine the same underlying distriy
`password
`hisffat] on as reePasse
`
`bution jon[thechoiceoffthepassword§the graphical
`(Text ual§Passwords jwith§Graphical
`Word thatfunderheshitMandevenjaconservativeests
`Assistance]
`input
`aSubstantial fi
`een
`mate offtheWariationspntroduced by[thegraphical)
`purcly [textual versionSgWe Jproposeland|
`In[thisfsection we presentapasswordSelectionjand|
`implementaSecond Scheme, called fadraw yaSecrets
`imputgscheme Jwhigh
`Pusesiitex tual]
`a
`merited|b eeeraphical{capabilities
`(DASMRpeeeshienhoeeee
`Secret ieee (the Pere)fonkegridsa
`enableJthe\decoupling foltemporal fordergol ing
`gue an
`rptextual fp
`fine a classpotpD — thatwebelieve,tcap+
`eT hich
`charactersfarc input
`tures mee RTT oftheMemorablejonesy
`ee because it=eroinput fabilitiespwhile yielding
`Classpconsistspo! pthose[passwords me
`erated|byfaBhortiipwegen 3aBimple[eridsbased
`language We|donot]
`aeara
`Password |nasge PhorippropranOo describeimbut
`
`Westart[by[definingfanormal Akcharacterguextuall
`
`
`schemesm by
`
`thanftextua
`
`3
`
`

`

`PET TLCMCT
`STOTT
`where A isithe setfoffallowed(characterspforgthe tex
`
`TheeRe pTeMeeap heme
`
`tual [password Wlthedomainjof] becauseithejchoicesfol [position pity
`
`ers(e.e%
`
`OtiBideiyinsid-outMevensgthcnglodds™aaandfcombinationsgthereot™
`Volvedfin)a beJderived fffom —
`reeara eidBofors
`ior
`keIgorithms)
`tions
`Be We willfreturnjto[this}Ti
`password miwejhave|=% (2) EHO
`
`isticoffi in[theNext] a
`Tere ereert Ee
`offatfleastrnBAnimportant}featureoffthisTe
`thackerpspwork load fwillfthus—beincreased|
`Nowtheusergisppresentedwithfasin]
`ple graphical
`displayconsistingjofMpay,yeisht
`thaththisptfleastfasptrong asfthe imitial|textual)
`word[that
`—iwasfichosen by [the[user
`ra
`POSitiOnspinto|tO Jenten BftexiTal] password,
`SPIee anae cep |
`(lo thotfireduce[theBizefoffitheBpace
`joffcharg
`UCT) they[chooseinFesponsetothe)
`
`
`the initial otpblanksmand|
`need[toTemembergapositional orders
`omopoeal| ox HonnsRSNomenNyua
`Ve. Wir (7)
`fisfentered fin rows: Sa The password [ean
`Depa alge gwgee Pe
`[Therefareja Jnumbergot Steps) take]to|
`
`shown pl [Figure |lla.mgDue}to [thejeraphicalfnature|
`makethisgschememoreusable-Mrinst to[maximize|
`oifthe inputfinterface}howevermtheUsergcouldenter
`the JeaseJoffhnputting
`with fvaried [posiy
`the edpenn Positionsmpaspwell&ai
`romeChae ehod
`
`Upc ——amodificationjun[which[the|userpentersptthepassword[in}aJleftatosright#imanners
`placesfit fin fe[position Matfleastiwith farondescript
`hee ee ee)
`uponehheres
`butfstartingi‘adifterenthi—athanthe
`itselt
`a departure ffom most
`al woutside-if gstrategy. aeet
`leftinostmgrigurejicshowsgenteriigthepassword[itt]
`emit Coonpee eonee pe
`acterpuordergtoprotect
`IgJPErsOLSEELLOWeVCIMOL by Pwhich|
`
`ations|can be combinedin the obvious Way,tas)sphown|
`in Figure[lid2
`reeen
`toy,
`Buch faspthe [Palm [Pilotitfisgmuch feasiergto Bhield|
`Tope omenoKCR ETMCeTmhee
`Formally, jk-jcharactergeraphical [passwordfun [this
`ee rti
`the interface mightfallowsthe usergtojfirstfentergthe|
`lefts omisht)Mandthenjdrag|as COTMon
`password fanorimallygk
`See
`Tears se1thentry (tempora. ly) figjthe _—
`Inevitably, lgthere Jare umerOuspvaliations—on pthe|
`ter aleaypaiiiton 74A [conventional[textual password|
`Scheme[presented fhere. One(direction fincludessarg
`
`7 entered[ui}th¢ Btandard[leftgtosright#way,4qcanJbe|oe taassppchemefaspa[graphical fppassword|
`ranging [the ]k finputffpositionspin Borne fothersway|
`thatBtraightBlite(eeMa (rid )Mtopromoteother
`
`TeghvhereTri?) SM(7)éBUSBishowing
`VarlatiOnspin Pp
`Rathérgthan pursuing[these
`ure |Tr. eeeeoe iy
`Options oycosetepromgpgpee
`Which
`On) Prep peeps
`— ie keieconventionalpassword
`Lppasswordsiirafand|ee fect Digwiltedinsccm a
`graphica erpassword[pacefexceedsaena
`(The }Drawsagsecret (DAS Scheme)
`tively aenterfor roSmaa= 104
`
`a.
`
`
`conventional fp
`
`space.)
`
`Car Jbefa relay
`
`chispfactorpi Epproxitnately(2{10m
`
`In [thisgsection [we[presenta[purelygraphical passg
`Officourse,qtherefareifargrewergthanJ2b [LO Bvariag
`pe fee pie
`a
`tionsgoffeach/8-charactergpassword[that]
`paw secrcigl( DAS)Sinthisfscheme.tthepassword|
`
`rable fOrghuman[USersmaLlOwevelmitpispeasytOderive|
`a ee picture ce On a grid.
`a convincinglower] boundfon [the unprovement
`Uaithuspnaking it
`achieves
`passwordBchemc.}
`eenTremember} apgisind offalphanumeric
`offanylanguage: Was
`conservative to assume thatiitheyr.positional frotas
`tionsgo! apasswordAplus
`aShandfulfoffoths
`
`4
`
`

`

`4c fo [mye i
`pt fo fn faJt|
`6. fo [nye | jo
`
`(a) fLeftgtosmeht
`
`p.Wt [oat Fee Jo ia
`6.8 [init fo Ja jo iam
`
`tO
`2 icy
`Bam ao
`Gataao
`
`
`
`(c)pOutsidein](cd) JABorecomplexfexainplc
`
`feomatoag heword ftomatoJcan Jbejiiput gin [the Janormal
`galcftgito Tight]
`Figure jf PVariations
`
`Step [0fisftheinitial Pow]offblanksBfandBtepsgilg6jindicatethetemporalfordergit|
`
`
`Tanner maspshowl ft|
`Which
`blanksMgIn faddition Bhowevermrthefusergcan vary [the[position foffthe[lettersyin|
`
`Lomato. Bhiftingthemputflettbyone, 4c) frepresciiispanjoutside=injinput]
`and @ the combination jof[these.|
`
`Sal MPasswordsSelectionjand [Input|
`‘The most™icompelling freason fforgexploring [thefuse|
`Offa Ppicture-based
`scheme [ismthatihusy
`
`they(cross) theBame sequence ol| grid|
`
`
`Talis rr faremarkablefability for
`pinterface Fonsisting pola Fectangulay
`Considerfan
`ine drawingsfand real[Objects)
`calling pictures
`(ite.
`‘The Jgpicture fettectys
`aaeftect ot spicto~
`grid forBize JGIRIGE Each [cell in [thisgenid fiside?
`moted Jby discreterectangular
`(24)
`rial fandobject
`lonfa Variety joffinieas
`BG IEG BiSupposethatfithethejusergisfeiven
`pfficarmingfandfmemoryJhasgbeen BtUdied [for
`|
`With [which Bhe(can fdraw adesign joupthis
`TIPPT b> bo pMcoomaescemean ee
`[Thedrawing isfthenfnapped{tofaBsquenceOf]
`
`shown Jthatiithere isa Bubstantiall
`of]
`coordinatepairsppy|
`theyll
`performance in recall fand[recognition with[pictorial]
`the|drawiis passespinthéjorderxin|passes)
`representationspo! |to7be-remembered [inaterial [than|
`through [themfwithfadistinguishedcoordinatepair
`forverbalfrepresentations™
`inserted fil [theBequenceforgfeach Papen [up geveut™
`Le-mwheneverthe Csergifts|the stylus
`Superiority jnrecall foffob jectsfovergwordsihinjmne-
`
`ing Purface. ror onsidergthefdrawing[i}
`diate recall fand fovershortffirctention finter valsfhas
`Figure2. BHere [the[coordinatesequencegenerated|
`been
`through Fa Jnumberglot
`flexperig
`byTthisidrawingis
`Tictsegeinpirical fevidenceOfOffpicttres
`Wwordsiidatesffback [to Jthe JI800s%
`Cooe)
`performed [by|Calkinsii/|Bhowed therecallfof[words
`
`declining [byp07 a.f/2hourgretention|
`
`where|the Jdistinguished fapen Jup indica,
`interee| andrecall foffobjectsidropping bylessithan|2074 —saine period @Studiespexhibiting strik+
`ingly Jhigh BSNSar
`on
`wereaBecond Btrokein [thisfexample.|
`
`then pits fwould [be|to Jthe Jen|
`
`
`ofthe sequenceabove,fandBunilarlyfor
`overgwords
`
`ptrokesmaln[thisfway,qwedividethespaceoffpossible
`
`
`OCCasiOUsyg27,30 have|922,90Sometheories)
`
`eenATpa classesmtWwo\rawifgs—bes
`
`been proposedtoexplaintheseexperimental [results
`Ling equivalentfif[theyjhave the same encodingFOupt|
`are outlined fill|Appendix|A™
`lothergwords
`
`5
`
`

`

`//wwwsaacecspoerkeley.cdu/pilot)
`
`
`Applicationjof DAS:JAn}Encryption|
`Toolffor JP DA|
`Figure 2: [Inputfotfaeraphicalfpasswordjonfaifx/4|
`BudMT he(hawits
`ppmapped[tOppeducuceor
`Our) Laraaremotivated|prig
`
`renAe ote PPP
`bylisting the cellsfinjtheorder
`the stylusppassesjthrough them
`bilities
`describeurgiinplementation Joffe |
`coordinatepairginsertédfin JtheBequencewhenever
`memoJpad jencryption[tool fforgthéPalinPilot
`the styluspsplifted[fromthedrawingsurface.)
`aTasers puigeraphicalfpassword[to\derive[the|
`Thesr SUpPOLtspaVery[ature|form jot peraphical inputPpand Such qprovides
`
`
`First—iwe [give define fthe|terminology.
`
`Ree Popehet ee
`McSMeomr enieae AS pencmes
`ey)Acky
`Ethap pooh ne Pecemspenapkomd poy
`rhephid
`oS
`used[tofentergthepassword Miiereweillustratejour
`fie a eTSe
`cells
`Tool periTheDASBehemen
`
`CocVMaemanidPehichdoesnot Epon|
`
`evertmg A] then|defined[toJoeaSequence|
`Jourgtool raaera de
`In
`ofBtrokesBeparatedbypenUp gevents™
`rivedfromaDAS[password(ite Mtg)
`
`offestrokeisfthemumberpol]
`follfonsa
`Bibe fe pbiffstring
`
`tainsmwhile thetotallengthoffapasswordisfthe Sum|Soe oe ee
`the Bequence fof}
`fined [a5 are WhereJh fis eee
`theTunique|Upgeidicator) Mmm Lhe|de]
`the japonip gicharactcrsi
`hash [fnction SHASIE
`key[derivation pssures
`SCONEWhispencme pon!
`AS
`two Jdistinctffcoordinate Bequences#are [transs
`
`Viable iffthe usergspstrokes While|
`[tned wich Jus Proabiitypure powo fusca
`they faredrawiL@Againtweappeal tothemaneuvers
`fixed length |keysaag
`Ltip é-DESwispthen Jused[tojens
`Abilitwrolpthedevices
`argeting @s, IPDAS)
`cry ptpand decrypt|thePDABStoredon
`
`
`to Support
`Imustyshield
`usiffskeyspderived[iromk
`the utputidisplayfromonlookers™
`
`4
`3
`2
`1
`least|twoSolitiOnsyto[this (I){theuser
`
`offered[toWiew]theinternal frepresentationadepictg
`ig[thepathjoffcellsmiwhen BheThooseslfapassword|
`So Tthat#Bhe|can confirm[which FeellsfwereJactually
`eeee [TheBystem\ocsgnot]
`ecceptffa Jdrawing pwhich
`strokespthat
`gt0o [close gto Ja Jerid line Wiiin pthe jimple-
`mentation®in ection [3.2 Awejoffersboth
`elternativesm
`3
`2
`
`6
`
`5
`1
`
`4
`
`1 2
`
`3 4
`
`Key pelection fispasifollows:|
`Ourfrequirementfoffrepeatabilityconstrainsgthepas
`With fan Fempty Jerid [to nputiithepassword Kdesign|
`raretersgo!pthispschemre.GAsplongpsythe Usergsictig
`OnceIthe Jpassword fisfenteredAk[isfiderived fand fa
`
`rentiidrawing iesfin [theBameequivalence[class
`pre-defined [phiase|p
`Gs Baty)
`antl
`SacomeibaDENWeoye ACCESS
`the Joriginal drawingAshehhasgsuccesstullyrepeated|
`a [chosen Jpassword Miln JeeneralMthispeivesgthejuser]
`prompted fagain [with [the|guid upon Pwhich|
`
`Sufticient{tolerancewhen(involuntaril?)fvarying the
`
`drawitg, the cellsfotthe afarenot}
`Bhe\drawspthe Byminetrickey[gis
`
`derived fand fan fattemptpisfinadeto|decrypth Eri?)m
`too Binal]
`Separate
`resultspail [pagunen pirgiBk and the Password
`ing [theJdrawings—into Jequivalence[lasses—ito Jbegin
`WichMEDiticuiuicspenehipericehowevempwnen [che
`BBased On lan Goldbergspportpor|
`(see]
`Uuserpchoosespa |drawille
`containspstrokcs)
`Intitp:
`
`cellsMfwith [the ybreakssbétween ptrokes occurringfi]
`he same places™
`
`oo close to a srid-litte. lnthose cascsmthe User
`the drawing finjsuch[a]
`tochange|
`
`might}
`
`
`
`reereerer of Chereareat
`
`6
`
`

`

`
`
`‘The interface for Show!|
`
`See ep tereaepe
`to factypt/decrypt Ts redeleted[from)
`guessingattackspsuccessiulMmLhesecondfactort
`renderspiextualfpasswordspvulnerable isft on
`There DARtpthelitest when ithe PDAfisfpoweredoff
`pnhasppignificanthl
`thedistribution,
`of] passwordsmganid [car|knowledge]t0
`
`her shaascMBuLpthe\caseJoffitextual passwords
`ea whoJcapturespehe[PDA [canJpresuin-
`— obtain fall folfithé [ciphertext ee nuder)
`knowledge hichudessinformation about#specitic|
`ki tie eithergpublicjorgstored [inJplaing
`peaks) heeete
`oftenJchoosepass—
`wor ds—based fon [theitfown Jame)Mfand finformation|
`textifon Ithe|deVice FheJadversarylhaspatflcastfone|
`iTOSS}
`bosiohe “idict’
`LTee
`empleophate pepe ch fenith Pons
`tack AMForga strong encryption Scheme/Bhowevers
`maethedistributionfanattacker)
`
`the |best| forgthe fattackerpremainsgto[euessgthe|
`tergottthanjiffuscrs en choosinguniformly..
`Which Maswe[will Bhowgin Secs
`
`tiomp.3¥onaverage isplikely to be much fharderfthan|
`Due to the dependence ofthesecurityoffaschemeon)
`
`Mp ShimekeereLed [ih Packieeee
`a chooseintPpractice,}
`password.
`passwordBchemecanJnot[be provenbetteufthan[an|niaeePerforming[trialSfor|ne
`PrienmecaCAfOrangpesunyaagaes
`i od OurgapplicationBhares
`to
`and Fallows
`ofthe
`inthecaseofa|fattackersproutinely fuse would
`encrypt/dectypifrecordsfinithedatabasebased[onfa)
`userpepccitied [drawingTheencryption[tool ffor
`
`Palmihttp://csmyufedu/|available from
`
`
`
`tO]to flearn Jthe jEnglis (among
`others) {givenMopriorknowledge offthe typespot|let™
`tabian/pilot/gpw shtml.
`tergcombinationspused fin pEnglish by paving pub|
`pectsitypei B-chatacterppasswordsailnthe absence
`ot Buch fobjectiveproofmwepresent
`S13 PaSccurityforthe|DAS Scheme
`
`ney|See t§that—ithe[DAS ocheme|hsseonsiderablyPharderyto|—than the|
`of]
`tional textual Scheme. wo offt
`~ defineftheinformation Jcontentffo! fia password|
`
`theinformationContentfol[the DASpasswordspace,}
`overgthat|space givenJby[thérelative ffequerciesrer
`spthe entropy jof| a probability [distribution|
`Which We argue improvesjortheimformationconcert]
`the passwordspthatfiu pr
`availablewith [textual passwordsmg Lhe[third farguy
`tion Jcontent#ispthecorrect—imeastrejfor] fern
`Men fscrep hericcphaporkPipes cr
`
`thedistributionfof fusergchoicesphasgonfan fttacker™
`difhiculty foffattack Fsincejit]
`the optimal
`Tocopemedcwheal Mmeiene
`Ciesfforgapassword}
`
`eeeeCmEdefinedjuritermsjof[the|
`
`
`The Size!thessseword Space)
`
`contentfmrendersima password|
`High
`less)
`Forgexample, iif]
`scheme
`
`
`userspdid fin fact—ichoosepasswordspumiformly [irom|Firsttherawpizeofthepasswordspace,t
`injothergwordsmitspin formationcontentPassuming|
`the space offallftextual[passwordsmsuccessttlattacks
`
`Would [beJunlikely.§areequallyjikelyjtopickfanyelement[fasrong
`
`SizeIIS) ee aead
`dersysuchfattacksisticcessful finJpractice? [Therearc|
`ChooseipracticeshereWaytOrea
`
`two factorsiyLhefirst inrealityjusersidoMot
`content #ol fit
`choose theirgpthat]uniformly.giifwe assume
`
`
`the data collectedinjkleiis aot 02 fs
`
`passwordSpaceinordergto obtaina fulite ansWeLPOL)
`eeebeersom
`eenSe
`tative jot] theeoueral]p
`hen — infiact]
`“fot [the)time. gouc Sarere
`
`use Only 10 Bagotthepossiblepasswords§25
`Zero [to Jan fintinite Bubset
`fio
`leaving
`
`finitesubset|thatfwe will fcount™ call
`offtotalflenst aenea|
`information fcontentpot|the[textual password pace|
`is
`ereaterthanSome fixed [valle have probability
`_ compute|theBizeJIL(Lmax:
`ioSnot pick[passwords}
`Howevermthefact
`offtotal length lessjthanorgequal|to-Linax.
`
`uniformly ispnitselfmotpsufticient{toMakepassword|
`
`7
`
`

`

`Sim
`
`OOOO TON TOON 1011010011
`1010010 100100 10101071001071070
`O11 101011 1001010000 10101
`
`(a) {UserginputsidesiredBecrcUggb )flnternal representation|(c)fRaw)ppitsering
`
`1. Entering tect inta your Palra ll
`2. Palrn Ill Basics
`3. 1+=cd0207-HS 6
`
`3 Please Try again.
`
`WE Specific
`
`i
`
`i
`
`i
`
`i
`
`
`
`(d) interfaceto\database MMe) ~Re-entryfff incorrect )psecret
`
`Figure (3:APpasswordlisfcreated[by dizawing[theBecretgou[the\lisplay Pspshownjin Ka) Both[theinternal]
`
`representation ifthe
`put gpassword showilis[thecellsscovered[by[the juscrspdrawingpnd[thederivedkey]
`anal ty CrOeil emeer petne
`(d) Belects|the recordsfand then re-inputs} theDAS password Mlf[the encryption|
`
`)Bthe user]
`cleartexthwit
`a
`d
`create
`hnitialization
`off [known Jcl ith [theinputfpasswordfmatchesstheStored[ciphertextficreated|duringfnitialization§
`
`
`then |the symmetric cryptographic routine, P(g).ts applied|tothe sélected recordsmOtherwise,ttheuser
`prompted [tofre-entergthe DAS Becretl
`
`
`
`Pay eeeee
`rl
`ending fatiithe a|5way
`
`
`Lace
`
`= Chen }V {canjbe defined finjtermsyotfr [by|WAAsx) a
`ae
`
`Terre?(LAGfoambedeniedperiaspor ahemSSrE aa
`actspoteedlaat 2
`offilengthjequal fto[bys] CLGIYEG Bir(sc8y IG) LSClearly,
`
`
`ee|
`
`PLM) Ba) (Lae)N(TRG) PEGPrecRyAG) BgChefunctionfrear]
`
`-
`) ye
`evaluated fusingithe following
`avewpstroke Offlength # may|befadded[to|LR AC) — lgal—
`
`alyphortergpasswordofflength |Mil[tomakeapassea.we set val
`wordof|totalflength (UMBY
`defining fa) = ilie
`HI ra ay mr)
`Completefeilefitition
`folftnepecumcnce
`Roky BL LSC)
`
`haveiverenteepsessionfori (0G) eT)
`
`
`
`
`
`
`
`
`mumbergo!| With[total flengthJequal to|.Aig Lhe[following pecurrenceWelation [definesgiN (0G)
`
`
`
`8
`
`

`

`SELTEeMacpeReeRC
`
`eridfis
`
`3322 Modeling UserChoice)
`
`ml [i] -oP
`
`Pattie [the piccesptogcthermywe Jcan|calculate ue
`ittthée Pbstracts Only poecause [the pemanitic|
`
`size offthe passwordspace.gLheresults|forpdifferent
`content #fo!| has—becn|character)
`
`
`by]
`use Joffe [written Jiang
`Uppergboundsponjtotal password[length fon Japkp |
`gridfaregiventin|lable
`Suage thatfwe cantalkaboutfsuchcontentfat fall AL|
`the DAS Scheme 4therefareObvious
`possible [a
`ponents}
`haveMeaningqbuteitgispim
`Thedareiny abel phowspthatptherat pie ofthe}
`
`prooratto identify|Which will fhave|
`graphical password BpaceSurpassespthatBorfrex tual,
`Dasswordspifor
`comfigurations™
`Bemmantic contentMand[tOhow] many(USersmpLecisely|
`motga representationwithmeanilesjess
`While |thesenumbers—areEncouragingAil practice|
`
`notfallferaphical fpasswordsfare equall¥ [ikel¥ [tojbe|tablished[bycommon[use.1
`chosen Joy
`rendering fa funiform distribution
`optimistic. grorpexample,Falthough[thenum
`bergofJpasswordspofflength ercatergthanjorgequal [to]
`Sunple Bhapes|
`already
`than [the Jnumbergor#tex tual]
`firstpsetfo!)
`passwords)
`passwordsgor]sCharactersporglessgconstructed [from)
`Se eopha
`pen
`the printableASCLIfcodcs] 95°F? a)Mthispiltcltides
`
`all
`offtwelve isolated|dots™
`
`two Buch BtrokesMweJalready [reach[theBizefof]
`In Jordergito jobtain famorerealisticestimatejof]
`fused [tojcrack[textual Bchemes™
`
`information contentMinthefollowingsectionweSUS
`bemoreprecise,fconsidergthe setfoffrectanglespwithin|
`
`Sestfamodel finWwhithwecharacterizepasswords
`EGP JGIeridBSincefarectanglefan [bejdetined[by]
`beitig Jginemorablegin|termspof|
`tworows the top fand[bottomedgespofftherectany
`generate them.
`gle)
`and Fighthedges) mit
`
`be expected to Carry Ineaning.qWe look atfall Strokes)eeaeee combi
`
`by[thefactiithatfithereexisted faBhort
`
`
`theFeason[that]
`We
`such fa Briall Subset of fitcxtual fpasswords
`EachjofftheserectanglesjcanJbegeneratedfin finany|
`the passwordsfin[thatfsey
`WaySeger Orpexample,qohe btarting Poultpotpa Stroke|
`
`those outsidejite lack foffimagination fon [the|
`iESMTAMAATTN
`
`partfoffthe usergisfnotfthe cause forgthe lack offvarig
`ae,aeeee
`may]
`Sty[is Seeelee
`ehPeeeeait omorcen
`passwordsghave[been fso funsuccessttl§2|MEBy finak-4
`to[close the rectangle by|
`
`igthesameassumptionfabout9DASpasswordsmwe|
`
`itothe sta motmagain doubling the possi
`
`SEeTeae ci
`biliticsmOnap Xp grid Fthidfamountsyto111600poss
`passwordsm—ltiwe[can show
`BibleStrokesBat lwo Btich Strokes Buccession [eives
`
`that SetmporgsoineSubsetfol ftMfhaspcardinality|
`2.56x109 passwordsmalready roughly the size offthe|
`largerthanthedictionary offtextual [passwords}from|
`textual iid
`contazied [the
`of
`Which ypically choose,ywecanplausibly claim|
`
`of] [eIREC earlyWwe[can|in jens)
`
`
`thatfaspfarpsyinformation content] goesMDAS is
`
`generateainuchflargerpset| by"consid4
`securethanjconventional textual [passwordschemcs™
`ering fvatiationspon [the |themejoffirectang]esmqor] by]
`Here,
`two Buch Bubséts)
`different]
`onsidering otherpGestalt#fornsg 33]
`criteria Jol
`and show]
`Cardi
`Mee nee vinesMemonOnes
`terion.
`on short Malgorithims|
`Whatiiconstitutesga fmemorablepassword? Bn Jthe|
`[The Becond Bei ffoffpasswords
`pusgested [by pthe |diScussion Joffitextgbased [eraphig
`textual ficase, fone fobvious Semantic|
`
`content@alt
`itheSequenceoffcharactersphasyemeany
`al PasswordsfinSection22 Awhich[pouted[toward[a]
`
`ing fforgthejusermthe[passwordfissmoreJlikely[toJbe|différent|idetinitionjofimemorability-qL here, ier
`orableBequenceJof—positionspseemed fcharacterized|
`memorable [18,427.40]
`Semantic(definition pis
`
`extremely Joardabl to Keharacterize|inot
`
`
`9
`
`

`

`igure[BBA SBexpectedMthissidata Bhowsgthatfithe|
`
`
`Thefirstiitwo [digits
`a Btarting
`definition Jol}
`rt
`describe the
`orablethatfiwewish [to fapply jhere. sinceitfican [be|
`Thefnstructionsfup sdown Alert Fand fright
`|Saaieel
`Characterized1mPrecisetCriis™
`endescribe itM™but]
`pen fispcurrentlyfn|thedown[position Athen[Moving|
`
`ii[thespecificdirection [will daw paline FOtherwisc|
`describablé by short]
`
`elgorithinsyk WeTwill) mu thatiithe|cardinality Ti Oe:
`the\direction Biatement™willfinerely fnove[the[pen
`locationagLheJpen Jbeginsyin fthe[Up [positions
`isgelready larger eeleeehe"atin
`repeat Btatement]
`iterators Wefallowsidigit)
`Spitom
`Spuost] era thei)
`reuse,euid[that]
`ree
`Valtiesfup to the faumbergoffigrid Bquaresffon
`Feach
`BXISK LCMOnXpstid)ftojindicatethenumber
`
`
`ment satandontaeS
`
`
`of frepetitionsmalthough inprincipleapasswordcong
`hardergito [crack fin Ppractice[than [theJconventional)
`lof fmore[than frepetitionspo!fppomething
`
`" xp gridfrepossible(6.2Sten|dotspinithesame
`textual cheme.|
`position) &
`Tn Jorden eerieedexityol[the alg
`aoea,hea
`gorithm required|togenerate a JDAS password Awe|
`literal fin|We assignevery statementfand. aea exityone,
`assignfacomplexitytO feac
`define fa]
`pimplelanguage Suited[to|thetaskjof|
`iiplanreoe
`
`describing passwords hen 4we[generate fall|
`programspin [thisflanguage[whosejcomplexity
`Most§a [chosenJmaximuiy.tLer toavoid [counts
`onejforgtheinteger)aa the number
`Peeeeee al
`Ins iddifferent#programsythat\produce the same passe
`Ro twice,§we then execute the generated programs
`titions) [plusfithecomplexityfol} areie
`eeWhichfarethenJbucketed|
`
`UradditionbeP Btatermentfoffaprogram
`udpiste Paterpommehope pane]
`offcomplexityfatfimost]eachosen fimaxiunurn.§
`mumbergoigDAS Ipasswords—gencrated by programs
`ispassignied fa]
`Zero (lifting pone’s per
`from the SurfaceftpthewendfoffenteringBJpassword|
`to orset)Bio aorgexamp
`Before eee theresultspof| We|
`
`offcomplexity only[two,)sificetheintegers
`
`give Bomedetails eleekeelsa
`CSTDRTLOeTePenioepl Thopteemt ae
`srattlal Progra
`of]
`ready consume a complexity offtwo withdoutfallowilg
`ulypendownBtatementsag Lhe fist ee:
`Whichthere are ally PrOgraruspis“a the two digs
`isfaspfollowsy
`eran end|theJpasswordsggenerated [by|
`hispdescribing|thejifitial Ptartingposition Hfollowed
`Pros Ba cs pplock
`ComysithOfEBinsléitaPouJoneolfithewerid er
`Spoifcomplexitythite are simply [those
`block M-> Bistatement——block|
`Statement > MELstrmy
`Note thatfourfcomplexitycalculations#forgp
`ee —bogoreneeleersrkaonga
`repeat Bdigitf™block Jend|
`movementSBpcrwecn BULokes) mentees
`Up BedOwnmmricht f
`Lust |
`raisedfarecounted[inithe complexity Off
`left Jpenup sependown|
`adda
`digi |
`
`eeioTeT
`“Aa
`fo
`oe)7 ppasswords) > BRO PRT|ei
`re
`19 PAST
`
`|o
`
`o]
`
`Poe#ppesswords) M3 TIPS J
`
`TableIE JNumberpotpasswordsfof [total flengthflessfthanjorgequalfto|Lmaxpou»xpgrids
`
`repeat|loopsshavefa fconr)
`
`[The Fresultspotmusing qthe Fubove Idescribed Fproce|
`Kure forpoounting [thé numberpofyDDAS[passwords Or
`
`
`fe,Lhose] a osuGoomanis APPLE [II]
`
`willrecognize,
`lbearsyaa resemblance
`Befgiven peomplexity Joaael
`
`SLOG |pss
`
`10
`
`

`

`20
`
`18
`
`16
`
`14
`
`12
`
`10
`
`log(# passwords)
`
`8
`
`5
`
`6
`
`7
`
`8
`
`complexity
`
`9
`
`10
`
`11
`
`

`

`ernment|purposesmotwithstandingallyCopyrightFann
`
`
`Conclusions jand§F ature] Work
`In contrast@repeatability isfachievedinourpchemesl
`thereby enablitte designsfinjwhich the device,
`5
`turedMispofflittle help to the attacker]
`Wehavepresentedgraphical [password schemes
`The Becurity fofftextual Ip
`hasbeen Jexam-}
`achieve JbetterpsecuritY [than]
`textual]
`
`ined Jby faumerouspresearchersmgnotably PIL,|
`passwoLdsgtOUr
`exploitithe inputfcapas
`29, S34]MW ithoutfexception Athese|
`offeraphical devices)
`allowgusyto|decous
`the fact{thatfpeople choosepasswords
`PhePoE Mp omencrempon Perl
`to Jind Joy automated Bearch Mtn Jordergto jimprove|
`
`
`iif Jwhich[theyJoccurm for
`the Security of|
`theBecurity Schemespilt [which Wejanalyzed|
`
`thejinformationcontent fof} —|rr
`System jadiministrators| toinvokereactive[password|
`checkersgto fidentify [weak[passwords 26 420/orgto|
`SpacesmgWealsopresented@novel approach forfcapy
`use proactive checkers|to filterpoutfcertain[classespot|
`toring [the Pamemorability@offeraphical
`Weak Jpasswords—when[theuserginputsghergpassword|
`Of
`Generated
`Mache eDoe
`Short[programspiifsimple grid-based (language,
`and
`Showed|thatfeven[hisprelativelysmall Bubsetfo!|
`
`Aftechniquetoimprovethesecurityoffevenapoorly
`Braphica.
`(forgsomejfixedprogramcom
`Chosen password15 areaing ptiwith a random JoumberagRAgbefore Jhash4
`plexity)ficonstitutespesfinuch largergpassword Space|
`than [the dictionariespof|textual [Passwordsyto[which|
`in8 9 Ao]Rg Thejeffect
`theSearch Bpace
`of]
`ahighPercentase offpasswords[typicallypclous.y
`the fattackcrpispincreased [by Jajfactorgo!|
`attackersdoessmotfhave accessytothesaltsm
`Forgmfuture Bwork Fwe Bare Bexploring Palternative|
`wordsmthatiiweJhopefwill Se ae
`Schemespormodeling the Imemorability Of[DAS passe
`The i|be fcombined fin]
`
`natural fwayspwith [the[téchniquessdiscussed Fibove|
`ptructure finorejintuitively pthan
`fourgcurrent™mod,
`elsecapturethe conceptforto
`
`
`fen,
`toim
`drawingsmin which [theWiewotfitheWholejis
`prove the security jofferaphical [passwordsmasgwell&
`thanjustithesum offtheindividual parts
`Stituteitm orgexample,foneCamView)
`More WorkfonJone-timne Jpassg
`
`objectffin fitselfffand Prot
`aadhooio achunlsating, gaia
`WOLdsmk
`€.2 Sp Lt]) MgOne-timnepassword Schemes}
`oftheindividual flines#ff om|it]
`against{theithyeatfor eea caps
`In [thissway,qwe[can |definejaSetfofsprimitiveStruc
`turespfromwhich fall memorable gdrawiesycall [be|
`tiring passwordinformationfnjtransitpbetweenjthe|
`derived using meta-leve
`usergand faBecureauthentication Bervergg Lorender
`itivesag We hope to Bhowythat]
`reducedBet]
`OfPDASpasswords) = SomeLeasonablemumbergo!]
`such eavesdroppingfharmiessmga [one-timepassword|
`Scheme[variespthejuserpsppassword [fromfeach flogin
`primitives)§constitutespa jiargermspace|than [thatffof
`to [theIextin Fa way thatffonly pthe fuserfland [the
`fextualgbasedpasswordsmand
`faspsuch[will]
`can predictPbased jon BtateShared [betwee|
`icantlyiharderjto(crackjinJpractice.|
`
`the Serverfand usergglnthemainSettingWeconsidcrm
`howevermthere15}
`Vulnerable tojeavesdropping gand consequently [the|
`attacksgwith[which[weareConcernedjissthe capture
`6 eAcknowledgement
`
`
`ald ofall BtoredBtaterelevant}toauthentig
`
`Cation injourpsettingMorgequivalently[the]
`serverpspand(clienthspstatespin[the one-time password|
`Workisfpartially Sponsored [byaUSENIX [schol
`Setting)egOne- tithe[password Bcheresporpwnich PWe|
`
`arsplicsearch|Grantgiand[bytheDefenseAdvanced[Re
`
`are aware Offergno|bénefit
`attacker]
`Search |ProjectSMA gency (DARPA) and [RomeLabora}
`traditional [passwordBchemes™
`ConAproneMateriel(Ommmand, (USAFRuudenperree,
`
`
`ment iumbers}!30602-96-19032030602-99-190517;]and
`
`
`and [by [theNational [Science|Foundation Jundergerant}
`umbergCCR941/1590.MELhe JUS BGovernment}
`thorized|toreproduceand |distribute reprintS#forglGov=
`
`12
`
`

`

`experimentallyprovenactpthatgpicturcsparcPasicl
`
`cation Tt
`7GEMandicreyourpaccpooks}familianpbutpl jeant]
`berjyourfnamesJA[reviewotdualprocess[theory.Relating|TheoDATOo99]
`hereinartheauthorsfand should notibe interg
`pretedasmnecessarily representing the official policies}
`NLSBGBAAMillerS}Thefmagical Jnumber seven,plusforpninus}
`endorsementsmeit her)
`implied Got FDARPAI
`two: Boome@limits)
`capacityforgprocessing infor,
`eeeDCec OSCees
`mation WPsychological [ReviewHostelgr,YL950m
`(LOWERSMorrisfand ks
`Password security: JA [case
`history.ofthe ACM,22IIL) 2504-59),|
`Novemberg|9/79m
`References
`120A EMuttet3Crack: JABensible[password checker }or[U nix.)
`‘p ffomcertorg.]
`VS. Nalwa. JAutomaticfon-liteBsignature
`LBA SAWareHow Jcrackersycrack passwordspor
`[what [pass
`Rwords|to avoid.Win Proceedingspof thep2ea—uSENTX [Ses
`ofthe PiiEapagesp |sg230mbebruary L997.|
`cuniyWorkshop,August 90g
`POOR. ANeion YU BS. Reed fendUMM Walline rictire
`Superiority effect Journal|ofEcperamental|Eeperimental |Psychology:
`2eMeBishop.gPassword [management Min Proceedings) oF|
`Human Learning and Memory, 3480497, IL977.
`COMPCONDyperry or1ooMrebrtarmom
`123A SPaivio.
`Jimagery
`and [Verbal [ProcessesmHoltmnineg
`