Password Hardening Based on Keystroke Dynamics
`
`Fabian Monrose
`
`Michael K. Reiter
`
`Susanne Wetzel
`
`Bell Labs, Lucent Technologies
`Murray Hill, NJ, USA
`{fabian,reiter,sgwetzel}©research.bell-labs.corn
`
`Abstract
`
`We present a novel approach to improvmg the security of
`passwords
`In our approach, the legitimate user's typmg
`patterns ( e.g , durations of keystrokes, and latencies between
`keystrokes) are combmed with the user's password to gen(cid:173)
`erate a hardened password that is convincingly more secure
`than conventional passwords against both onhne and offimc
`attackers. In add1t1on, out scheme automatically adapts to
`gradual changes in a user's typmg patterns while rnaintam(cid:173)
`ing the same hardened password across multiple logms, for
`use m file encryption or other applications requiring a long(cid:173)
`term secret key Usmg empirical data and a prototype im(cid:173)
`plementation of our scheme, we grve evidence that our ap(cid:173)
`proach is viable 111 practice, m terms of ease of use, improved
`secunty, and performance
`
`1
`
`Introduction
`
`Textual passwords have been the primary means of authcn(cid:173)
`ticatmg users to computers smce the mtrodm::tfon of access
`controls m computer systems Passwords remain the domi(cid:173)
`nant user authentication technology today, despite the fact
`that they have been shown to be a fairly weak mechanism
`for authenticatmg users Studies have shown that users tend
`to choose passwords that can be broken by an exhaustive
`search of a relatively small subset of all possible passwords.
`In one case study of 14,000 Umx passwords, almost. 25%
`of the passwords were found by searchmg for words from a
`carefully formed "dict10nary'' of only 3 x 106 words [10] (see
`also (21, 4, 27, 29]) Th1s high success rate is not unusual
`despite the fact that there are roughly 2 x 1014 8-character
`passwords consisting of digits and upper and lower case let(cid:173)
`ters alone
`In thJS paper, we propose a technique for improving the
`security of password-based applications by mcorporatmg bio(cid:173)
`metric mformation into the password Spec,fica.lly, our tech(cid:173)
`nique generates a hardened passwm·d based on hoth the pass(cid:173)
`word characters and the user's typmg patterns when typing
`the password. This hardened password can be tested for
`logm purposes or used as a cryptographic key for file en(cid:173)
`cryptwn, virtual private network access, etc. An attacker
`wl10 nbtams a.II stored system mformation for password ver-
`1ficat10n (the analog of the /etc/passvd file 111 a typical Unix
`environment) is faced with a convincmgly more drllicult task
`
`Permission to make d1gn:al or hard copies of ,all or part of this work for
`personal or classroom use rs granted without fee provided that
`copies are not made or d1.stnbuted for profit or commercial advpnt
`-age and that copies bear this notice and the full c1tat1on on the hrst page
`To copy otherwise, 10 rnpubhsh, to post oo servers or to
`redistribute to bsts, requires pnor spec1f1e perm1Ht0n and/or a tee
`CCS '99 11 /99 Srngapore
`l;l 1999 ACM 1-58113-148•8/99/0010 $5 00
`
`to exhaustively search for the hardened password than in a
`traditional password scheme Moreover, an attacker who
`learns the user's textual password (e g., by ohservi11g it be(cid:173)
`mg typed) must type it like the legitimate user to log mto
`an account protected by our scheme
`There are several challenges to realizing this goal. The
`first is to identify features of a user's typmg patterns (e.g,
`latencies between keystrokes, or duration of keystrokes) that
`the user reliably repeats (approx1mat.ely) when typmg her
`password The second is to use these features when the
`user types her password to generate the correct hardened
`password At the same time, however, the attacker who cap(cid:173)
`tures system rnformat1on used to generate or venfy hardened
`passwords should be unable to determine wh\ch features are
`relevant to generating a user's hardened password, since re(cid:173)
`vealmg this mformation could reveal mformation about the
`characters related to that password feature. For example,
`suppose the attacker learns that the latency between the
`first and second keystrokes 1s a feature that is reliably re(cid:173)
`peated by the user and thus is used to generate her hardened
`password Then this may reveal infonnat10n about the first
`and second characters of the text pass"'urd, smce due to
`keyboard dynanucs, some digraphs are more amenable to
`reliable latency repetitions than others.
`Our approach effectively hides information about which
`of a user's features are relevant to generating her hardened
`password, even from an attacker that ca1itures all system
`information. At the same time, 1t employs novel techniques
`to impose an additional (multiplicative) work factor on the
`attacker who attempts to exhaustively search the password
`space. Using empirical data, we evaluate both this work
`factor and the reliability with which legitimate users can
`generate their hardened passwords Our empirical studies
`demonstrate various chokes of parameters that yield both
`increased security and sufficient ease of use
`Our scheme 1s very attractive for use in practice. Unhke
`other b,ometnc aut,hentication procedures (e.g., fingerprint
`recognition, retma or irJS scans}, our approach is unmtru(cid:173)
`sive and works with off-the-shelf keyboards. Our scheme
`mitially is as secure as a "normal" password scheme and
`then adapts to the user's typmg patterns over time, grad(cid:173)
`ually hardening the password with biornetr,c mforurntiun
`Moreover, while fully able to adapt to gradual changes m
`user typmg patterns, our scheme can be used to generate
`the same hardened password indefimtely, despite changes in
`the user's typing patterns. Therefore, the hardened pass(cid:173)
`word can be used, e.g , to encrypt files, without needing to
`decrypt and re-encrypt files with a new hardened password
`on each logm.
`The main )imitation of our scheme is that a user whose
`typmg patterns change substantially between consecutive in(cid:173)
`stances of typing her pass'\\-Ord may be unable to generate
`
`73
`
`ASSA ABLOY Ex. 1015 - Page 1
`ASSA ABLOY AB v. CPC Patent Technologies Pty Ltd.
`IPR2022-01006 - U.S. Patent No. 9,665,705
`
`

`

`her cqrrect hardened password and thus, e g , might be un(cid:173)
`able to log in The most common c1rcumstance m which this
`could happen 1s if the user attempts to log III usmg a different
`style keyboard than her regular one, which can cause a dra(cid:173)
`matic change m the user's typing patterns. In hght of this,
`app1icat1011s for which our scheme 1s ideally smted are access
`to v1rtual private networks from laptop computers, and file
`or disk encrypt10n on laptop computers Laptops provide a
`smgle, persistently available keyboard at which the user can
`type her password, which 1s the ideal situat10n for repeated
`generat10n of her hardened password Moreover, with the
`nsmg rate of laptop thefts (cg, see [22]), these apphcat10ns
`demand secunty better than that provided by traditmnal
`passwords
`
`2 Related work
`
`The motivatwn for usmg keystroke features to harden pass(cid:173)
`words comes from years of research vahdatmg the hypoth(cid:173)
`esis that user keystroke features both are highly repeat(cid:173)
`able and different between users (e g, [6, 28, 14, 15, 1, 9,
`20, 24]). Pnor work has anticipated utilizing keystroke in(cid:173)
`formation m the user login process (e g, [9]), and indeed
`products 1mplementmg this are bemg marketed today (e g,
`see http:/ /wwv. biopassword. com/) All such pnor schemes
`work by stormg a model of user keystroke behav10r m the
`system, and then comparing user keystroke behavior during
`password entry to this model Thus, while they are useful to
`defend agamst an onhne attacker who attempts to log into
`the system directly, they provide no additional protection
`against an offime attacker who captures system information
`related to user authentication and then conducts an offime
`d1ct10nary attack to find the password (e.g, to then decrypt
`files encrypted under the password). On the contrary, the
`captured model of the legitimate user's keystroke behav10r
`can leak mformat10n about the password to such an attacker,
`as discussed in Section 1 Thns, our work improves on these
`schemes m two ways. First, our method is the first to offer
`stronger secunty against both onlme and offime attackers.
`Second, our scheme is the first to generate a repeatable se(cid:173)
`cret based on the password and keystroke dynamics that 1s
`stronger than the password itself and that can be used in
`apphcatmns other than login, such a.s file encryptmn
`The only work of which we are aware that previously
`proposed generatmg a repeatable key based on biometric
`In this scheme, a user carries a portable
`mformat1on 1s (3]
`storage device containing ( 1) error correct mg parameters to
`decode readmgs of the bmmetnc (e.g , an ms scan) with a
`limited number of errors to a "canomcal" readmg for that
`user, and (ii) a one-way hash of that canonical readmg for
`vcrificat10n purposes Moreover, they further proposed a
`scheme in which the canomcal b10metnc readmg for that
`user 1s hashed together with a password Their techmques,
`however, are inappropriate for our goals because the stored
`error correcting parameters, if captured, reveal information
`about the canonical form of the biometnc for the user. For
`this rea.son, their approach requires a biometnc with sub(cid:173)
`stantial entropy. e g , they considered iris scans offering an
`estimated 173 bits of entropy, so that the remaming entropy
`after exposure of the error correcting parameters ( they esti(cid:173)
`mated 147 bits of remaming entropy) was still sufficiently
`In our case, the measurable
`large for their application.
`keystroke features for an 8-character password·are relatively
`few (at most 15 on standard keyboards), and indeed in our
`scheme, the password's entropy will generally dominate the
`entropy available from keystroke features. Thus, exposing
`
`error-correcting param.eters 111 our setting would substan(cid:173)
`tially dimmish the available entropy from keystroke features,
`almost to the pomt of negatmg then utility Moreover, ex(cid:173)
`posing information about the keystroke features can, in turn,
`expose mformation about the password itself (as discussed
`in Sect10n I) This makes the careful ut1hzat10n of keystroke
`features critical m our settmg, whereas in their settmg, the
`b10metncs they considered were presumed mdependent of
`the password chosen.
`Our method to harden user passwords has conceptual
`similarities to password "saltmg" for user logm Salting 1s
`a method m which the user's password is prepended with a
`random number (the "salt") of s bits 111 length before hash(cid:173)
`ing the password and comparmg the result to a prev10usly
`stored value [21, 16] As a result, the search space of an
`attacker is mcreased by a factor of 2' 1f the attacker does
`not have access to the salts. However, the correct salt either
`must be stored m the system or found by exhaustive search
`at logm time
`Intmtively, the scheme that we propose in
`this paper can be used to improve this approach, by deter(cid:173)
`mming some or all of the salt bits using the user's typmg
`In addition, an advantage of our approach over
`features.
`saltmg is that our scheme can be effective agamst an onlme
`attacker who learns the leg1t1mate user's pa.ssword ( e.g , by
`observing the user type it) and who then attempts to log in
`as that user.
`Finally, we note that several other research efforts on
`password security have focused on detecting the unautho(cid:173)
`rized modification of system information related to password
`authentication ( e g , the attacker adds a new account with
`a password 1t knows, or changes the password of an exist(cid:173)
`mg account) (13, 12, 8] Here we do not focus on this threat
`model, though our hardened passwords can be directly com(cid:173)
`bined with these techniques to provide secunty agamst this
`attacker, as well
`
`3 Preliminaries
`
`The hardened passwords generated m our scheme have many
`potential uses, including user logm, file encryption, and au(cid:173)
`thentication to virtual pnvate networks However, for con(cid:173)
`creteness of exposit10n, m the rest of this paper we focus on
`the generation and use of hardened passwords for the pur(cid:173)
`poses of user login Extending our discussion to these other
`applications is straightforward.
`We assume a computer system with a set A of user ac(cid:173)
`counts Access to each user account is regulated by a login
`program that challenges the user for an account name and
`password. Using the user's. mput and some stored informa(cid:173)
`tion for the account a that the user 1s trying to access, the
`logm program e,ther accepts or re1ects the attempt to log
`into a. Like m computer systems today, the· characters that
`the user types mto the password field are a factor in the
`determination to accept or reJect the logm. For the rest of
`this paper, we denote by pwd. the correct strmg of char(cid:173)
`acters for the password field when logging mto account a.
`That is, pwd. denotes the correct text pa.~sword as typically
`used m computer systems today.
`In our architecture, typmg pwd. is necessary but not
`sufficient to access a. Rather, the logm program combines
`the characters typed in the password field with keystroke
`features to form a hardened password that is tested to de(cid:173)
`termine whether login is successful. The correct hardened
`password for account a is denoted hpwd". The login pro(cid:173)
`gram will fail to generate hpwd" 1f either somethmg other
`than pwda is entered m the password field or if the user's
`
`74
`
`ASSA ABLOY Ex. 1015 - Page 2
`ASSA ABLOY AB v. CPC Patent Technologies Pty Ltd.
`IPR2022-01006 - U.S. Patent No. 9,665,705
`
`

`

