Generation of repeatable cryptographic key based on varying parameters

• US 6,901,145 B1
• Filed: 02/10/2000
• Issued: 05/31/2005
• Est. Priority Date: 04/08/1999
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Bohannon, Philip L., Jakobsson, Bjorn Markus, Reiter, Michael Kendrick, Monrose, Fabian, Wetzel, Susanne Gudrun
• Primary Examiner(s): Peeso, Thomas R.
• Assistant Examiner(s): ZIA, SYED
• Application Number:
  US09/501,902
• Time in Patent Office: 1,937 Days
• Field of Search: 380/44, 713/165
• US Class Current: 380/44
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 21/316 by observing the pattern of computer usage, e.g. typical user behaviour
• CPC Class Codes: G06F 21/32 using biometric data, e.g. fingerprints, iris scans or voiceprints
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0866 involving user or device identifiers, e.g. serial number, physical or biometrical information, DNA, hand-signature or measurable physical characteristics
• CPC Class Codes: H04L 9/3231 Biological data, e.g. fingerprint, voice or retina network architectures or network communication protocols for supporting authentication of entities using biometrical features in a packet data network H04L63/0861

Abstract

A repeatable cryptographic key is generated based on varying parameters which represent physical measurements. 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 configured such that locations which are expected to be identified 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 compressed. A keystroke feature authentication embodiment uses the inventive techniques to implement an authentication system which authenticates based on an entered password and the manner in which (e.g. keystroke dynamics) the keystroke is entered. Another embodiment uses the inventive techniques to protect sensitive database information which is accessible using DNA measurements.

Claims

1. A method for generating a repeatable cryptographic key using at least one parameter comprising the steps of:

generating at least one index as a function of said at least one parameter, said one parameter being from a plurality of varying parameters;

retrieving at least one cryptographic share from a memory location identified as a function of said at least one index; and

generating said repeatable cryptographic key based on said at least one cryptographic share, wherein said generated repeatable cryptographic key remains the same from one said generating of said repeatable cryptographic key to a next generating of said repeatable cryptographic key regardless of whether said plurality of varying parameters change from said generating of said repeatable cryptographic key to said next generating of said repeatable cryptographic key.

2. The method of claim 1 wherein said at least one retrieved cryptographic share is encrypted, said method further comprising the step of:

decrypting said at least one cryptographic share.

3. The method of claim 2 wherein said step of decrypting comprises the step of:

decrypting using a value computed as a function of said at least one parameter.

4. The method of claim 1 wherein said at least one parameter represents at least one measurement of a physical property.

5. The method of claim 1 wherein the plurality of varying parameters change from said one generation of said repeatable cryptographic key to said next generation of said repeatable cryptographic key.

6. The method of claim 5 further comprising the step of:

retrieving a cryptographic share from a memory location in the vicinity of said memory location identified by said index.

7. The method of claim 5 wherein said step of generating at least one index comprises the step of generating the same index for a set of parameter values.

8. The method of claim 7 wherein said set of parameter values are within a predetermined range of values.

9. A method for generating a repeatable cryptographic key comprising the steps of:

measuring a plurality of keystroke features during entry of a password;

generating a plurality of indices using said plurality of keystroke features;

retrieving from a data structure a plurality of cryptographic shares as a function of said plurality of indices; and

generating said repeatable cryptographic key using said cryptographic shares wherein said generated repeatable cryptographic key remains the same from one said generating of said repeatable cryptographic key to a next generating of said repeatable cryptographic key regardless of whether said plurality of keystroke features change from said one generating of said cryptographic repeatable key to said next generating of said repeatable cryptographic key.

10. The method of claim 9 wherein said cryptographic shares represent points on a polynomial.

11. The method of claim 9 wherein said cryptographic shares represent vectors.

12. The method of claim 9 wherein said cryptographic shares are compressed.

13. The method of claim 12 wherein said cryptographic shares comprise y values of points on a polynomial and the corresponding x values are derivable from a data structure location.

14. The method of claim 9 wherein said plurality of keystroke features vary from said one generating of said repeatable cryptographic key to said next generation of said repeatable cryptographic key.

15. The method of claim 9 wherein said step of generating a plurality of indices as a function of said keystroke features comprises the step of:

for each of said keystroke features, generating one of two indices as a function of a threshold value, h_i, where said function is defined by;

ƒ

(φ

₁, φ

₂, . . . φ

_m)={ψ

₁, ψ

₂, . . . ψ

_m}ε

{0,1}^m

where

φ

represents said keystroke features, ψ

represents said indices, m is a particular number of measured features associated with said password; and

${\mathrm{\psi <br><br>}}_i<br><br>\{\begin{array}{c}0<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\varphi <br><br>}}_i<<br><br>h_i\\ 1<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\varphi <br><br>}}_i\ge <br><br>h_i.\end{array}$

16. The method of claim 9 wherein said step of generating a plurality of indices as a function of said keystroke features comprises the step of:

for each of said keystroke features, generating one of a plurality of indices as a function of a plurality of threshold values, h_i, where said function is defined by;

ƒ

(φ

₁, φ

₂, . . . φ

_m)={ψ

₁, ψ

₂, . . . ψ

_m}ε

{0,1}^m

where

φ

represents said keystroke features, ψ

represents said indices, m is a particular number of measured features associated with said password; and

${\mathrm{\psi <br><br>}}_i<br><br>\{\begin{array}{c}0<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\varphi <br><br>}}_i<<br><br>h_i\\ 1<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\varphi <br><br>}}_i\ge <br><br>h_i.\end{array}$

17. The method of claim 9 wherein said cryptographic shares stored in said data structure are encrypted, said method further comprising the step of:

decrypting said cryptographic shares using said password.

18. The method of claim 9 further comprising the steps of:

maintaining a history file containing information relating to prior successful key generation attempts; and

based on said history file, storing invalid cryptographic shares in data structure locations which are not expected to be accessed during subsequent legitimate key generation attempts.

19. A method for generating a repeatable cryptographic key using a plurality of varying parameters, said varying parameters representing physical measurements, said method comprising the steps of:

for each of said plurality of parameters;

generating at least one index using said parameter;

retrieving an encrypted cryptographic share from a memory location as a function of said at least one index;

decrypting said encrypted cryptographic share with a function of said parameter; and

generating said repeatable cryptographic key using said decrypted cryptographic shares, wherein said generated repeatable cryptographic key remains the same from one said generating of said repeatable cryptographic key to a next generating of said repeatable cryptographic key regardless of whether said plurality of varying parameters change from said one generating of said repeatable cryptographic key to said next generating of said repeatable cryptographic key.

20. The method of claim 19 wherein said physical measurements are measurements of DNA.

21. The method of claim 19 wherein said function of said parameter used to decrypt said encrypted cryptographic share is a hash function.

22. A data structure for use in generating a repeatable cryptographic key based on n parameters representing physical measurements, said data structure comprising:

n storage locations each associated with a respective one of said n parameters, each particular storage location containing an encrypted cryptographic share which was encrypted using an expected value of a function of the parameter associated with said particular storage location, each said n storage location being associated with at least one index of a plurality of indices, where said plurality of indices are generated using said physical measurements such that said repeatable cryptographic key remains the same from one generation to a next generation of said repeatable cryptographic key regardless of whether said n parameters change from said one generation of said repeatable cryptographic key to said next generation of said repeatable cryptographic key.

23. The data structure of claim 22 wherein said function is a hash function.

24. The data structure of claim 22 wherein said repeatable cryptographic key may be generated using less than n cryptographic shares.