(12) United States Patent
`Bohannon et al.
`
`USOO6901145B1
`(10) Patent No.:
`US 6,901,145 B1
`(45) Date of Patent:
`May 31, 2005
`
`2
`
`----
`
`OaCW C a
`
`- - -
`
`
`
`5,737,420 A 4/1998 Tomko ........................ 380/23
`57.
`A E SON, O.S.)
`5,790,668 A 8/1998 Tomko ........................ 380/25
`(Continued)
`FOREIGN PATENT DOCUMENTS
`WO960S673 A1
`2/1996
`............. HO4L/9/08
`OTHER PUBLICATIONS
`Mytec Technologies Inc., Mytec: Biometrics, downloaded
`from Internet website http://www.mytec.com/biometrics/ on
`Nov. 1, 1999.
`
`WO
`
`(Continued)
`Primary Examiner Thomas R. Peeso
`Assistant Examiner Syed A. Zia
`(74) Attorney, Agent, or Firm-Jeffrey Weinick; Donald P.
`Dinella
`ABSTRACT
`(57)
`A repeatable cryptographic key is generated based on vary
`ing parameters which represent physical measurements.
`-
`0
`Locations within a share table, which locations Store valid
`and invalid cryptographic shares, are identified as a function
`of received varying parameters. The share table is config
`
`ured Such that locations which C expected tO be identified
`
`(54) GENERATION OF REPEATABLE
`CRYPTOGRAPHC KEY BASED ON
`WARYING PARAMETERS
`(75) Inventors: Philip L. Bohannon, Piscataway, NJ
`(US); Bjorn Markus Jakobsson,
`Hoboken, NJ (US); Fabian Monrose,
`New York, NY (US); Michael
`Kendrick Reiter, Raritan, NJ (US);
`Susanne Gudrun Wetzel, New
`Providence, NJ (US)
`(73) Assignee: Lucent Technologies Inc., Murray Hill,
`NJ (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(*) Notice:
`
`(21) Appl. No.: 09/501,902
`
`(22) Filed:
`
`Feb. 10, 2000
`Related U.S. Application Data
`(60) Pisis application No. 60/128,413, filed on Apr. 8,
`, and provisional application No. 60/147,880, filed on
`Aug. 9, 1999.
`7
`(51) Int. Cl.' .................................................. H04L 9/00
`
`(52) U.S. C. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 380/44; 380/45; 380/47;
`
`380/277; 380/286; 713/165; 713/168; 713/171;
`713/202
`(58) Field of Search ............................. 380/44; 713/165
`(56)
`References Cited
`
`by legitimate acceSS attempts contain valid cryptographic
`shares, and locations which are not expected to be identified
`by legitimate acceSS attempts contain invalid cryptographic
`shares. The share table configuration may be modified based
`on prior history of legitimate access attempts. In various
`embodiments, the Stored shares may be encrypted or com
`pressed. A keystroke feature authentication embodiment
`U.S. PATENT DOCUMENTS
`uses the inventive techniques to implement an authentication
`4,805.222 A 2/1989 Young et al. .................. 382/2
`System which authenticates based on an entered password
`4,876,725 A 10/1989 Tomko .......................... 382/4
`and the manner in which (e.g. keystroke dynamics) the
`5,369,707 A * 11/1994 Follendore, III ............ 713/155
`keystroke is entered. Another embodiment uses the inven
`55:12 A : o
`t
`s al - - - - - -
`"s'
`2
`2
`Ipner et al. . . . . . . . . . . . . . . .
`5,557.686 A * 9/1996 Brown et al. ............... 382/115 S. S. R. DNAR information
`5,625,692 A * 4/1997 Herzberg et al. ........... 380/286
`9.
`5,680,460 A 10/1997 Tomko et al. ................ 380/23
`5,712,912 A
`1/1998 Tomko et al. .............. 713/186
`
`24 Claims, 3 Drawing Sheets
`
`p
`S
`
`y
`
`P (X 1)
`
`k
`
`20
`y
`
`p (X2)
`
`p(s)
`
`205
`
`)
`p(x4)
`
`X
`
`x2
`
`IPR2018-00067
`Unified EX1030 Page 1
`
`