`typmg patterns sigmficantly differ from the typmg patterns
`displayed m previous successful logins to the account Here
`we present our scheme m a way that mamtams hpwda con(cid:173)
`stant across log1ns 1 even despite gradual shifts 1n the uscr 1s
`typmg patterns, so that hpwd" can also be used for longer(cid:173)
`term purposes (e g, file encrypt10n) However, our scheme
`can be easily tuned to change hpwda after each successful
`logm, 1£ dcsued
`
`3.1 Features
`In order to generate hpwd" from pwd" and the (leg1t1mate)
`user's typmg patterns, the logm program measures a set
`of features whenever a user types a password Empmcally
`we w,II examme the use of keystroke durat10n and latency
`between keystrokes as features of interest, but other fea(cid:173)
`tures (e g, force of keystrokes) could be used if they can be
`measured by the logm program. Abstractly, we represent
`a feature by a funct10n ,j, A x N -+ nt+ where ,j,(a,£) 1s
`the measurement of that feature durmg the t-th (successful
`or unsuccessful) logm attempt to account a For example,
`if the feature ,j, denotes the latency between the first and
`second keystrokes, then ,j,(a, 6) is that latency on the sixth
`attempt to log mto a Let m denote the number of features
`.. , <Pm denote
`that are measured durmg logms, and let c/>1,
`the1r respective funct10ns.
`Central to our scheme is the not10n of a distinguishing
`feature. For each feature cf,,, let t, E nt+ be a fixed parameter
`of the system Also, let µ 0 , and a 0 , be the mean and stan(cid:173)
`,cp,(a,1h)
`dard deviat10n of the measurements cf,,(a,ji),
`. ,Jh are the last h successful logins to the ac(cid:173)
`where Jt,
`count a and h E N is a fixed parameter of the system We
`say that cf,, 1s a distmguishmg feature for the account (af(cid:173)
`ter these last h successful logins) if \µa, - t,\ > k<Ta, where
`k E nt+ is a parameter of the system. If cf,, 1s a distinguish(cid:173)
`ing feature for the account a, then either t, > µa, + kaa,,
`i e., the user consistently measures below t, on this feature,
`or t 1 < µa 1 - ka01 , 1.e , the user consistently measures above
`t, on th1s feature
`
`3.2 Security goals
`In our login architecture, the system stores informat10n per
`account that 1s accessed by the logm program to venfy at(cid:173)
`tempts to log m. This mformat1on 1s necessarily based on
`, but w11l not include either of these values
`pwda and hpwd 0
`themselves This is snnilar to Umx systems, for example,
`where the /etc/passwd file contains the salt for that pass(cid:173)
`word and the result of encrypting a fixed strmg with a key
`In our logm archi(cid:173)
`generated from the password and salt
`tecture, the 1ufonnat10n stored per account will be more
`extensive but will still be relatively small
`The pnmary attacker with which we are concerned is an
`"offiine" attacker who captures this mformation stored in
`the system, and then uses this 1nfonnat10n 1n an offiine effort
`to find hpwd. (and pwd.) A first and basic requirement is
`that any such attack be at least as difficult as exhaustively
`searchmg for pwda m a traditional Unix setting where the
`attacker has /etc/passwd. In particular, 1f the user chooses
`pwda to be difficult for an attacker to find using a dictionary
`attack, then hpwda will be at least as secure m our scheme
`A more ambit10us goal of our scheme 1s to mcrease the
`work that the attacker must undertake by a considerable
`amount even if pwd" 1s chosen poorly, i.e , in a way that
`is susceptible to a dictionary attack. The amount of add1-
`t10nal work that the attacker must undertake m our scheme
`generally grows with the number of distmguishmg features
`
`75
`
`for the account (when the attacker captured the system m(cid:173)
`formation) On one extreme, 1f there are no d1stmgmshmg
`features for the account, then the attacker can find pwd.
`and hpwd m roughly the same amount of time as the at(cid:173)
`tacker wo~ld take to find pwda in a traditional Umx settmg.
`On the other extreme, 1£ all m features are distingmshing
`for the account, then the attacker's task can be slowed by a
`mult1phcat1ve factor up to 2m. In Section 7, we describe an
`empmcal analysis that sheds light on what this slowdown
`factor 1s likely to be in practice. In addit10n, we show how
`our scheme can be combined with saltmg teclnnques, and
`so the slowdown factor that our scheme achieves 1s over and
`above any benefits that salting offers.
`A second attacker that we defend agamst with our scheme
`is an "online" attacker who learns pwda (e g., by observmg
`1t being typed in) and then attempts to log in using 1t Our
`scheme makes this no easier and typically harder for this
`attacker to succeed in logging m.
`
`4 Overview
`
`In this section we give an overview of our techmque for
`generatmg hpwda from pwda and user keystroke features
`When the account a 1s initialized, the mitiahzat10n pro(cid:173)
`gram chooses the value of hpwda at random from Zq, where
`q is a fixed, sufficiently large pnme number, e.g, a q of
`length 160 bits should suffice The initializat10n program
`then creates 2m shares {s~,s!}1:Si:Sm of hpwda using a se(cid:173)
`cret sharmg scheme such that for any b E {O, 1} m, the shares
`{s:<•lh:;;,:;;m can be used to reconstruct hpwda
`(Here, ?.(i)
`is the 1-th bit of b.) These shares are arranged m an m(cid:173)
`struct10n table".
`
`< t,
`
`'2:. t,
`
`s'f.
`sg
`
`81
`s~
`
`1
`2
`
`m
`
`SI m
`
`s::.
`The initialization program encrypts each element of both
`columns {i.e , the "< t," and "2: t," columns) with pwda
`This ( encrypted) table is stored in the system. In the £-th
`login attempt to a, the login program uses the entered pass(cid:173)
`word text pwd' to decrypt the elements of the table, winch
`will result in the previously stored values only if pwd. =
`pwd'. For each feature </,,, the value of ¢,(a, e) indicates
`which of the two values in the i-th row should be used in
`the reconstruct10n to find hpwda: if ,j,,(a, £) < t,, then the
`value in the first column is used, and otherw,se the value in
`the second column 1s used. In the first logms after initial(cid:173)
`ization, the value m either the first or second column works
`equally well However, as distmgmshing features cf,, for this
`account develop over time, the login program perturbs the
`value in the second column of row i 1f /la, < t, and perturbs
`the value m the first column of row i otherwise. So, the
`reconstruction to find hpwda m the future will succeed only
`when future measurements of features are consistent with
`the user's prev10us dJStinguished features.
`In this way, our scheme helps defend agamst an onlme at(cid:173)
`tacker who learns (or tnes to guess) pwda and then attempts
`to log mto a using 1t. Unless this attacker can mimic the
`legitimate user's keystroke behavior for the account's distm(cid:173)
`guishmg features, the attacker will fat! m logging into the
`account Moreover, numerous prior studies have shown that
`
`ASSA ABLOY Ex. 1015 - Page 3
`ASSA ABLOY AB v. CPC Patent Technologies Pty Ltd.
`IPR2022-01006 - U.S. Patent No. 9,665,705
`
`

`

`keystroke dynamics tend to differ sigrnficantly from user to
`user ( see Sect10n 2), and so typically the onhne attacker will
`fail m his attempts to log mto a Thus, the secunty analysis
`in the rest of this paper will focus on the offime attacker
`Not any secret sharing scheme satisfymg the properties
`descnbed above will suffice for our technique, since to de(cid:173)
`fend against an offiine attacker, the shares must be of a form
`that does not easily reveal if a guessed password pwd' suc(cid:173)
`cessfully decrypts the table. In the followmg sections, we
`present mstances of our techrnque using two different shar(cid:173)
`mg schemes
`Our scheme can be easily combmed with saltmg to fur(cid:173)
`ther improve secunty A natural place to include a salt 1s 111
`the val1dat10n of hpwda just after reconstructmg 1t For ex(cid:173)
`ample, when hpwda 1s generated durmg a logm, 1t could be
`prepended with a salt before hashmg 1t and testmg agamst
`a prev10usly stored brush value The salt can be stored as
`1s typically done today, or may not be stored so that the
`In this case,
`system must exhaustively search for 1t [16]
`the extra salt results in an additional work factor that the
`offime attacker must overcome.
`
`5 An instance using polynomials
`
`In this sect10n, we descnbe an instance of the techmque of
`Section 4 using Shamlf's secret sharmg scheme (25] In this
`scheme, hpwd" is shared by choosmg a random polynomial
`la E Zq(x] of degree m - 1 such that la(O) = hpwd" The
`shares are pomts on this polynomial. \Ve present the method
`m two steps, by first describmg a simpler vanation and then
`extendmg 1t m Sect10n 5.4 to be more secure agamst an
`offime attack
`
`5.1 Stored data structures and initialization
`Let G be a pseudorandom funct10n family [23) such that
`element of zz. 1 In practice, a likely implementation of G
`for any key Kand any mput x, GK(x) is a pseudorandom
`would be GK(x) = F(K,x) where F 1s a one-way function,
`e.g., SHA-1 [26] There are two data structures stored m
`the system per account.
`
`• An instruction table that contains "instructions" regard(cid:173)
`mg how feature measurements are to be used to generate
`hpwda. More specifically, tins mstruction table contams an
`entry of the form <i,Oia,,/3a,> for each feature¢,,. Here,
`O:'ai = Y2i . Gpwda (2i) mod q
`/3a, = Y!, · Gpwd 0 (2i + 1) mod q
`and Y2,, y~, are elements of z; Imtially (1 e , when the
`user first chooses pwda), all 2m values {y2,, Y!,}i:,;,:,;m are
`chosen such that all the pomts {(2i, Y2,), (2i+l, y~,) }i:,;,:,;m
`lie on a single, random polynomial la E Zq[x] of degree
`m - 1 such that la (0) = hpwda
`• An encrypted, constant-size history file that contains the
`measurements for all features over the last h successful
`logms to a for some fixed parameter h. More specifi(cid:173)
`cally, if smce the last time pwd" was changed, the logm
`1That 1s, a polynom1ally-bounded adversary not knowmg K can~
`not distinguish between GK(x) and a randomly chosen element of Z~,
`even 1f he 1s first allowed to exam me GK ( i:) for many i: 1s of his chmce
`and is allowed to even pick x ( as long as 1t 1s different from every X
`he prevwusly asked about)
`
`. , Jt to a were successful, then this file con(cid:173)
`attempts J1,
`,Jt}
`tams </>,(a,J) for each 1 $ i $ m and J E {Jt-h+I,
`In addition, enough redundancy is added to this file so
`that when 1t 1s decrypted with the key under which ,t
`was previously encrypted, the fact that the file decrypted
`successfully can be recogmzed
`This file is initialized with all values set to 0, and then is
`encrypted with hpwd" usmg a symmetric cipher The size
`of this file should remain constant over time ( e g , must
`be padded out when necessary), so that its size yields no
`informat10n about how many successful logms there have
`been.
`
`5.2 Logging in
`The login program takes the followmg steps whenever the
`user attempts to log mto a Suppose that this is the £-th
`attempt to log mto a, and let pwd' denote the sequence of
`characters that the user typed. The logm program takes the
`followmg steps.
`
`1. For each¢,,, the logm program uses pwd' to "decrypt" Ola,
`if </>,(a,£) < t,, and uses pwd' to "decrypt" f3a, otherwise
`Specifically, 1t assigns
`
`The login program now holds m points {(x,, y,)}1:5,:,;m
`
`2 The logm program sets
`
`m
`
`hpwd' = LY• · A, mod q
`
`i=l
`
`where
`
`1s the standard Lagrange coefficient for mterpolat10n ( e.g ,
`It then decrypts the history file usmg
`see [19, p. 526])
`hpwd'. If this decrypt10n yield~ a properly-formed plain(cid:173)
`(If
`text history file, then the logm is deemed successful
`the logm were deemed unsuccessful, then the login proce(cid:173)
`dure would halt here.)
`
`3. The login program updates the data 111 the history file,
`computes the standard deviation aa, and mean µa, for
`each feature ¢,, over the last h successful logms to a, en(cid:173)
`crypts the new history file with hpwd' (i.e , hpwda), and
`overwrites the old history file with this new encrypted
`history file 2
`
`4 The login program generates a new random polynomial
`la E z.[x) of degree m - 1 such that la(O) = hpwd'
`t,I > kaa,,
`5 For each c:hstinguishmg feature</>,, i e., lµa, -
`the logm program chooses new random values y2., y~, E
`z; subject to the following constraints·
`µa, < t, ~ la(2i) = Y~, A la(2i + 1) 'f' Y!,
`µa, c'.'. t, ~ la(2i) 'f' Y~, A fa(2i + 1) = Y!,
`2 For maximum security, this and the previous step should be per(cid:173)
`formed without writing the plamtext history file to disk Rather, the
`login program should hold the plamtcxt history in volatile storage
`only
`
`76
`
`ASSA ABLOY Ex. 1015 - Page 4
`ASSA ABLOY AB v. CPC Patent Technologies Pty Ltd.
`IPR2022-01006 - U.S. Patent No. 9,665,705
`
`

`

`For all other features cf;, -1 e , those for which lµa, - t, I '.'::
`ka "" or all features 1f there have been fewer than h suc(cid:173)
`cessful logms to this account smce m1tiahzat1on (see Sec(cid:173)
`tion 3 1 )-the logm program sets y2, = la (2,) and y,;, =
`la(2, + 1)
`6 The logm program replaces the mstruct1on table with a
`new table with an entry of the form <z, a~n fi~i> for each
`feature qi,. Here,
`
`Y~i Gpwd' (2i) mod q
`a~l
`v!, Gpwd' (2, + 1) mod q
`fJ:,
`where yi,, y,;, are the new values generated m the prev10us
`step
`
`Step 4 above is particularly noteworthy for two reasons
`F1rst, due to th1s step, the polynomial fa 1s changed to a
`new random polynomial during each successful logm This
`ensures that an attacker v1ewmg the mstruction table at
`two d1fferent times w11l gam no informat10n about wh1ch
`features switched from distmguishmg to non-d1stmgmshmg
`and vice-versa during the mtenm logins. That 1s, each time
`the attacker views an instruction table for an account, either
`all values will be the same since the la.st time ( 1f there were
`no successful logms smce the attacker last saw the table)
`or all values will be different. Second, though generated
`randomly, la IS chosen so that la(0) = hpwda This ensures
`that hpwda remams constant across multiple logms
`Step 5 1s also noteworthy, since 1t shows that whether
`each feature 1s du~t1ngu1sh1ng 1s recornputed 1n each success~
`fol logm So, a feature that was previously d1stmgu1shmg
`can become undistmgmshmg and vice-versa This 1s the
`mechanism that enables our scheme to naturally adapt to
`gradual changes in the user's typing patterns over time
`
`5.3 Security
`Consider the "offhne" attacker who obtams account a's his(cid:173)
`tory file and 111struct10n table, and attempts to find the value
`of hpwd" Presummg that the encrypt10n of the history file
`using hpwda 1s secure, since the values y~ 1 , y! 1 are effectively
`encrypted under pwda, and smce pwda is presumably chosen
`from a much smaller space than hpwda, the easiest way to
`find hpwda 1s to first find pwda Thus, to argue the bene(cid:173)
`fits of this scheme, we have to show two tlnngs First, we
`have to show that findmg pwda is not made easier m our
`scheme than 1t 1s III a typical environment where access is
`determmed by testmg the hash of the password agamst a
`prev10usly stored hash value. Second, we have to show that
`the cost to the attacker of findmg hpwda is generally greater
`by a sigmficant mult1phcative factor
`That searching for pwda 1s not made easier in our scheme
`1s clear The attacker has available only the instrnction table
`and the encrypted history file. Since there 1s a row m the
`instrnct10n table for each feature ( not JUSt those that are
`d1stingmshing for a), and since the contents of each row
`are pseudorandon1 values, the rows reveal no n1fonnation
`about pwd" And, all other data available to the attacker 1s
`encrypted with hpwda
`The more mterestmg security consideration in this scheme
`is how much security it achieves over a traditwnal password
`scheme. Suppose that the attacker captured the history file
`and instruction table after f 2: h successful logms to a, and
`let d be the number of distmguishing features for tlus ac(cid:173)
`count in the l-th logm When guessmg a password pwd',
`the attacker can decrypt each field <>a, and (1a, usmg pwd'
`
`to yield pomts (2i, yg,) and (2i + 1, !),;,), respectively, for
`1 $ i $ m Note that !)2, = y~, and !),;, = y,;,, where y~,, y,;,
`are as generated in Step 5, if and (with overwhelmmg prob(cid:173)
`ab1hty) only 1f pwd' -= pwda, Therefore, there exists a bit
`strmg b E {0, l}m such that {(Zi + b(i),11!;'))},c",c"m mter(cid:173)
`polates to a polynomial j with j (0) = hpwda, 1f and only
`1f pwd' = pwd0
`• Consequently, one approach that the at(cid:173)
`tacker can take is to enumerate through all b E {0, l}m and,
`for each j thus computed, see if f(O) == hpwd" (1 e , 1f f (0)
`will decrypt the history file). This approach slows down the
`attacker's search for hpwda (and pwda) by a mult1phcat1ve
`In practice, the slowdown that the attacker
`factor of 2m
`suffers may be substantially less because user typmg pat(cid:173)
`terns are not random. In Sectmn 7, we use empirical data
`to quantify the degree of security achieved against this form
`of attack, and show that 1t 1s nevertheless substantial
`However, the attacker has potentially more powerful at(cid:173)
`tacks agamst tlus scheme using the 2m pomts {(2i, 11~,), (2,+
`l,j),;,)},<,<m, due to the following contrast On the one
`hand, 1Cpwd' #- pwda, then with overwhelmmg probab1hty,
`no m + 1 pomts will lie on a single degree m - 1 polynomial,
`i e , each subset of m points interpolates to a different poly(cid:173)
`nonual with a d1fferent y-intercept (not equal to hpwdal· On
`the other hand, 1f pwd' = pwda, then there are 2m - d :C: m
`pomts that all he on a polynomial f of degree m - 1 ( and
`f(0) = hpwda), 111 particular if d < m, then there are at
`least m + 1 points that all lie on some such I- Asymp(cid:173)
`totically (1.e, as m grows arbitrarily large), it is known
`that the second case can be distmgmshed from the first 111
`O(m2
`) time if d '.':: (2-v'2)m:::; .585m usmg error-correctmg
`techniques [7]. These techmques do not directly break our
`scheme, smce our analysis in Section 7 suggests that for
`many reasonable values of k, d will typically be too large
`relative to m for these techniques to succeed ( unless the at(cid:173)
`tacker captures the account mformation before the account
`1s used). Moreover, typically m will be too small in our sce(cid:173)
`nario for these techniques to offer benefit over the exhaustive
`approach above. However, because these techniques might
`be improved with apphcation-specific knowledge-e g , that
`111 the second case, at least one of (2,, j)i,) and (2i + 1, 11!,)
`hes on f-1t is prudent to look for schemes that confound
`the use of error-correcting techniques. This 1s the goal of
`Section 5 4
`
`5.4 A variation using exponentiation
`In this section we present a mmor var