Databaseless security system - Patent Review 5120939

Claims

We claim:

1. A system for enabling entry into a secure facility, the system including a portable object and means for transferring data between the portable object and the facility,

the facility comprising:

memory means for storing encryption algorithms E.sub.1 and E.sub.2 ;

means for generating a challenge number;

means responsive to an identification signal, supplied by the portable object itself, that identifies the particular portable object seeking to gain access to the facility, and to encryption algorithm E.sub.1 for generating a secret code;

means responsive to the challenge number, to the secret code and to encryption algorithm E.sub.2 for generating a first response signal;

means for comparing the first response signal with a second response signal generated by the portable object, and for providing an enabling signal when the comparison is favorable;

the portable object comprising:

means for supplying the identification signal;

memory means for storing the secret code and the encryption algorithm E.sub.2, but not encryption algorithm E.sub.1 used for generating the secret code, said secret code and encryption algorithm E.sub.2 having been previously generated and entered into the memory means; and

means responsive to the secret code, to the challenge number received from the facility, and to encryption algorithm E.sub.2 for generating the second response signal and transmitting same to the facility.

2. The system of claim 1 wherein the means for generating the secret code comprises a first processor, jointly responsive to the identification signal and to a secret master string, for executing a predetermined sequence of steps in accordance with encryption algorithm E.sub.1, the secret master string being a plurality of numbers that are stored within the memory means of the facility.

3. The system of claim 1 wherein the means for generating the first response signal comprises a first processor, jointly responsive to the secret code and to the challenge number, for executing a predetermined sequence of steps in accordance with encryption algorithm E.sub.2.

4. The system of claim 1 wherein the means for generating the second response signal comprises a second processor, responsive to the secret code and to the challenge number, for executing a predetermined sequence of steps in accordance with encryption algorithm E.sub.2.

5. The system of claim 2 wherein encryption algorithm E.sub.1 is a process for encrypting data in accordance with the Data Encryption Standard.

6. The system of claim 4 wherein encryption algorithm E.sub.2 is a process for encrypting data in accordance with the Data Encryption Standard.

7. The system of claim 1 wherein the challenge number is substantially random.

8. A portable electronic device for use in obtaining access to a secure facility comprising:

memory means storing an identification number, a secret code, and an encryption process E.sub.2, the secret code having been formed by an encryption process E.sub.1 using the identification number and a secret master string, but not storing encryption algorithm E.sub.1 itself, said secret code and encryption algorithm E.sub.2 having been previously generated and entered into the memory means;

a processor, responsive to (i) a received challenge number, (ii) the secret code, and (iii) encryption process E.sub.2, for generating and transmitting a signal in response to the challenge number; whereby the portable electronic device can authenticate itself to an authentication apparatus which does not store a list of acceptable identification numbers.

9. A system for controlling access to a plurality of secure facilities, the system including a portable object and means for transferring data between the portable object and each of the facilities,

the portable object comprising:

means for supplying an identification signal;

means for storing two or more secret codes and an encryption algorithm E.sub.2, but not storing any encryption algorithm used for generating the secret codes, said secret codes and encryption algorithm E.sub.2 having been previously generated and entered into the storing means;

means responsive to a code selection signal, received from one of the facilities, for selecting one of the secret codes;

means responsive to the selected secret code, to a challenge number received from said one of the facilities, and to E.sub.2 for generating a first response signal:

said one of the facilities comprising:

memory means for storing encryption algorithms E.sub.1 and E.sub.2 ;

means for generating a challenge number;

means for generating the code selection signal;

means responsive to said identification signal, supplied by the portable object itself, that identifies the particular portable object seeking to gain access to the facility, and to encryption algorithm E.sub.1 for generating the secret code;

means responsive to the challenge number, the secret code and E.sub.2 for generating a second response signal; and

means for comparing the first and second response signals and denying access to the secure facility when the comparison is not favorable.

10. The system of claim 9 wherein the challenge number includes the code selection signal.

11. The system of claim 9 wherein the facility further includes:

means for storing a list of identification numbers not entitled to access the secure facility; and

means for determining correspondence between the stored list of identification numbers and the identification signal that identifies the particular portable object seeking access to the facility; whereby access to the facility will be denied when such correspondence exists.