`

`US 6,901,145 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`
`
`9/1998 Kara .......................... 380/277
`5,802,175. A
`5,832,091 A 11/1998 Tomko et al. ................ 380/30
`5.991,408 A * 11/1999 Pearson et al. .
`... 713/186
`6,035,042 A * 3/2000 Mittenthal ......
`380/37
`6,317,834 B1
`11/2001 Gennaro et al. ............ 713/186
`OTHER PUBLICATIONS
`Mytec Technologies Inc., Mytec: Products-Mytec Gate
`way, downloaded from Internet website http://www.mytec.
`com/products/gateway on Nov. 1, 1999.
`Mytec Technologies Inc., Mytec: Why Mytec, downloaded
`from
`Internet
`website
`http://www.mytec.com/why
`mytec.htm on Nov. 1, 1999.
`Mytec Technolgies Inc., Mytec: Mytec: Products-Touch
`stone Pro, downloaded from Internet website http//www.
`mytec.com/products/touchstone on Nov. 1, 1999.
`BIOPassword, Net Nanny Software International Inc.
`1994–1998, Bellevue, WA USA, pp. 2–9, 1–3.
`
`F. Monrose, M.K. Reiter, and S. Wetzel, “Password hard
`ening based on keystroke dynamics.” Proceedings of the 6'
`ACM Conference on Computer and Communications Secu
`rity, Nov. 1999, pp. 73–82.
`C. Soutar and G.J. Tomko; “Secure Private Key Generation
`Using a Fingerprint,” Card tech/Securetech Conference Pro
`ceedings, vol. 1, May 1996, pp. 245-252.
`European Patent Search Report, Application No.
`00302540,0–1237-, The Hague, Jun. 5, 2002.
`Shamir, A., How to Share a Secret, Communications of the
`ACM, vol. 22, No. 11, Nov., 1979, pp. 612-613.
`Davida, G. I., et al., On Enabling Secure Applications
`Through Off-line Biometric Identification, IEEE, 1998, pp.
`148-157.
`Monrose, F. et al., Password Hardening Based on Keystroke
`Dynamics, ACM, 1999, pp. 73–82.
`* cited by examiner
`
`IPR2018-00067
`Unified EX1030 Page 2
`
`

`

`U.S. Patent
`
`May 31, 2005
`
`Sheet 1 of 3
`
`US 6,901,145 B1
`
`FIC.
`
`1
`
`
`
`100
`
`FIC. 2
`
`p
`
`20
`
`S () )
`p(X2)
`
`p(s)
`
`2O3
`
`)
`p(X)
`
`k
`
`IPR2018-00067
`Unified EX1030 Page 3
`
`

`

`U.S. Patent
`
`May 31, 2005
`
`Sheet 2 of 3
`
`US 6,901,145 B1
`
`FIC. 3
`
`300
`
`
`
`
`
`fy - EXPECTED (81 Y1)
`y - EXPECTED (; ; )
`
`IPR2018-00067
`Unified EX1030 Page 4
`
`

`

`U.S. Patent
`
`May 31, 2005
`
`Sheet 3 of 3
`
`US 6,901,145 B1
`
`
`
`SUCCESSFUL ACCESS ATTEMPT
`LAST
`
`MEASURED PARAMETERS
`A 6, , , , 6m
`
`IPR2018-00067
`Unified EX1030 Page 5
`
`

`

