Source: http://patents.com/us-7979716.html
Timestamp: 2019-06-19 05:07:25
Document Index: 121483781

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60']

US Patent # 7,979,716. Method of generating access keys - Patents.com
United States Patent 7,979,716
Fiske July 12, 2011
Method of generating access keys
Inventors: Fiske; Michael (San Francisco, CA)
Assignee: Biogy, Inc. (San Francisco, CA)
Appl. No.: 11/131,652
11106930 Apr., 2005
11106183 Apr., 2005
11104357 Apr., 2005
11104343 Apr., 2005
11102407 Apr., 2005
11100803 Apr., 2005
60637536 Dec., 2004
60646463 Jan., 2005
60629868 Nov., 2004
60631199 Nov., 2004
Current U.S. Class: 713/184 ; 711/164; 713/185; 726/27
Current International Class: G06F 21/00 (20060101); G06F 7/04 (20060101); G06F 13/00 (20060101)
Field of Search: 713/184
5481672 January 1996 Okuno et al.
5612683 March 1997 Trempala et al.
5616683 April 1997 Neuert et al.
5802199 September 1998 Pare, Jr. et al.
5903225 May 1999 Schmitt et al.
6112187 August 2000 Fukawa
6782120 August 2004 Modl et al.
6898711 May 2005 Bauman et al.
7066382 June 2006 Kaplan
7142699 November 2006 Reisman et al.
7299364 November 2007 Noble et al.
7308708 December 2007 Blume
7415614 August 2008 Guillou
7415729 August 2008 Ukeda et al.
7423515 September 2008 Fiske
7441263 October 2008 Bakshi et al.
7565548 July 2009 Fiske et al.
2003/0063782 April 2003 Acharya
2003/0156011 August 2003 Modl et al.
2004/0267387 December 2004 Samadani
2005/0036611 February 2005 Seaton, Jr. et al.
2006/0107040 May 2006 Fiske
2006/0107041 May 2006 Fiske
2006/0107063 May 2006 Fiske
2006/0107064 May 2006 Fiske
2006/0107065 May 2006 Fiske
2006/0107067 May 2006 Safal et al.
2006/0107068 May 2006 Fiske
2006/0107309 May 2006 Fiske
2006/0107312 May 2006 Fiske
2006/0107315 May 2006 Fiske
2006/0117188 June 2006 Fiske
2006/0230284 October 2006 Fiske
2007/0118754 May 2007 Togashi et al.
2009/0158049 June 2009 Fiske
2009/0178115 July 2009 Fiske
PCT/US05/41799 May., 2006 WO
PCT/US05/46215 Jun., 2006 WO
PCT/US06/02271 Aug., 2006 WO
Weiss, Kenneth P. "When A Password Is Not A Password". IEEE 1990 International Carnahan Conference on Security Technology. Pub. Date: Oct. 1990. Relevant pp. 100-108. Found on the World Wide Web at: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=111393. cited by examiner .
U.S. Appl. No. 11/106,183, filed Apr. 13, 2005, Michael Fiske. cited by other .
U.S. Appl. No. 12/214,883, filed Jun. 20, 2008, Michael Fiske. cited by other .
U.S. Appl. No. 12/157,413, filed Jun. 7, 2008, Michael Fiske. cited by other .
U.S. Appl. No. 12/157,354, filed Jun. 7, 2008, Michael Fiske. cited by other .
Menezes et al., Handbook of Applied Cryptography, "Identification and Entity Authentication." CRC Press. 1996. pp. 385-424. cited by other.
Attorney, Agent or Firm: Lewis; David
This application is a continuation-in-part of U.S. patent application Ser. No. 11/106,930, entitled "API For a System Having a Passcode Authenticator" filed Apr. 14, 2005, which in turn is a continuation-in-part of U.S. patent application Ser. No. 11/106,183, entitled. "Interfacing With a System That Includes a Passcode Authenticator", filed Apr. 13, 2005, which in turn is a continuation-in-part of U.S. patent application Ser. No. 11/104,357, entitled, "System For Generating Requests For Access To a Passcode Protected Entity", filed Apr. 12, 2005, which in turn is a continuation-in-part of U.S. patent application Ser. No. 11/104,343, entitled, "Generating Requests For Access To a Passcode Protected Entity," filed Apr. 11, 2005, which in turn is a continuation-in-part of U.S. patent application Ser. No. 11/102,407, entitled "System For Handling Requests For Access To a Passcode Protected Entity," filed Apr. 7, 2005, which in turn is a continuation-in-part of U.S. patent application Ser. No. 11/100,803, entitled "Determining Whether To Grant Access To a Passcode Protected System," filed Apr. 6, 2005, which in turn claims priority benefit of U.S. Provisional Patent Application No. 60/637,536, entitled "Secure Keys," filed Dec. 20, 2004 and claims priority benefit of U.S. Provisional Patent Application No. 60/646,463, entitled "Passcode Generator," filed Jan. 24, 2005; this application is a continuation-in-part of U.S. patent application Ser. No. 11/100,803, entitled, "Determining Whether To Grant Access To a Passcode Protected System", filed Apr. 6, 2005, which is incorporated herein by reference; this application also claims priority benefit of U.S. Provisional Patent Application No. 60/637,536, entitled "Secure Keys" filed Dec. 20, 2004, and this application claims priority benefit of U.S. Provisional Patent Application No. 60/646,463, filed Jan. 24, 2005. All of the above applications are incorporated herein by reference. This application incorporates herein by reference U.S. Provisional Patent Application No. 60/629,868, filed Nov. 18, 2004. This application also incorporates herein by reference U.S. Provisional Patent Application No. 60/631, 199, filed Nov. 26, 2004. This application also incorporates herein by reference U.S. patent application Ser. No. 10/778,503, filed Feb. 15, 2004. This application also incorporates herein by reference U.S. patent application Ser. No. 10/889,237, filed Jul. 11, 2004.
1. A machine-implemented method comprising: after a registration session is complete, performing a process that includes at least storing an access key in long term memory in a secure area of a portable device; at the portable device, receiving a passcode from a host system, the passcode generated by a method of generating passcodes; at the portable device, verifying the passcode was generated by the method of generating passcodes; the portable device supplying the access key to the host system to perform a task, the host being separate from the secure area; and erasing the access key from the host system after the supplying; wherein the process is repeated every session.
2. A machine-implemented method comprising: after a registration session is complete, performing a process that includes at least storing an access key in long term memory in a secure area of a portable device; at the portable device, receiving a passcode from a host system, the passcode generated by a method of generating passcodes; at the portable device, verifying the passcode was generated by the method of generating passcodes; the portable device supplying the access key to the host system to perform a task; and erasing the access key from the host after the supplying; wherein the portable device does not have an operating system; and wherein the process is repeated every session.
7. The method of claim 1, further comprising at the portable device, receiving a request from the host for the access key; and authenticating the passcode at the portable device, via the comparing, prior to the supplying.
9. The method of claim 1, further comprising: at the portable device acquiring user data.
10. The method of claim 9, further comprising: at the portable device, comparing the user data to stored user information.
11. The method of claim 10, comprising: if the user data and the user information do not match, at the portable device, terminating the method.
12. The method of claim 10, comprising: if the user data and the user information do match, at the portable device, requesting the host to perform an action.
13. A machine-implemented method comprising: after a registration session is complete, performing a process that includes at least at a portable module, receiving a passcode from a host system, the passcode generated by a method of generating passcodes; at the portable module, verifying the passcode was generated by the method of generating passcodes; and and if the passcode matches the method for generating passcodes, sending an access key from the portable module to the host system; wherein the process is repeated every session.
14. A machine-implemented method comprising: after a registration session is complete, performing a process that includes at least at a module, receiving a passcode from a system, the passcode generated by a method of generating passcodes; at the module, verifying the passcode was generated by the method of generating passcodes; and and if the passcode matches the method for generating passcodes, sending an access key from the module to the system, further comprising: as part of each session, at the module, if a determination is made that the passcode matches the method for generating passcodes, in response to the determination that the passcode matches, automatically generating a new passcode; and wherein the process is repeated every session.
15. The method of claim 14, further comprising: if the passcode matches the method for generating passcodes, generating a new passcode, after the generating of the new passcode, automatically sending the new passcode from the module to the system.
17. A machine-implemented method comprising: after a registration session is complete, performing a process that includes at least acquiring user data at a portable module; at the portable module, comparing the user data to user information stored at the portable module; if the user data and the user information do not match, terminating the method; if the user data and the user information do match, sending a request from the portable module to an unsecured system to perform encryption; at the portable module, in response to the sending of the request, receiving a passcode from the unsecured system, the passcode generated by a method of generating passcodes; at the portable module, verifying the passcode that was received was generated by the method of generating passcodes; and if the passcode matches the method for generating passcodes, sending an encryption key from the portable module to the unsecured system, at the portable module, generating a new passcode, sending the new passcode to the unsecured device, wherein the new passcode is not stored at a module that performed the sending; wherein the process is repeated every session.
18. A machine-implemented method comprising: after a registration session is complete, performing a process that includes at least at a portable module, acquiring user data; at the portable module, comparing the user data to stored user information; if the user data and the user information do not match, at the portable module, terminating the method; and if the user data and the user information do match, the portable module requesting an unsecured system to perform encryption, generating a new passcode, receiving a passcode from the unsecured system, the passcode generated by a method of generating passcodes, verifying the passcode that was received was generated by the method of generating passcodes, encrypting the encryption key with the passcode received from the unsecure system, and sending the encrypted encryption key to the unsecured device; wherein the process is repeated every session.
System 100 is an example of a system in which the security of a secure entity is kept by requiring a user to submit a passcode (e.g., a password) in order to gain access to the secure entity. The term "user" refers to someone that has access to passcode device 101. The user may use passcode device 101 to gain access to a secure entity. Any sequence of bits (which may represent any string of symbols) may be used as a passcode. In some cases, the passcode may be directly transmitted without human intervention to the administrator, so the sequence of bits may not have a visual display in standard formats such as ASCII. Unicode, and so on. For example, the first sequence of 8 bits in the passcode could in ASCII represent the end of file character, which currently does not have a visual representation, in other embodiments where the passcode is displayed as a sequence of symbols on a graphical display, then the symbols may be chosen from any subset of or combination of alphanumeric, punctuation, picture symbols, math, uppercase, and/or lower case symbols, for example. The choice of alphanumeric symbols may include characters from a multiplicity of languages. An example of an alphanumeric passcode with 8 symbols is 4RIpa5Wx. An example of a possible passcode with 8 symbols is . An example with 16 symbols including punctuation and other symbols is .
Passcode device 101 may be used for generating passcodes and/or for setting up a new user in system 100. Setting up a new user may include "registering" the new users. Registering a new user refers to the process of adding a new user so that the new user is able to use a system, such as passcode device 101 or system 100. Passcode device 101 may have multiple other uses.
In an embodiment, a timestamp may be associated with a one-time passcode or other passcode. If the current time is later than the associated timestamp, when the passcode is submitted to an "administrator," then the passcode has expired, is invalid, and access would be denied. The word administrator is used to refer to an entity that grants or denies access to the secure entity.
There are many types of identifying information that may be stored by passcode device 101, such as fingerprints, a birthday, a favorite, number, a social security number, and/or a driver's license, a profile, an image of a face, an iris scan, a toe print, a handprint, and/or a footprint. In an embodiment, the item used to generate the passcodes is any item that is unique. In this specification, using a first item (e.g., a fingerprint) to "generate" a second item (e.g., a passcode) may refer to using the first item to "directly" generate the second item or to "indirectly" generate the second item by, for example, first generating one or more intermediary items from which the second item is ultimately generated. The intermediary items may include a chain of multiple intermediary items that each generated one from another. In an embodiment the item used to generate the passcode is one that is difficult to fabricate, guess, find by trial and error, and/or compute. In an embodiment, the item used to generate the passcodes is uniquely associated with the user. In an embodiment, the item used to generate the passcodes has an unpredictable element to it (e.g., the unpredictable manner in which the patterns of lines in fingerprints differ between fingerprints).
In FIG. 1B. each passcode, denoted as P.sub.i, is a sequence of bits. Although this specification uses a specific notation, the invention is in no way limited by this notation. Software implementing the methods of this specification may use a notation that is unrelated to the notation used in this specification. Setup portion 104 may be used for registering a new user, configuring passcode device 101, and/or for setting up passcode device 101. Setup portion 104 acquires identification information, T. In an embodiment, setup portion 104 may generate a registration code, which may be denoted as R, for the sake of registering the user with another entity.
In an embodiment, a method, .PHI..sub.1, may be used for generating registration code R from the identification information. The method .PHI..sub.1 (which may be referred to as a generating method) may be a "one-way" method such as a one-way algorithm, a one-way function, and/or another one-way method. For example, the registration code may be generated according to the equation .PHI..sub.1(T)=R. A one-way method, herein denoted .phi..sub.1 (possibly having one or more indices representing different functions associated with different users or applications), has the property that given an output value z, it is computationally extremely difficult to find the input m.sub.z such that .PHI..sub.1(m.sub.z)=z. In other words, a one-way method is a method .PHI..sub.1 that can be easily computed, but whose inverse .phi..sub.1.sup.-1 is extremely difficult (e.g., impossible) to compute. One way to quantify the difficulty to compute .PHI..sub.1 given an output z, is to use the number of computations that are expected to be required to compute and/or guess .PHI..sub.1For one type of method, it is that it is expected to take between O(2.sup.n/2) and O(2.sup.n) computational steps to find or guess m.sub.z, (depending on the how clever the one performing the computations is) where n is the number of bits in the output z. By using a one-way method for computing the registration code, even if the registration code is intercepted or otherwise stolen, it is unlikely that the registration code can be used to discover identifying information T.
One set of methods that may be used are one-way functions in which finding the inverse involves an operation that is mathematically indeterminate, impossible, intractable, or computationally impractical or difficult. For example, one method is to use a collection of step functions each of whose domain and range is [0, 1, 2 . . . 255] and apply a distinct step function to a part of T. The information from T could be used to determine which step functions to select from the collection. If 16 step functions are chosen from the collection, then this would create an output of 128 bits. If n step functions are chosen from the collection, then this would create an output of 8n bits. An alternative to this would be to construct 32 matrices resulting from the step functions and compute the determinant modulo 256 for each of the 32 matrices. This creates a one-way function whose output is 256 bits. As another example, method .phi..sub.1 could involve first representing user information T by a string of digits. Then, each digit of the string of digits could be multiplied by a corresponding digit from another string of digits, where at least one digit of the other string has a value of zero. The inverse of this method would involve at least one division by zero for each multiplication by a digit with the value of zero, which has no inverse, and consequently this method would also be one-way. Similarly, functions for which finding their inverses involves computing a non-convergent series or non-convergent integral are other examples of classes of functions that may be used as one-way functions.
In an embodiment, a one-way hash function is used as method .phi..sub.1. A hash function is one that accepts as its input argument an arbitrarily long string of bits (or bytes) and produces a fixed-size output. In other words, a hash function maps a variable length input m to a fixed-sized output, .phi..sub.1(m). Typical output sizes range from 128 to 512 bits, but can also be larger. An ideal hash function is a .phi..sub.1 whose output is uniformly distributed in the following way. For example, suppose the output size is of .phi..sub.1 is n bits. If the input m is chosen randomly, then for each of the 2.sup.n possible outputs z, the probability that .phi..sub.1(m)=z is 2.sup.-n possible outputs can be compared against the ideal probability of 2.sup.-n. The chi-square function on n-1 degrees of freedom is a useful way to measure the quality of a real hash function. One uses a chi-square on n-1 degrees because there are n bits of output. And then one can compute a confidence level that the real hash function is close to an ideal hash function. Some typical confidence levels could be 90%, 95%, 99%, 99.5% and 99.999% depending on the level of security desired. In an embodiment, the hash functions that are used are one-way. Other types of one-way functions or methods may be used in place of a hash function. In an embodiment, the hash functions that are used are one-way. Other types of one-way functions or methods may be used in place of a hash function.
Any of a number of hash functions may be used for .phi..sub.1. One possible hash function is SHA-256, designed by the National Security Agency and standardized by the NIST, [NIST_STANDARDS_1995]. The output size of SHA-256 is 256 bits. Other alternative hash functions are of the type that conforms to the standard SHA-1, which produces output values of 160 bits, and SHA-512, which produces output values of 512 bits, [NIST_STANDARDS_2001].
There are different methods that .phi..sub.1 may be used for hashing fingerprints and other kinds of input. As an alternative to biometric data, other types of input could be used. For example, the input to a hashing function could be a sequence of symbols such as a passcode or a registration code (that is different from the passcode or registration code that is produced). Different types of methods of hashing are appropriate for different sizes of codes, and different types of fingerprint information that is passed to the hash function. One method is to take two different fingerprints and apply the hash function SHA-256 to each print. For ease of explanation, denote the hash function SHA-256 as .phi..sub.1. Each application of .phi..sub.1 to a fingerprint produces an output value of 256 bits. With two fingerprints, these bits are concatenated together to create a 512-bit code, which may be called C.
Another method for .phi..sub.1 uses two different sections S and T of a single acquired fingerprint, and produce a 512-bit code, C, by concatenating .phi..sub.1(S) and .phi..sub.1(T). An enhancement of this method can be used to create codes larger than 512-bits. Divide one acquired fingerprint into n sections: S.sub.1, S.sub.2, . . ., S.sub.n. Then concatenate the bits .phi..sub.1(S.sub.1), .phi..sub.1(S.sub.2), . . ., .phi..sub.1(S.sub.n). This creates a code C that is 256n bits in length. For example, if the acquired fingerprint is divided into 10 sections, then this method would create a code with 2,560 bits. Any of the methods used as one-way function is useful. In another embodiment, method .phi..sub.1 could be a random number generator.
Setup portion 104 uses registration code R and a method .phi..sub.2, which may be a one-way function, to generate an initial passcode generator G.sub.1. Initial passcode generator G.sub.1 may be used for generating an initial passcode. A passcode generator, also known as a seed, can be a string of characters or other form of a code similar to registration code R or a passcode. Passcode generators may be stored securely by administrator 102 for use in verifying a passcode that is submitted by passcode device 101. The initial passcode generator G.sub.1 may be generated according to the equation .phi..sub.2(R)=G.sub.1. Method .phi..sub.2 (which also may be referred to as a generating method) may be the same as, or different from, method .phi..sub.1.
Using passcode generators, such as G.sub.1, enables the identification of a person without having access to the user's identifying data, such as the user's biometric data (e.g., fingerprints) or social security number or other identifying data. For example, some citizens and organizations are concerned about the government and other institutions storing a person's biometric data. using a passcode generator, such as G.sub.1, an institution can identify a person with a unique registration or passcode, which is derived from his or her fingerprint, other biometric data, and/or other authentication data.
Request portion 106 requests access to a secure device. In an embodiment, request portion 106 generates a passcode, which may be used for requesting access to a secure entity. For example, request portion may use a method, .phi..sub.3, and a generator. G.sub.i, for generating a passcode P.sub.i. Method .phi..sub.3 may be a one-way method such as a one way function, similar to method .phi..sub.2. Method .phi..sub.3 (which may be referred to as a generating method) may be the same as or different from methods .phi..sub.1 and/or .phi..sub.2. For example, request portion 106 may compute a passcode using the equation, .phi..sub.3(G.sub.i)=P.sub.i. The index i is used to indicate the ith passcode P.sub.i, which in an embodiment is generated by the ith request for a passcode. In an embodiment, each passcode, P.sub.i, is generated by using a different generator G.sub.i.In an embodiment, each new generator, G.sub.i+1, may be generated from a prior generator, G.sub.i, using a method f, according to the equation, f(G.sub.i)=G.sub.i+1, for example.
In embodiments that use a graphical (e.g. LCD) display for the registration code and/or passcode, the function .phi..sub.3 may be equal to D .degree. .phi._where D is a display function and .phi. is, for example, a one-way hash function. An example of a display function D, entitled code_to_alphanumeric_no_IO, may be implemented in the C programming language as follows:
//Does not return little `I` and capital `O`: 60 distinct symbols UNSIGN_8_BITS convert_alphanumeric_no_IO (UNSIGN_8_BITS c) {
if (val<11) return (`a`+val);
else if (val<25) return (`m`+(val-11));
else if (val<35) return (`0`+(val-25));
else if (val<49) return (`A`+(val-35));
else return (`P`+(val-49)); }
In general, the output of .phi..sub.3(G.sub.i) is a sequence of bytes and each of these bytes may be a value ranging from 0 to 255. In embodiments where there is a graphical display of the registration and/or passcode, the display function D is helpful because some byte values have a graphical output that is difficult to read by a user, (letter O versus the number 0), unreadable such as an end of file character, or a character that is difficult for a person to reliably describe, such as `&`, which some people do not know is call an ampersand. The primary purpose of the display function D is to convert unreadable or difficult-to-read byte values to readable byte values.
Setup 108, request for access 110, reply 112, and access to secure device 114 are different forms of communications in which passcode device 101 participates. Setup 108, request for access 110, and reply 112 are embodiments of the communications represented by the lines connecting passcode device 101, administrator 102, and secure entity 103 in FIG. 1B. In an embodiment, passcode device 101 may send registration code R to another entity, when sending setup 108. In an embodiment, passcode device 101 sends a user ID U with the registration code R to another entity or elsewhere as part of setup 108. Alternatively, passcode device 101 receives the user ID U from the other entity or from elsewhere. Request access 110 is a request for access to secure device 103. Request 110 may include sending passcode P.sub.i, for example. In an embodiment, user ID U is also sent as part of request 110.
Administrator 102 includes setup portion 116, which uses registration code R received from passcode device 101, to generate the initial passcode generator G.sub.1. In alternative embodiments, setup portion 116 may be located outside of administrator 102. Since administrator 102 may service several passcode devices 101 and/or several users, user ID U may be used to associate a registration code R, the generators G.sub.i, and the passcodes generated with a passcode device 100 and/or a user U, which may be written as R.sub.U and G.sub.Ui, respectively. In this notation, the index U distinguishes the registration code R.sub.U at the administrator's side.
Since administrator 102 may need to authenticate the passcode submitted by passcode device 101, administrator 102 may need to generate the same set of passcodes as passcode device 101 in order to perform the authentication. Administrator 102 may generate the passcodes generated by passcode device 101 by using the same methods (e.g., one-way functions such as one-way hash functions or random number generators) and generators as used by passcode device 101. Consequently, administrator 102 uses method .phi..sub.U2 to generate an initial passcode generator G.sub.U1, Method .phi..sub.U2 may be the same for all U as long as the registration codes R.sub.U are different for each of the U's. In an embodiment, methods .phi..sub.U2 are in general different for each U. If methods .phi..sub.U2 are different, then the R.sub.U's do not need to necessarily be different so long as the resulting passcodes for different users are in general different. The passcodes of different users can be different if methods .phi..sub.U3 or passcode generators G.sub.ui are different for different users, while the G.sub.Ui's will be different for different users if methods .phi..sub.U2 and/or R.sub.U are different.
Similar to passcode device 101, administrator 102 may generate the initial passcode generator G.sub.U1 according to the equation .phi..sub.U2(R.sub.U)=G.sub.U1. In an embodiment, for a given authorized user U, .phi..sub.U2, R.sub.U, and G.sub.U1 are the same as .phi..sub.2, R, and G.sub.1.
Administrator 102 also includes request portion 118. In alternative embodiments, request portion may be located outside of administrator 102. For example, request portion 118 may be stored and executed on a system having a database that stores information being accessed. Request portion 118 receives, via request 110, passcode P.sub.i and user ID U from request portion 106 of passcode device 101. Database 122 may be part of administrator 102, as illustrated in FIG. 1B, or may be located elsewhere. Database 122 may store current passcode generators and/or other user information. In an embodiment, based on user ID U, request portion 118 receives a passcode generator form database 122, and generates a passcode that is compared with the passcode, P.sub.i received from the passcode device. The passcode p.sub.i generated is expected to be same passcode that user U sent with the current request if user U is an authorized user.
For example, request portion 118 may use method .phi..sub.U3 and a passcode generator, G.sub.Ui, for generating a passcode P.sub.Ui. Method .phi..sub.U3 may be the same as or different from method .phi..sub.U2. For example, request portion 118 computes a passcode using the equation, .phi..sub.U3(G.sub.Ui)=P.sub.Ui. Each passcode, P.sub.Ui, is generated by using a different passcode generator G.sub.Ui. Each new passcode generator, G.sub.Ui+1, may be generated from a prior passcode generator, G.sub.Ui, using method f.sub.U, according to the equation, f.sub.U(G.sub.Ui) =G.sub.Ui+1, for example. Request portion 118 compares passcode P.sub.Ui to passcode P.sub.i, and if passcode P.sub.Ui and passcode P.sub.i are the same, authorization to access to secure entity 103 is granted from request portion 118 of administrator 102, via reply 112, to the user associated with passcode device 101.
Method .phi..sub.U3 and f.sub.U may be the same for all U as long as the passcode generators G.sub.Ui and G.sub.Ui+1 are different. In an embodiment, methods .phi..sub.U3 and f.sub.U are in general different for different U. In an embodiment, for a given authorized user U, .phi..sub.U3, f.sub.U, G.sub.Ui, and G.sub.Ui+1 are the same as .phi..sub.3, f, G.sub.i, and G.sub.i+1, respectively, except that .phi..sub.U3, G.sub.Ui, and G.sub.Ui.degree.1 are generated in association with administrator 102 and .phi..sub.3, f, G.sub.i, and G.sub.i+1 are generated at passcode device 101. Setup portion 116 and request portion 118 may be separate portions of code, such as objects, subroutines, functions, and/or methods. Setup portion 116 and request portion 118 may not be separate portions of code, but may be lines of code intermingled with one another and/or other parts of administrator 102.
To explain setup API 145 in conjunction with setup portion 156, setup API 145 may cause user information, such as passcode generators G.sub.Ui to be stored in database 160. Setup API 145 may cause methods .phi..sub.2 and/or .phi..sub.U3 to be stored within administrator 102 for use by setup portion 156. Methods .phi..sub.2, .phi..sub.U3, and/or f.sub.u may also be stored within administrator 102 for use by setup portion 156.
Request portion 158 may contain proprietary executable code that receives a passcode from request API 147. Request portion 158 may determine whether passcode P.sub.i is valid or not.
Regarding database 160, database 160 may have existed prior to the installation of system 100, and may store a variety of different types of information, some of which may have not had any relationship to granting access to the secure entity 103. When configuring system 100 or when setting up a new user, if database 160 already exists and already has a records for the user of interest, system 100 may add a field to the record for a user ID U and for a passcode generator G.sub.Ui. In an alternative embodiment, database 160 is within administrator 102, and is installed with and/or after administrator 102.
In an embodiment, setup portion 156 determines if registration code R is valid, and sends a valid or invalid message back to setup API 145. The determination of whether registration code R is valid may be a determination as to whether registration code R fits a particular format. If administrator 102 stores a copy of the user information from which registration code was derived, then the determination as to whether registration code is valid may include generating the registration code at registration portion 156, comparing the generated registration code with the received registration code. Determining whether registration code R is valid may involve verifying that the user associated with registration code R exists, determining whether user ID U is valid, and/or verifying other user information code R is valid may involve administrator 102 sending a communication to passcode device 101 or the associated user confirming that the registration code was sent. If valid, the setup API 145 also sends a passcode generator G.sub.Ui (generated from registration code R) and may optionally send other user information, such as the user ID U, to database 160.
When a user would like to access secure entity 103, a passcode P.sub.i is entered into, transmitted to, and/or received by request API 147 based on output from passcode device 101. Request API 147 calls request portion 158, using passcode P.sub.i as an argument. User ID U may be encoded within passcode P.sub.i, and request portion 158 may extract user ID U for passcode P.sub.i. Request portion 158 may return user ID U to request API 147. If passcode P.sub.i is invalid, request portion 158 may return an invalid user ID U. Alternatively, instead of request portion 158 extracting the user ID U from passcode P.sub.i, the user may enter user ID U into request API 147, or request API 147 may receive user ID U from passcode device 101.
Administrator 102 uses user ID U as a database index for the purpose of retrieving passcode generator G.sub.Ui from the database 160. If user ID U is an invalid index, then administrator 102 sends an invalid message to request API 147. If user ID U is a valid index, the administrator 102 sends passcode generator G.sub.Ui to request API 147. Request API 147 calls request portion 158, and sends two arguments, passcode P.sub.i and passcode generator G.sub.Ui, which are received by request portion 158. Request portion 158 determines whether passcode P.sub.i and passcode generator G.sub.Ui match. If passcode P.sub.i and passcode G.sub.Ui match, then request portion 158 returns a valid message and the updated passcode generator G.sub.Ui+1=f(G.sub.Ui) to request API 147. Administrator 102 stores passcode generator G.sub.i or an updated version of passcode generator G.sub.Ui+1 in database 160, such that passcode generator G.sub.i or its updated version is indexed by user ID U. However, if passcode P.sub.i and passcode generator G.sub.Ui do not match, the request portion 158 returns and invalid message to request API 147. Then request API 147 may send an invalid message to the user U, a human administrator, and/or passcode device 101.
Passcode circuitry 602 generates passcodes P.sub.i, registration codes R, passcode generators G.sub.i or G.sub.Ui, and communicates with administrator 102. Passcode circuitry 602 authenticates information acquired from the user and decides whether to generate a passcode, based on the information. Passcode circuitry 602 may implement setup portion 104 request portion 106. Passcode circuitry 602 may include a processor chip. Alternatively, passcode circuitry 602 may send instructions to be processed by a processor associated with computer 204 (FIG. 2) and/or include specialized logic circuits for performing specific functions.
In yet another embodiment, user information is used to generate registration code R, passcode generator G.sub.i, and/or passcodes P.sub.i within secure area 604. Secure area 604 may store method f, method .phi..sub.1, method .phi..sub.2, and/or method .phi..sub.3. The use of fingerprints or other user information to create passcodes within secure area 604 or the use of fingerprints or other user information instead of passcodes within a secure area eliminates or reduces the need to memorize and store passcodes in an unsecure system.
User information 606 may also be stored in secure area 604. User information 606 may include, or may be information derived from, any of the forms for user information and identifying information discussed above (e.g., fingerprints, iris scans. etc.), registration code R, method f, method .phi..sub.1, method .phi..sub.2, and/or method .phi..sub.3, and/or passcode generator G.sub.i. Storing passcode generator G.sub.i in secure area 604 may facilitate quickly generating a one-time passcode, because the user does not need to wait for passcode generator G.sub.i to be generated.
FIG. 7 shows a flowchart of and example of a method for setting up passcode device 101. During step 702, identifying information T is acquired by passcode device 101. For example one or more fingerprints, one or more images of the face, one or more images of eyes, or other pieces of identifying information T are acquired. Optionally, information may be extracted from the identifying information. Optionally. identifying information T is also acquired by administrator 102. For example, administrator 102 may be associated with a bank, and the bank may require that the user visit the bank so that the identifying information T (e.g., fingerprints) can be acquired in person. During step 704, one or more unique registration codes R are generated from the one or more of the fingerprints, which may be generated according to the equation .phi..sub.1(T)=R. In an embodiment, during step 704, in the secure area 604 of the passcode device 101, fingerprint information obtained from the user is passed to method which may be a one-way function or another method of encoding that generates a registration code, R.
During step 706, registration code R is securely given to administrator 102. Registration code R is created during step 704, and securely given to administrator 102 during step 706. The registration code R may be given to administrator 102 in the same physical place, such as at a bank, or registration code R may be mailed or electronically transmitted to administrator 102 if the Setup is accomplished remotely. In some applications, registration code R may be encrypted first and then electronically transmitted or sent by mail. In the embodiment in which administrator 102 is associated with an entity that has acquired identifying information T, administrator 102 causes the identifying information to be authenticated, thereby verifying that the user is legitimate. Optionally, registration code R is stored and indexed by administrator 102 according to user ID U, as R.sub.U. Alternatively, even if identifying information T is not collected by administrator 102, other information may be checked to determine the validity of registration code R. For example, other identifying information may be sent with registration code R or the format of registration code R may checked to determine whether registration code R is valid.
During step 708, and initial passcode generator G.sub.1 is created and stored in flash memory, a cache, or other memory of the processor contained in the secure area 604 (FIG. 6) of passcode device 101. Initial passcode generator G.sub.1 may be created according to equation .phi..sub.2(R)=G.sub.1. Initial passcode generator G.sub.1 may then be stored for later use in generating and initial passcode P.sub.1 according to P.sub.1+.phi..sub.3(G.sub.1). During this later use of initial passcode generator G.sub.1 after generating passcode P.sub.1a, passcode P.sub.1 is subsequently transmitted to the host (e.g., administrator 102) for authentication. In this embodiment, passcode P.sub.1 is not stored at passcode device 101, but is created just prior to being used and then discarded just after being used to reduce the chance of passcode P.sub.1 being stolen. In an alternative embodiment, passcode P.sub.1 can also be stored in secure area 604 of the processor to reduce execution time at passcode device 101.
Similarly, at administrator 102, the initial passcode generator G.sub.1 is created and stored. Optionally, as part of storing initial passcode generator G.sub.1, initial passcode generator G.sub.1 is indexed according to a user ID U as G.sub.U1, Similarly, each subsequent passcode generator G.sub.i may be stored and indexed according to user ID U, as G.sub.Ui, In this embodiment, passcode P.sub.1 is not stored at administrator 102, but is created just prior to being used and then discarded just after being used to reduce the chance of passcode P.sub.1 being stolen. In an alternative embodiment, passcode P.sub.1 can be generated at administrator 102 immediately after generating passcode generator G.sub.1 and then passcode P.sub.1 can also be stored in database 122 or 160 to reduce execution time at administrator 102. In other embodiments, method 700 may not have all of the steps listed above or may have other steps instead of and/or in addition to those listed above. Additionally the steps of method 700 may not be distinct steps.
FIG. 8 is a flowchart of an example of a method 800 of generating a passcode. In step 802, the passcode generator G.sub.i is retrieved form a secure area 604 (FIG. 6). In the notation of this specification, if this is the first time passcode device 101 is being used after registration, the index i is equal to 1, passcode generator G.sub.i is the initial passcode generator G.sub.1. In step 808, a method .phi..sub.3 is applied to a passcode generator G.sub.i, denoted as .phi..sub.3(G.sub.i), to create passcode P.sub.i. In other words, P.sub.i=.phi..sub.3(G.sub.i).
In step 806, the passcode generator G.sub.i is changed to a new value G.sub.i+1, where G.sub.i+1 is set equal to the new value f(G.sub.i). There are an infinite number of functions that f could be. The method f may be referred to as a perturbing method (e.g., a perturbing function). One possible perturbing method f could add .phi..sub.3(G.sub.i) to G.sub.i. Another possible perturbing function could be f(G.sub.i)=.phi..sub.3(G.sub.i+.phi..sub.3(G.sub.i)). More generally, the perturbing function f(G.sub.i)=(.phi.(G.sub.i) * G.sub.i) or f(G.sub.i)=.phi.(G.sub.i * .phi.(G.sub.i)), where "*" may be any operator. For example, "*" may be binary operators such as +, -, OR, NOR AND, NAND, XOR, , NOT(XOR). Another possible perturbing method f could consider passcode generator G.sub.i as a number and add 1. Another possible perturbing method f could increase passcode generator G.sub.i by 2. Another possible perturbing method f could add 1 to passcode generator G.sub.i and permute the order of the symbols in passcode G.sub.i using some randomly chosen permutation. Even another possible perturbing method f could add 1 to passcode generator G.sub.i, and then permute the bits in passcode generator G.sub.i, Passcode generator G.sub.i could be used as a seed for a random number generator, which is used as f to generate G.sub.i+1. Steps 804 and 806 may be performed concurrently or in any order with respect to one another. Step 806 may be performed at anytime after step 802.
In step 808, a passcode P.sub.i (e.g., a one time passcode) is either transmitted to a display or submitted directly to administrator 102. During transmission, in some cases P.sub.i can be encrypted for additional security, for example in a wireless transmission. There are many different methods for transmitting the passcode P.sub.i to the administrator 102. In one method, passcode P.sub.i can be displayed to administrator 102 (e.g., if administrator 102 is a human being or if administrator 102 includes a scanner that can scan the display) when the user is in the same physical location as administrator 102. In a second method, the user may transmit passcode P.sub.i over the phone (e.g., via a phone call and human voice or via a modem and an electronic signal). In a third method, the user may submit the passcode P.sub.i using the Internet. The user may submit the passcode P.sub.i by other electronics means such as a fax machine or an ATM machine. Step 808 may be performed anytime after step 804. Steps 806 and 808 may be performed concurrently or in any order with respect to one another. In other embodiments secure module 800 may not have all of the steps listed above or may have other steps instead of and/or in addition to those listed above. Additionally the steps of method 800 may not be distinct steps.
FIG. 9 shows a flowchart of method 900 of authenticating a passcode P.sub.i. Method 900 may be performed in response to step 808 of method 800 (FIG. 8). In step 902. administrator 102 enters or receives passcode P.sub.i from the user. In an embodiment in which administrator 102 caused passcode generator G.sub.i to be indexed according to user ID U, step 902 may include at least two parts, which are step 904 and 906. In step 904, passcode P.sub.i is received, and in step 906 user ID U is received, User ID U aid passcode P.sub.i may be sent as two separate sequences of bits. Alternatively, user ID U and passcode P.sub.i may be sent as one sequence of bits in which user ID U is encoded within passcode P.sub.i. If User ID is encoded within passcode P.sub.i, then receiving user ID U includes extracting user ID U from P.sub.i. In another embodiment, passcode P.sub.i and user ID U may be concatenated together or otherwise encoded within the same sequence of bits. Step 906 is optional, and passcode P.sub.i may be sent without any user ID.
In step 908, user ID U is associated with a passcode generator G.sub.Ui, and passcode generator G.sub.Ui is retrieved. Alternatively, in an embodiment in which passcode generators G.sub.i are not indexed according to user ID U, for example, a set of all possible passcode generators G.sub.i may be retrieved. In step 910, for each passcode generator G.sub.i in the database, a method .phi..sub.3 is applied to passcode generator G.sub.i, denoted as .phi..sub.3(G.sub.i), and .phi..sub.3(G.sub.i)=P.sub.Ui is compared to passcode P.sub.i. Alternatively, if the passcode generators are indexed, the passcode generator G.sub.Ui that is associated with user ID U, a method .phi..sub.3 is applied to passcode generator G.sub.Ui, denoted as .phi..sub.3(G.sub.Ui), and .phi..sub.3(G.sub.Ui)=P.sub.Ui is compared to passcode P.sub.i.
In step 912, if the passcode generators are indexed, a decision is made as to whether .phi..sub.3(G.sub.Ui) equals passcode P.sub.i. If the passcode generators are not indexed, a decision is made as to whether there is any .phi..sub.3(G.sub.i) that equals passcode P.sub.i. If .phi..sub.3(G.sub.Ui) equals passcode P.sub.i or if there is a .phi..sub.3(G.sub.i), that equals passcode P.sub.i, then the passcode P.sub.i submitted by the user is valid, method 900 continues with step 914. In step 914, access to secure entity 103 is granted. Next, in step 916, the value stored for the passcode generator is set equal to a new value G.sub.Ui+1=f(G.sub.Ui) or G.sub.i+1=f(G.sup.i) where f is a method, which may be one of the infinite number of perturbing methods (e.g., perturbing functions), as discussed above. If the passcode generators G.sub.i are not indexed according to user ID, the method f is applied only to the passcode generator that matched the submitted passcode P.sub.i. After step 916, method 900 terminates.
Returning to step 912, if .phi..sub.3(G.sub.Ui) does not equal to P.sub.i or if there is no .phi..sub.3(G.sub.i) that equals P.sub.i, then the passcode P.sub.i submitted by the users is invalid, method 900 continues with step 918 where access is not granted. After step 918, in optional step 920 a further check is performed to see if P.sub.i is valid in case there was a human error. Step 920 is discussed further in conjunction FIG. 10. If step 920 is not included in method 900, then step 918 may also include sending a message to the user that passcode P.sub.i is invalid. In other embodiments method 900 may not have all of the steps listed above or may have other steps instead of and/or in addition to those listed above. Additionally the steps of method 900 may not be distinct steps.
FIG. 10 shows a flowchart of an example of a method for carrying out step 920 of the method 900. In step 1002 an initial trial passcode generator, G.sub.TUi, is computed according to f(G.sub.Ui)=G.sub.TUi. In other words, if the user generated a passcode P.sub.i, but never submitted passcode P.sub.i, then the value of passcode generator G.sub.i at passcode device 101 will be different from passcode generator G.sub.Ui or the set of passcode generators G.sub.i at administrator 102. Consequently, one manner for correcting this problem is to advance the value of passcode generator G.sub.Ui or the set of passcode generators G.sub.i to that of the next index value of i, which is accomplished by applying the perturbing method to the current value of passcode generator G.sub.Ui or of the set of passcode generators G.sub.i. If the passcode generators are not indexed according to user, then the perturbing method needs to be applied to all of the current values of passcode generator G.sub.i to obtain a set of initial trial passcode generators G.sub.Ti.
Next, in step 1004, for trial passcode generator G.sub.TUi or for each trial passcode generator G.sub.Ti a trial passcode P.sub.TUi or a set of trial passcodes P.sub.Ti are generated according to .phi..sub.3(G.sub.TUi)=P.sub.TUi or .phi..sub.3(G.sub.Ti)=P.sub.Ti. In step 1006, P.sub.i is compared to each of the P.sub.Ti or P.sub.TUi. If passcode P.sub.TUi matches passcode P.sub.i or if there are any trial passcodes P.sub.Ti that match passcode P.sub.i, then step 920 proceeds to step 1008, where access is granted. As part of step 1008, the value of a trial passcode generator G.sub.TUi is updated, and the updated value of trial passcode generator G.sub.TUi+1 is used to replace passcode generator G.sub.Ui or the updated value of trial passcode generator G.sub.Ti+1 is used to replace the passcode generator of the set of passcode generators G.sub.i from which trial passcode generator G.sub.Ti+1 was generated. After step 1008, step 920 terminates.
Returning to step 1006, if passcode P.sub.TUi does not match passcode P.sub.i or if there are no trial passcode P.sub.Ti that match passcode P.sub.i, then step 920 proceeds to step 1010, where a determination is made as to whether the maximum number of trials has been reached. In other words, it is possible that the user generated multiple passcodes P.sub.i and consequently passcode generator G.sub.Ui or one of the set of passcode generators G.sub.i associated with administrator 102 may lag the value of passcode generator G.sub.i at passcode device 101 by several values of index i. Consequently, step 920 may try several applications of perturbing method f before deciding that passcode P.sub.i is invalid. Thus, step 920 may be configured for applying f up until a maximum number of trials. If that maximum has been reached without finding a match, then step 920 proceeds from step 1010 to step 1012, and access is not granted. After step 1012, step 920 terminates.
Returning to step 1010, if the maximum number of trial has not been reached, then step 1010 proceed to step 1014 where the perturbing method f is applied to the trial passcode generator G.sub.TUi or trial set of passcode generators G.sub.Ti according to f(G.sub.Ti)=G.sub.Ti+1 or f(G.sub.UTi)=G.sub.UTi+1. Next in step 1016, a new passcode P.sub.UTi+1 or set of passcodes P.sub.Ti+1 are generated according to .phi..sub.3(G.sub.Ti) =P.sub.Ti+1 or .phi..sub.3(G.sub.UTi)=P.sub.UTi+1. After step 1010, step 1006 is repeated. Steps 1006, 1010, 1014 and 1016 are repeated until either the maximum number of trials is reached and access is not granted in step 1012 or until a match trial passcode is found, and access is granted in step 1008. In other embodiments, method 1000 may not have all of the steps listed above or may have other steps instead of and/or in addition to those listed above. Additionally the steps of method 1000 may not be distinct steps.
FIG. 11 shows a flowchart of an example of a method 1100 for registering a user. Method 1100 is an embodiment of, or may be used as a replacement for, steps 704 and 706 of method 700. In step 1102, the registration code, and optionally other user information, is entered into, transmitted to, and/or received by setup API 145 (FIG. 1C), based on output from passcode device 101. In response, in step 1104 setup API 145 calls setup portion 156 (FIG. 1C) located in administrator 102 (FIG. 1C), and passes registration code R as an argument to setup portion 156 in administrator 102. In step 1106, setup portion 156 determines whether the registration code R is valid. If setup portion 156 determines that registration code R is invalid, method 1100 proceeds to step 1108. In step 1108, a message is sent to setup API 145 that registration code R is invalid. After step 1108, method 1100 terminates. Returning to step 1106, if setup portion 156 determines that registration code R is valid, method 1100 proceeds to step 1110. In step 1110, setup portion 156 sends a passcode generator G.sub.Ui or G.sub.i and a message back to setup API 145 that registration code R is valid. Setup portion 156 may also send other information to setup API 145, such as user ID U or other information.
Next, in step 1112, if the registration code R is valid, then setup API 145 transmits arguments, the passcode generator G.sub.Ui or G.sub.i and optionally user ID U (which may be used as a database index) to database 160. Optionally, other user information may also be sent to database 160. In other embodiments method 1100 may not have all of the steps listed above or may have other steps instead of and/or in addition to those listed above. Additionally the steps of method 1100 may not be distinct steps.
FIGS. 12A and 12B show a flowchart of an example of a method 1200 for authenticating a passcode at administrator 102. Method 1200 is an alternative to method 900. In step 1202, a passcode P.sub.i is received by request API 147. For example, passcode P.sub.i is entered into request API 147 or transmitted to request API 147. In step 1204, administrator 102 retrieves P.sub.i from its request API 147. In step 1206, administrator 102 places user ID U in request API 147. In step 1208, request API 147 sends user ID U to database 160. In step 1210, database 160 decides whether user ID U is valid. Database 160 attempts to retrieve passcode generator G.sub.Ui or G.sub.i by looking up user ID U. Database 160 may discover that user ID U does not exist, and therefore is invalid. If user ID U is invalid, then method 1200 proceeds to step 1212. In step 1212, administrator 102 sends an invalid message to request API 147. After step 1212. method 1200 ends. Returning to step 1210, if user ID U is valid, then method 1200 proceeds to step 1214 where administrator 102 sends passcode generator G.sub.Ui to request API 147. Next, in step 1216, request API 147 calls request portion 158, and sends two arguments, passcode P.sub.i and passcode generator G.sub.Ui to determine whether passcode P.sub.i and passcode generator G.sub.Ui match.
In step 1218, request portion 158 determines whether passcode P.sub.i and passcode generator G.sub.Ui match. In general, the output of .phi..sub.3(G.sub.Ui) is a sequence of bytes and each of these bytes may be a value ranging from 0 to 255. Thus, P.sub.i and G.sub.Ui match if P.sub.i=.phi..sub.3(G.sub.Ui).
Step 1218 may also include applying an error handling routine, such as method 1000 (FIG. 10), prior to concluding that passcode P.sub.i and passcode generator G.sub.Ui do not match. Thus, a determination that passcode P.sub.i and passcode generator G.sub.Ui match may involve one or more prior determinations that passcode P.sub.i and trial passcode generator G.sub.UTi do not match.
If passcode P.sub.i and passcode generator G.sub.Ui match, then method 1200 proceeds to step 1220. In step 1220 request portion 158 updates G.sub.Ui according to f(G.sub.Ui) =G.sub.Ui+1, returns the updated passcode generator G.sub.Ui+1 and a message that passcode P.sub.i is valid to request API 147. In step 1222. request API 147 calls administrator 102, and sends a message that passcode P.sub.i is valid, and sends the updated passcode generator G.sub.i+1 as an argument. Optionally, user ID U is also sent to administrator 102. In step 1224, administrator 102 causes updated passcode generator G.sub.i+1 to be stored in database 160, indexed by user ID U. After step 1224, method 1200 is terminated.
Returning to step 1218, if passcode P.sub.i and passcode generator G.sub.Ui do not match, the method proceeds to step 1226. In step 1226. the request portion 158 returns an invalid message to request API 147. Next, instep 1228. request API 147 calls administrator 102, and sends a message that passcode P.sub.i is invalid. After step 1228, method 1200 terminates. In other embodiments method 1200 may not have all of the steps listed above or may have other steps instead of and/or in addition to those listed above. Additionally the steps of method 1200 may not be distinct steps.
FIG. 13 is a flowchart of an example of method of installing system 100. In step 1302 the administrator is installed. For example, administrator 102 may be installed on a computer that is separate from secure entity 103. If the system on which system 100 is being installed has other software, the administrator may be integrated into that software or may be installed as a separate software module. Installing administrator 102 may involve installing setup portion 116 or 156 and request portion 118 or 158. In optional step 1306, an API is installed. In an embodiment, step 1306 may involve installing a request API 147 and a setup API 145. In step 1308, an offer is made to allow the installer to choose whether to use a preexisting database. If the choice of using a preexisting data is chosen, in step 1310 the API is configured to communicate with the database. Step 1310 may involve adding to database .160 a field for storing passcode generators to each user record. Step 1310 may additionally involve adding a field for a user ID U to each user record. For example, database 160 may not have field for user IDs or may use different user IDs than system 100. Of course, database 160 may have two fields for user IDs--one field in a location where system 100 is configured for accessing, and another which system 100 is not configured to access. Alternatively, the database may already have a field for a user ID, and the same user ID is used for system 100. Returning to step 1308. if a choice is made to not use any preexisting database, then in step 1312, a database, a file, part of a file, or part of a database is setup for storing passcode generators, which may be indexed according to a user ID. In an embodiment, the passcode generators are not indexed according to user ID. In other embodiments, method 1300 may not have all of the steps listed above or may have other steps instead of and/or in addition to those listed above. Additionally, steps 1302, 1304, 1306, and 1308 may be performed concurrently or in any order with respect to one another. Steps 1310 and 1312 may be performed any time after step 1308, but otherwise may be performed in concurrently or in any order with respect to steps 1302, 1304, and 1306. Additionally the steps of method 1300 may not be distinct steps.
FIG. 14 is a flowchart of an example of a method 1400 for assembling passcode device 101. In step 1402, passcode circuitry 602 (FIG. 6) is assembled, which may include installing onboard memory (e.g., secure area 604). In step 1404, the acquisition mechanism 608 (FIG. 6) is coupled to the passcode circuitry 602. In step 1406, interface 610 (FIG. 6) is coupled to passcode circuitry 602. In step 1408, an embedded program (e.g., program 605) is configured for generating registration codes R, passcode generators G.sub.i, and passcodes P.sub.i, and for using the onboard memory for work space and for storing passcode generators. In step 1410, passcode circuitry 602, acquisition mechanism 608, and interface 610 are enclosed within a housing that is small enough to fit within a user's hand (e.g., shorter than a typical pen and no more than a two or three times wider than a typical pen). For example, the housing may be 2 to 6 inches long and less than a half inch in diameter. The passcode device 101 may be of a size that is comparable to a thumb print. In other words, passcode device 101 only need to be large enough to accept user information. In embodiments where the user information is fingerprints, the passcode device 101 could be the size of a portion of a thumb large enough to capture a thumb print during a swipe, for example. In embodiments where acquisition mechanism is a camera, passcode device 101 does not need to be much larger than a small camera. In an embodiment, passcode device 101 is less than 6 inches, less than 2 inches, less than an inch, or less than a centimeter in size. In other embodiments method 1400 may not have all of the steps listed above or may have other steps instead of and/or in addition to those listed above. Additionally, the steps of method 1400 may be performed in, other orders, may not be distinct steps, and/or many of the may be performed concurrently with one another. Additionally the steps of method 1400 may not be distinct steps.
A particular application of system 100 is a child identity program. System 100 enables the government to identify a child with a unique registration code R or with a passcode P.sub.i, which is never stored anywhere. For example, the FBI can store a database of registration codes R, but a database intruder would not have access to the biometric data. social security number, or other data of any child. Alternatively, the FBI can store a database of generators G.sub.i, which change each time a new passcode P.sub.i is submitted. Consequently, in addition to the database intruder not having access to the biometric data of any child, the information stolen (passcode generator G.sub.i) is of little use to the intruder in identifying the child, because passcode generator G.sub.i changes periodically, such as with each legitimate access of the data. Similarly, no authorized FBI employee would have access to the biometric data of any child. Consequently, the passcode generator helps act as a child ID for safety, yet also protects private information about the child.
Memory 1510 may be incorporated within encryption key circuitry 1508 and may include volatile and nonvolatile memory. The use of non-volatile memory enables the secure module 1502 to permanently store user information, executable code, and/or encryption keys. In some embodiments, the memory 1510 is on (e.g., "onboard") encryption key circuitry 1508. Memory 1510 may include embedded instructions that are executed by encryption key circuitry 1508.
Encryption keys 1522 may include one or more encryption keys, which are codes (sequences of bits or symbols) that are used for generating passcodes. Encryption keys 1522 may be used by an encryption algorithm to encrypt and/or decrypt data. In this specification, encryption keys 1522 may also be represented by the symbol K.sub.d. Encryption keys 1522 may be stored on secure module 1502. Encryption keys 1522 may be stored in the internal memory (e.g., memory 1510) of encryption key circuitry 1508. One or more fingerprint images and/or other user data may be used to determine values for encryption keys 1522. Using user information 1520 to create encryption keys 1522 helps ensure that the encryption key of each user is unique. Encryption keys 1522 may be used as seed values for an encryption method that is implemented on an unsecured system. In another embodiment, encryption keys 1522 are not used as seed values, but are just an access code, which may be referred to as an access key, for a method or other entity associated with the unsecured system.
Generate encryption keys 1523 may be a "one-way" method, which is a method for which finding an inverse or for which finding the input based on the output is expected to be difficult or intractable. Throughout this specification generate encryption keys 1523 may be replaced with instructions for generating access keys to obtain a different embodiment. Stated differently, a one-way method .phi. has the property that given an output value z, it is not possible or computationally extremely difficult to find an input (e.g., message) mz such that .phi.(mz)=z. For some one-way functions, it could take over 10.sup.30 years of computer processor execution time to compute .phi..sup.-1(z). In other words, a one-way method .phi. is a method that can be easily computed, but that has an inverse .phi..sup.-1 that is extremely difficult (e.g., impossible) to compute. One manner of quantifying the difficulty of finding m.sub.z (given an output z) is to use the number of computations that are expected to be required to compute and/or guess m.sub.z. For one type of method, it is expected to take between O(2.sup.n/2) and O(2.sup.n) (e.g. between 2.sup.n/2 and 2.sup.n) computational steps to find or guess m.sub.z, (depending on the how clever the one performing the computations is), where n is the number of bits in the output z. The method .phi. (which may be referred to as a generating method) may be a one-way algorithm, a one-way function, and/or another one-way method. By using a one-way method for computing encryption keys 1522, even if one of encryption keys 1522 is intercepted, stolen, or otherwise obtained, it is unlikely that the encryption key can be used to discover user information 1520 or (if user information 1520 was derived from user data) used to discover the user data from which user information 1520 was derived.
As another example, one-way method .phi. could involve first representing user information 1520 by a string of digits. Then, each digit of the string of digits could be multiplied by a corresponding digit from another string of digits, where at least one digit of the other string has a value of zero. The inverse of this method would involve at least one division by zero for each multiplication by a digit with the value of zero, which has no inverse, and consequently this method would also be one-way. Similarly, functions for which finding their inverses involves computing a non-convergent series or non- convergent integral are other examples of classes of functions that may be used as one-way methods.
In an embodiment, generate encryption key 1523 includes a hash function. A "hash function," denoted .phi., is a function that accepts as its input argument an arbitrarily long string of bits (or bytes) and produces a fixed-size output. In other words, a hash function maps a variable length input m to a fixed-sized output, .phi.(m). Typical output sizes range from 128 to 512 bits, but can also be larger or smaller. An ideal hash function is a function .phi. whose output is "uniformly distributed".In other words, suppose the output size of .phi. is n bits. If the message m is chosen randomly, then for each of the 2.sup.n possible outputs for z, the probability that .phi.(m)=z is 2.sup.-n. In an embodiment, the hash functions used in generate encryption key 1523 are one-way.
In contrast to an ideal hash function, if the input m is chosen randomly, then for each of the 2.sup.n possible outputs for z, the probability that .phi.(m)=z is a value P, which is compared to 2.sup.-n. In an embodiment, the hash function is designed so that P is relatively close to 2.sup.-n. How close P is to 2.sup.-n is a measure of the quality of the hash function. The chi-square function on n-1 degrees of freedom is a useful way to measure the quality of a real hash function. One uses a chi-square on n-1 degrees, because there are n bits of output. A confidence level that the real hash function is close to an ideal hash function (or has a certain quality) can be computed based on the chi-square function. Some typical confidence levels could be at least 90%, at least 95%, at least 99%, at least 99.5%, at least 99.999%, or greater depending on the level of security desired. In an embodiment, these confidence levels may represent a confidence that at least 2.sup.n/100 to 2.sup.n computations are required to find the inverse of the hash function. In another embodiment, the above confidence levels represent a confidence that at least 2.sup.n/2 2.sup.n computations are required to find the inverse of the hash function. In an embodiment, these confidence levels may represent a confidence that at least 2.sup.log(n) to 2.sup.n computations are required to find the inverse of the hash function. In an embodiment, these confidence levels may represent a confidence that at least .9(2.sup.n) to 2.sup.n computations are required to find the inverse of the hash function. In an embodiment, the hash functions that are used are one-way. Other types of one-way functions or methods may be used in place of a hash function.
Any of a number of hash functions may be used for one-way method .phi.. One possible hash function is SHA-256, designed by the National Security Agency and standardized by the NIST, [NIST_STANDARDS_1995], which is incorporated herein by reference. The output size of SHA-256 is 256 bits. Other examples of alternative hash functions are of those that are of the type that conforms to the standard SHA-1, which produces output values of 160 bits, and SHA-512, which produces output values of 512 bits, see [NIST_STANDARDS_2001], which is incorporated herein by reference.
There are different methods that may be used for hashing user information 1520, such as fingerprints. Different types of methods of hashing user information 1520 are appropriate for different sizes of encryption keys, and different types of user information 1520 that may be passed to the hash function. One method is to take two different pieces of user information 1520 (e.g., two fingerprints) and apply the hash function SHA-256 to each piece of user information 1520. For ease of explanation, denote the hash function SHA-256 as .phi..sub.1. Each application of to user information 1520 produces an output value of 256 bits. With two pieces of user information 1520, (e.g., two fingerprints), these bits are concatenated together to create a 512-bit encryption key, called K.sub.d. Another method is to use two different sections S and T of a single acquired set of pieces of user data (e.g., two sections of one fingerprint), and produce a 512-bit encryption key, K.sub.d, by concatenating .phi..sub.1(S) and .phi..sub.1(T). An enhancement of this method can be used to create encryption keys larger than 512-bits. Divide one acquired piece of user information 1520 (e.g., one fingerprint) into n sections: S.sub.1, S.sub.2, . . . , S.sub.n. Then concatenate the bits .phi..sub.1(S.sub.1), .phi..sub.1(S.sub.2), . . . , This creates an encryption key K.sub.d that is 256n bits in length. For example, if user information 1520 is divided into 10 sections, then this method would create an encryption key with 2,560 bits.
Another embodiment is to use two different parts of user information, denoted S1 and S2, apply a one-way function .phi. to each part of the finger print information to form fingerprint information that has the same length as each of the parts. For example, let the symbol .sym. denote the exclusive-or function i.e. as a binary operator on bits 0.sym.0=1.sym.1=0-and -1.sym.0=0.sym.1=1. .sym. is extended coordinate-wise to strings of bits;--as an example, if A=0011 and B=0101, then A.sym.B=0110. In an embodiment, a one-way function .phi.is applied to each part and then take an exclusive-or, .sym., of the two results. In other words, the encryption key is K.sub.d=.sym.(S1).sym..phi.(S2). If .sym. has an output size of m bits, then K.sub.d has a size of m bits. A similar process could be performed using other operators in place of an exclusive-or to create an encryption key K.sub.d having a size of m bits.
Similarly, to create a larger key, start with 2n pieces of user information, S.sub.1, S.sub.2, . . . , S.sub.2n. Create n different m-bit keys, k.sub.1, k.sub.2, . . . k.sub.n where k.sub.1=.phi.(S.sub.1).sym..phi.(.sub.2), k.sub.2 =.phi.(S.sub.3) .sym..phi.(S.sub.4), k.sub.3=.phi.(S.sub.4).sym..phi.(S.sub.5), . . . , kn=.phi.(S.sub.2n-1) .sym..phi.(S.sub.2n). Then create the key K.sub.d by concatenating these n keys; in other words, K.sub.d=k.sub.1 k.sub.2 k.sub.3 . . . k.sub.n. Thus, K.sub.d has a size of mn bits, where the output of one-way function .phi. is m bits. If .phi.=.phi..sub.1 (i.e. SHA-256), then K.sub.d has a size of 256n bits. A similar process could be performed using other operators in place of an exclusive-or to create an encryption key K.sub.d having a size of mn bits.
Unsecured system 1526 may be a host computer, encryption device, or other machine that is used for encrypting data. The word "host" refers to a laptop, desktop, other type of computer, or possibly another electronic device. Unsecured system 1526 may be a single module or a large system having many components. Unsecured system 1526 is referred to as "unsecured" only because, in an embodiment, no steps are necessarily taken to secure unsecured system 1526. However, unsecured system 1526 may have been secured, and may have any combination of security safeguards protecting it. For example, unsecured system 1526 may require entry of a passcode and/or any type of user data (e.g., any of the user data upon which user information 1520 may be based) prior to entry. Alternatively, unsecured system 1526 may have no security features.
In still another embodiment, the key K.sub.d is encrypted before it is sent from secure module 1502 to unsecured system 1526. In some encryption schemes, passcode 1706 may be used as an encryption key to encrypt key K.sub.d. For example, if passcode 1706 is 256 bits, then AES 256 bit encryption could use passcode 1706 as the key and encrypt key K.sub.d, denoted as E(K.sub.d). Then E(K.sub.d) is transmitted to unsecured system 1526, where the unsecured system 1526 executes a AES 256 bit decryption code, and its copy of passcode 1706 to decrypt E(K.sub.d) so that the unsecured system 1526 has possession of key K.sub.d. Other encryption methods may also be used to securely transmit K.sub.d from secure module 1502 to unsecured system 41526, such as DES, Blowfish, or RSA.
In step 2306, the acquired user data is passed, inside of the secure module 1502, to a one-way hash function or another type of one-way method of encoding user data. In step 2308, generate encryption keys 1523 is executed, and the one-way method generates an encryption key, K.sub.d. In step 2310, on secure module 1502, the encryption key, K.sub.d is passed to a one-way hash function or another type of one way method .phi.. In step 2312, the value P.sub.d=.phi.(K.sub.d), a passcode, is computed on secure module 1502 and subsequently, in step 2314, passcode P.sub.d is transmitted to unsecured system 1526. In step 2316, unsecured system 1526 stores passcode P.sub.d. If an intruder finds passcode P.sub.d on unsecured system 1526, the information obtained from passcode P.sub.d is not helpful to the intruder, because the inverse of the encoding function, .phi. is computationally difficult to compute.
FIG. 24 shows a flowchart of an example of a method 2400 for encrypting or decrypting data. In step 2402, encryption key circuitry 1508 makes a request to the unsecured system 1526 to encrypt or decrypt some data. The request may be in response to a user entering user data (e.g., the user scanning a fingerprint into authentication mechanism 1504), and the user data being authenticated. In step 2404, unsecured system 1526 sends the passcode P.sub.d to the secure module 1502. In step 2406, secure module 1502 authenticates the unsecured system 1526, by checking whether passcode P.sub.d is correct. If passcode P.sub.d is not correct, then in step 2407 method 2400 is terminated. Consequently, encryption key K.sub.d is not passed to unsecured system 1526. The reason for not passing encryption key K.sub.d is because it is expected that an intruder program is running and attempting to perform the encryption or decryption.
Returning to step 62406, if passcode P.sub.d is correct, then in step 82408 secure module 1502 retrieves encryption key K.sub.d from memory 1510 (e.g., flash memory) and transmits encryption key K.sub.d to unsecured system 1526. In another embodiment, step 2408 may involve encrypting encryption key K.sub.d before sending encryption key K.sub.d from secure module 1502 to unsecured system 1526. For example, passcode 1706 may be used as an encryption key to encrypt encryption key K.sub.d. If passcode 1706 is 1656 bits, then AES 256 bit encryption could use passcode 1706 as the encryption key and encrypt encryption key K.sub.d. The encrypted encryption key may be denoted by E(K.sub.d). Then the encrypted encryption E(K.sub.d) is transmitted to unsecured system 1526.
In step 2410, unsecured system 1526 receives (e.g., accepts) encryption key K.sub.d. Receiving encryption key K.sub.d, may involve receiving encrypted encryption key E(K.sub.d). Additionally, step 2410 may involve unsecured system 1526 executing an AES 256 bit decryption code, using the copy of passcode 1706 stored at unsecured system 1526 to decrypt E(K.sub.d) so that unsecured system 1526 has possession of key K.sub.d. Other encryption methods may also be used to securely transmit K.sub.d from secure module 1502 to unsecured system 1526, such as DES, Blowfish, or RSA.
In step 2412, unsecured system 1526 uses encryption key K.sub.d to encrypt or decrypt the data. In step 2414, encryption key K.sub.d is discarded. Encryption key K.sub.d is not stored on unsecured system 1526; encryption key K.sub.d only remains in the volatile memory of unsecured system 1526 for a brief period of time. Immediately, after the encryption or decryption process is finished making use of encryption key K.sub.d, the volatile memory, which contains encryption key K.sub.d, is erased. Encryption key K.sub.d may be erased using any of several methods. For example, a value containing no information, such as the number 0, written at the one or more memory locations where encryption key K.sub.d was located. As another example, a value containing information that is unrelated to encryption key K.sub.d is written in the location where encryption key K.sub.d was located. Since encryption key K.sub.d is in the unsecured system 1526, which is not secure, for only a short while, it is difficult for an intruder to copy encryption key K.sub.d. Other embodiments may not include all of the above steps and/or may include other steps in addition to or instead of those listed in method 2400. Additionally the steps listed in method 2400 may not be distinct steps.
In FIG. 25, the fingerprint sensor, processor. and memory comprise the hardware of FPALM. The sensor, processor, and memory together may be integrated into a single chip, or their functions may be separated into two or more chips. The fingerprint sensor scans the fingerprint of a "lock administrator" and the fingerprint, or a representation of it, is stored in long-term memory while in setup mode. Long-term memory allows the system to maintain a digital representation of the fingerprint even if the power supply shuts off, fails or is removed. Only the lock administrator, using his own fingerprint, may authorize the addition or removal of subsequent fingerprints to the database. If necessary, the lock administrator may remove his own fingerprint(s) from the database and reassign the role of lock administrator to someone else who must then scan their fingerprint into the device during setup. The number of fingerprints that the lock administrator may add to the database is limited only by the amount of available memory. Thus, the database may consist of one fingerprint, or up to ten thousand or more.
In FIG. 25, the fingerprint sensor, processor, and memory comprise the primary electronic hardware of FPALM II. The sensor. processor. and memory together may be integrated into a single chip, or their functions may be separated into two or more chips. The fingerprint sensor scans the fingerprint of a 'lock administrator" and the fingerprint, or a representation of it, is stored in long-term memory while in "setup mode".Long-term memory allows the system to maintain a digital representation of the authorized user(s) fingerprint(s) even if the power supply shuts off. fails or is removed. Only the lock administrator, using his own fingerprint, may authorize the addition or removal of subsequent fingerprints to the database. Users who are added to the database by the lock administrator do not possess this capability. If necessary, the lock administrator may remove his own fingerprint(s) from the database and reassign the role of lock administrator to someone else who must then scan their fingerprint into the device during setup mode. The number of fingerprints that the lock administrator may add to the database is limited only by the amount of available memory. Thus, the database may consist of one fingerprint, or up to ten thousand fingerprints or more.
Previous Patent US 7,979,715 | Next Patent US 7,979,717