12. A system for controlling access to a secure facility, the system including a portable object and means for transferring data between the portable object and the facility,

the portable object comprising:

means for supplying an identification signal;

means for storing two or more secret codes and an encryption algorithm E.sub.2 ;

means responsive to a code selection signal, received from the facility, for selecting one of the secret codes;

means responsive to the selected secret code, to a challenge signal received from the facility, and to E.sub.2 for generating a first response signal;

the facility comprising:

memory means for storing encryption algorithms E.sub.1 and E.sub.2 ;

means for generating said challenge signal;

means for generating the code selection signal;

means responsive to said identification signal, supplied by the portable object itself, that identifies the particular portable object seeking to gain access to the facility, and to encryption algorithm E.sub.1 for generating the secret code;

means responsive to the challenge signal, the secret code and E.sub.2 for generating a second response signal; and

means for comparing the first and second response signals; whereby favorable comparison is required for obtaining access to the secure facility.

13. A door lock system including an electronic key, a door, support structure for the door, and an electronic lock;

the electronic lock comprising:

means for exchanging electrical data with the electronic key;

means responsive to an identification signal, proffered by the electronic key, for converting same into a secret code number;

means for generating a challenge number and communicating same to the electronic key;

means responsive to the challenge number and to the secret code number for generating a first response number;

means for comparing the first response number with a second response number, the second response number having been generated by the electronic key in response to the challenge number; and

means for unlocking the door when the comparison between the first and second response numbers is favorable;

the electronic key comprising

means for supplying the identification signal;

memory means for storing the secret code number, but not storing the means for converting the identification signal into the secret code number, said secret code number having been previously generated and entered into the memory means;

means responsive to the secret code number and to the challenge number for generating the second response number and communicating same to the electronic lock.

14. The system of claim 13 wherein the means for converting the proffered identification signal into the secret code number comprises a processor which is jointly responsive to the identification signal and to a master string in executing a predetermined sequence of steps of a first encryption algorithm E.sub.1, the master string comprising a plurality of secret numbers that are stored within a memory of the electronic lock.

15. The system of claim 13 wherein the means for generating the first response number comprises said processor which is jointly responsive to the secret code number and to the challenge number in executing a predetermined sequence of steps of a second encryption algorithm E.sub.2.

16. The system of claim 14 wherein encryption algorithm E.sub.1 is a process for encrypting data in accordance with the Data Encryption Standard.

17. The system of claim 15 wherein encryption algorithm E.sub.2 is a process for encrypting data in accordance with the Data Encryption Standard.

18. The system of claim 13 wherein the challenge number is substantially random.

19. The system of claim 13 wherein the electronic lock is positioned on the support structure for the door.

20. The system of claim 19 wherein the support structure of the door further includes a user interface having a keyboard device for the user to enter information for the purpose of identifying himself in addition to identification information provided by the electronic key.

21. A system for enabling entry into a secure facility, the system including a portable object and means for transferring data between the portable object and the facility,

the facility comprising:

memory means for storing encryption algorithms E.sub.1 and E.sub.2 ;

means for generating a challenge number;

means responsive to an identification signal, supplied by the holder of the portable object through a keyboard device, that identifies the particular portable object seeking to gain access to the facility, and to encryption algorithm E.sub.1 for generating a secret code;

means responsive to the challenge number, to the secret code and to encryption algorithm E.sub.2 for generating a first response signal;

means for comparing the first response signal with a second response signal generated by the portable object, and for providing an enabling signal when the comparison is favorable;

the portable object comprising:

memory means for storing the secret code and the encryption algorithm E.sub.2, but not encryption algorithm E.sub.1 used for generating the secret code, said secret code and encryption algorithm E.sub.2 having been previously generated and entered into the memory means; and

means responsive to the secret code, to the challenge number received from the facility, and to encryption algorithm E.sub.2 for generating the second response signal and transmitting same to the facility.

22. A system for controlling access to a plurality of secure facilities, the system including a portable object and means for transferring data between the portable object and each of the facilities,

the portable object comprising:

means for storing two or more secret codes and an encryption algorithm E.sub.2, but not storing any encryption algorithm used for generating the secret codes, said secret codes and encryption algorithm E.sub.2 having been previously generated and entered into the storing means;

means responsive to a code selection signal, received from one of the facilities, for selecting one of the secret codes;

