SpringerBriefs in Computer Science SeriesEditors StanZdonik ShashiShekhar JonathanKatz XindongWu LakhmiC.Jain DavidPadua Xuemin(Sherman)Shen BorkoFurht V.S.Subrahmanian MartialHebert KatsushiIkeuchi BrunoSiciliano SushilJajodia NewtonLee Forfurthervolumes: http://www.springer.com/series/10028 Benjamin S. Riggan • Wesley E. Snyder Cliff Wang Fundamentals of Sketch-Based Passwords A General Framework 2123 BenjaminS.Riggan CliffWang DepartmentofElectricalandComputerEngineering USArmyResearchOffice NorthCarolinaStateUniversity Durham,NorthCarolina Raleigh,NorthCarolina USA USA WesleyE.Snyder DepartmentofElectricalandComputerEngineering NorthCarolinaStateUniversity Raleigh,NorthCarolina USA ISSN2191-5768 ISSN2191-5776(electronic) SpringerBriefsinComputerScience ISBN978-3-319-13628-8 ISBN978-3-319-13629-5(eBook) DOI10.1007/978-3-319-13629-5 LibraryofCongressControlNumber:2014957406 SpringerHeidelbergNewYorkDordrechtLondon © TheAuthor(s)2014 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartofthe materialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsorthe editorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinorforanyerrors oromissionsthatmayhavebeenmade. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Thisbookisdedicatedtomybelovedwife, Alyssa,whohasalwayssupportedmein allmyendeavors. Preface Thepurposeofthisbookistointroducethefundamentalproceduresnecessaryfor implementinga“sketch-basedauthenticationsystem.”Thenotionofusingadrawing orsketchoriginallycamefromXiaogangWang,whothoughtrandomalphanumeric strings were too complicated to remember. This idea combined with biometric in- formation(e.g.pressure,velocity,oracceleration)posedaninteresting,yetdifficult problemtosolve. Thisbookisintendedforresearchersinterestedinpatternrecognitionapplications similartotheapplicationofsketch-basedpasswords,suchassignaturerecognition methods, graphical passwords, biometrics, or human-computer interaction tech- niques. First, concepts utilized by other alternatives to traditional passwords are introducedandanalyzed,Then,twodifferentpatternrecognitiontechniquesthatmay beusedforrecognizingsketch-basedpasswords(includinganyassociatedbiometric information) are discussed in detail. Lastly, fundamental theory and experiments relatedtothesecurityandusabilityofsketch-basedpasswordsareprovided. Thanks toWesley E. Synder and XiaogangWang for their contributions to this work,withoutwhomthiswouldnothavebeenpossible. Raleigh,NC BenjaminRiggan October2014 vii Acknowledgements TheinformationpresentedinthisbookisbasedonworkfundedbytheUnitedStates ArmyResearchOffice(ARO)grantW911NF-04-D-0003-0019. ix Contents 1 Introduction................................................... 1 1.1 Sketch-BasedPasswords..................................... 2 1.2 Contributions .............................................. 3 1.3 PrimaryResults ............................................ 3 1.4 Organization............................................... 4 References ..................................................... 4 2 Background ................................................... 5 2.1 Terminology............................................... 5 2.2 GraphicalPasswords........................................ 7 2.3 BiometricSystems ......................................... 9 2.4 KeyPoints ................................................ 14 References ..................................................... 14 3 Sketch-BasedAuthentication .................................... 17 3.1 DynamicTimeWarping ..................................... 17 3.2 SimpleK-Space............................................ 20 3.3 KeyPoints ................................................ 29 Appendix1 .................................................... 29 Appendix2 .................................................... 31 References ..................................................... 33 4 Efficiency,Uniqueness,andRobustness........................... 35 4.1 Efficiency ................................................. 35 4.2 Uniqueness................................................ 39 4.3 Robustness ................................................ 40 4.4 KeyPoints ................................................ 41 5 Human-ComputerInteraction................................... 43 5.1 Features .................................................. 44 5.2 BioSketchDatabase ........................................ 45 5.3 SimilarityMeasures ........................................ 46 xi xii Contents 5.4 VariabilityAnalysis......................................... 48 5.5 KeyPoints ................................................ 50 References ..................................................... 50 6 ExperimentsandResults........................................ 51 6.1 UniquenessandRobustnessExperiments....................... 52 6.2 PerformanceAnalysis ....................................... 54 6.3 KeyPoints ................................................ 61 References ..................................................... 61 7 Conclusions ................................................... 63 7.1 FutureWork ............................................... 64 AppendixAOptimization .......................................... 65 AppendixBSubspaceApproximations............................... 69 Chapter 1 Introduction Abstract Keeping data, which is stored on a variety of information systems, e.g. networks,desktopandlaptopcomputers,personaldigitalassistants(PDAs),smart- phones, tablets, or any other electronic media, private is essential for individual security,corporatesecurity,andnationalsecurity.Whileamajorityofauthentication mechanismsremainthesameastheyweremorethanadecadeago, attacksonin- formationsysteminfrastructuresarebecomingmoresophisticated.Many,including financialinstitution, governmentagencies, andlargeorganization, havealwaysin- vestedbothtimeandmoneyintoimprovedsecuritysolutions.Oneemergingtopic, namelysketch-basedpasswords,isthesubjectofthisbrief.Inthischapter,theneed foralternativesecuritysolutionsisgreatlyemphasized,andthefundamentalconcept ofusingsketch-basedpasswords(onepossiblesolution)isintroduced.Additionally, themajorcontributionsandresultspresentedinthisbriefaresummarized. Keywords Privacy·Security·Sketch-basedpasswords·Authentication Theprivacyofcriticalinformation,suchascreditcardnumbers,socialsecuritynum- bers, usernames/passwords, andetc., isahugeproblemforindividuals, businesses (smallandlarge),andgovernments.Theworldhasbecomemoreconnected,comput- ershavebecomefaster,andhackersmoresophisticated,yetthemajorityofsystems stillrelyontraditionalpasswordsandencryptionmechanismstoprovidesecurityof suchinformation. Passwords are not the only way to protect private information. Authentication systemsarebasedononeormoreofthefollowingqueries:whatauserscarries(e.g. identification cards), what a user knows (e.g. passwords or personal identification numbers), or who a users is (e.g. fingerprint or facial recognition).Authentication systemsbasedoneachqueryhaverespectivestrengthsandweaknesses.Identification (ID) cards and electronic keys provide a simple and easy to use security solution which are effortless to maintain (i.e. revoke, alter, and issue), but they are also relativelyeasyforunauthorizedpersonneltostealandduplicate.Passwordsarealso fairlyeffortlesstomaintain,butifpasswordsdonotadheretocertainrequirements: (cid:129) be10–15characterslong (cid:129) containbothupperandlowercaseletters (cid:129) containnumbers(0–9) (cid:129) containspecialcharacters(e.g.!,,#,$,%,&.,(,or)) (cid:129) notcontaindictionarywords ©TheAuthor(s)2014 1 B.S.Rigganetal.,FundamentalsofSketch-BasedPasswords, SpringerBriefsinComputerScience,DOI10.1007/978-3-319-13629-5_1