`US 6,901,145 B1
`
`1
`GENERATION OF REPEATABLE
`CRYPTOGRAPHIC KEY BASED ON
`WARYING PARAMETERS
`
`This application claims the benefit of U.S. Provisional
`Application Ser. No. 60/128,413, filed Apr. 8, 1999 and U.S.
`Provisional Application Ser. No. 60/147,880 filed Aug. 9,
`1999, both of which are incorporated herein by reference.
`
`FIELD OF THE INVENTION
`The present invention relates generally to computer Secu
`rity. More particularly, the present invention relates to the
`generation and use of cryptographic keys for computer
`Security applications.
`
`15
`
`25
`
`35
`
`40
`
`BACKGROUND OF THE INVENTION
`AS computer use becomes more widespread, the problem
`of computer System Security also becomes increasingly
`critical. The Volume of information Stored in computer
`Systems is growing at a large rate. Further, the accessibility
`of Such information Systems is increasing due to the inter
`connection of computer Systems through networkS Such as
`the Internet. A major problem facing computer owners is
`how to protect computer Systems, and the information they
`contain, from adversaries wishing to gain unauthorized
`access to Stored information.
`One type of computer System Security is referred to as
`authentication. Authentication refers to confirming the iden
`tity of a user prior to allowing access to a computer System.
`Most authentication Schemes are based on the user's knowl
`edge of a Secret, called a password. A user must have
`knowledge of a Secret password in order to gain access to the
`computer System.
`Another type of computer System Security is referred to as
`encryption. Some, or all, of the information on the computer
`System may be encrypted Such that the information is
`rendered unreadable or unusable until it is decrypted. Like
`authentication, decryption also relies on the knowledge of a
`Secret, called a key, which is used to decrypt the information.
`Thus, even though a perSon may have access to information,
`that information may be useless to Someone who does not
`possess the appropriate decryption key.
`These two Security techniques of authentication and
`encryption are related in many ways. For example, a Secret
`known by a user may serve as both a password and a
`decryption key. Further, a computer System may employ
`both types of Security techniques.
`With respect to authentication, textual passwords have
`been, and remain, the primary means of authenticating users.
`However, passwords have been shown to be a relatively
`weak mechanism for authentication. Studies have shown
`that users tend to choose passwords that can be easily
`guessed by an exhaustive Search of a relatively Small Subset
`of all possible passwords. For example, in a study of 14,000
`computer System passwords, it was found that almost 24%
`of the passwords could be found in a “dictionary” of only
`3x10' words. Considering the high speed at which a com
`puter could generate and test 3x10' words, passwords are
`60
`considered to be a weak form of computer Security.
`One known technique for Strengthening passwords is to
`require not only that the correct password be typed, but also
`that the user's keystroke features (e.g. duration of keystrokes
`and latency between keystrokes) match a predetermined
`Stored model of expected keystroke features. This technique
`is effective against So-called online attacks in which an
`
`45
`
`50
`
`55
`
`65
`
`2
`adversary is attempting to gain access to a computer System
`through the computer's authentication System. However,
`this technique is not effective against a So-called off-line
`attack, in which an adversary gains physical access to the
`computer's data, for example by taking physical possession
`of a laptop computer or by otherwise circumventing the
`computer's authentication System. Once an adversary has
`physical access to computer information, the above
`described keystroke feature technique is ineffective. Further,
`if an adversary gets physical access to a computer which
`allows access to the Stored keystroke feature models, the
`models may leak sensitive information which would then
`make it easier for the adversary to determine actual user
`passwords.
`Other techniques exist which do not require the Storage of
`such models in memory. For example, U.S. Pat. No. 5,680,
`460 describes a technique in which a user's fingerprint
`characteristics are measured and various filters are applied to
`the measurements to generate a key which can then be used
`to authenticate the user on a computer System. Another
`example is G. I. Davida, Y. Frankel, and B. J. Matt, On
`Enabling Secure Applications Through Off-Line Biometric
`Identification, Proceedings of the 1998 IEEE Symposium on
`Security and Privacy, pp. 148-157, May 1998, in which
`error correcting parameters are used to decode biometric
`(e.g. iris Scan) readings into a canonical form for a particular
`user. This canonical form may then be used to generate a key
`for authentication purposes. However, both of these tech
`niques also Suffer from the above described deficiency in
`that any compromise of the underlying System data (either
`the filters or the error correcting parameters) will leak
`Sensitive information which, in certain applications, would
`allow an adversary to more easily determine the user's
`authentication key.
`
`SUMMARY OF THE INVENTION
`The present invention provides for the generation of a
`repeatable cryptographic key based on potentially varying
`parameters which are received, for example, during a com
`puter resource access attempt. The key is repeatable in that
`the same key may be generated using different received
`parameters. In accordance with the invention, So-called
`cryptographic shares are retrieved from memory locations
`identified as a function of the parameters. The key may be
`determined from knowledge of a Sufficient number of cryp
`tographic shares.
`In accordance with one embodiment, values of the
`received parameters are used to generate indices into a
`So-called share table which Stores valid and invalid crypto
`graphic shares. Valid cryptographic shares (i.e., those which
`may be used to generate the key) are stored in memory
`locations whose indices are expected to be generated during
`legitimate access attempts. Invalid cryptographic shares
`(i.e., those which may not be used to generate the key) are
`Stored in memory locations whose indices are not expected
`to be identified during legitimate acceSS attempts. Thus, the
`share table may be configured to take into account expected
`variations in the received parameters. In accordance with
`one technique, valid shares may be periodically replaced
`with invalid shares (and vice versa) based on a history of
`acceSS attempts and a change in expected parameter values.
`In various embodiments, the Stored shares may be
`encrypted in various ways. In one embodiment, the shares
`are encrypted using a value computed as a function of
`expected parameter values. In this embodiment, one
`encrypted share is Stored and associated with each param
`
`IPR2018-00067
`Unified EX1030 Page 6
`
`