means responsive to the selected secret code, to a challenge number received from said one of the facilities, and to E.sub.2 for generating a first response signal;

said one of the facilities comprising:

memory means for storing encryption algorithms E.sub.1 and E.sub.2 ;

means for generating said challenge number;

means for generating the code selection signal;

means responsive to an identification signal, supplied by a holder of the portable object through a keyboard device, that identifies the particular portable object seeking to gain access to the facility, and to encryption algorithm E.sub.1 for generating the secret code;

means responsive to the challenge number, the secret code and E.sub.2 for generating a second response signal; and

means for comparing the first and second response signals and denying access to the secure facility when the comparison is not favorable.

23. A system for controlling access to a secure facility, the system including a portable object and means for transferring data between the portable object and the facility,

the portable object comprising:

means for storing two or more secret codes and an encryption algorithm

means responsive to a code selection signal, received from the facility, for selecting one of the secret codes;

means responsive to the selected secret code, to a challenge signal received from the facility, and to E.sub.2 for generating a first response signal;

the facility comprising:

memory means for storing encryption algorithms E.sub.1 and E.sub.2 ;

means for generating said challenge signal;

means for generating the code selection signal;

means responsive to an identification signal, supplied by a holder of the portable object through a keyboard device, that identifies the particular portable object seeking to gain access to the facility, and to encryption algorithm E.sub.1 for generating the secret code;

means responsive to the challenge signal, the secret code and E.sub.2 for generating a second response signal; and

means for comparing the first and second response signals; whereby favorable comparison is required for obtaining access to the secure facility.

24. A door lock system including an electronic key, a door, support structure for the door, and an electronic lock;

the electronic lock comprising:

means for exchanging electrical data with the electronic key;

means responsive to an identification signal, proffered by a user of the electronic key through a keyboard device, for converting same into a secret code number;

means for generating a challenge number and for communicating same to the electronic key;

means responsive to the challenge number and to the secret code number for generating a first response number;

means for comparing the first response number with a second response number, the second response number having been generated by the electronic key in response to the challenge number; and

means for unlocking the door when the comparison between the first and second response numbers is favorable;

the electronic key comprising

memory means for storing the secret code number, but not storing the means for converting the identification signal into the secret code number, said secret code number having been previously generated and entered into the memory means;

means responsive to the secret code number and to the challenge number for generating the second response number and communicating same to the electronic lock.

TECHNICAL FIELD

The present invention relates to a system for granting access to a secure facility, and more particularly to an authentication procedure.

BACKGROUND OF THE INVENTION

Although we may be evolving toward a kinder and gentler civilization, there are still those who prefer to make money the old fashioned way, by stealing. It would therefore seem to be a good idea to protect goods in a similarly old fashioned way, under lock and key. Unfortunately, many who steal have achieved great expertise in circumventing old fashioned ways of protection and are ready for more sophisticated undertakings. Such expertise is not easily achieved, and requires great learning and diligence which, if properly channeled, might lead to even greater rewards. However, more than making money is involved. The thrill of an intellectual challenge is an important factor; witness the number of "hackers" seeking entry into government and industry computer systems, not for theft, but just to look around and create a little mischief, demonstrate their prowess, and perhaps even plant a software "bug" for good measure. A challenge also exists for those who provide secure facilities; namely, to exclude all unauthorized persons seeking entry while simultaneously making authentication procedures as convenient as possible for both authorized persons and facility administrators. Such goals are frequently incompatible with each other.

The use of a password is perhaps the simplest and least expensive technique for providing access security. Additionally, passwords are relatively easy to change. However, there are problems with passwords; when they are fixed for long periods of time the chances of guessing them are improved; and when they are changed too frequently, they are forgotten by the rightful users. Further, when passwords are transmitted across an interface, they can be intercepted by anyone with the proper monitoring equipment.

