Abstract:
A method and apparatus to provide authentication. The method comprising sending a challenge to a user to be authenticated, the challenge including a reference on a card issued to the user and receiving a user-supplied value purported by the user to be associated with the reference on the card issued to the user. The method further comprising accessing a secret key associated with the card issued to the user and generating a password using a function F of the secret key and the reference. The method further comprising mapping the function F to a value in an alphabet and authenticating the user by comparing the value in the alphabet to the user-supplied value.

Description:
COPYRIGHT NOTICE 
     Contained herein is material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent disclosure by any person as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all rights to the copyright whatsoever. 
     BACKGROUND 
     1. Field 
     Embodiments of the present invention relate generally to the field of authentication. More particularly, embodiments of the present invention relate to a second factor used for authentication. 
     2. Description of the Related Art 
     Authentication is the process of determining whether someone or something is, in fact, who or what it is declared to be. In private and public computer networks (including the Internet), authentication is commonly done through the use of logon passwords. Knowledge of the password is assumed to guarantee that the user is authentic. Each user registers initially using an assigned or self-declared password. On each subsequent use, the user must know and use the previously declared password. The password is considered a first factor, because it is something the user knows that presumptively no one else knows. 
     Since passwords are vulnerable to clever hackers, more security can be provided by adding a second factor to the authentication. The second factor is generally something the user has (as opposed to something the user knows). Common second factors are credit cards, smart keys, and other similar objects. A second factor containing only one piece of information is relatively vulnerable. What is needed is a second factor containing information that can be generated systematically and verified efficiently while not consuming excessive memory at the authentication authority. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Embodiments of the present invention are illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements and in which: 
         FIG. 1A  is a block diagram illustrating an authentication card according to one embodiment of the present invention; 
         FIG. 1B  is a block diagram illustrating an authentication card according to another embodiment of the present invention; 
         FIG. 2  is a flow diagram illustrating prior art prefetch optimization including static prefetch distance calculation; 
         FIG. 3  is a flow diagram illustrating authentication processing according to one embodiment of the present invention; 
         FIG. 4A  is a flow diagram illustrating authentication processing according to another embodiment of the present invention; 
         FIG. 4B  is a flow diagram continuing the illustration of authentication processing according to one embodiment of the present invention; and 
         FIG. 5  is a block diagram illustrating an example computer system according to one embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     The Authentication Card 
     One embodiment of the invention provides an authentication card as a second factor for authentication. One embodiment of such an authentication card is now described with reference to  FIG. 1A . In one embodiment, the authentication card  100  may be a plastic card in the shape of a credit card or other similar shape that fits into most wallets. In other embodiments, the authentication card may be fabricated out of paper, cardboard, metal, or any other suitable material. 
     In one embodiment, the card is uniquely associated with a card number  120 . For example, the card number  120  for authentication card  100  in  FIG. 1A  is 4536 3657 2352 7658. In one embodiment, the numbers on the card may include the card number itself (for identification purposes) and the method of computation. For example, the card number may be 4536 3657 2352 7658 A1. The number 4536 3657 2352 7658 is the card number for identification, while the A1 indicates the method computation. Various methods of computation may be utilized, as is described in more detail below. In one embodiment, the authentication card  100  also includes a set of reference/value pairs. A reference/value pair describes a reference and a value associated with the reference. For example, the authentication card  100  in  FIG. 1A  has twelve reference/value pairs, listed in order from top to bottom in three columns. Reference one has value F, reference two has value Q, and so on until reference twelve which has value L. While the Figures show the matrix and the card number on the same side, of course, they may be on opposite sides. In one embodiment, one side may include the card number and branding information while the other includes the matrix. In one embodiment, both sides can include parts of the matrix and/or card information. The distribution of information on the card itself can be varied without affecting the underlying invention. 
     The reference/value pairs can be represented in numerous ways on the authentication card  100 . Another way to represent reference/value pairs is shown in  FIG. 1B . In  FIG. 1B  each reference is a cell in a grid, represented by its (row, column) coordinate. For example, in  FIG. 1B , the reference ( 1 , 1 ) has value F, the reference ( 2 , 1 ) has value Q, and so on until reference ( 4 , 3 ) which has a value L. There are numerous other ways to represent reference value pairs including a list or a number of graphic devices such as color coding, shape coding, and so on. The concept of a reference/value pair, which is a reference and a value associated with the reference remains constant regardless of physical representation. 
     In one embodiment, the authentication cards issued by an entity (such as a bank or other organization that wishes to authenticate users) all have the same number of references and associated values. For example, the authentication cards  100  in  FIGS. 1A and 1B  have twelve references. In other embodiments, cards can have a variable number of references. 
     In one embodiment, the values associated with the references are generated methodically. In one embodiment, a secret key associated with the card is used to generate values for the reference numbers. In such an embodiment, when a card is being produced a secret key is generated and associated with the card. This association can be stored using the card number  112  associated with the authentication card  100 . 
     In one embodiment, the value associated with each reference is generated by performing a one-way operation (e.g., a one-way hash function such as MD5 or SHA-1) on a combination of the secret key and the reference. In one embodiment the one way function used is the Hash-based One-Time Password (HOTP) algorithm, a publicly available algorithm published by the Open Initiative for Authentication (OATH). See Internet Engineering Task Force (IETF) HMAC OTP Draft 4, available at http://www.openauthentication.com. For example, using the authentication card  100  in  FIG. 1A , the value associated with reference  6  would be HOTP (K, 6), where K is the secret key and the arguments of the hash function are concatenated. In the example of  FIG. 1A , the resulting hash would be mapped to an alphabet resulting in “I.” 
     The HOTP algorithm results in a 6-digit code, and is thus able to support any alphabet up to 999,999 “letters,” or members. Other one-way functions can support larger or smaller alphabets. In the examples shown in  FIGS. 1A and 1B , a standard A-Z alphabet is shown. However, any alphabet could be used, including characters, hexadecimal and decimal numerals, or any other symbols. In one embodiment all possible values in the alphabet used can be represented using a standard QWERTY keyboard. 
     Another example of using the HOTP algorithm to generate the reference-value pairs is now given with reference to  FIG. 1B . The x-y coordinates of a cell can be combined with the secret key to give the value. For example cell ( 2 , 3 ) can be mapped as HOTP (K, 23). In this example, the x-y coordinates are simply concatenated, which produces a unique reference for each cell. The x-y coordinates may be combined in some other way, such as multiplication, although multiplication in particular will not produce unique references. 
     Authentication System 
     With an understanding of some embodiments of an authentication card  100 , one embodiment of an authentication system using the authentication card  100  is now described with reference to  FIG. 2 .  FIG. 2  shows a card generator  216  that generates the authentication card  100  using the secret key  218 . The card generator  216  may be a separate entity or company specializing in authentication or card printing and pressing. The card generator  216  may generate the secret key  218  itself, or may receive the secret key  218  from another entity. 
     In one embodiment, the secret key  218  is a random number generated by a random number generator. The secret key  218  can be created by any other means. One characteristic of the secret key is that it is not known to anyone outside of the card generator  216 . The card generator  216  provides the authentication card  100  to a user  220  and the secret key  218  to an authentication entity  222 . In one embodiment, the secret key  218  can be delivered on an secure physical medium, or via transmission on a secure encrypted communication channel. The card  100  can be provided first to an intermediary (such as a bank that will issue it to a customer), before coming into the possession of the user  220  who will use it for authentication. 
     The authentication entity  222  can be the entity requesting the authentication (e.g., the bank) or an entity or company specializing in authentication contracted by the entity requesting the authentication. In one embodiment, the secret key  218  is stored in a key database  224 . In one embodiment, the secret key is associated with the card number of the authentication card it was used to generate. For example, the Key 1  was used by the card generator  216  to generate card with card number 1234 5678 9101, then a record in the key database  224  will associate Key 1  with card number 1234 5678 9101. In one embodiment, the key database is searchable by card number. In one embodiment, to protect the secret keys, the key database is stored on a hardware security module (HSM). 
     The authentication entity  222  also includes an authentication module  226 . In one embodiment, the authentication entity  222  creates the challenges presented to the user  220  and evaluates the response received from the user  220 . The authentication module  226  can contain a user interface  229  to communicate challenges to, and receive responses from the user  220 . In another embodiment, a separate entity (such as the bank) interfaces with the user, and forwards the response to the challenge to the authentication entity  222 . In other embodiments, one entity handles both user interface and authentication. 
     In one embodiment, a challenge generator  250  in the authentication entity  222  presents a challenge to the user  220  in the form of asking for the value associated with one or more references on the authentication card  100  issued to the user. For example, in one embodiment, in addition to the user&#39;s logon and password (first factor), the logon interface will also ask for the values associated with three randomly chosen references. Fewer or more references may be used. 
     For example, a user in possession of the authentication card  100  shown in  FIG. 1A  may be asked to provide the values of references  3  and  10 . The correct answers for this example are P and S. A look-up logic  255  in the authentication entity  220  can look up the card number of the card  100  issued to the user  220  and access the key database  224  to access the secret key tied to the card number. The authentication module  226  can then regenerate the values asked for in the challenge using the algorithm used to generate the card. In this manner, the authentication module  226  can verify the possession of the card  100  by the user  220  without being in possession of all the reference-value pairs on the card  100 . This enables efficient hardware protection of the information needed to verify the user  220 . 
     If the authentication module successfully authenticates the user  220 , then the authentication module  226  can send an authentication message to a content provider  228  that the user  220  wants to access. This communication may be implemented by a special content provider interface module that may be separate from the user interface  229 . The content provider  228  may be a bank, an insurance company, and internet service provider or any other content or service provider that has users that the content provider  228  wishes to authenticate. The content provider  228  may be the same entity as the authentication entity  222 , if the content provider  228  is handling the authentication in-house. 
     Upon receiving the authentication from the authentication module  226 , the user  220  and the content provider  228  can engage in an authenticated session which may include online banking, web surfing, gaming or any other content or service provided. If authentication is not successful, the authentication module  226  informs the content provider that authentication has failed in the authentication message. The user  220  is then considered not authenticated, and will not be allowed authenticated access to the content provider  228 . 
     Challenge-Response Protocols 
     One embodiment of a challenge-response protocol to authenticate a user having a second factor authentication card as described above is now set forth with reference to  FIG. 3 . The process described with reference to  FIG. 3  can be performed, e.g., by the authentication entity  222  in  FIG. 2 . 
     In block  302 , a challenge is sent to a user wanting access to some content or service. The challenge can be presented along with a standard login interface that asks for a user identifier (ID) or some other logon name and a password. For example, an email program typically asks for an email address (e.g. joe_smith@company.com) and a password. 
     In one embodiment, in addition to the usual logon screen, the logon also presents a challenge to identify one or more specific values on the authentication card issued to the user. The values may be identified by reference (such as a number or cell coordinates) or in some other manner. The challenge can ask for more than one value, however only one value is discussed for simplicity and ease of understanding. For example, a challenge asking for three values may ask a user for a user ID, a password, and the values of references  4 ,  9 , and  12 . For a user in possession of the card  100  shown in  FIG. 1A , the correct values would be T, N, and L. 
     In block  304 , a user-supplied value (or values in the case of multiple reference challenges) is received along with the user ID, in response to the challenge sent in block  302 . For example, if the challenge asked for the value of reference  4 , the user in possession of the card  100  in  FIG. 1A  may have entered T as the user-supplied value. However, a user not in possession of the card  100  (or a user making a mistake) may have entered a different (incorrect) value. The user-supplied value may have been entered by the user via the logon interface described above, or via some other challenge-response interface. 
     In block  306 , the user ID is mapped to a card number of the authentication card issued to the user and bound to the user ID. The user ID to card number mapping may be contained in a customer table or customer database. In block  308 , the card number is used to access the secret key associated with the card number. In one embodiment, the secret key was used to generate the reference-value pairs contained on the card, as described above. 
     In one embodiment, accessing the secret key can include searching a secure database using the card number as the search term. The database then includes the secret key associated with the card number. The secret key may be stored in encrypted form, and may need to be decrypted after being accessed before it can be used. 
     In block  310 , the value associated with the reference asked for in the challenge sent in block  302  is calculated by calculating the HOTP of the concatenation of the secret key and the reference. Since, as described above, this algorithm was used to generate the value associated with the reference by the card generator, this calculation regenerates the value associated with the reference asked for in the challenge. In other embodiments, other algorithms can be used. So long as the algorithm used is the same algorithm used to initially generate the value on the card requested in the challenge, any suitable algorithm (such as hash algorithms) may be used. 
     In block  312 , a determination is made as to whether the user-supplied value received in block  304  matches the HOTP calculated in block  310 . Since the HOTP calculated in block  310  is the same as the original value of the reference printed on the card, if the user-supplied value matches the HOTP, then that is strong evidence that the user is in possession of the card associated to the user ID. Therefore, if there is a match in block  312 , then, in block  314  the user is authenticated, and allowed access to the content or service requested by the user. 
     If, one the other hand, the HOTP and the user-supplied value do not match in block  312 , then, in block  316  the user is not authenticated, and is not allowed access to the content or service requested by the user. If not authenticated, the account of the user ID may be alerted of the failed authentication, and the account may be locked to prevent further attack. In one embodiment, the user is given one or more additional chances to correctly respond to the challenge. In one embodiment, additional chances ask for the values associated with the same reference or references as the initial failed authentication attempt. In another embodiment, different references are used. 
     One embodiment of a different challenge-response protocol using the authentication card is now described with reference to  FIGS. 4A and 4B . In block  402 , a logon request is received from the user, such as a logon to an email account or some other online content or service. The logon will include a user ID (such as an email address) as described above. In block  404  the user ID is mapped to a card number, and in block  406  the secret key associated with the card number is accessed. 
     In block  408  a set of reference-value pairs are calculated using the secret key. This can be done by calculating a set of HOTP using the secret key and a set of references, as described above. In another embodiment, the process and function used to generate the card is used to regenerate the values associated with a set of selected references. For example, if four references are selected (e.g.,  2 ,  6 ,  9 , and  11  of the card illustrated by  FIG. 1A ) then four reference-value pairs are calculated (e.g.,  2 -Q,  6 -I,  9 -N, and  11 -W using the card illustrated by  FIG. 1A ). 
     In block  410 , a graphical display is delivered to the user displaying one or more correct reference-pairs. In one embodiment, the other reference value pairs are purposefully displayed incorrectly. In the example above, reference  9  may be selected for correct display, resulting is a display showing  2 -J,  6 -O,  9 -N, and  11 -R. In another embodiment, more than one reference-value pair can be displayed correctly. Stated generally, a subset of the set of calculated reference-value pairs are displayed correctly and the remainder (all other reference-value pairs calculated) is displayed incorrectly. In one embodiment, the number of correct reference-value pairs is less than the number of incorrect reference-value pairs to make guessing the correct response more difficult. 
     In block  412 , a user-supplied reference is received indicating which reference the user believes shows the correct associated value. In an embodiment where multiple reference value-pairs are displayed, multiple user-supplied references may be received. In this example, however, only one reference and value pair is displayed correctly, thus only one user-supplied reference is expected from the user in block  412 . In one embodiment, the user can indicate the user&#39;s selection of the correct reference-value pair by clicking a mouse or cursor on a graphical representation of the reference-value pair. In this manner, the actual value of the correct reference value pair need not be transmitted between the user and the authentication entity resulting in additional security. 
     In block  414 , a determination is made as to whether the user-supplied reference corresponds with the correct reference-value pair of block  410 . In other words, did the user identify which reference-value pair displayed in the challenge in block  410  correctly matched a reference-value pair on the authentication card issued to the user? If, it is determined that the user-supplied reference (or references) does correspond with the correct reference-value pair, then in block  416  the user is authenticated. However, if it is determined that the user-supplied reference (or references) does not correspond with the correct reference-value pair, then in block  416  the user is not authenticated. 
     Example Computer System 
     Various embodiments of the present invention have been described in the context of a compiler that generates code that is inserted into a program being compiled by the compiler. An example computer system on which such a compiler can be implemented in now described with reference to  FIG. 5 . Computer system  500  that may be used to perform one or more of the operations described herein. In alternative embodiments, the machine may comprise a network router, a network switch, a network bridge, Personal Digital Assistant (PDA), a cellular telephone, a web appliance or any machine capable of executing a sequence of instructions that specify actions to be taken by that machine. 
     The computer system  500  includes a processor  502 , a main memory  504  and a static memory  506 , which communicate with each other via a bus  508 . The computer system  500  may further include a video display unit  510  (e.g., a liquid crystal display (LCD) or a cathode ray tube (CRT)). The computer system  500  also includes an alpha-numeric input device  512  (e.g., a keyboard), a cursor control device  514  (e.g., a mouse), a disk drive unit  516 , a signal generation device  520  (e.g., a speaker) and a network interface device  522 . 
     The disk drive unit  516  includes a machine-readable medium  524  on which is stored a set of instructions (i.e., software)  526  embodying any one, or all, of the methodologies described above. The software  526  is also shown to reside, completely or at least partially, within the main memory  504  and/or within the processor  502 . The software  526  may further be transmitted or received via the network interface device  522 . For the purposes of this specification, the term “machine-readable medium” shall be taken to include any medium that is capable of storing or encoding a sequence of instructions for execution by the computer and that cause the computer to perform any one of the methodologies of the present invention. The term “machine-readable medium” shall accordingly be taken to included, but not be limited to, solid-state memories, optical and magnetic disks, and carrier wave signals. 
     General Matters 
     In the description above, for the purposes of explanation, numerous specific details have been set forth. However, it is understood that embodiments of the invention may be practiced without these specific details. In other instances, well-known circuits, structures and techniques have not been shown in detail in order not to obscure the understanding of this description. 
     Embodiments of the present invention include various processes. The processes may be performed by hardware components or may be embodied in machine-executable instructions, which may be used to cause one or more processors programmed with the instructions to perform the processes. Alternatively, the processes may be performed by a combination of hardware and software. 
     Embodiments of the present invention may be provided as a computer program product that may include a machine-readable medium having stored thereon instructions, which may be used to program a computer (or other electronic device) to perform a process according to one or more embodiments of the present invention. The machine-readable medium may include, but is not limited to, floppy diskettes, optical disks, compact disc read-only memories (CD-ROMs), and magneto-optical disks, read-only memories (ROMs), random access memories (RAMs), erasable programmable read-only memories (EPROMs), electrically erasable programmable read-only memories (EEPROMs), magnetic or optical cards, flash memory, or other type of media/machine-readable medium suitable for storing instructions. Moreover, embodiments of the present invention may also be downloaded as a computer program product, wherein the program may be transferred from a remote computer to a requesting computer by way of data signals embodied in a carrier wave or other propagation medium via a communication link (e.g., a modem or network connection). 
     While the invention has been described in terms of several embodiments, those skilled in the art will recognize that the invention is not limited to the embodiments described, but can be practiced with modification and alteration within the spirit and scope of the appended claims. The description is thus to be regarded as illustrative instead of limiting.