`

`US 6,901,145 B1
`
`3
`eter. When a parameter is received during an access attempt,
`the associated Stored encrypted share is retrieved from
`memory and an attempt to decrypt the share is made using
`a value computed as a function of the parameter value. Only
`if the computed value is the same as the value used to
`encrypt the share (i.e., the expected value) will a valid share
`be obtained. Otherwise, an invalid share will be obtained. In
`various embodiments, the cryptographic shares may be
`chosen So as to allow generation of the key even if Some
`number of invalid shares are generated, as long as a Suffi
`cient number of valid shares are generated. This embodi
`ment is particularly advantageous when the number of
`possible parameter values is very large. This embodiment is
`described in further detail below in accordance with an
`embodiment of the invention in which the contents of a
`database may be decrypted using parameters representing
`measured DNA information.
`Various Secret Sharing Schemes may be used to generate
`the cryptographic shares. In accordance with one embodi
`ment of the invention, a So-called polynomial Secret Sharing
`Scheme is used. In this embodiment, the Secret key is the
`point where the polynomial crosses the y axis and the
`cryptographic shares are points on the polynomial. Knowl
`edge of a Sufficient number of points on the polynomial (i.e.,
`cryptographic shares), allows for the determination of the
`polynomial, and thus determination of the key. These poly
`nomial points may be Stored in a Straightforward manner by
`Storing (x,y) pair values in the share table. Alternatively, in
`order to save memory space (at the expense of an increase
`in computational complexity) compressed shares may be
`stored in the share table.
`In accordance with an advantageous embodiment of the
`invention, the inventive techniques are used to implement a
`keystroke feature authentication System in which users are
`authenticated based on a combination of an entered pass
`word and the manner in which the password was typed. In
`accordance with this embodiment, a share table contains a
`row for each keystroke feature to be considered (e.g.,
`duration of keypresses, latencies between keypresses). Upon
`receipt of a measured keystroke parameter, a function
`chooses one of two columns in the share table associated
`with the parameter row, depending on a comparison of the
`parameter with a predetermined threshold. A history of
`legitimate authentications is kept. When a measured key
`Stroke parameter consistently results in the function choos
`ing one of the two columns, the associated keystroke feature
`is considers a distinguishing feature, and the other of the two
`columns in the share table is updated to contain an invalid
`cryptographic share. Over time, the share table is updated
`Such that only share table entries which are expected to be
`accessed during future legitimate access attempts contain
`valid cryptographic shares, while the share table entries
`which are not expected to be accessed during a legitimate
`access attempt contain invalid cryptographic shares. In this
`manner, an illegitimate access attempt will retrieve invalid
`cryptographic shares from the share table Such that it will not
`be possible to generate the cryptographic key. In accordance
`with another aspect of this embodiment, the shares Stored in
`the share table are encrypted using the password as the
`decryption key in order to add additional Security.
`These and other advantages of the invention will be
`apparent to those of ordinary skill in the art by reference to
`the following detailed description and the accompanying
`drawings.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 shows an exemplary share table;
`FIG. 2 illustrates an exemplary polynomial which may be
`used in conjunction with a polynomial Secret Sharing
`Scheme,
`
`4
`FIG. 3 illustrates a share table which stores compressed
`cryptographic shares,
`FIG. 4 illustrates a share table which stores encrypted
`cryptographic shares,
`FIG. 5 illustrates a share table in accordance with a
`keystroke features authentication embodiment of the inven
`tion; and
`FIG. 6 illustrates a history table in accordance with a
`keystroke features authentication embodiment of the inven
`tion.
`
`DETAILED DESCRIPTION
`The present invention provides for the generation of a
`repeatable cryptographic key based on a Set of potentially
`varying parameters. The cryptographic key is repeatable in
`that the same key is generated notwithstanding that the
`parameters, on which generation of the key is based, may
`vary from one generation of the key to the next. In an
`advantageous embodiment, the parameters represent mea
`Surements of Some physical characteristics of either a perSon
`or a thing. For example, one class of physical characteristics
`is biometric characteristics of a perSon. AS used herein, the
`term biometric characteristics includes any measurable
`biological, physiological, or biomechanical characteristics
`of a perSon. Such characteristics include, for example,
`fingerprint, iris, DNA, typing patterns, Voice, blood, etc.
`Thus, for computer Security applications of the present
`invention, any biometric characteristic, or combination of
`biometric characteristics, which could reasonably identify a
`particular perSon would be appropriate. Another class of
`physical characteristics are the characteristics of things (e.g.
`non-biological items). Such characteristics include, for
`example, chemical or molecular composition, etc. Although
`the following description describes the invention in terms of
`parameters representing measurements of physical
`characteristics, it is to be understood that the invention is not
`limited to any particular type of parameters, but instead
`applies to any type of varying parameters.
`Actual measurement techniques will vary depending on
`the embodiment of the invention, and the details of particu
`lar measurement techniques are not the Subject of this
`invention. It is the use of the physical measurements, once
`obtained, to generate a repeatable cryptographic key for use
`in computer Security applications that is the Subject of this
`invention. Thus, we assume that the measurements have
`been made and that we are Supplied with physical measure
`ment parameters, represented here as parameters: (p, p.2, . . .
`(Pn.
`It is expected that the measurements of the same physical
`characteristics of the same entity may vary from one mea
`surement to the next. This may be due to two factors. First,
`the measured physical characteristic itself may be dynamic.
`For example, if the measured physical characteristic were
`the biometric characteristics of voice (e.g. pitch, amplitude)
`during the Speaking of Some word or phrase, it is expected
`that an individual's voice characteristics will not be exactly
`the same during repeated vocalizations of the same word or
`phrase. AS Such, the measured characteristics represented as
`parameters p, p, . . . (p, will be different even though the
`Same perSon Speaks the same word or phrase. Second, the
`measured physical characteristic itself may be Static, but the
`measurement of the physical characteristic may be imprecise
`or incomplete. For example, a perSon's fingerprint is Static,
`but the results of different measurements of the same fin
`gerprint may change slightly, due to imprecise measuring
`equipment, or because of an incomplete Sample.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`IPR2018-00067
`Unified EX1030 Page 7
`
`

`

`S
`One of the advantages of the present invention is its
`ability to generate a repeatable cryptographic key in View of
`varying measurements. As a result, the invention may be
`used for various computer Security applications. For
`example, as will be described in further detail below, in one
`embodiment the inventive technique is used to authenticate
`computer System users based on particular keystroke fea
`tures during entry of a password. A user must be authenti
`cated even though his/her keystroke features will change
`Slightly during multiple entries of the Same password. The
`present invention will generate a repeatable key for a par
`ticular user if the keystroke feature measurements vary
`within certain tolerances, thus authenticating the user.
`In another embodiment (also discussed in further detail
`below) the invention may be used to protect information in
`a Sensitive database containing private information. For
`example, consider a database which contains private infor
`mation of convicted felons which is only meant to be used
`for legitimate criminal investigation purposes. For example,
`if a criminal is Suspected of a crime the database record for
`only that particular criminal should be accessible by inves
`tigators. AS Such, each record in the database is encrypted
`and may only be decrypted using a key which is generated
`using DNA measurements of the associated perSon. This is
`to assure that prior to accessing potentially private informa
`tion about a perSon, the person's DNA has already been
`recovered from a crime Scene, thus making the perSon a
`suspect in a crime. While a person's DNA is not dynamic,
`imprecise measurement techniques or imprecise Samples
`may result in having incomplete DNA measurements. In
`accordance with the techniques of the present invention, a
`repeatable key to unlock the database records could be
`generated with this incomplete DNA information.
`In advantageous embodiments, the invention may be
`implemented using a programmable computer. Such a com
`35
`puter comprises a processor for executing computer program
`code Stored in a memory which is accessible by the proces
`Sor. AS used herein, the term memory is used to refer to any
`computer readable medium, including without limitation,
`random access memory (RAM), read only memory (ROM),
`magnetic disk, optical disk, and holographic memory. In an
`advantageous embodiment, the computer program code is
`Stored in a high Speed memory, Such as a RAM, which is
`connected to the computer processor. The computer program
`code required to implement the invention may be written in
`any well known computer language. Given the present
`description of the invention, one of ordinary skill in the art
`to which the invention pertains could readily write the
`program code necessary to implement the invention. The
`data structures described below (e.g. the share table) are also
`Stored in memory. A user interacts with the computer using
`well known input/output devices and techniques (e.g. dis
`play Screen, keyboard, mouse). Programmable computers of
`the type described herein are well known in the art and as
`Such, further details are not required here.
`AS described above, we will assume that measurements of
`Some physical characteristic have been taken and we are
`thus in possession of parameters (p, qp2, ... (p, representing
`those physical characteristics. In one embodiment of the
`invention, a function f is applied to the parameters (p, qp, . . .
`(p, in order to generate a set of indices
`,
`, . . .
`. Such
`that f(p1, p.2, ... (p,u)={1, 2, ...
`}. (The Subscript m'
`is used for the parameters (cp) to indicate that there need not
`be the same number of parameters (cp) and indices (up)). The
`indices 1,
`2, . . .
`. are used to acceSS a Set of Stored
`values, where at least Some of the Stored values are So-called
`cryptographic shares of a Secret Sharing Scheme. Secret
`
`6
`Sharing Schemes and cryptographic shares will be described
`in further detail below. At this point, let it suffice to say that
`possession of a Sufficient number of valid cryptographic
`shares of a Secret Sharing Scheme may be used to generate
`the repeatable key. In order to provide Security, not all the
`Stored values represent valid cryptographic shares. Instead,
`the particular values in the Set of values which contain valid
`cryptographic shares are chosen to correspond to values of
`the indices
`,
`, . .
`.
`), which are expected to be
`generated during a legitimate attempt to access the computer
`resource. The other values in the set (i.e., those for which
`corresponding indices are not expected to be generated
`during a legitimate access attempt) do not contain valid
`cryptographic shares. AS will be described in further detail
`below, a designer of the Security System will be able to
`identify the indices which would be expected to be gener
`ated during a legitimate access attempt.
`AS an example, consider the physical measurement
`parameters (p, (p, qps, p. corresponding to 4 measured
`keystroke features of a particular user during the typing of
`a password. Further, assume that the function f when
`applied to these parameters, produces a set of indices, each
`in the range of 1-10. For example, the indices in the range
`of 1-10 may be a result of normalizing the latency mea
`Surements. Also, assume that the user has engaged in a
`training Session during which the user typed the password
`five times. After applying the function f to the parameters
`(p., (p.2, p-s, p. generated during the training Session, the
`indices
`,
`,
`, ) were generated as follows:
`password entry 1:
`1,
`2, l's, '-1,5,9.3
`password entry 2:
`,
`,
`, ) =2,6,9.3
`password entry 3: 1,
`2, l's, '-2.5.8.4
`password entry 4: 1,
`2, l's, '-3,5,8,3
`password entry 5:
`1,
`2, l's, '-1,6,7,3
`From this information, a Security designer can conclude that
`expected values of the indices for this user are as follows:
`
`INDEX
`
`1.
`2
`l's
`'4
`
`EXPECTED
`VALUES
`
`1,2,3
`5,6
`7,8,9
`3,4
`
`The indices are used to Select values from a data structure
`called a share table, So named because it contains crypto
`graphic shares. An exemplary share table is shown in FIG.
`1 as table 100. The indices select values from the share table
`as follows. The first index up selects a value from the first
`row, the Second indeX - Selects a value from the Second
`row, the third indeX - Selects a value from the third row,
`and the fourth index up selects a value from the fourth row.
`The value of the particular index determines the column
`from which the value is Selected. Thus, using conventional
`(row.column) notation, given an index up a value is selected
`from the share table 100 at location (i, j).
`Based on the expected values found during the training
`session, the locations in the share table 100 corresponding to
`the expected values for each of the indices will be set to
`contain valid cryptographic shares Such that the repeatable
`key may be generated from those valid cryptographic shares.
`Those locations which do not correspond to the expected
`values for each of the indices will be set to contain values
`which are not valid cryptographic shares, called invalid
`
`US 6,901,145 B1
`
`15
`
`25
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`IPR2018-00067
`Unified EX1030 Page 8
`
`

`

`US 6,901,145 B1
`
`7
`cryptographic shares, Such that the repeatable key may not
`be generated from those values. In FIG. 1, locations in Share
`table 100 which contain valid cryptographic shares are
`identified with a V and locations which contain invalid
`cryptographic shares are identified with a X.
`Secret sharing schemes will be described in further detail
`below. For purposes of the present example, assume that
`four valid cryptographic shares are required to generate the
`repeatable key. Also assume that on a particular acceSS
`attempt the user types his/her password and the function f
`generates the following indices based on measurements of
`the keystroke features:
`acceSS attempt 1:
`1, 2, l's, l =2,6,8.4
`Note that although this exact Set of indices did not appear in
`any of the training Sessions, each of the values is an expected
`value for the corresponding index. AS Such, the indices
`correspond to locations in the share table 100 which contain
`valid cryptographic shares. More particularly, index up
`Selects row 1, column 2 from the Share table, indeX -
`Selects row 2, column 6 from the Share table, indeX |
`Selects row 3, column 8 from the share table, and indeX |
`Selects row 4, column 4 from the share table. AS can be seen
`from FIG. 1, each of these share table locations contains a
`valid cryptographic share as indicated by a V. AS Such, the
`correct repeatable key could be generated from the valid
`cryptographic shares and the user would be authenticated.
`Alternatively, assume that the user types his/her password
`and the function f generates the following indices based on
`measurements of the keystroke features:
`access attempt 2:
`,
`,
`, ) =2,7.5,4
`Note here that the index values for 2,
`are not expected
`values for these indices and as such, the entries in the share
`table 100 corresponding to these indices (row 2, column 7
`and row 3, column 5) contain X indicating an invalid
`cryptographic share. AS Such, the correct repeatable key
`could not be generated from these cryptographic shares and
`the user would not be authenticated. Further details of an
`advantageous keystroke feature authentication embodiment
`of the invention will be given below.
`According to one embodiment of the invention, errors, or
`variations, in measured physical characteristics may also be
`tolerated by Selecting share table locations which were not
`actually indexed by the Set of indices generated by the
`function f. This error tolerance is advantageously accom
`plished by Selecting share table locations which are in the
`vicinity of locations actually indexed by the indices gener
`ated by the function f. For example, assume the share table
`100 shown in FIG. 1 and an embodiment in which four
`indices
`,
`,
`, ) are generated. If the repeatable key
`is not generated correctly by Selecting shares from the Share
`table locations indexed by 1,
`2, l's, l', then the System
`may first attempt to vary the Selection of a share table
`location associated with the first indeX
`, by choosing,
`during two separate key generation attempts, the Share table
`location on either side of the location indexed by up. If the
`generation of the repeatable key is unsuccessful, the System
`may then attempt to vary the Selection of a share table
`location associated with the Second indeX - in a similar
`manner. These Steps of varying the actual chosen share table
`location may continue for each of the indices. Of course, this
`process of varying the Selection of share table locations may
`be extended in order to implement an appropriate Security
`Scheme for different embodiments of the invention. For
`example, during each key generation attempt, one or more
`share table locations may be chosen using this variation
`technique. Further, the amount of variation allowed for each
`location may vary. AS described above, the variation consists
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`of one table location on either Side of the actual indexed
`location. However, the variation may also consist of more
`than one table location on either Side of the actual indexed
`location. Additionally, depending on the implementation, it
`may be appropriate to vary the Selection of a share table
`location for only certain of the indices. Of course, many
`other variation techniques may be used and are contem
`plated by this description.
`Advantageously the invalid cryptographic shares in a
`share table should be chosen such that they cannot be readily
`recognized as invalid by an adversary who compromises the
`computer System data and gains access to the share table. In
`this way, the adversary would not be able to gain any
`information from the share table. Further, the values in a
`share table may be encrypted for further security. For
`example, as will be described in further detail below, in the
`keystroke feature authentication embodiment, the values in
`the share table are encrypted with the user's actual password
`in order to provide additional Security.
`Thus, as can be seen, the techniques in accordance with
`the present invention