In one known system, a common secret code is stored within each of two devices (key and lock). The secret codes are logically combined with a random number, available to each device, and the resulting numbers are compared with each other for identity. This technique is generally employed by various data communication systems (see e.g., "Locking Up System Security"--Electronics Week Feb. 18, 1985 regarding Intel Corporation's 27916 KEPROM.TM. Keyed Access EPROM). Advantageously, the secret code itself needs never be transmitted so that an electronic intruder, monitoring interface signals, sees only the random data (challenge) and the modified random data (response) which are insufficient to teach the correct response to subsequent challenges. Unfortunately, this technique stores the same secret code in all keys which precludes selective revocation of lost or stolen keys.

One way to prevent tampering with private information in electronic systems is the use of cryptosystems (i.e., methods for encrypting, or transforming, information so that it is unintelligible and, therefore, useless to those who are not meant to have access to it). Ideally, the transformation of the information is so complicated that it is beyond the economic means of an eavesdropper to reverse the process. The eavesdropper is therefore not inclined to become an intruder who not only would compromise the confidential nature of the stored information, but also might engage in forgery, vandalism and theft. A popular technique, known as public-key cryptography, relies on the use of two keys--one to encode the information and another to decode it. These keys are related in the sense that they serve to specify inverse transformations; however, it is computationally infeasible to derive one key from the other. That being the case, one of the keys can be made public for improved convenience without compromising the security of such a system. Applying public-key cryptography to the challenge of excluding unauthorized persons seeking entry to a secure facility, the party seeking entry would use his private key to encrypt (authenticate) a message. The party receiving the encrypted message would use the public key of the transmitter to decrypt the incoming message in order to transform it to its original text. A discussion of such systems is contained in the August, 1979 issue of Scientific American in an article by Martin E. Hellman entitled "The Mathematics of Public-Key Cryptography." An example of a public-key system is disclosed in U.S. Pat. No. 4,453,074 issued to S. B. Weinstein for a "Protection System for Intelligent Cards." Unfortunately, in public-key systems, the party receiving the encrypted message must maintain a database that contains the public keys of all parties having authorization to enter the secure facility.

One particularly promising system involves the use of a password along with a smart card that exchanges data with an authentication device during an authentication procedure. It is noted that the smart card contains a processor and a memory; it is portable and frequently has the shape of a conventional credit card. Security is improved by requiring the holder of the smart card to remember a password. This password can either be sent to the smart card enabling it to exchange data with the authentication device, or the password can be sent directly to the authentication device itself. In either case, two conditions must now be satisfied: something in the user's head and something in the user's hand.

A known system stores an identification (ID) number within each smart card which is transmitted to the authentication device in order commence the authentication procedure. The authentication device scrutinizes the ID number to determine whether it corresponds to a presently valid ID number and then commences the authentication procedure only when the result is affirmative. Such a system is disclosed in U.S. Pat. No. 4,471,216. While personal identification numbers additionally offer the ability to improve flexibility (e.g., expiration date may be built into the ID itself), the storage of each individual ID number in the authentication device requires significant memory space. For example, storing 25,000 user keys, each 8 bytes long, requires 200K bytes of memory. Further, each time a new smart card is issued, the memory of the authentication device must be updated to recognize it. This is particularly impractical in a distributed system where, for example, the authentication device is used in connection with room or building access. Even when the authentication device comprises a host computer that is easily updated, it is undesirable from a security standpoint to store all ID numbers therein because they might be compromised if someone found a way to break into the computer.

SUMMARY OF THE INVENTION

A security system includes a portable object, such as a smart card, and an authentication device for electrically interacting with the portable object to regulate access to a secure facility. An identification number (ID).sub.n is presented to the authentication device which uses an encryption algorithm, E.sub.1, to convert it into a secret code S.sub.n. The authentication device also generates a challenge number, C, which is transmitted to the portable object. Stored within the portable object is secret code S.sub.n and encryption algorithm E.sub.2 which are used together with the challenge number C to create a response signal R.sub.n. Stored within the authentication device is encryption algorithm E.sub.2, which is used together with secret code S.sub.n and the challenge number C to create response signal R.sub.n '. A favorable comparison between R.sub.n and R.sub.n ' is necessary to gain access to the secure facility.

In an illustrative embodiment of the invention, E.sub.1 and E.sub.2 are identical processes that use different master strings (secret keys) to transform a first binary number into a second binary number. Knowledge of the encryption algorithm, however, is insufficient for an intruder to determine the master string. The present invention illustratively uses the Data Encryption Standard (DES) in the implementation of E.sub.1 and E.sub.2.

In a preferred embodiment of the invention, challenge number C is a 64-bit random number. Such numbers are generally non-repeating and enhance security by virtue of their non-predictable character.

The present invention advantageously regulates access to any one of a number of protected resources including information, cash, and physical entry into a facility without requiring the transmission of secret information across an interface. Importantly, the present invention eliminates the need to store and administer identification information regarding each user entitled to access to the protected resources.

It is a feature of the present invention that multiple secret codes are easily stored within a smart card, each providing access to a different facility, or backup access to the same facility in the event of a security breach (e.g., the master string becomes known). In the situation that security is breached, new secret codes can be derived at the authentication device by merely using a new master string. Such new secret codes would have already been stored within each smart card at the time of issue as a precautionary measure. Thus, should security become compromised, new smart cards do not need to be issued.

These and other features of the present invention will be more fully understood when reference is made to the detailed description and associated drawing.

BRIEF DESCRIPTION OF THE DRAWING

FIG. 1 is a flow diagram illustrating the various steps performed in practicing the invention;

FIG. 2 is a flow diagram of the enciphering computation of the Data Encryption Standard;

FIG. 3 is a block diagram that illustrates the calculation of f(R,K) used in the Data Encryption Standard;

FIG. 4 discloses selection table S.sub.1 used in the Data Encryption Standard;

FIG. 5 is a block diagram representation of the major functional components of a smart card system and their general interconnection with each other;

FIG. 6 illustrates use of the present invention in a computer access security system in accordance with the invention;

FIG. 7 illustrates use of the present invention in a premises access security system in accordance with the invention;

FIG. 8 discloses the functional components of a door lock such as used in connection with FIG. 7;

FIG. 9 illustrates the structure of a master string used in the encryption process;

FIG. 10 illustrates the structure of a challenge signal including information regarding the selection of the secret code to be used during the encryption process; and

FIG. 11 discloses a pseudo-random number generator suitable for use as a challenge number generator.

DETAILED DESCRIPTION

General

Referring to FIG. 1, there is disclosed a diagram which illustrates the salient features of the invention in modified flow chart form. The mechanical analog of a key and a lock is useful in connection with FIG. 1 because smart card 500 functions as a key and authentication device 700 functions as a lock. Since the authentication process requires activity on the part of both the smart card and the authentication device, the activity associated with each part is segregated to assist the reader in understanding the invention. Although not required in the practice of the invention, security is enhanced by requiring the holder of the smart card to enter a password into the smart card, enabling it to commence the authentication process by transmitting a personal identification number (ID).sub.n to authentication device 700. Alternatively, the holder of the smart card could directly transmit (ID).sub.n to the authentication device 700. In either case, the following steps describe the authentication process: (1) In response to the receipt of a signal such as (ID).sub.n, box 740 recognizes the signal and initiates the generation of a challenge number. Additionally, secret code S.sub.n is created (box 710) using encryption algorithm E.sub.1 (box 730) and the proffered personal identification number (ID).sub.n. (2) Challenge number C is generated (box 750), transmitted to smart card 500, and used internally (box 720). Note that a valid ID number is not required to initiate the generation of a challenge number--a feature that helps preserve confidentiality of the ID number. (3) Both the smart card 500 and the authentication device 700 (box 563 and box 720) calculate a response (R.sub.n and R.sub.n ' respectively) to the challenge number. Since secret code S.sub.n and encryption algorithm E.sub.2 are contained in both the smart card and in the authentication device, the responses should be identical when compared (box 760). (4) Block 770 further enhances security, with minimum inconvenience to the system administrator, by testing whether the proffered (ID).sub.n corresponds to a lost or stolen card. The list of such cards is presumably small and is seldom updated. Once all of the above steps have been successfully completed, access to the computer is granted, a door is opened, a credit transaction is validated, or cash is delivered, etc.

The various boxes need not reside within the particular device as shown in FIG. 1. For example, in a number of applications, the challenge number generator can be located within the smart card while still preserving the benefits of the invention. Indeed, in the peer-to-peer authentication application described hereinafter, each smart card contains a challenge number generator, means for comparing response numbers, and the E.sub.1 algorithm including a master string. Further, user interface 100 can be built into the smart card 500 or the authentication device 700. It is an important advantage that the list of valid ID numbers need not be stored within the authentication device. It is sufficient that only the encryption algorithm E.sub.1, originally used to create S.sub.n from