`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
`
`
`
`mmmmnflnw
`
`mm W
`WWW.-
`
`WEE-W1]
`ATۤT Labs
`
`Abstract
`
`graphical
`tmflfli Wm iii graphical
`W Eachieve better Wthan M:-
`__ W Eng-mi Elam mama
`
`D?m_ _mifiz‘fim
`WW3! Whlfimflh
`BXIWMHIiIII- W _Ima
`Isaw Email—III- am there
`roughly
`II IWS- W
`WWMW—I—m
`
`.uthorization @_st
`
`[til- win
`thehtication WEI! We?W
`_thmfilatMm-aium [IE-13a
`Wm?
`authentication
`film
`Wpasswordsz”mil
`Passwords
`“11W WEE-l
`WW2+EE§1Emm H:
`ad]
`85.!!me IW]
`password_-SEW-Lb: mmflaflm
`[Endesi_gns (drawings)WEE-W-
`flhfldevices by whichlw--primarily
`W—JdigitalW (PDAS) MaI-
`WW“ pple NewtonTMl Casio
`:E-flflm. MW mmu s—iia
`
`
`
`“W—.@JEIWE
`that this decouplin
`enerate
`W -
`g
`g
`passwordm Wuostantiaily larger (memo—
`W" HEW bevaluate the se-
`ou
`,
`
`mam @Ei HIE!"
`mm W
`ENE-3 W!
`“by W Emil- ma}-
`Emml] W (PDA5) W DEE: graphical
`‘
`WEWI describe our
`prototype implementation [flo_[fiou WEI
`Edi-1mmMme Palm PilotTMr-
`
`fl
`
`Introduction
`
`E9: imam majority:11W swim. IRE-i=-
`Ma_flfimethod [ii fightauthenticating
`—- I I WEE-Emu Wfi tpasswords
`”WM
`WEE maxim Wilm-
`iiEIi W-mwfim -W in
`mm- hing [bi *__ [til
`“WEI E47000 WSW-311m
`
`graphicsnput to the device Via a stylus.
`graphical
`flm rm
`graphica Eng-mi mm—ml
`
`film 911
`
`Imam] 95 an
`E WWW Elv-
`“WW
`WWW
`aflflmflfiio-mm
`mm “imaml-fl
`imageinn
`m0I [E93
`
`2
`
`
`
`
`
`proposal, WI 4 did m fifither explore the
`power BE .rnphicnl
`-mBBzM
`its particu ar
`
`that W —eL§zBMii
`—BJEM th W B21
`orable I AS
`passwordsi | argert@fiW_passwords anewi‘h aflfi
`
`William]
`In W
`and Wm? graohical _- “WE-I a
`main BiMMthe mmfigfimflfllw
`words“ BEWWM
`We designWfi _BdMfiflB
`be ieve mm—_WW passwords
`W__WEMBBMEEBE 4 hBflm
`WWW MMMEB to ma e this W
`meht-
`implementation pfl
`map?
`_BdMnr-B -WM
`Pilot-
`
`a graphical interface for providing input
`
`The
`_B§M¢M
`
`derive their ”strengthfrom the following observation:
`user 11¢”.me loft-m [MM
`their temporal ma
`sls MW MW
`passwords Enid!
`Meal—ail
`WWWmull-ul-
`termines BM: WEE“-[MW-
`inaI“ mi; % consisting @5 W
`drawn [Em-t-fififlposition 511 malinea_@
`determined independently [fl “all my fly]
`which EMEMB -Etm lB'MB W M
`dependence him WWI-M
`be used Ea—H- _.BBMIM
`and En:—WEI“ EB
`vineing y stronger mm
`significantly harder m—-
`
`M!
`
`The first gr.WW‘W
`
`en ancingm
`ontextual Io
`put pfiMiiIEfl echniques
`In this ml we assume t e same underlying distri-
`butiono-t e graphical
`
`Bi! [Mia ntBMpa BMW We
`
`lm WHIWWW
`
`
`l—IwmtzBI-l
`
`MIME-fl "WW
`m that“W.
`-rmiHMMBJJ Mon-graphica
`Wrecognition 911
`(see Sec—
`MQ} Where I BBEMB M Write lecog-
`mm I “WW M1
`ME
`WWW
`Because0(attern recognitionm
`Estoragepfl (some representfimmfllt
`Wan-mIII—Ils- ml}-
`*MWEEM WW Blil—
`Mm W.because graphics
`mm _derive a secret Mag“
`mm mm [film-WM WWW
`mp1!) [Em
`M] 5361* mm WEE-1%
`was t e device fans nun—p [MEE-
`
`MM
`miflggfii B21WEBB Wnd
`afiqfiill-
`-!mfi Wilfiil _passworS
`muW [InWI. “mm
`1121!! mm We
`-W-BME - esign BEE]
`‘ cheme
`
`Wmeoses WWW
`
`.bnalyzeand estimate the3security ofDAS and grflpjhe-
`
`M]— EiJ-generEflsMMMJI_
`BM
`schemes
`Ba
`_IW putting ourmfl Wr-
`mWconcludes
`
`Ram—WW
`MW
`
`[tum Wm present BI_EEMMEIB1EI
`M3111! BEMMIWhich SW
`nug-
`W Wire-meal:
`mama
`fimfl-Mfifimg
`“in hie WWr-T
`
`Winteresting because it simp y demonstrates
`
`[flamphical EmW hile yielding
`
`iiMltextua
`
`password
`
`word that WWIfllfliflmfl-
`mate B21MW_mmw
`input MW Miami!
`WW parsim- lpmfil
`implement ammwm ”Em 3W
`(DAS).WE Wgrsphicsi Bus-m W p]
`secret design (the password)o)-n@m. Mina]:-
`gue an
`rMiIEfl I'
`.m
`fine a class flD
`that_
`tures EBJJEHW BEEMI
`osne -
`
`class MBMB BE EM— magen-
`fllfian‘Mflp—EnEW‘E?
`language .Efilmfl
`twa—
`moi I‘M eaBM’Lipmay—I.M!
`
`3
`
`
`
`IW]Wl I {1.-._, a}
`password
`where A is M [ii fl-characters fly] the tex—
`tua1_-'
`“iii
`the temporaoIEEI uII Ema-IIItTiiEi-nut
`1km W}. WEI-T tEIEi I
`password
`I-Ema
`a E m a m
`oaui-Iiu a air-Is: 5 iii
`in: a is
`
`Now
`
`W1 Imam:
`
`numoer
`
`Forrnaily, Elia-W gram _Elts
`H51] [EmsIfl I
`uniJJJJJ'JJJJ-J
`means Ete i— h entry (tempora 1y) is the charac—
`ter mposlition j. n —textual Io
`
`7r “lathe —left—to—rightmexpressed Efi-SEW-aI :raphical Io
`'a] Iula-mmmg?
`
`sums-Emil
`
`ure fl.i
`
`(e-g-, WWWWIWW
`oddsI odds-then—evens)I mil M
`Imam Di position EE-
`
`I'zdl'r-fil El@W Ba“ torn shit?_W
`
`tionsW-We will wantsSW:-
`E11193 memorability @1111!!me
`WE
`ill FEE
`LEW
`dial! W m- EEEEW IE1»? WEE
`II-strong asW
`WEI'EI- Why Ema-.- %
`Emma WWW-Joli meg-3m LIE}-
`WWII—mi
`W
`IEEIIE— EIW-
`
`“WEE
`WEE-Em of film
`LIME-III Isaiah Firstflmflnflfl
`“to? inputting
`WWW-
`MWEW should
`WE Elam at! W my“
`
`mm:mm'IafluIII firearm
`
`WT s.sa departure from most password--input
`WIIWI mElnondfescript {#51}-
`W sum [MW
`hams- W39: Iflbflm‘ffls m-
`
`new
`“primarily
`m. the Palm PilottI1t 15mm 1!“-
`mile--IimmmmmWWW.
`the interface might WW WEE! W IE.)
`password “ orma 1y”
`left— o—rightmfindrag
`WW WEE finazwmmI
`
`WEE-1E!
`W imam—i
`Mflm WWW a}-
`ranging IIW Wm En—EEI'IEI my
`Mum [Esmeg a.rid .m#
`m Eam- Rather than 11mm
`mmWWW
`
`IWW!WW
`
`ple graphical WMQSI m=eight
`positions W mm] film password
`as WEI igure fl- [MIME-131E
`the initial
`@5 blanksIEfifil
`tempora @flsfi EEIW 511W!
`1e? 710') WEE- E- III—-
`be placed EEIWIWWW Wm
`W31 El Figure Irm- WEIR-1* mm
`ofW interface, WIN mm
`the _EME'IEI Wm.- mfll- EH
`am e, WWWI.“
`user m I_Eflnleft— o—right
`but '. rting from a differentIWposition than the
`leftmost, |MIW I—En
`an WW strategy MofimW
`ations can be combinedin the obvious maW
`i
`“ WIS!-
`
`11%
`
`
`--[Imslmflmm in"
`' mallI! WWIISas:
`—"haracter _]Io
`tom
`
`Ellgraoical WEEflumil
`Isis-1am: Immune-mm Ime-
`indeed
`graohica password_§W_8mm
`tively —WI 123.1193 IESEMI-E- III.
`this actor “MW-
`
`conventional Io
`
`[hum-
`
`[011 Hamlin Ema] WIIW mils:-
`tions @Zi Willi}— will
`tale for [Emma--WI. WWW
`ammmm
`achieves
`_§dIIEIIE
`conservative toW ilk-fl m
`tions of 3—431151
`3W :9? EE-
`
`Eutsmiflm-mma
`WWMW Wham-mil]
`WWW-WWI—
`Isa simple oicture drawn on a gridT
`IIIEE making it
`Iii mlangiLage Elm:
`fink-ind fl alphanumeric
`
`{swab
`
`4
`
`
`
`u H“H H
`
`L! fififififififi
`flan fifififififi
`Egan‘s
`flamma‘
`EEEMEE‘H
`flygygyg2:
`
`Eam“
`Eama‘
`EEEEE‘H
`flgmgyg=z
`
`Mm
`
`gall-lull-
`
`languages
`fl!-!EEEI n
`
`WW
`
`"HWY-W?
`
`Figure I!W
`manner WEE
`which
`
`imam “MWWW
`tum-W mm
`WE“ mm-mmmWHW Ell
`[WEE- EEMWW ”mums? [iii-1W in
`tomato. Figure b) WW [Enema 39]—§ -Wnfln§!fl
`and w the combination {ofl m.
`
`other W W- Wame sequence of w
`
`
`W Wm 911 ami!-
`Ei‘flefl shag Il- HKefl] Eil- will 51-:
`Wreetangular
`(may)
`ilmfil
`Ilmfiu that WEE-l- is given
`a! mmsfia-W ENE]
`-' revving Lilian—w
`L-EEWWIE by I
`Irma
`ldrawing mm in
`IE in W
`through them,William
`inserted ism—[29:1 will WW mm.
`mmW Ellis the stylus
`ham Eli
`onsider MIME
`HamilWilliam
`[E]- Iminah
`
`The W compelling _flm exploring @-
`:921 2a
`@313
`that [fil-
`mans —Eg possess _ability E9]
`ca ling pictures
`ine drawings objects)
`
`Lthem pfl WE-
`The “picture effectfl
`-51 ariety 05 mm
`rial MW
`D? —mflmmm mstudied Em
`decades ll...- a“g [Em
`W- WEI IW @21
`performance in Wrecognition _W
`representations @fi to—be-remembered WW
`for WM#-
`
`Superiority 33mm mm -EE~1 Emmi:
`diate mm— mm mm [EE
`been W E!W 911 m-
`mentsu HEW
`@ZiW
`-@ W “WWI-a
`performed [531W IIJ _@Zi WEE:
`declining m-
`I-mW
`mm, mm“)? objects dropping mm m]!
`20%
`he same period. W ex ibiting m-
`ing y high
`Emma]! L921 pictures
`over
`ords
`
`[Ema
`@Jr- WEE-1931??!
`mints l. .319].
`been proposed to -Mthese experimental films
`are outlined IAppendix fl.
`
`B! WWMW
`
`@fileWWflfiflll-Efil
`
`mdistinguished WW W.
`WE
`_SIecond WWW mm
`1191-
`W m 'l—mfil lien-III m mm:
`@21_rmfl
`[29:
`W- Eni- m e divide the space of I0 ossible
`u rawings Wequivalence classes-Wig” M;
`ing equivalent if
`have the same encoding,
`fly]
`
`5
`
`
`
`—-— -
`
`might
`
`00 close to a gr1d—‘l1ne.fl3]those caseSIt e user
`the drawing Eam-
`Buhchange
`—Efi
`(1) m
`REE! Emsolutions WEI
`“Elm mile-Emma . epreseniaiioni ale-33E-
`£113me EJIE.W§E-ldfim Ba—
`39-WEE];W-Th-ECIdIE mm
`[IE0 raWing. WW m
`flaw—nun:
`-mmmWe
`WWW mgrid [Em [til-imple-
`
`m in ection 3% -®: both
`W-
`
`I. Application of DAS: -|WM
`To—llfizi
`
`m graohical passwordmm
`marily oy PDAs
`fl]
`Em W
`—_ Mimi-H1921 rm
`_Efil
`[Ed] EDI WWW
`51W graphien1p_ihEE-Jfifl%
`
`key. The Pilot-supports am
`3933]. graphicalfinjqflWI anda- mmprovidesEll
`platform fig] Hmplementing ml! AS mm
`Eflifii Lil mm Lil WEE ”WEEK?
`WWW Emi—WW-
`Masha—m
`
`E5:
`
`encryption / decryption E1]
`my},
`[I]:
`[Em-password (ie, E
`ERNIE!
`8 [im- string
`m—Sifi
`(including
`Puma
`up” ndicator)- Eh
`II E
`“E Itime) Wis mcrEmographic
`WSHA-1_W——
`WWC-EEEBE_ -EEJE:
`W WW[flfiflnproalhtfl Wigwam.
`Wength m- rip e—DES1 is WWW-
`nd Wei Wm_
`WEEK-W WW5!-
`
`WWI Wm:
`m-mmmmfl mesign-
`anssword pflEEEl. IE“and en
`pre—defined
`pI
`E5
`iEEEI-EEIPDA flaw—i
`rE
`
`prompted#eigeiin8LEmit
`E393:-
`hes_deesign
`WEE-WisEm#W E: p)-
`I I miEnlEEEIIE Wpassword
`1Based 011 Ian Goldbergs @3311
`“P tfifi
`
`cells. with the brfiks between trokes WE“
`he same p aces-
`
`1
`
`2
`
`3
`
`4
`
`6
`
`5
`1
`
`2
`
`4
`
`3
`
`1 2
`
`3 4
`
`FigureT2 BEN dietI” _-raIlI
`grin-T-drawingsE —Bua_cpii
`mlisting the cells Efl_
`the stylus W through them
`worm inserted Efi-—Whenever
`the stylus E —Emmflmfiigmfim
`
`eterminology Wei WEE-l
`First! -give
`:19?SKEW HE“tdi
`neighborsu
`fig)“[13' y
`the setLifl
`Ingrid leu'
`ale:
`iline aWfim_ cells El-
`cz IflfinWWW m1
`l’igenmfl
`mm- H _E mam—Ram
`ofW “WW ME The 1ength
`1921 mmW @Eif
`tam-W
`Iii Eli-Imp? I
`EEK-E
`the “Belling-f Wt.
`
`WI.- WEE-1E m
`As
`viable ifWE EEK-E
`Wilma
`they
`“weappeal Ila—t
`
`ability [git-mww--targetingg-géiPDAs)
`the inputWHI-
`
`IMWAEMWID
`
`
`manage—”ii
`
`Em #requirement @fl “Wm iam-
`raineters @Eit 8% ISEnatE WE my}-
`rent drawing BE flaw—#m
`the origina drawing, mm
`a WWE In .eneral, m gives 11E!-
`W _(inv01untari1§) varying the
`drawing,
`the cells {011 t e rid m
`too mall
`S-
`Willie
`illng EM-WingSIWfiflm imbegin
`with Difficulties [mm mm. Wthe
`user mm a drawing
`tmflEEE Wt
`
`6
`
`
`
`flaw simm- .mm
`mm man] passwords mm W
`WYEE significant | nowledge ofmm
`D? _n mil-m knowledge in
`[Ed] afimfiiuse [Milk—oi W was.
`knowledge mm“mmWEIR!
`m5}:Wdistribution gm)WWW
`MbH-m mname) NIH
`W m
`words Ei! he English W
`Minimumchosen)
`WtWattifizfl would be no bet-
`lmoIEEEI ms wag-113% “mm
`
`WWWWt
`#smfli oi
`which we argue improves“gm
`
`vailablem=w1thW passwor1ds_T
`mm Eli-Em wasn't—-Ilsa knowiedge of
`
`@M—w
`
`to encr pt/d_e_'crypt W_EEI- IEd“film
`the DA at thelatest W he PDA I _dfl.
`
`nadversary Wcaptures m- npresum-
`
`aAbly Wall [921 them encrypted [mfih]
`k: Melina- I mmW0t stored Emits!!!
`
`textoIWWmhm all Weom
`knownnpmaeaWW mm mmmm
`tack E- E1] a strong encryptionW“W“
`the W - h the attacker m mm m
`m as -W]] W En El:
`tionm_ likely to oe muc W m]!
`if -Efii§EEfl —faced man—lumen
`password.
`
`m
`
`The interface for
`in Figure .3]- [fim application m
`oi he
`pplication? mm in
`/decrypt -EE Enthe database based
`user specified drawing. The encryption Mb]
`Pa m
`available [imm-
`fabian/pilot/gpw.html.
`
`3.3 mama-am
`
`WeWfl mm @EiaPW“
`st e entropyE—fltflfi
`over
`space givenm
`{ii
`the passwords thatu mmm
`tion W1Itlsmémm_E93 describing
`
`the optimal
`difficulty [95 mm.
`c oices Emmmmflfimfli
`ties [to] sawmil-
`
`119313231! Win a mil
`High
`Em
`Eli mammal
`scheme
`users IEEIM m— mm
`the space of sum—mmnm
`would MIME-WHEE-
`@-
`der: mm WEE-W Elma-
`two factors- flit-fin!
`baseman-s mm
`c ooset eirlo
`uniformly._
`the data “Elm study lIZlIS
`tative {ofl mgeneral population, hen 1-5“? Elm
`use only mg 05*- @21-
`time- Sue 3Winformation W [fl @textual _§W
`
`is
`
`Emmi WE_
`However-W
`uniformly is flaw BEE Elm—1’3
`
`II ue to the dependence of“mm
`WWI-
`_mm —I§emai W-
`om Mall-sonIWIism
`Maintain—mm
`Emmil—ism;-
`In the case ofW_
`W routinely use would
`in [brain El Englis W(
`[in
`m, given @3919] knowledge of t e types (DEM:-
`E] comoinatisons WEnglish Whaving mm-
`mm passwords- flatthe aosence
`@fi Wobjectiveproofw-present Wplausibil—
`
`.flurgumentsthat
`tthat [Ibr-
`I considerably W 329tam! WEE! [Ev]
`
`flflWIG-II “fishnet?
`
`
`:93
`
`“to? m [En ---ttacker_
`
`wwm—wm
`
`Elisa—WM
`lflflfiiflifi 311%“me
`WWWWWWEE
`QIIEI -IBE§€] Wail--
`_@flia:fii @21
`WW —some way to delimit LIE-l
`#mifi:ma finite answer.-
`hflfl an“
`"WWW .
`WWWW-—Efl]
`_EEWIII
`greatermtome fixedHvalue have prooabilityBREW?
`wlenggh less mm mm]
`
`7
`
`
`
`WWW—m IM#
`
`1. Entering text int:- your Palm III
`2. Palm "I Basic:
`3. 1+=cdfl3¢U?~H£¢ 6
`
`|I|1|I||I||I|1|I||I|1|IIII|1|IIIII1|II1|IIIIIIII1III11|I|1|I||I|11
`1fllflfllfl1flfl1flfl1fl1fl1fl11E||II1|II11|II1|II
`U11E|111|J1|J111|JE|1|J1|JIJEIIJ1EI1EI1
`
`Huthnrizut
`
`II F
`
`6 Please TI'5.|I again.
`
`- [El]!
`
`Specific
`
`mm fimflwm
`
`Figure 53 I WEEE “by.WWW IEEIdisplayaI Winfifi_HEIM
`representationwt-I'np11t passwordEEfi'H-Eia-@IE _Imthe -fidWWW
`
`
`database(Shown (fiLthegflfqausermtherecordsandthenflnyflImgtheDASpassworfl.m”
`“in
`resoectively.dflsymmetric cryptographic W[tum fly]the
`:11mam-cleanextdwith [film wflde-E LIE-MW “III-m
`thenWEIWEmmm-WW E
`
`prompted mm the DAS m-
`
`numer @fl
`[DWI-‘33
`
`WWWWWE
`
`riding ' t e WI“:6y) Magi“)? WI-LG
`
`L21
`
`
`
`
`
`WEN-_h'm©§ll§fl
`(Elsa-flaw”
`EWEI?
`’
`III-Ianmwm.
`WWWWWIW W lll-Ql
`Mm1/7)I
`Wtofldefinewmye)
`PM a
`P W |I«Q77n(:v y7l7G)EMM—W
`evaluated mthe following
`u llp
`I
`
`EMIEE
`
`|«Ql
`
`a
`: 1
`=
`Ell W length Emilia-Ea
`{tillength I III-In;- W "#2 I“ ‘ 5&1
`mmm'7
`Wength E.
`defining PM] E hm
`I W. m a]
`completelikidefinition WWH—m
`H W ‘M flag]
`ave given _EE:I WQ}
`I Wflflp HQ]
`
`8
`
`
`
`together. m-caIC-u'late the
`Putting t e
`912395 the passworflafimW lb: @931!
`upper M Emir-flWWI-lull
`grid *EEWIEII-
`
`The data animal m m M ans-
`grahica password swamp-3m
`{921 Wall
`passwords for
`#.
`While WW -—gma LEW
`not all] raphical WE are equally likely bib
`C osen by
`“uniform distribution
`
`mjgmiflmfim E):“Wber . —Dlilehgt :
`
`@31- may
`than lanai-Ia: @fl W
`already
`passwords f Elm [lam WWI
`the mam WEE (958 WM.W
`all
`of “misr-
`
`In nib: mmE—me
`information WIm the f0 lowing section we sug-
`gest .flmfifi] En-we characterize passwords
`being “memorable” Emma Iii
`generate them.
`
`3-3. nun-Imam
`
`What W n—Wifl [til-
`textual W -W mam:
`content- WEI—oilW [En El-
`mg lb: film LEI—I _Wfiafih
`memorable lIII
`@I- WWI
`mum-u. mi!
`I:mm
`
`L931 @391! WEE:
`
`WWW @Zi
`
`rfl-MEE-IWDEW
`al—WWEWEI
`mmw—W
`#flwflm _d&n§fii§fl@fil
`
`on y because the mm
`Eat e Wstr
`W 921 W [EH [then
`m
`-@21 Emmi! [lan-
`guage that __mii mm Ed! 51]!- E?!
`the DAS mafia-W
`mam Wmeanmg,
`ii _n
`thich will [Ema
`emantic content-Emmim-IW
`mi “mi!!!
`se-
`“[5]—
`
`IH-sflmfla»
`[EEG mi! :93 ‘ emorable” was-
`mafia! oi Empasswords
`might
`be expected to carry meaning. We look at 3mm
`MW WE-
`lmmmfl BEIGE-E. -Hm1l
`skate?
`Mmmmfl] imam-
`—@1oifihi EM @Zi rectang es mu
`El. E1. grid Wdefihed [fix
`firm- (the Wedges @Zi Wit-Lima-
`gle)
`aml I ight edgeS).I
`ear m an [fin ectangles -a G m
`an.
`
`leaflets-r
`
`WEE Whgles wmhm
`ways- w] exam. e, the starting point fl .m
`. ny of the corners-and the stroke direction
`cube clockwise or
`was a
`[bi mm ectangle. unm—
`[hlclose the rectangle [W
`m. again doubling the possi-
`W.
`—- @31- lmthis We @1le
`WW- WWW ngves
`”W _Ialready roughly the size of ER.)
`Wm- contained the
`oil
`oil
`rum IIIII-
`by KNEE]-
`mlarger Ed!
`ering W -t e Mcfl rectangles.- m
`onsidering am my]: Em _.
`
`
`WWW-MWEW
`
`.IiiEIi
`We
`will aim]! W :93 W was
`the passworE‘I Rum Eel!
`those WI-
`“[921 magination @31-
`part dimmm the lack simil-
`cfizI flwm
`passwords liken-unsuccessful III, By @-
`ingWW -passwordslwza
`can W W oil
`oil
`_- fill-gm
`mil-m —W hill-Em -Efimmz
`that
`largerWIEHWW E19311
`which
`ypically gym—plausibly Shh]
`that h] E information mm FIDAS is
`WWW—“WM-
`Here, -mmmflm Wham
`criteria @21
`MW
`DEE"
`nalitieS oiW”W
`terion.
`
`9
`
`
`
`73.nm77l1 Jlfllljfl7wflflfl
`WEIWEENI llfillfl IIin 11-
`Em
`lfiifl17
`lhggmfilml .17"H- .l 111%
`
`WE!W DEWEEE IWWEE GEE!- WWW-Emlm
`
`Bastarting Wm-
`EIEIEEEE WEE
`EEIW mmmmu ight
`mmmlifil
`WEE WEIWWWME
`mwmfimm [01mm
`WWIW will] WWW-mm
`Wm- IW}: flaw-misman-
`IW W- IEJIEE digit
`Wires .mmmfiflfl Eli WW ach
`ESE Warm)WI
`Lair-alt ough in“
`firm_HE]:J5 | epetitionS [93 Something-
`a! I gridmbeg, IEEEEEEIW
`
`position)-
`
`megr
`WEWE-ac 1itera1 EJI
`We assign every statement . nd digit comp exity one,
`WTtorS6361193515]WEE. whiEh
`
`Ilka}: EEK-In-
`WEE mmfimtIrepeat
`.335]
`-E9] ginteger indicating the W [dim
`titiorIS) W501mm
`[111. dditiohWEE-11E!" Wrfia
`
`WEED?
`E!
`describe the
`mala- IEEIIEEWEEEEIKEI Iii-l
`0 arm argue that
`mIfFLEE mm algorithm to
`describe itlm
`describable by m
`algorithmsa
`lwflfl m that m
`cardinality flit 'sEdEEZi Eli
`is 1ready larger Wflfiimmfi W
`from
`m Wilma WEE
`Passwordsu FEE]-
`Margu-
`ment mshould be
`harder EWEWWWI
`textual m.
`
`In [9%] figcharacterize the ‘comp exity” [921 W]-
`gorithm flagenerate mDAS _m
`define Ea Mianguage mwwmw
`describing
`passwords. m -generate flfl
`progrEI Eil- mfiflcomplexity
`most ndfimnmflm [inward] Elavoid mm-
`i-n_gW programs
`tproduce the same oass—
`wo-rd twice we then execute the generated programs
`tow mpaSSWOFdS. whic m bucketed
`
`and W passwordsl-Imm Elam E Elli-l
`numoer @fl DAS passwords generated Im—
`ofmm mth_ec osen amalgam].
`
`Before describing imam Eli
`m
`give Ieetaiis {fismfl-m
`flthee pgogrm.
`[flthe language
`is I“W2
`
`Isdescribing minitial
`
`followed
`
`stEEEMZEEE tail-l
`
`
`E assigned E]
`_(liftng [9% W]!
`fromICEthe1Ema! mww entering fl_
`Id ltfig 01%,-QOWI_ere are no
`s19? com 0 exityWWI
`wstarting We? mprogramm-
`ready consume a comp exity ofWm
`mpendownW- Them
`
`-Weresare any programs kwthe two dig-
`mfl=p Empasswords generated m
`thre_eare simply W-
`pistihgEliaIWWOH
`IIEE ME!rid
`1 ate thatoIWI forp
`Elm— En Elia—We rim;
`W1)Im MWWWBE
`MIEHQD
`
`tau-"WM
`MI WI
`
`W IEEEH
`
`“WEE!
`EEE Imylflmlrflfifill
`“Manual
`Ella! IIIIlHEI,1
`
`‘ PPLE I
`W OIIIIIEI
`Wrecognizet
`[my a striking resemlance
`0 LOGO |||_
`
`Era-mm at using trauma-II
`
`My] counting the number pflDDAS IoWEE@fl
`emplexityoIlallm-Wflfl
`
`mg s
`
`10
`
`
`
`20
`
`18
`
`16
`
`14
`
`12
`
`10
`
`log(# passwords)
`
`8
`
`5
`
`6
`
`7
`
`8
`
`complexity
`
`9
`
`10
`
`11
`
`
`
`um: idiom.
`In mama
`there y enabling designs Eflwhich the device, i.
`tured Infilittle help to t e attm
`
`1i|_
`
`Conc usions m W—
`
`The Wm?WW [Ea [Eailem
`ined I5]— In mi
`IIIIImI
`29, EI- mm mm
`the fact IE!#35:
`to max—um Elmira] Liam
`
`the security 95
`system administrator: EWWWEI
`C ec ers midentifyW_ m. 391-933 I“
`use proactive checkersW mmm 511
`weak I- mm m IE1 WWII
`or IIEIIEI Imam. II-
`
`A technique to improve the security of -.
`c osen WEEEma
`ingIIII will! EWW: I. before [GEE-
`i__ng III III-T-pfi‘iii It hm}!
`iii
`the WWI—Wimp)? I-
`mmmmrImW_
`
`The
`
`Wnatural W Wilt-330m mm
`
`Em” -IE*E
`
`W M WW
`words eg.7 jIIfl L. Wpassword Wm
`relevant
`fig] network Wettings in—
`against WM [921 nWeavesdropper my
`turing “Em —IIE
`user Mn—fl—u [Em
`
`_:
`WW mm] IE3
`1W
`_- @193
`{MWWW
`Iii graphical Wt tumISEW
`EMILEposition':II m Elm-Emma] MEI
`
`III
`E- :-_
`mm ppm EW-#
`IiLE_mfia31I oi IiLEmflflizapaSSW/ord
`33am- “mzmfl approach for ca-—
`mm “memorability” (fl;thical
`generated
`ofD
`m pg-Irogrmsimple grid- oased alnguage,
`Wt ate—II‘IE§ may]: subset pfl
`
`graphica _asswords_s@mo—IIEEI—_
`plexity) W amfil~
`MEI! he dictionaries www— Em
`WWW W“
`
`fimmodeling the memorabihty of DAS pass-
`
`IE1[WEE MW- exploring
`EmaWW-|L'I!qzamfl] Wuheirm
`moreWWW Email! Infl-
`ela- flI8E_ pfl
`mm. InWin-m IiiImam
`WM lemon?.mm mm -
`
`W- in#-mM InNE W:m0%-_a_rangement
`II I composed
`Iii IEEW [Em [1193:]
`[Elm m-_EEIEEIW Iii I'WT“
`mm WWII] WWdIIWingsca-EE
`u erived using meta—leve
`[git ese orim—
`We how to am
`II-Ir-a
`
`”loasswor =for1_utmmj}q3 @fi
`primitives))constitutes allarger BMWtpfi
`textualbasedm{Enaand1mm“
`WWEWEIEIEEIE
`
`[fl Ac now edgement
`
`WI Wflma— W-
`arp—WI MW-_EE
`WW mmARPA) mamma—
`Rom-HOW: "1935513
`Imam—m
`MWWWW‘W gem!
`mm ---II -E'Jflflmmmm
`WWW” II: Em-
`
`
`WWI—
`
`Mfllfimflmn IDEMIIIIEWEI
`mmt
`fipassword WWI ogin
`to EECIIEKI Emmy hat EMILE mthe
`-mieifiii based IWMW
`the server amm-WWI—-
`however-WEBB
`vulnerable Iigeavesdropping7 mil onsequently m
`attEIdE WWW—I11 the ca-ture
`and
`of 51]]m_ mm
`cation
`Efl- setting, [0]] “W
`r13 MME W Enthe one—time oEIasswor
`:flifiqfl-Ompassword M iii Wm
`
`are aware offerImbenefit
`traditiona Wilm-
`
`SWO
`
`12
`
`
`
`m and conclusions contained
`mt
`Mar W and should not W:-
`IE necessarily representing the official W
`_.@IIIEE
`WEE IIARPA7
`WW
`
`References
`
`llll “Elm-Emmi?! crack passwords W passi-
`m—m Proceedings of the I”d USENIX e—
`WWW I9 -
`
`III M Bishop. —management- [tu_ sfl
`COMPCON m— I7w169fl-
`
`III I- Iishop. Improving W Wproactive
`password checking. 0W and Security, 148%:-
`249M Isa-
`
`J a-I-I.W—United States W
`nuisan-
`
`II fl-El-H-B-mmm
`MW Wim-—WWI
`Isms]-
`m Inn-mufl-E-Elifl-EE-
`Wand recognition of words and pictures by adults .
`"
`MI
`Elm:- Bulletin W WIW Society, EME-
`
`
`
`II] fl-Mandler- Your Em MEWI fl LEI!
`rm MIWEEWW
`IIIIJIE. Ell-
`III flum- *Wmm ERIE
`Em Ema [EDIE may: processing infor-
`Psychological WEIEEW IE-
`
`Ewm Password security: E-
`| istory.
`Dim -II1):'594- II
`Novemoer Efl-
`
`251 “m— IW Password checker Emma.
`p from m-
`III EEWW milks signature
`W IEEE, —I15—2 EIFebruary 19E-
`El WWafling- mm
`uperiority effect. IWHfErperimental Psychology:
`Human Learnin and Memory, II-Iz485—49I77.
`
`El um , mun—mm
`mm In...
`
`EH] Wlmagery in recall and recognition. WW
`l-I-I-hfl'wuey, WW“).-
`II Emu-Mfl-mythe
`Wm recallW Psychonomic Science,
`HIE-IE1-
`
`IrII fl-Raleigh and R.
`password WProceedings W W
`Security MW— WAugust, IE-
`III E. m. hepard. Recognition memory fig] m
`m nd pictures. Jam Verbal W W
`“Behavior. anWI.
`
`Efal ISpafford. Preventing weak password c oices. W:
`ceedings W 4th
`ational COWMI-
`m—M_ nan.
`EEI ISpafford-
`In Proceedings WIW SENIX Security Sympoflmml
`September 1992_
`
`IStanding. Learning 0mm W“ Ouarterly Jour—
`mdlo Experimental PsychoWY—‘2273
`-Solomon and Seymour Papert.
`.
`o a young child doing Turt e Graphics in LOGO.
`Wm 5'75,
`1y 19761-
`
`I_ El- I'i'EIE- “WEI Emits: mil-2i! mil
`Iictorial timid!- mm
`mm
`24242725'. ll-
`WWW 0 organization Emperceptual
`forms.
`IGe‘stalt psychology (pp. 71!8E§I.
`| ondon: Routledge IKegan Pau . 193E}-
`
`IIII Wreal-world analysis still——
`I ity. In Proceedinls of the 1500 Syn-pomWW
`and Distributed System W1999
`
`*WmmW-m
`
`IIII Emu-III man-survey of, .fifldimrove—
`m ”password security. in; of the lam
`SIecurity ershop, W W90
`IIII Emilia
`signature was}
`mmn
`di- W_Imematsonal
`Imma E-WTWWW
`msgmsm.m 19-
`IIII 3W mill—m In
`Wsignature
`Eu Imputer W
`Ward Handwritinl,
`Im World Scientific,
`lat-
`
`“um- W mmmm
`W euesley Co legs Inn—WW
`WWI-flfl2fiw-
`
`M W. A. Thomas. Elements ofInformatio-
`WWWIMEE-
`El El-_ muflm-W:
`Ten years WEE— my ryptomCRl/PTO
`mm W% Elam
`
`“was-
`II “Sparrow. Win—W
`WHAssociates, Ema-m-
`IIII III-mm key(tm)WIEE
`f the 1' WW @IWW
`Distributed System W- ”Hm
`
`emory, mil
`I|Il EIW memory. In Imagezy,
`W— EWIW I r'lbaum Associates,
`III?-
`
`II WWW-WWW
`WWWW
`IWEQWJW-
`
`IWEWBW
`Wail-3
`
`Em ”Emmy!“ MI “in
`
`13
`
`
`
`W
`IIIe
`WWW
`—©§_— Rum]!
`
`LlComrnon—code m m @fl my}:
`WWW W mm
`mm:
`med]
`I—Imflmwflm
`[Eta
`mam—ME
`before accessing semantic information,
`Em
`Emil-Eh
`WIW Common-code
`
`[1mm Emud‘ "W WEE:
`
`I
`t e enco mg
`Em“
`Wm MIMIC
`mm MIMI!
`Ifixmsmflm era! @21
`WW-
`Emma] Iii
`
`W-
`. ietionary
`Wof WEE mmmamm
`Mafl— my.
`
`'73 g3?
`
`Ezra]
`
`IW ords Emil
`—Emflnammmafllfifi
`IE9:WW
`mIt MW Iengage
`
`mu tip e representations @fl— ith
`mm: knowledge about mm
`ging E]_elaborate IW—s
`with IE! lllj-
`
`gamma—I‘m Emma in
`
`rejects m
`the-diialfide ap_proach, t is theor
`m Eli
`mm between
`WMIW eta—am.
`I—Mfilofim
`IIWEEWWWEE
`Wm MW;WI-
`
`tW Emma]! will!flpostuatesWmayHMWWW
`
`
`encoding effects Wsuggested [mm
`code theorists- Propositional heoristg W
`W m? fistmctive and interpretive pro-
`Eill
`the em anation Em
`WWW HIE!- Iflm bfl
`MEI mflfiiWIfl I
`W15I
`he drawings En-
`Imm Hamlin: t e same
`drawingS.
`En Immfl will] Mi
`m oetter fl_ interpretation
`magi]
`interpretive process
`”WWII-
`
`IIstrongest Im Em [bitI935
`Wait-111m-be mdnal-Code the-
`ory(see Ilia.- nderstanding {ofl_
`nd them SIEz-mflxaaflmmfl
`IBMWW Is
`ongoing challenge I.”
`provides Margumentg Ram @fit
`
`bility @fi drawingsorm Efllecognition m
`.nd | ence its applicability mmm.
`
`E] WI—
`
`WI W in Elana I em 2a m
`m— long WEE-1W programs
`Imdfiamfll using iii-l— outlined
`
`EflWfin-fl] flifiltheir#-
`
`mum mafia—I
`pproach,
`t eory I'
`[b3]-
`guage and know edge ofW
`in functiona ly W WEI] EEG]
`memory systems Imfifl was:
`dealing WW
`MEET—”MW
`Wan-TIm W Iii Etta]
`Wait-1mm“:
`“mm—WW3
`WWWI'WEI
`th0 they
`e recognize a melody7
`Wto remembertIs
`rWiEenI WEE-l
`IIITEflnfiir-ldi Emma.
`Email-H Elmmmfimm}
`Immdmlm
`mm: bfl
`@5331]th—
`Lii [WWI We at! Km 5!! EH! *
`WWW. Iii:-
`Emmm llilr-
`
`14
`
`
`
`
`
`pendown
`repeat4
`flgm
`end
`repeat4
`down
`end
`repeat4
`mfl
`end
`repeat4
`UP
`and
`penup
`
`22
`pendown
`repeat2
`figm
`down
`lefl
`end
`penup
`figm
`figm
`down
`pendown
`lefl
`lefl
`penup
`repeat4
`UP
`
`11
`pendown
`penup
`repeat4
`figm
`end
`pendown
`penup
`down
`repeat3
`lefl
`end
`pendown
`penup
`figm
`figm
`pendown
`
`end
`ngm
`ngm
`pendown
`Iefl
`Iefl
`penup
`
`repeat 2
`penup
`down
`Iefl
`pendown
`end
`penup
`ngm
`ngm
`pendown
`penup
`down
`repeatS
`Iefl
`end
`pendown
`penup
`
`W —cost _
`
`Elana- -drawings ”Em Ell mm] WW1] EM fina
`
`11
`repeat2
`pendown
`down
`figm
`UP
`penup
`len
`repeat3
`down
`end
`pendown
`down
`figm
`UP
`penup
`
`11
`pendown
`repeat 4
`ngm
`end
`down
`Iefl
`UP
`Iefl
`Iefl
`down
`Iefl
`UP
`penup
`repeat 3
`down
`
`repeatS
`UP
`end
`Hgm
`end
`pendown
`repeat4
`down
`end
`penup
`
`and
`repeat 4
`Hgm
`end
`pendown
`down
`repeat 4
`lefl
`end
`UP
`figm
`down
`lefl
`lefl
`UP
`figm
`
`penup
`UP
`repeat4
`Iefl
`and
`repeat 3
`Iefl
`pendown
`penup
`end
`
`15
`
`