CN1659597A - Physical access control - Google Patents

Abstract

A system and method are disclosed for controlling physical access through a digital certificate validation process that works with standard certificate formats and that enables a certifying authority (CA) to prove the validity status of each certificate C at any time interval (e.g., every day, hour, or minute) starting with C's issue date, D1. C's time granularity may be specified within the certificate itself, unless it is the same for all certificates. For example, all certificates may have a one-day granularity with each certificate expires 365 days after issuance. Given certain initial inputs provided by CA, a one-way hash function is utilized to compute values of a specified byte size that are included on the digital certificate and to compute other values that are kept secret and used in the validation process.

Description

physical access control

Cross References to Related Applications

This application is based upon: U.S. Provisional Application 60/370,867, filed April 8, 2002, entitled "Upgradeable Certificate Validation and Simplified PKI Management"; U.S. Provisional Application 60/372,951, filed April 17, 2002, entitled "Techniques for Traversing Hash Sequences"; U.S. Provisional Application 60/374,861, filed October 23, 2002, entitled "Secure Physical Access"; U.S. Provisional Application 60/421,197, filed October 28, 2002, entitled "Real-Time Credentials"; U.S. Provisional Application 60/421,756, filed October 28, 2002, entitled "Securing Mobile Computing Resources U.S. Provisional Application 60/422,416, filed November 19, 2002, entitled "Private Key Secure Physical Access or Real-Time Credentials (RTC) in a Kerberos-Like Setup," U.S. Provisional Application 60/427,504, filed November 19, 2002; U.S. Provisional Application 60/443,407, filed February 29, entitled "Three-Factor Authentication with Real-Time Confirmation"; and filed February 10, 2003, entitled "RTC Physical Access with Low-End Cards" US Provisional Application 60/446,149; the teachings of all of these applications are incorporated herein by reference.

This application is a continuation-in-part of U.S. Patent Application 10/103,541, filed March 20, 2002, entitled "Upgradeable Credential Validation and Simplified Management (Pending)," the teachings of which are incorporated herein by reference. Reference, itself a continuation-in-part of U.S. Patent Application 09/915,180, entitled "Certificate Revocation System (Pending)," filed July 25, 2001, and U.S. Continuation (pending) of patent application 09/483,125, which is a continuation (pending) of U.S. patent application 09/356,745, which was filed on July 19, 1999, which is a continuation (pending) of U.S. patent application which was filed on March 24, 1997 Continuation of 08/823,354 (now U.S. Patent 5,960,083), which is a continuation of U.S. Patent Application 08/559,533 filed November 16, 1995 (now U.S. Patent 5,666,416), based on U.S. Provisional application 60/006,038. U.S. Patent Application 10/103,541 is also a continuation of U.S. Patent Application 08/992,897, filed December 18, 1997, which is based on U.S. Provisional Application 60/033,415, filed December 18, 1996, which was filed September 19, 1996 Continuation-in-Part of filed U.S. Patent Application 08/715,712, entitled "Certificate Revocation System" (Abandoned), based on U.S. Provisional Application 60/5, filed October 2, 1995, entitled "Certificate Revocation System" Continuation of 004,796. US Patent Application 08/992,897 is also a continuation-in-part of US Patent Application 08/729,619 (now US Patent 6,097,811 ), filed October 11, 1996, and entitled "Tree-Based Certificate Revocation System," based on the 1995 US Provisional Application 60/006,143, entitled "Tree-Based Certificate Revocation System," filed November 2. U.S. Patent Application 08/992,897 is also a continuation-in-part of U.S. Patent Application 08/804,868 (abandoned), filed February 24, 1997, entitled "Tree-Based Certificate Revocation System," which was filed on November 1, 1996. Continuation of U.S. Patent Application Serial No. 08/741,601, entitled "Tree-Based Certificate Revocation System," filed on November 2, 1995, and entitled "Tree-Based Certificate Revocation System" Application 60/006,143. U.S. Patent Application 08/992,897 is also a continuation-in-part of U.S. Patent Application 08/872,900 (abandoned), filed June 11, 1997, entitled "Certificate-Based Revocation System," which was filed on November 5, 1996 Continuation of filed U.S. Patent Application 08/746,007 (now U.S. Patent 5,793,868) entitled "Certificate Revocation System" based on U.S. Provisional Application 60 filed August 29, 1996 and entitled "Certificate Revocation System" /025,128. U.S. Patent Application 08/992,897 is also based on U.S. Provisional Application 60/035,119, filed February 3, 1997, entitled "Certificate Revocation System," which also filed August 5, 1997, and entitled "Certificate-Based Certificate Continuation-in-part of U.S. Patent Application 08/906,464 (Abandoned), filed December 9, 1996, entitled "Certificate-Based Revocation System" (now U.S. 5,717,758), which is based on U.S. Provisional Application 60/024,786, filed September 10, 1996, entitled "Certificate-Based Certificate Revocation System," and based on U.S. Patent Application 08/08, filed April 23, 1996 636,854 (now US Patent 5,604,804), and also based on US Provisional Application 60/025,128, filed August 29, 1996, entitled "Certificate Revocation System." U.S. Patent Application 08/992,897 is also a continuation-in-part of U.S. Patent Application 08/756,720 (Abandoned), filed November 26, 1996, entitled "Segmented Certificate Revocation List," based on August 29, 1996 filed on U.S. Provisional Application 60/025,128, entitled "Certificate Revocation System," and also based on U.S. Patent Application 08/715,712 (abandoned), entitled "Certificate Revocation System," filed September 19, 1996, and Also based on US Patent Application 08/559,533 filed November 16, 1995 (now US Patent 5,666,416). US Patent Application 08/992,897 is also a continuation-in-part of US Patent Application 08/992,897, filed November 19, 1996, entitled "Certificate Issuance List" (now US Patent 5,717,757), based on August 29, 1996 US Provisional Application 60/025,128, entitled "Certificate Revocation System," and in part U.S. Patent Application 08/804,869, entitled "Tree-Based Certificate Revocation System," filed February 24, 1997 (filed A continuation of renunciation), especially. Continuation of U.S. Patent Application Serial No. 08/741,601 (Abandoned), filed November 1, 1996, entitled "Tree-Based Certificate Revocation System," which is based on application filed November 2, 1995, entitled "Tree-Based "Certificate Revocation System" for U.S. Provisional Application 60/006,143. US Patent Application 08/992,897 is also a continuation-in-part of US Patent Application 08/823,354, filed March 24, 1997, entitled "Certificate Revocation System" (now US Patent 5,960,083), which was filed on November 16, 1995 Continuation of filed U.S. Patent Application 08/559,533 (now U.S. Patent 5,666,416), entitled "Certificate Revocation System," based on U.S. Provisional Application 60/006,038. U.S. Patent Application 10/103,541 is also based on U.S. Provisional Application 60/277,244, filed March 20, 2001, and U.S. Provisional Application 60/300,621, filed June 25, 2001, and U.S. Provisional Application Apply 60/344,245. All of the above applications are hereby incorporated by reference.

This application is also a continuation-in-part of U.S. Patent Application Serial No. 09/915,180, entitled "Certificate Revocation System" (pending), filed June 25, 2001, the teachings of which are incorporated herein by reference, itself 2000 Continuation of U.S. Patent Application 09/483,125 (pending), filed January 14, 1999, which is a continuation of U.S. Patent Application 09/356,745 (abandoned), filed July 19, 1999, which was filed March 1997 Continuation of U.S. Patent Application 08/823,354 (now U.S. Patent 5,960,083) filed on the 24th, which is a continuation of U.S. Patent Application 08/559,533 (now U.S. Patent 5,666,416) filed on November 16, 1995, based on the 1995 U.S. provisional application 60/006,038 filed October 24 (abandoned). The teachings of all of the above applications are incorporated herein by reference.

This application is also a continuation-in-part of U.S. Patent Application 10/395,017 (pending), filed March 21, 2003, entitled "Certificate Revocation of Validity," the teachings of which are incorporated herein by reference, which are themselves Continuation of U.S. Patent Application 10/244,695 (pending), filed September 16, 2002, which is a continuation of U.S. Patent Application 08/992,897, filed December 18, 1997 (now U.S. Patent 6,487,658), based on U.S. Provisional Patent Application 60/033,415, filed December 18, 1996, and a continuation in part of U.S. Patent Application 08/715,712 (abandoned), filed September 19, 1996, entitled "Certificate Revocation System," It is based on U.S. Patent Application 60/004,796, filed October 2, 1995, entitled "Certificate Revocation System," and in part, also filed October 10, 1996, and entitled "Tree-Based Certificate Revocation System" Continuation of U.S. Patent Application 08/729,619 (now U.S. Patent 6,097,811), which is based on U.S. Patent Application 60/006,143, filed November 2, 1995, entitled "Tree-Based Certificate Revocation System," and in part Also a continuation of U.S. Patent Application Serial No. 08/804,868 (Abandoned), filed February 24, 1997, entitled "Tree-Based Certificate Revocation System," which was filed on November 1, 1996, and entitled "Based on Continuation of U.S. Patent Application 08/741,601 (Abandoned), "A Tree-Based Certificate Revocation System" based on U.S. Patent Application 60/006,143, filed November 2, 1995, entitled "A Tree-Based Certificate Revocation System" , and is also a continuation-in-part of U.S. Patent Application Serial No. 08/872,900 (Abandoned), filed June 11, 1997, entitled "Certificate-Based Revocation System," which was filed on November 5, 1996, and entitled is a continuation of U.S. Patent Application 08/746,007 (now U.S. Patent 5,793,868) for "Certificate Revocation System," which is based on U.S. Patent Application 60/025,128, filed August 29, 1996, and entitled "Certificate Revocation System," and It is also based on U.S. Patent Application 60/035,119, filed February 3, 1997, entitled "Certificate Revocation System," and in part, also filed August 5, 1997, entitled "Based on the Prominent Certificate Revocation System" Continuation of U.S. Patent Application 08/906,464 (Abandoned), which is a continuation of U.S. Patent Application 08/763,536, filed December 9, 1996, entitled "Certificate-Based Revocation System" (now U.S. Patent 5,717,758) Continuation based on U.S. Patent Application 60/024,786, filed September 10, 1996, entitled "Certificate-Based Revocation System," and also based on U.S. Patent Application 08/636,854, filed April 23, 1997 (now U.S. Patent 5,604,804) and U.S. Patent Application 60/025,128, filed August 29, 1996, entitled "Certificate Revocation System," and in part, also filed November 26, 1996, entitled "Certificate in Sections A continuation of U.S. Patent Application 08/756,720 (Abandoned), filed August 29, 1996, entitled "Certificate Revocation System," and based on September 1996 U.S. Patent Application 08/715,712, entitled "Certificate Revocation System," filed on the 19th (abandoned), and also based on U.S. Patent Application 08/559,533, filed November 16, 1995 (now U.S. Patent 5,666,416), and It is also a continuation-in-part of U.S. Patent Application Serial No. 08/752,223 (now U.S. Patent 5,717,757), filed November 19, 1996, entitled "List of Certificate Issuance," which is based on application filed on August 29, 1996, entitled " US Patent Application 60/025,128, "Certificate Revocation System", and is also a continuation in part of US Patent Application 08/804,869 (Abandoned), filed February 24, 1997, entitled "Tree-Based Certificate Revocation System", which is a continuation of U.S. Patent Application Serial No. 08/741,601 (Abandoned), filed November 1, 1996, entitled "Tree-Based Certificate Revocation System," which is based on Tree-like Certificate Revocation System" U.S. Patent Application 60/006,143, and in part, U.S. Patent Application 08/823,354, filed March 24, 1997, entitled "Certificate Revocation System" (now U.S. Patent 5,960,083) Continuation of U.S. Patent Application Serial No. 08/559,533 (now U.S. Patent 5,666,416) filed November 16, 1995, entitled "Certificate Revocation System," based on application filed October 24, 1995, entitled US Patent Application 60/006,038 for a "Certificate Revocation System." The teachings of all of the above applications are incorporated herein by reference.

technical field

The present invention relates to the field of digital certificates, in particular to the field of verification of digital certificates for controlling physical access.

Background technique

A digital certificate (C) consists of the digital signature of the issuing authority (CA), which securely brings together several values: SN, a serial number unique to the certificate, PK, the user's public key, U-user's identifier, D ₁ - Date of Issue, D ₂ - Expiration Date, and additional fields. Expressed notationally, C = SIG _CA (SN, PK, U, D ₁ , D ₂ , . . . ).

It has been widely proven that digital certificates provide the best form of Internet and other access authentication. However, they are also difficult to manage. Certificates may expire after one year (ie _D2 - _D2 = 1 year), but they may be canceled before their expiration, for example, because their holders leave their company or take a different position within the company. Thus, every transaction enabled by a given digital certificate requires appropriate proof that the certificate is currently valid, and this proof typically needs to be archived to protect future claims.

Unfortunately, conventional techniques for proving the validity of issued certificates do not do a very good job. At the capacity of future digital certificates, today's evidence of validity would be both difficult to obtain in a secure manner, and too long, and thus too expensive, to transmit (especially in a wireless setting). Credential validation is generally considered to be a critical issue. Unless effectively addressed, it will severely limit the growth and usefulness of PKI.

Currently, there are two main methods to prove the validity of certificates: Certificate Revocation List (CRL) and Online Certificate Status Protocol (OCSP).

CRLs

CRLs are issued periodically. A CRL essentially consists of a CA-signed list containing the serial numbers of all revoked certificates. The digital certificate presented with the electronic transaction is then compared to the most recent CRL. If a given certificate has not expired but is on the list, everyone knows from the CRL that the certificate is not valid and the certificate holder is no longer authorized to conduct the transaction; otherwise, if the certificate does not appear in the CRL, then The certificate is deduced to be valid (double negative).

CRLs haven't gotten much attention for fear of them becoming unmanageably long. (This fear has been somewhat mitigated by recent CRL partitioning techniques). A few years ago, the National Institute of Standards and Technology tasked MITER Corporation with studying the organization and cost of the federal government's public key infrastructure (PKI). (See Public Key Infrastructure, Final Report; MITER Corporation; National Institute of Standards and Technology, 1994). The study concluded that CRLs constitute by far the largest item on the federal list of PKI costs.

OCSP

In OCSP, the CA answers a query by returning the validity status of C's own digital signature at the current time. OCSP has some problems in the following aspects.

bandwidth. Each validity evidence produced by OCSP is of unusual length. If an RSA or other factorization-based signature scheme is used, in practice, the proof requires a minimum of 2,048 bits for the CA's signature.

calculate. Digital signatures are computationally complex operations. In some large-scale applications, such as peak traffic, OCSP may require computing millions of signatures in a short period of time, which is very expensive in computation.

Communication (if centralized). Suppose a validation server implements OCSP in a centralized fashion. Then, preferably all certificate validity queries would have to be sent to it, and this server would be a large "bottleneck" causing considerable congestion and delay. A "denial of service" outage will likely occur if a large number of honest users suddenly interrogate the server.

Safe (if distributed). Typically, the load of one server is distributed across several (eg, 100) servers strategically located around the world to alleviate network congestion. However, in the case of OCSP, load distribution creates problems worse than it solves. Each of the 100 servers should have its own secret signing key in order to add its response to the certificate challenge it receives. Thus, compromising any one of 100 servers will compromise the entire system. Secure electronic vaults can protect such distribution servers, but are very expensive.

Contents of the invention

The present invention discloses a system and method for controlling physical access through a digital certificate validation process that works with a standard certificate format and enables a Certificate Authority (CA) to certify every The validity status of a certificate C, the time interval starts from C's issue date D ₁ . The time interval for C may be specified within the certificate itself, unless it is the same for all certificates. For example, all certificates may have an interval of one day, and each certificate expires 365 days after issue. Assuming some initial input is provided by the CA, a one-way hash function is used to calculate the specified byte-sized value included on the digital certificate, and to calculate secrets and use other values in the validation process.

Controlling physical access includes checking real-time credentials, where the real-time credential includes a fixed first part and a periodically modified second part, where the second part provides evidence that the real-time credential is up-to-date; by performing operations on the second part and comparing the results with the first part verifying the validity of the real-time credential by comparison; and allowing physical access only when the real-time credential is verified as valid. The first part can be digitally signed by the institution. The institution may provide the second part or the second part may be provided by an entity other than the institution. Real-time credentials can be provided on the smart card. The user can obtain the second portion of the real-time credential at the first location. A user may be allowed access to a second location that is different from and separate from the first location. At least a portion of the first portion of the real-time credential may represent a one-way hash that is applied multiple times to a portion of the second portion of the real-time credential. The number of times may correspond to the amount of time that has elapsed since the first portion of the real-time credential was issued. Controlling physical access may include controlling access through doors.

Description of drawings

The invention will be described with reference to several drawings, in which:

Fig. 1 is a schematic diagram showing how a CA sends to an index blog information about each individual certificate revocation status CRS _i issued by it, wherein these certificates C ₁ , ... C _k have not yet expired, according to an embodiment of the present invention.

Fig. 2 is a schematic diagram of transaction sequence in a non-trivial OCSP environment.

Figure 3 is a schematic diagram of a large "bottleneck" in a server causing considerable congestion and delay.

Figure 4 is a schematic diagram illustrating how OCSP has difficulties in servicing certificate validity requests originating from different security domains.

FIG. 5 is a schematic diagram of serving certificate validity requests from different security domains according to an embodiment of the present invention.

FIG. 6 is a schematic diagram of an RTC system according to an embodiment of the present invention.

FIG. 7 is a schematic diagram of how RTC-over-OCSP will be deployed in a cross-CA environment according to an embodiment of the present invention.

Fig. 8 is a schematic diagram of system operation according to an embodiment of the present invention.

Figure 9 is a schematic diagram of a stolen computer timeline.

Detailed description of the preferred embodiment

Secure Physical Access

It is critical to ensure that only authorized individuals have access to protected areas (eg, at airports, military installations, office buildings, etc.). The protected area may be defined by physical doors (particularly, doors through which people may enter, or doors of containers, safes, or cars) and walls, or may be otherwise substantially defined. For example, a protected area may include an area into which entry will cause a detector to emit an intrusion signal (and, if not authorized, an alarm signal or sound). In airports, generally, entering a gate area through an exit passage will trigger such a signal, even if no gate or wall is violated. It should also be noted that in this application door should be interpreted to include all other types of access-control devices, which may be implemented with keys of traditional or more modern types. In particular, a key mechanism for starting an engine (thus our invention is a new way of ensuring that only the currently authorized user can start an airplane, train, or other valuable access).

Having established the generality of our context, in a specific, but without loss of general conclusion, we refer to "door" as a means of controlling access or establishing a perimeter, and "entry" as access to what one wishes to protect regional means.

Smart doors provide such access control. At the simplest level, a smart door can be equipped with a keypad through which the user enters his/her PIN or password. The keypad has an additional memory or underlying processor in which a list of valid PINs/passwords is kept so that it can be checked whether the currently entered PIN/password belongs to one of the PINs/passwords on the list. If yes, the door is opened, otherwise it remains locked. This basic access control mechanism provides minimal security. In particular, a dismissed employee is no longer authorized to pass through the door; however, if he still remembers his PIN, he will have no problem opening such a basic smart door. Therefore, it is very necessary to "eliminate" the PIN of terminated employees. However, such a procedure is cumbersome and costly: an airport facility may have hundreds of gates, and it would be impractical to send a special team of workers out to "eliminate" all such gates whenever an employee leaves or is fired. There is definitely a need for more security without incurring excessive cost and sacrificing convenience.

Of course, instead of relying (only) on traditional keys or simple keypads, more modern smart doors can work with cards or contactless devices such as smart cards and magnetic stripe cards (either alone or together). But this enhanced facility does not inherently guarantee the security, convenience and low cost of an access-control system. These all depend very heavily on how many of these tools are used in the overall security architecture.

Ideally, a smart door should recognize the person entering and verify that they are currently authorized to enter. Of the two tasks, the first is probably the easier. Identification can be performed in various ways: Specifically:

1. Use PIN and password, which can be entered on the key pad connected to the door;

2. Using biometric features, which can be entered by the user via a special reader connected to the door;

3. Using a traditional signature, which is provided by the user via a special pad attached to the door;

4. Use of smart cards or contactless cards (e.g. PIN sent to the door via a special reader/receiver);

5. Use of digital certificates - if stored on a smart card, contactless card or wireless device, which can be "communicated to the door" via a card reader or other receiver.

We believe that digital certificates are particularly attractive for use within the system of the present invention, and thus we wish to describe in further detail the ways in which they are used with smart cards which we envisage being combined within the system of the present invention. Specifically, but without loss of generality, we refer to a device owned by an individual wishing to access as a "card". The card can store digital certificates and corresponding keys. Based on appropriate instructions from the cardholder (e.g. executed by pressing a password on a keypad on the card), the card transmits the digital certificate to the door mechanism and executes the identification protocol (e.g. decrypting a random challenge) by using the corresponding key . Preferably, the digital certificate, and in particular its corresponding key, should be protected within a secure hardware part of the card/device.

In some cases, it may be desirable to have access control for anonymity rather than security. In this case, identification does not need to be performed, but authorization does. In most cases, however, some form of identification is prescribed: we therefore assume that identification can or has been performed (eg by one of the 5 methods above). In summary: How can authorization be enforced? Even if the door knows for sure that it is dealing with John Doe, how can the door ensure that John Doe is the one who currently has the right to enter? Traditionally, a smart door consults a database of currently (eg, a given day/date) authorized users to verify that it is in fact the individual requesting access. But this requires the smart door to connect to a remote database. Also, this is no ordinary network connection: it must be a secure network connection. Actually, not only must password protected communication be used to prevent an imposter from impersonating the database connected to the door, but the enemy must also be prevented from cutting the cable connecting the door to the database, otherwise once disconnected, the door must choose from equally bad options :( a) always open or (b) always remain closed. But the security network connection can easily make the cost of the electromechanical components of the door lock small: the wiring assembly can cost up to $1000, and the security network connection can cost $4000 (more if the cable must be connected safely over a large distance, such as in an airport. Moreover, even After spending this $4000, is there a secure network connection in a public place such as an airport? It should be noted that it is also not possible to provide a smart door with a wireless connection to a remote database. First, long-distance wireless transmitters and receivers are very Expensive. Second, in some facilities, wireless bandwidth may be severely limited (to avoid possible interference with other devices) or such use prohibited at all. Third, wireless communications can easily jam, effectively disconnecting the gate from the database (thus forcing it to choose two equally bad decisions). Fourth, if the door belongs to a container in the middle of the Atlantic, it is likely that it cannot communicate wirelessly with any database on shore at all).

It is thus an aspect of the present invention to provide a low cost, convenient and safe separate smart door that is a low cost, convenient and safe smart door that is not connected (whether wired or wireless) to any database or mechanism.

Digital Signatures and Certificates

In a preferred embodiment, the present invention relies on digital signatures, and preferably on 20-byte technology. Digital signatures (such as RSA) are used to prove that a specific message M originates from a specific user U. For this purpose, U generates a pair of matching keys: a verification key PK and a signing key SK. The digital signature is generated by SK and verified by matching key PK. User U should keep his own SK secret (so that only U can sign on behalf of U). Digital signatures work because the PK does not "betray" the matching key SK, i.e., knowledge of the PK does not give the enemy any real advantage in computing the SK. Therefore, user U should make his own PK as public as possible (so that everyone can verify U's signature). For this reason, the PK is best called a public key. We will denote the digital signature of U of message M by SIG _U (M). Digital signatures are meant to include private key signatures, in which case the signer and verifier may share a common key.

The alphanumeric string called the certificate enables digital signatures by guaranteeing that the specific key PK is indeed the user U's public key. Once the user's identity is determined, a certificate authority (CA) generates and issues a certificate to the user. Thus, the certificate proves to everyone that the CA has verified the holder's identity, and possibly other attributes. (eg, if a company acts as its own CA and issues certificates to its employees, the certificate serves as a sort of proof that its holder is authorized to bind his/her employer). Certificates expire after a specified amount of time, typically 1 year in the case of public CAs. In essence, a digital certificate C consists of the CA's digital signature, which securely combines several numbers: SN, unique certificate serial number, PK, user's public key, U, user's name, date of issue D ₁ , Expiration date D ₂ , and additional data. Expressed notationally, C = SIG _CA (SN, PK, U, D ₁ , D ₂ , . . . ).

Certificates can also include cases where the PK is an encryption key. In this case, U can prove its identity to verifier V by sending certificate C to V, and having V encrypt a random challenge (string) R with key PK, and then request U to send back the decryption. If the user responds with R, V is confident that it is dealing with U, since only U knows the decryption key that matches PK.

Preferred embodiments of the present invention provide a very good solution for access control. In particular, if the card contains a digital certificate according to the invention, authorization will be performed very cheaply. Instead of asking the central database for the validity of each digital certificate, the gate need only obtain the 20-byte validity proof according to the invention, which confirms the current validity of the card.

example 1:

Now, A is the institution (i.e. entity) that controls a set of smart doors, and U is the users who should be authorized to access a specific door during a specific time period.

Each user has a card (as in the aforementioned general sense of the card).

Each smart door has an associated card reader (generally capable of communicating or at least receiving information from a user's card), which is linked to an electromechanical lock in the case of a true physical (rather than virtual) door. Preferably, each door also has a unique identifier (and knows its own). The door has a card reader and a lock that cannot be tampered with, and a computing device that has A's public key PKA and can verify A's signature.

During a certain period of time, the agency decides which user can go through which door. (For example, without loss of generality, we assume that each time interval of interest consists of days.) For this purpose, A can use its own private database DBl, which holds all permissions, which are who has the right to pass which door on that day (or any day in the foreseeable future). Presumably, A protects this database, otherwise an adversary could alter the permissions stored there for his own purposes. However, A calculates the public database PDB from DB as follows. For each user U who has permission to pass through door D on day d, A computes a digital signature SUDd, which states that this is indeed the case. For example, A calculates SUDd= _SIGA (U,D,d). It should be noted that only A can compute these digital signatures, and everyone who has A's public key PKA can verify them. It is impossible for someone who does not know A's key SKA to forge these signatures, and they cannot modify them in any way (such as converting U's permission to an unauthorized user U's permission) without invalidating these signatures. sign. Thus, A can compute and send (eg at the beginning of the day) these signatures to the repository PR in time and without much worry. A repository is a place that can be accessed by users. For example, a server located at the employee entrance of a large facility, such as that of an airport. Since A's signature is unforgeable, the connection between A and PR need not be secure. It is sufficient for A to successfully transfer its signature to PR within a reasonable time.

When employee U arrives at work at the facility on day d (e.g., via an entry point at which the PR is located), he may connect his card to the PR (e.g., he inserts the card into a card reader connected to or in remote communication with the PR /Recorder). By doing so, it gets SIGUDd on its card, indicating that it is authorized to pass through the digital signature of door D on that day. This requires an entry point to connect to A rather than hundreds of doors, and the connection also does not need to be secure. Actually, D doesn't have to refer to only a single door. For example, it may refer to a group of doors (such as baggage handling doors), and A's signature means that U can pass through each door referred to by D. Alternatively, multiple gates Dl,...,Dn may be specified one by one, and the fact that U can pass through each of them may be indicated by more than one signature of A. For example, SIGUD1d...SIGUDnd. In this case, all these signatures are transferred to U's card.

Now assume that during a day d U walks around the facility and arrives at door D for which he has authorized clearances. So its card now saves SIGUDd. U can then insert his card C into the card reader at door D. The processor associated with the gate then uses A's public key to verify that SIGUDd is indeed valid. It then verifies that the current day is indeed d using its own clock. If both are true, then door D is open. It should be noted that the door can check that it is indeed the card holder by performing various means of identification. In particular, U may also be required to enter his PIN on the keypad associated with the door. (Note that, unlike before, a fired employee cannot enter door D even if he remembers his PIN. In fact, the door in this example will require both the PIN and the correct signature for the day. However, after U has been fired , A no longer produces the signature SIGUDd for any subsequent day d, so U cannot provide this signature to the door. Nor can he forge this signature of A. Therefore, he cannot "convince" D on any day after his dismissal Open.) Alternatively, the card may transfer SIGUDd to D's card reader only if U enters the correct PIN on the keypad on the back of C, and only after the card proves that it is indeed U's card, store Library PR downloads SIGUDd to card C. Alternatively, U can delineate the identifier of a card C belonging to U, and when inserted in a card reader, the card can prove that it is indeed card C, eg by means of a cryptographic protocol. Or, finally preferably, U's card carries U's certificate, and after entering the correct PIN, the card proves U's identity by decrypting the door's random challenge. In this case, SIGUDd preferably indicates that U has permission to pass through gate D, by indicating that U's certificate carries the permission of its owner. For example, SIGUDd=SIGuDd, where u is the identifier of U's certificate, such as the serial number (and issuer) of U's certificate.

In all of these ways, it should be appreciated that the gate is "separated" from A. The gate only (possibly identifies U and) checks that U has permission to enter via internal calculations and using A's public key and its own internal clock. Therefore, the system is not only very safe, but also very economical.

This proof of validity or authorization can be provided in a number of different ways. The following is an example of how this is done.

Example 2:

Proof of validity can be "obtained" by the card owner at the appropriate time. For example, in a work environment, current evidence of effectiveness is available to each person when they report for work and start work. In many workplaces (particularly those that are security sensitive, such as airports), employees sign in when they report to begin work. This "check-in" may include taking the 20 byte valid value, SIGUDd, and storing it on the card. The card can obtain this value via a wired or wireless connection.

Example 3:

Cards can obtain proof of validity over a wireless network such as a pager network. At the appropriate time, if the card is authorized for access, the 20 byte value is sent to the card. It should be noted that the bandwidth requirements are minimal: the grant value is shorter than a typical message transmitted by a pager network. At the appropriate time, if the card is authorized for access, SIGUDd is sent to the card.

Example 4:

Via a wired or wireless network, the door can similarly obtain proof of validity in advance for each card it expects to encounter.

Example 5:

When the card begins to interact with it, the door can obtain proof of the validity of the card on demand.

It should be noted that none of the above methods require any kind of secure connection between the gate and the central server. This is because the validity proof is self-authenticating so that even if the gate receives the validity proof from an untrusted source and/or over an insecure connection, its validity can still be determined. The fact is that in large and/or remote areas, areas with multiple doors, and moving areas, such as the doors of an airplane or train, these methods do not require connections at all for the doors to provide a better means for access control.

It should also be noted that in this application, doors and protected areas should be construed to include all other types of access points that may be secured by traditional or more modern types of keys. In particular, a key mechanism for starting an engine (so that only currently authorized employees can start an airplane, train or other engine).

Those skilled in the art will recognize that 20-byte validity proofs are a particularly restricted type of digital signature scheme, and while they offer unique advantages, such as compression and efficiency, by practicing this method with more general digital signature schemes Many other advantages are available to the invention, which may not require validation techniques. The components of the preferred embodiment of the invention are: (1) a door mechanism capable of verifying a digital signature, which is connected to a device that opens the door upon successful verification; Authorization to enter has been granted for a specified period of time; (3) A card or other wired/wireless device component capable of receiving a digital signature and presenting it.

Access authorization can be accompanied by one of the following sequence of steps:

Order 1:

(1) The mechanism component causes the card to receive the authorized signature;

(2) The card receives and saves the authorized signature;

(3) The card presents the authorized signature to the door, which verifies the signature and only opens if the authorized signature is valid.

Sequence 2:

(1) Present the card to the door to request access authorization;

(2) The door requests an authorized signature;

(3) The mechanism component enables the door to receive the authorized signature;

(4) The door verifies the authorization signature and opens only if it is valid.

Order 3:

(1) The card requests an authorized signature from the institution component;

(2) The agency component transmits the authorized signature to the card;

(3) The card receives and saves the authorized signature;

(4) The card presents the authorization signature to the door, which verifies the signature and only opens if the authorization signature is valid.

Order 4:

(1) A door receives in advance (or at its own request or not) authorized signatures from an agency component for multiple cards it anticipates encountering;

(2) Present the card to the door to request access authorization;

(3) The door verifies the authorized signature of the card and opens only if it is valid.

These sequences are only some of the many examples. Additionally, these orders can be combined. For example, a door may receive one part of the information/authorization (such as a 20 byte value), while a card may receive another part (such as a digital certificate). They can also be separated in time: the card can first receive one part of the information/authorization (eg digital certificate) and later the other part (eg hourly 20 byte value).

Additionally, an authorized digital signature can be assigned to the cardholder's long-term certificate. For example, the card may contain a long-term certificate that is valid for each year, and the authority component may issue a daily signature to verify that the certificate is still valid for the current day.

Authority components can automatically generate authorizations without any request. For example, an agency component may generate authorization signatures each night for employees who will be authorized the next day. This approach enables the authorization components to be non-interactive and thus easier to build securely.

Additionally, the authorization component may use a separate, potentially insecure device for distributing authorization signatures to cards and/or doors. This will enable the authorization component to focus on only one task: generating authorizations. It would not require a cumbersome direct connection between the security authorization component and the (possibly less secure) door and card. In particular, distribution of authorizations may occur as follows: (1) the agency component generates the authorization; (2) the agency component transmits the authorization to the distribution database over a possibly insecure connection. These databases can be in multiple locations and need not be secure. For example, in a company with 5 employee entries, there might be a distribution database at each entry. (3) The distribution database transmits the authorization to the card and/or door, either on request ("pull") or automatically ("push").

The feature that enables the above distribution is that the authorization itself is unforgeable, it can only be generated by institutional components. Therefore, once generated, it can be distributed over potentially untrusted circuits and devices without any security risk. This eliminates the need for any other party or device to interact with the mechanism components, thus resulting in a cheaper solution than any solution requiring a secure connection.

In fact, none of the connections between any components in the system need be secure. (Only the institutional component itself must be secured so that improper authorization cannot be generated.) Thus, fault-tolerant, distributed access authorization architectures can be more easily built. Furthermore, as mentioned earlier, it is possible to build this architecture without requiring any connections for the gates.

It should be appreciated that the access control system of the present invention can be combined with the tenant CAs of Section 3. For example, several facilities (e.g., within an office building, a parking agency, a cleaning agency, or multiple companies sharing the use of an office building) may maintain separate controls over the holders' ability to access different protected areas Use the same certificate.

Example 6:

The system may operate as follows. The user U (or his card) has a certificate CERT containing a confirmation field - ie D365 - for each door D of interest. U's permission to pass through gate D on day j can be proven by releasing the unforgeable 20-byte value X365 _-j . Gate D can check the license by hashing it j times and checking that the result agrees with the validity field D365 of the CERT. If A has to cope with multiple gates (say 1000 gates), the CERT can contain 1000 different validity fields, each field corresponding to a different gate, and each gate Dj checks its relative to the jth validity field calculation. In this case, each user has at most 1000 proofs on a specific day even if the user's permission through each gate is provided separately. Thus it requires at most 20k bytes to be loaded on its card on a given day.

It should be noted that since the card is a normal card here, the card may be a contactless card, the reader may be the receiver, and the card need not be inserted into the reader but transmitted to the reader. Note that this "wireless" card-reader interaction is also very local and very different from the card-mechanism/database interaction when A or the database is at a distance.

Additionally, an authorized digital signature can be assigned to the cardholder's long-term certificate. For example, the card may contain a long-term certificate that is valid for each year, and the authority component may issue a daily signature to verify that the certificate is still valid for the current day.

Authority components can automatically generate authorizations without any request. For example, an agency component may generate authorization signatures each night for employees who will be authorized the next day. This approach enables the authorization components to be non-interactive and thus easier to build securely.

In fact, none of the connections between any components in the system need be secure. (Only the institutional component itself must be secured so that improper authorization cannot be generated.) Thus, fault-tolerant, distributed access authorization architectures can be more easily built. Furthermore, as mentioned earlier, it is possible to build this architecture without requiring any connections for the gates.

It should be appreciated that the access control system of the present invention can be combined with the tenant CAs of Section 3. For example, several facilities (e.g., within an office building, a parking agency, a cleaning agency, or multiple companies sharing the use of an office building) may maintain separate controls over the holders' ability to access different protected areas Use the same certificate.

Record access evidence for detached doors

While separate (separate from the mechanism and database) and also very secure, a low-cost and convenient smart door is preferably a connected smart door, which provides the ability to record access through a specific door. For example, it is very important to know who has passed through a particular door on a particular day. Connected gates do this easily by sending the appropriate access information to remote databases or institutions. But the separated door cannot completely do this. Access information may be collected by sending the appropriate personal information to collect that information from door to door. This is not always convenient to do. However, the system below offers very viable options.

When user U passes (or attempts to pass) door D at time t, the door may generate the appropriate string LOGUDt and save it locally (at least temporarily). To ensure that this information reaches the appropriate database, the door may use a card for entry through it. For example, D may write (or cause LOGUDt to be written) on the cards of other users U (possibly including U himself). Whenever U is connected to PR (eg next business day) or any other wired or well-connected device, PR or said device transmits LOGUDt to the appropriate database. In this case, the appropriate database will be the last to receive and then store the LOGUDt more permanently in a more easily verifiable manner. It is possible that the database will receive a redundant copy of LOGUDt, but it is easy to clean up any unwanted redundancy and keep only the original copy.

The preferred LOGUDt includes U's own digital signature. In this case, U cannot be easily denied when he passes a certain door at a certain time, and U claims that the access information of the door is forged. In fact, only he has the secret signed key used to generate LOGUDt. For example, LOGUDt e consists of SIG _U (D,t), which indicates that U passed gate D at time t. This is very easy to achieve if the user U's card carries a privately signed key SKU that matches the public key PKU. Preferably, the card also carries PKU's digital certificate, and thus LOGUD may include not only SIG _U (D,t), but also U's certificate. Also preferably, the user card can generate a SIG _U (D,t) from the time t displayed on its own clock, and the door can provide this access proof only at U (possibly in addition to other authorization proofs such as those previously discussed ) SIG _U (D, t) then lets U in if the time identified by U is close enough to the current time t as measured by the gate clock. A user may also ask to enter door D at time t, but that door is in another place entirely, so SIG _U (D, t) can't at all prove that he has passed through, say, the second door on the third floor of a particular building: some The pass in question transmits the location to the door's card reader, etc. To prevent such a request, or to protect the user from such fraud, the user card (device) can incorporate a GPS mechanism, and SIG _U (D, t) can actually include the local position LP measured by the card. In this case, the user can approach the access proof SIG _U (D, t, ps) towards the door, which accepts it and only lets the user in if not only the time looks correct but also the local location. Instead of calculating ps within the card/device, the user can use one or more components that they trust and which can calculate the user's location (and possibly their own) from the information they receive from the user.

implement

basic system

As seen in Figure 1, the CA sends individual certificate revocation status information CRS to the directory for each of its issued certificates C ₁ , . . . C _k that have not yet expired. The directory sends CRS _i to the requesting user who has asked the issuing authority for a certificate with serial number "i".

The present invention discloses a system and method for controlling physical access through a digital certificate validation process that works with a standard certificate format (such as X.509v3) and that enables a Certificate Authority (CA) to certify The validity status of each certificate C for any time interval (such as daily, hourly, or minutely) from the issue date _D1 of C, the time interval of C may be specified within the certificate itself, unless it is the same for all certificates. For purposes of specificity but not limitation, below we assume an interval of one day for all certificates, with each certificate expiring 365 days from its issuance.

Make a certificate C. In addition to traditional numbers such as serial number SN, public key PK, user name U, issue date D ₁ , expiration date D ₂ (=D ₁ +365), the certificate C also includes two unique 20-byte value. Specifically, before issuing certificate C, the CA randomly selects two different 20-byte values, Y ₀ and X ₀ , and computes from them two corresponding 20-byte values, Y ₁ and X ₃₆₅ , which use the enjoyment A one-way hash function H with the following properties: H is at least 10,000 times faster than digital signature computation; H produces a 20-byte output no matter how long the input is; and H is hard to reverse: Given Y, find X such that H(X) = Y is practically impossible. (See, e.g., the Secure Hash Standard; FIPS PUB 180, Revised Jul 11, 94 (Federal Register, Vol. , Vol.59, No.150, pp.39937-40204)). The value Y ₁ is computed by hashing Y ₀ once: Y ₁ =H(Y ₀ ); X ₃₆₅ is computed by hashing X ₀ 365 times: X ₁ =H(X ₀ ), X ₂ =H(X ₁ ),. . . . X ₃₆₅ =H(X ₃₆₄ ). Since H always produces 20 bytes of output, Y ₁ , X ₃₆₅ and all intermediate values X _j are 20 bytes long. The values Y ₀ , X ₀ , X ₁ , ..., X ₃₆₄ are kept secret, while Y ₁ and X ₃₆₅ are included in the certificate: C = SIG _CA (SN, PK, U, D ₁ , D ₂ , .. ., Y ₁ , X ₃₆₅ ). We will refer to Y ₁ as the abolition target and X ₃₆₅ as the effective target.

Revocation and confirmation of certificate C that has not yet expired. On the i-th day after C is issued (ie, on D ₁ +i days), the CA calculates as follows and releases the 20-byte evidence of C's state. If C is revoked, then as evidence of C revocation, CA releases Y ₀ , ie, the H-inverse of the revoked target Y ₁ . Otherwise, as evidence that C was valid that day, CA releases X _365-i , ie, the ith H inversion of the valid target X ₃₆₅ . (For example, proof that C is valid 100 days after issue consists of X _265. ) The CA may release Y ₀ or X _365-i by providing a value in response to a challenge or sending it on the World Wide Web.

Verify the status of certificate C that has not expired. On any day, C's revocation proof Y ₀ is verified by hashing Y ₀ once and checking that the result is equal to C's revocation target Y ₁ . (i.e., the verifier himself tests that Y ₀ is really the H inversion of Y _1. ) Note that Y ₁ is guaranteed to be the abolition target of C, since Y ₁ is proved within C. On the i-th day after C is issued, C's valid proof X _365-i for that day is verified by hashing the value X _365-i i times and checking whether the result is equal to C's valid target X ₃₆₅ . (ie the verifier himself tested that X _365-i is really the H inversion of X ₃₆₅ ). Note that the verifier knows the current date D and C's issue date D ₁ , (since D ₁ is proven in C), and thus immediately computes i=DD ₁ .

Security piece

Evidence of revocation cannot be falsified. Certificate C's revocation proof consists of the H inversion of C's revocation target Y ₁ . Because H is essentially impossible to invert, once a verifier checks that a given 20-byte value Y ₀ is indeed proof of C's revocation, it knows that Y ₀ must have been released by the CA. In fact, only the CA can compute the H inversion of Y ₁ : not because the CA can invert H better than anyone else, but because it computes Y ₁ by starting with Y ₀ and hashing it. Because CA never releases C's revocation proof as long as C remains valid, the enemy cannot forge the revocation proof.

Evidence of validity cannot be falsified. On day i, certificate C's validity proof consists of the ith H inversion of C's validity target X ₃₆₅ . Because H is essentially impossible to invert, once a verifier checks that a given 20-byte value X _365-i is indeed proof of C's validity on day i, it knows that the CA must have released X _365-i . In fact, only CA can compute the ith H inversion of X ₃₆₅ : not because CA can invert H better than anyone else, but because it computes X ₃₆₅ by starting with X ₀ and hashing it 365 times, thus Computes all first 365 inversions of X ₃₆₅ . If certificate C is revoked on day i+1, the CA has released the values X _365-1 , ..., X _365-i in the previous i days (while C was still valid) but has not yet released and will release forever in the future Value X _365-i-1 (or any other value X _j , j<365-i). Therefore, to falsify the evidence that C is valid on day i+1, the enemy should calculate the i+1 ^st H inversion of X ₃₆₅ (ie the H inversion of X _365-i ), which is very difficult to implement. Similarly, the adversary cannot compute evidence of validity for C for any days after i+1. To do that, it should be possible to invert the H again based on the input X _365-i. For example, if it can calculate the proof of validity of C on day i+2, X _362-i-2 , then by hashing it once, the H inversion of X _365-i-1 , X _365-i can be easily obtained .

efficiency

Certificate C includes only two additional 20 byte values, Y ₁ and X ₃₆₅ . This is a negligible cost. Canceled C already includes data CA signature (at least 2048 bits long), which includes the public key PK (at least 1024 bits long), and C can include comments and a lot in addition to SN, PK, U, D ₁ and D ₂ other data.

Generates and requires only 366 hashes. This is a negligible cost. It cancels the requirement that the issuing certificate already requires computing a signature.

Revocation Proof and Validity Proof are only 20 bytes long. Our 20-byte proofs are both trivial to transmit and store, making 20-byte technology ideal for wireless applications (where, since bandwidth is still limited, many mobile phones and other wireless devices also have limited storage capacity).

Proofs according to embodiments of the present invention can be so short because they derive their security from fundamental cryptographic components, like one-way functions, which can exhibit exponential security. (Very differently, digital signature schemes have complex security requirements. Typical number-theoretic implementations of them provide at best sub-exponential security, and thus necessitate very long keys.) Regardless of the total number of certificates Hundreds or billions, evidence remains 20 bytes long. In fact, there are 2 ¹⁶⁰ possible 20-byte strings, and the probability that two certificates happen to have the same proof of revocation or validity is negligible.

It should also be noted that our 20-byte proof does not increase in length due to encryption or authentication. Our 20-byte proofs tend to be public and thus don't have to be encrypted. Similarly, our 20-byte proofs are self-authenticating: by hashing them the appropriate number of times, they yield the validity or revocation goal specified in the certificate. If forged or altered, they will not work and thus do not have to be signed or authenticated in any way.

Finally, the 20-byte validity proof X _365-i at day i does not have to additionally include the value i: in a sense it already includes its own timestamp. Indeed, as stated above, i is the difference between the current date and the certificate's issue date, and if hashing X _365-i i times yields the validity target for certificate C, then this proves that X _365-i is C on day i evidence of effectiveness.

The 20-byte proof is computed immediately. Revocation evidence Y ₀ or validity evidence X _365-i is simply retrieved from memory. (Alternatively, if only X ₀ is saved during certificate issuance, each X _365-i can be recalculated on the fly at i days; e.g., by hashing at most 364 times. A surprisingly more efficient strategy is in the following discussed in the section.)

wireless environment

Embodiments of the present invention are ideal for wireless implementations. Its scalability is enormous: it can easily provision billions of certificates. It requires negligible bandwidth, essentially a 30-bit sequence number for the query and 20 bytes for the response. The computation it requires is also negligible, since certificate status queries are answered by a single table lookup and can be verified immediately. Of course, the large scalability, minimal bandwidth, and trivial computation make the present technique an option in wireless environments.

But there is another application of the invention which provides additional advantages in wireless applications. That is, each morning—eg, at midnight—a wireless user may receive a 20-byte proof of validity of his certificate for the remainder of the day. (The 20-byte value can be obtained based on the user's request, or automatically pushed to the user's mobile device—for example, by means of an SMS message or other control message.) Due to its insignificant length, this proof can be easily saved in a large file. Most mobile phones and PDAs. Then, no matter what time of day the user wants to transact, the user simply sends their own certificate along with the certificate's 20 byte proof of validity for that day. Since validity evidence is verifiable everywhere, verifiers of certificates and evidence do not have to invoke any CA or any responder. Validators work completely offline. In a mobile environment, where any call translates into a cost in money and time, this offline capability is very valuable.

Compared with OCSP

Both the present invention and OCSP are on-demand systems: that is, a user sends a query about the current validity of a certificate and retrieves in response an unforgeable and everywhere verifiable proof. But there are also the following differences: time accuracy; bandwidth; CA efficiency; security;

Time precision: In principle, OCSP can specify time with great precision, whereas responses according to a preferred embodiment of the invention specify time with predetermined precision: one day, one hour, one minute, etc. In low-value applications, 1-day availability is generally accepted. For most financial applications, Digital Signature Trust considers 4 hours of accuracy to be sufficient. (Perhaps this is less surprising than it seems: for most financial transactions, orders received in the morning are executed in the afternoon, and orders received in the afternoon are executed the next business day.) In any case, time is not dictated by Real number designation of infinite number of Arabic numerals. Time accuracy of less than 1 minute is rarely meaningful in a request-for-validation system, since the clocks of the challenge and certificate relying parties may not be synchronized. In fact, in such a system, a time accuracy of 15 seconds is practically real time.

To handle such extreme precision, the preferred embodiment of the present invention computes approximately 1M long hash chains (ie, needs to compute X _1M validity fields), since there are at most 527,040 minutes in a year. The preferred embodiment of the invention is practically real-time if such long chains can be efficiently processed. Computing 1M hashes when certificates are issued is no problem: 1M hashes can be performed in less than 1 second, even with very reasonable platforms, and certificates are usually issued once a year without huge time pressure. Similarly, 1-second calculations are no problem for verifiers of certificate validity proofs (such as merchants relying on certificates), given that they are usually only concerned with individual transactions and have more time. However, computing the 1M hash from the certificate status request may affect the performance of the server that produces the proof of validity, since it typically handles many transactions at a time. Fortunately, the server does not have to compute all these hashes starting at X ₀ online, but instead does a table lookup - utilizing the entire hash chain with each certificate in memory. However, keeping 1M long hash chains can be a problem in applications with a huge number of certificates. But, fortunately, as we will mention later, even an ordinary server can recalculate a 1M long hash chain with surprising efficiency by using a better algorithm.

Bandwidth: The preferred embodiment of the present invention has a significant bandwidth advantage over OCSP. The former uses a 20-byte answer, while the latter typically uses 256 bytes.

CA Efficiency: In the case of OCSP, the validity query is answered by a (complex) digital signature, while in the case of the present invention it is answered by a (trivial) table lookup, as long as the CA keeps the entire X-chain for each certificate.

Note that with a volume of 1 million certificates, a CA can afford to keep the entire X-chain for each certificate when the time accuracy is 1 day or 1 hour. (In the first case, the CA has to save 365 20-byte values, or 7.3K bytes per certificate, so all are 7.3B bytes. In the second case, all are 175.2B bytes.) If With a time accuracy of 15 seconds, each hash chain contains 1M20 byte values, and for the entire system, the total storage requirement would be 10.5 tera bytes, a considerable amount of storage.

To greatly reduce this storage requirement, the CA may only save a single 20-byte value (ie X ₀ ) per certificate, and recompute each _Xi value by at most 1M hashes from it. Alternatively, Jacobsson [5] has discovered a surprising time/storage tradeoff. That is, the CA can recompute all n _Xi values in the correct order by saving the log(n) hash values and performing the log(n) hash each time. If n is 1M, this means that only 20 hashes per certificate are stored, and only 20 hashes are performed each time a certificate needs to be validated. Other compromises are also possible. In particular, for our 1M chain case, Reyzin [R] has shown that CA can compute all _Xi values (i=1M down to 1) by saving only 3 hash values and executing at most 100 secondary hash implementation.

In summary, even in practically real-time applications (ie, using 15 second time accuracy), the preferred embodiment of the present invention can replace complex digital signature operations with a trivial 100 hash operations by saving only 60 bytes per certificate.

Security and Operating Cost: The last two differences will be better discussed after specifying the preferred embodiment of the invention and the type of implementation of OCSP under consideration.

Centralized Implementation: Security Analysis

Whenever attesting to the validity of a certificate relies on the secrecy of a particular key, a secure electronic vault should protect that key to guarantee the integrity of the entire system. By centralized implementation of the present invention or OCSP, we mean that one electronic repository can answer all validity queries. Centralized implementation is preferred if the number of certificates configured is small (e.g. no greater than 100K) so that the e-vault can handle the resulting query volume even if almost all certificates are used within a small time interval, triggering almost simultaneously Validity query. In this implementation, the preferred embodiment is superior to OCSP in the following ways.

Doomsday protection: In traditional OCSP, if (despite the protection of the vault and armor) an enemy succeeds in penetrating the vault and compromising the security of the secret signing key, it can "resurrect" and "revoke" a previously revoked certificate Also valid certificate. (Similarly, if the CRL signing key is compromised in the CRL system). By contrast, in the preferred embodiment of the present invention, penetrating the secure electronic vault does not help an adversary to falsify the validity of any previously revoked certificates. In fact, when a certificate is revoked on day i, not only its revocation proof Y ₀ is made public, but, simultaneously, all its _Xi values (or at least values X ₀ to X _365-i ) are deleted. Thus, after a successful entry, the enemy finds nothing that enables him to "extend" the validity of the revoked certificate. To do that, it should successfully invert the one-way hash H based on X _365-i without any help, where it is welcome to try (and a real try can be done without access to any secure electronic vault) . Worst case, according to the present invention, an adversary can forge the revocation of valid certificates in the system after successful entry, thus preventing honest users from authenticating legitimate transactions. Of course, this is a bad situation, but not as bad as making dishonest users authenticate illegal transactions.

Distributed Implementation: Security and Operating Cost Analysis

Centralized implementation requires that all inquiries regarding certificate validity be sent to the same electronic repository. In applications with millions of active certificates, this can easily lead to long delays and denial of service. To protect against such congestion, delays, and denial of service, the load of answering validity queries can be spread across several geographically separated responder servers. However, in the case of OCSP, each additional responder needs to have a privately signed key, and thus needs to be kept in an electronic vault, making the OCSP system very costly to own. Advanced electronic libraries that meet financial institution requirements cost at least $1M to build, and $1M to run. (A good electronics bank would contain armored concrete, steel doors, generators for backup power, protected fuel banks to run the generators for potential periods of time, etc. Running it would involve a minimum of 4 different groups of 24x7x365 operations , plus management oversight, etc.) In an application where 10 electronic banks are required to ensure a reasonably fast response during peak traffic, the cost of ownership of the OCSP system would be an initial investment of $10M and an ongoing budget of $10M per year . Even with less secure electronic libraries and algorithms, initial and ongoing costs of several million dollars are necessary.

However, in the case of the preferred embodiment of the invention, a distributed implementation can be achieved using one electronic repository (which the CA should have anyway) and any number of "untrusted responders" (ie common servers). Let's look at the exact details of a distributed system according to the invention, specifically assuming (a) there are 10M certificates; (b) there are 1000 servers, strategically located around the globe to minimize response time; and (3) time The interval is 1 day.

CA runs (initialization fee): Every morning, starting with the smallest serial number, compile the 10M record array as follows: For each certificate C with serial number j, save C's 20-byte validity/revocation proof at location j. Next, date and sign F and send it to each of the 1000 servers.

User runs (asking fee): To know the status of certificate C, send C's serial number, j (and CA ID, if necessary) to server S.

Server operation (answer fee): Each morning, if properly dated and signed array F is received, replace old array with new array.

At any time: Answer the query about sequence number j by returning the current 20-byte value of F at position j.

Operation of the preferred embodiment

1. Immediate Preparation of Array F

If the entire hash chain for each certificate is kept, each record is only computed by table lookup operations. In another embodiment, it can also be calculated on the spot.

2.F does not contain a secret

It includes exact and complete accounts of certificates that are still valid as well as certificates that have been revoked. (The CA's goal is actually to make this non-secret information as public as possible in the most efficient way.)

3. Directly transfer F to the server

This is done because F contains no secrets, requires no encryption, and poses no security risk. Despite the large volume of 10M certificates, it is very feasible to send a 200M byte file to 1000 servers at normal intervals.

4. Each server reply is 20 bytes long

Again, each answer does not require encryption, signing or timestamping.

5. No Honest Refusal of Service

Because each value sent is only 20 bytes long, because each such value is computed immediately (via a table lookup), and because the traffic can be spread out to 1000's of servers, there should be no denial of service, at least on the system period of legal use no.

6. The server does not have to be trusted

They only forward the 20 byte evidence received by the CA. Being self-authenticating, these proofs cannot be changed and hashed to the corresponding target.

A distributed implementation of the invention continues to enjoy the same doom protection of its centralized counterpart: ie, it is impossible for an adversary who has successfully gained access to the electronic vault to revive a revoked certificate. Sophisticated adversaries, however, refrain from exploiting electronic libraries, preferring software attacks whenever possible. Fortunately, although it is possible to hit distributed/centralized OCSP, software attacks cannot mount on the distributed implementation of the present invention.

In OCSP, in fact, the CA is required to receive external challenges from untrusted parties and answer them with digital signatures and thus by means of its valuable keys. Therefore, there is a possibility that the "window to the outside world" required by OCSP could be used hostilely to expose the secret signing key.

For comparison, in a distributed implementation of the invention, there is no such "window": the CA is in the electronic vault and never receives or answers any queries from the outside world; it only outputs non-secret data at regular intervals . In fact, every day (or hour) its output includes a file F of public information. (CAs may receive revocation requests from their RAs, but these requests are from a few trusted entities over authenticated channels—for example, using secure smart cards.) Untrusted responders receive challenges from untrusted parties, but they rely on Their files F and thus answer those queries through the published data. Thus, common responders only "expose" public information when software attacks the preferred embodiment of the present invention.

Simplified PKI Management

PKI management is not trivial. (See, e.g., Internet Public Key Infrastructure, Part III: Certificate Management Protocols; by S. Farrell, A. Adams, and W. Ford; Internet Draft, 1996; Privacy Enhancement for Internet Electronic Mail-PART II: Certificate-Based Key Management ; by S. Kent and J. Linn; 1989). Preferred embodiments of the present invention improve PKI management in many applications by: (1) reducing the number of certificates issued; (2) enabling privilege management of certificates; and (3) sharing certificates with multiple independent CAs. Register function.

Let us illustrate informally the improvements in PKI management with a series of concrete examples. (Note that features and techniques used in one example could easily be embedded in another. We do not do this explicitly to avoid an infinite number of possible variations.)

Turn certificates on/off (and disable it)

Example 7: Music download

Assume that an Internet music vendor wishes to let users download any song they want for $1/day from any of 1000 servers. This can be efficiently achieved with digital certificates. However, in this example, U may be very sure that he will download music on certain days of the year, but he cannot predict which or how many of these days will be. Thus the music center needs to issue a different 1-day certificate for U no matter when U requests that: U requests such a certificate, and after paying or agreeing to pay, it receives the certificate and then communicates with any of the 1000 music servers that day use together. However, issuing 1-day certificates has unusual administrative costs, both for the vendor and for the user. And these costs must be replicated each time the user wishes to enjoy another "music day".

In a preferred embodiment, the present invention mitigates these costs as follows. The first time U contacts the vendor, it may be issued a certificate C with Issue Date D ₁ =0, Expiration Date D ₂ =365, and Validity field X ₃₆₅ , Revocation Target Y ₁ , and Suspension field Z ₃₆₅ . (Vendor's CA creates the same abort field as the validity field: by starting with a random 20 byte value Z ₀ , and then hashing it 365 times, with 1-day intervals. It then saves the entire hash chain , or just Z ₀ , or use an appropriate time/storage method that yields any desired Zi.) On days i=1,...,365, if U requests a "music day" for that day, the vendor simply A 20-byte value Z _365-i is released to indicate that the certificate is valid. Otherwise it is released to indicate that the certificate is "suspended". Otherwise, it releases Y ₀ to indicate that the certificate has been revoked. Alternatively, if U and the music vendor agree - assuming - that "music week begins on day i", then either the 20-byte value for those 7 days is released at the appropriate time, or a single 20-byte value X _{365- i-7} was released on day i.

That is, rather than giving U a new one-day certificate whenever U wishes to download music, the vendor might give U a 1-year certificate. At any time, this single certificate can be opened some day, just by releasing the appropriate 20-byte value. Thus, for example, the preferred embodiment of the invention replaces issuing (and embedding in the user's browser) 10 single-day certificates by issuing yearly certificates, as they happen to be opened on 10 of the 365 days of the year. Vendors can also issue certificates that specify a priori the number of days that can be opened (eg, certificates for 10 out of 365 days) using the methods described above. Because of its predictable cost, such a certificate is more suitable as a gift.

Turn on/off many certificates for the same user

Example 8: Security Verification Management

Digital certificates work really well in ensuring that only the proper users can access certain resources. In principle, privileges could be indicated on the certificate itself. For example, the State Department may have 10 different security verification levels, L1...L10, indicating that it has authorized security level 5 by issuing a certificate C like the following:

C=SIG _SD (SN, PK, U, L5, D ₁ , D ₂ ,...)

Among them, D ₁ and D ₂ indicate the date of issue and the date of expiration.

However, specifying privileges on the certificate itself can lead to a certificate management nightmare: whenever its privileges change, the certificate needs to be revoked. In fact, an employee's security level can vary with his assignment, which often changes during the same year. For example, if U's security verification level is temporarily upgraded to 3, the State Department should revoke the original C and issue a new certificate C. This task can be simplified by having U and C' keep the same public key (and expiration date) as before; for example, by having:

C'=SIG _SD (SN', PK, U, L3, D ₁ ', D ₂ ,...)

However, U is also faced with the task of "plugging" the new C' into its browsers in various places: its desktop PC, its laptop, its mobile phone, its PDA, etc. Now, it's one thing to make the CA take action to reissue the certificate in a slightly different form, but it's quite another thing to rely on the user to take action.

This management problem is only exacerbated if short-lived certificates are used (eg expire 1 day after issue). In the context of this example, a single-day certificate may enable a State Department employee or User U to attend meetings that require a higher level of security. (If U has such a credential in an appropriate mobile device, smart card, or even a magnetic stripe card, it could, for example, use the credential to open the door to that day's meeting.) The use of short-term credentialing is widespread and has been advocated, Because it largely eliminates the difficulty of revocation (there is no need to revoke a certificate that will expire within 24 hours, at least in most applications). However, there is still an administrative cost to issuing short-lived certificates such that they reside in all relevant users' browsers.

These administrative costs can be mitigated by using the preferred embodiments of the present invention as follows. Assuming that the time accuracy of 1 day is enough, the State Council issues a certificate to user U, which contains 10 validity fields and 1 revocation field: if

C=SIG _SD (SN, PK, U, D ₁ , D ₂ , A ₃₆₅ , B ₃₆₅ , C ₃₆₅ , D ₃₆₅ , E _{365 , F 365 ,} G ₃₆₅ , H ₃₆₅ , I ₃₆₅ , J ₃₆₅ , Y ₁ , )

Wherein the first validity field A ₃₆₅ corresponds to security verification level _{1 .} Certificate C is used as follows. On day n, if U is still in place (that is, certificate C is still valid), and U’s security verification level is 5, the State Council discloses (for example, sends to all its responders in the distributed NOVOMODO implementation) the 20-byte Evidence of Effectiveness E _365-n . If on day m, the security verification level of U becomes 2, the State Council discloses B _365-m . and so on. Once C becomes invalid (e.g. because U is terminated as an employee or because U's keys are compromised), the State Department _publishes (and erases from its memory) the "future" A, B, C, D, E , F, G, H, I and J values.

This way, despite specifying its own privileges internally, certificates C do not need to be revoked and users do not have to load new certificates in their browsers when their privileges change in the normal way. In essence, the preferred embodiment of the invention has such a minimal footprint that the CA (rather than issuing, revoking, reissuing many related certificates) can very simply issue a certificate with a very high probability of not being revoked (because A change in security verification level does not translate into a repeal). Consequently, fewer certificates will cease to be issued or revoked in the application, resulting in simpler PKI management.

In summary, the preferred embodiment of the present invention replaces complex credential management for a dynamically changing set of properties or attributes with a single credential (with minimal extra length) and a single 20-byte value for the attribute implementation.

A telecommunications company can use a method similar to Example 2 to switch a wireless device from one tariff to another, such as for roaming purposes.

Landlord CA and Tenant CA

The main PKI cost is related to RA functionality. In fact, identifying user U may require an expensive personal interview and verify that U does know the correct key (corresponding to the public key PK to be proven). It would be nice if this RA function could be shared among many CAs, while keeping them completely independent control over their own certificates.

Example 9: Organization certificate

Government and large institutions include parallel and hierarchical branches: departments, business units, etc. An employee may have affiliations with two or more branches. For example, in the US government, it may work for NIST and the Department of Commerce. Issuing a digital certificate for each such affiliation would result in a high total number of certificates and complicate PKI management: each time an employee stops/adds one of his affiliations, it is better to revoke the corresponding certificate/issue a new one. Ideally, the two opposites should be reconciled: (1) the agency issues only one certificate per employee, and (2) each branch issues and controls a separate certificate for each of its affiliations.

These two opposites can be reconciled by the preferred embodiment of the invention as follows. At the outset, it should be noted that the preferred embodiment of the present invention is consistent with separating the certification process from the validation process, the first process being controlled by the CA and the second process being controlled by the Validation Authority (VA). For example, assuming a time accuracy of 1 day, once the CA is ready to issue a certificate C with a serial number SN, it sends the SN to the VA, which chooses Y ₀ and X ₀ , keeping the triplet (SN,Y ₀ ,X ₀ ), calculate Y ₁ and X ₃₆₅ as usual, and then return Y ₁ and X ₃₆₅ to CA, which includes them in C. This way, the CA doesn't have to bother validating the C: the CA is solely responsible for identifying the user and issuing the C appropriately, while the VA is the only one who can prove that the C is valid or revoked. This separation can be used in a variety of ways to allow the organization certificate to flexibly reflect internal branch dynamics. What follows is just one of these approaches, and uses governments and ministries as operational examples. The government as a whole will have its own CA, as will each department.

Assuming that k different departments have corresponding CAs, CA ¹ ... CA ^k , and a time accuracy of 1 day, the government certificate C has the following form:

C=SIG _GOV (SN, PK, U, D ₁ , D ₂ , X ₃₆₅ , Y ₁ , [X ₃₆₅ ¹ , Z ₃₆₅ ¹ ], ..., [X ₃₆₅ ^k , Z ₃₆₅ ^k ])

Where, as usual, SN is the serial number of the certificate, PK is the user's public key, U is the user's identity, D ₁ is the issue date, D ₂ is the expiration date, X ₃₆₅ is the validity field, Y ₁ is the revocation field, And wherein X365 ^j is the confirmation field of CA ^j , and Z ₃₆₅ ^j is the stop field of CA ^j .

Such certificates are generated by government CAs with input from departmental CAs. After identifying the user U and selecting a unique serial number SN, issue date _D1 , and expiration date _D2 , the government CA sends the SN, PK, U, _D1 , _D2 (preferably in authenticated form) to each A department CA. The jth such CA then: select two secret 20-byte values X ₀ ^j and Z ₀ ^j ; save (SN, PK, U, D ₁ , D ₂ , X ₀ ^j , Z ₀ ^j ), or more Simply, (SN, X ₀ ^j , Z ₀ ^j ); and return for combining it in a government certificate at position j (or use "tag" j).

This certificate C is managed with the distributed implementation of the invention as follows, so that works as 1 certificate, 2 certificates, ..., k certificates; ie as k independent certificates, one for each department. On day n, imagine 100 responders: the government CA sends the 20-byte value X _365-n to all 100 responders if C is still valid, and Y ₀ otherwise. Next, the jth department CA sends the 20-byte value X _365-n ^j to all 100 responders to indicate that C can be relied upon as certificate j, otherwise sends Z _365-n ^j .

Thus, the government CA is solely responsible for identifying users and issuing certificates, but each departmental CA can independently manage what is effectively its own certificate. (This is absolutely critical. If CA ¹ is the Judiciary and CA ² is the DOD, it is best to each act individually, although there are some overlapping interests). The resulting certificate system is very economical to run. Firstly, the number of certificates is greatly reduced (in principle, there is only one certificate for an employee). Second, a particular employee can leave and join a different department without the need to revoke the old certificate or issue a new certificate. Third, different departmental CAs may share the same responder. (Actually, whenever the minimal fact that a particular user belongs to a particular department is not a secret—something will be true for most departments—the server essentially only contains "discloseable information.") Thus, about A query for the C status of a certificate is answered with two 20-byte values: one for the government certificate and one for the j certificate. This enables one or more to nimbly revoke C at the "centralized level" (eg, if U loses the key corresponding to PK).

Example 10:

In the example above, certificate C could only be revoked in a centralized manner, but it can easily be arranged that the responsibility for revocation is pushed to individual departments. For example, in order for the jth department CA to fully autonomously revoke and suspend C as a j certificate, C can take the following form:

C=SIG _GOV (SN, PK, U, D ₁ , D ₂ , [X _N1 ¹ , Y ₁ ¹ Z _N1 ¹ ],..., [X _Nk ^k , Y ₁ ¹ , Z _Nk ^k ]).

Also, different departments may have different time precisions for their own certificates. This is easily accomplished by having C have the following format,

C=SIG _GOV (SN, PK, U, D ₁ , D ₂ , [TA ¹ , X _N1 ¹ , Y ₁ ¹ , Z _N1 ¹ ], . . . , [TA ^k , X _Nk ^k , Y ₁ ¹ , Z _Nk ^k )

where TA ^j is the time accuracy of the jth CA and Nj is the number of time units between _D1 and _D2 . (eg, if TA ^j is 1 day and D ₁ -D ₂ = 1 year, then X _Nj ^j = X ₃₆₅ ^j .)

Within an organization, a major advantage of issuing certificates structured and managed as described above includes enabling the certificate to remain valid despite the user moving from one branch to another. However, it should be appreciated that the techniques described above can also be used outside the confines of a single institution. In fact, the government CA can be viewed as a landlord CA, the k departmental CAs as tenant CAs serving unrelated organizations (rather than branch offices), and the certificates can be viewed as leased certificates. The term is borrowed from more common examples where the advantages of "joint structure and independent control" are applied. The rented certificate is in fact modeled on a specimen building with traces of the same floor.

Instead of building just his own room, a wealthy builder builds a 20-story building, placing himself in a shed room while renting out or selling the nicer rooms on the other floors. Each of the 20 tenants then acts as a single owner. It decides completely autonomously and independently of the builder who will be allowed into its apartment and who will be given the keys. Of course, a 20-story building is 20 times cheaper than a single story: it might cost exactly 10 times. This economic saving is even more significant in leased certificates. In fact, the cost of issuing a normal certificate is exactly the same as the cost of issuing a leased certificate. Thus, it would be highly beneficial for the landlord CA to issue leased certificates, or at least fully reimburse the costs incurred for its own certificates. On the other hand, tenant CAs also have their own advantages, in fact: they save issuance costs: they share the cost of issuing certificate k, and they save infrastructure costs: they share the same responder (since they only contain public data ).

Natural candidates for a landlord CA to serve as an external tenant CA are: credit card companies, large financial institutions, and the government (eg via USPS or IRS). In fact, in many cases, they have long-standing and intimate relationships with millions of "users" and may more easily issue them a digital certificate (such as , credit card companies have sent annual statements to their customers and can add to support that knowledge). A credit card company might like the idea of issuing certificates as a landlord CA to more efficiently run its own similar programs (with hotel chains, airlines, etc. as their tenants). The IRS may have decided to use digital certificates, and leased certificates may then provide them with a revenue stream that will reimburse the costs of building faster and better services.

Example 11:

The way we have described Landlord and Tenant CAs thus far requires that the Landlord CA cooperates with its own Tenant CAs during the issuance process, and thus it already pre-identifies its Tenant CAs. However, for a Landlord CA, issuing certificates for lease assumes that - assuming - 20 tenant CAs are actually possible, not all or any of these tenants have been identified. More suitably, future tenant CAs will be able to lease space in already issued certificates. This capability is ideal for new certificate enabled applications. Rather than suffer the expense necessary to issue certificates to millions of customers, a company offering a new certificate-enabled product could start with a landlord CA that has millions of certificates issued, lease out space in them after the facility, and then Subscribing clients as most landlord CA users, they open all their corresponding certificates overnight (without any client identification and other issuance fees) and then start managing them according to their own rules. We describe various techniques to enable this functionality below.

another system

Equipment Confirmation System

Now let's see how we can adapt the technique of the present invention to devices such as mobile phones, PDAs, radio frequency identification tokens, PCs, laptops, VCRs, network equipment, routers, firewalls, set-top boxes, CD players consoles, game consoles, DVD devices, etc.).

For example, there is ample ability to turn on these devices, or keep them running. If a device is stolen, for example, it is hoped that it will no longer function. On the other hand, if it has not been stolen, it will continue to function normally. Similarly, if the user "rents" the device, or pays a subscription fee, or uses the device on behalf of the company (for example, if the device is a company laptop), if the user no longer pays the rental or subscription fee, or ceases to work for the company , the device needs to be switched off/disabled. Otherwise, the device should function normally. Also, these devices can be turned on, off, and back on in a dynamic fashion.

Of course, these functions can be realized by means of the system according to the preferred embodiment of the present invention. In essence, assume again that, for a specific but without any limiting purpose, at daily intervals, a device may carry a digital certificate C specifying a validity field X, and that the device only has evidence of its validity for X each day Only available to work on certain days. Devices can have trusted/protected clocks to avoid spoofing. Devices (especially mobile devices) can be "pushed" with their own everyday evidence of effectiveness. Alternatively, the device may request proof of its validity for that day from the second entity. For example, a device may provide its serial number and receive proof of validity for that day in response.

This works because the integrity of the validity field is guaranteed by the certificate, and thus by the CA's digital signature of X (along with other information such as date information). However, we can protect the integrity of X in another way: namely, by "burning into" the device in an unalterable way: for example, by writing it into read-only memory, i.e. a chip (smart card/PDA/phone/ chipsets such as laptops). In this way, the user of the device cannot change X in any way. Evidence verification algorithms can also be burned in. Thus, once a so-called proof of validity P for a particular day appears, P is hashed an appropriate number of times and then compared with the burnt-in X. More generally, a one-way function F may be used here instead of a one-way hash function. Thus, the whole process including fabrication looks like this:

The first entity generates an initial value IV, and iterates the one-way function F for a given number of times based on V, so as to obtain a final value FV. A second entity (possibly equal to the first) burns X into device D. The device D has means for iterating the function F. The device D then receives a so-called nth proof value PV, where n is a positive integer, and verifies the PV by iterating the function F n times based on the PV and checks whether the resulting value is equal to the burned-in value X.

Device D may interrogate its own clock to ensure that the nth evidence value corresponds to the current date. The current date can actually be the nth date in a sequence of dates starting from a fixed date. Fixed dates can also be burned into the device to preserve its integrity.

At each iteration, the function F may receive additional inputs as inputs (not just previously calculated values, but also). For example, an identifier for D may be an input at each iteration. This additional input can also be different at each different iteration. For example, an integer k may be an input at iteration k.

Likewise, it is impossible to have only one one-way function F. In fact, there is a chain of one-way functions, and Fk can be the function applied at iteration k.

The validity field X (essentially unique to D) can also be used as an identifier for D (or a part thereof) to save processing of D's serial number and validity fields, respectively.

The systems described so far can be used to switch specific devices D on or off. But it can also be used to switch on or off a specific only one function or one of several possible functions. For example, X may be the validity field for function FX, Z is the validity field for function FZ, and so on. In this case, receiving validity evidence for X(Z) means that function FX(FZ) was opened on device D on that day. Such an additional validity field Z... can also be burned into device D. Likewise, a description/identifier whose function is associated with X/Z/... can also be burned in.

If the number of possible functions (and the number of validity fields) is large, the validity field can be Merkle hashed and then the root value of the Merkle tree can be burned in. In this case, to turn on function FX (on a particular day), the device may be provided with appropriate proof of validity for X (for that day), along with an authenticated path from X to the root in the Merkle tree. The Merkle authentication path algorithm can also be baked in.

No clock device acknowledgment

As we have seen, the technology of the preferred embodiment can be used to identify devices and turn them on or off to prevent their misuse. Typically, the security of this application lies in the fact that the device has a clock that is not controllable by the adversary, only the true owner of the device may control it (e.g., a fired employee wishes to use his company laptop that is still at home after he is fired) computer access to company data). In fact, even if the company no longer sends out proof of validity for day j, and even without such proof of validity, the device would not work on day j, an adversary could rewind the clock of the device to cause the device to believe that the current day j For d<j, then send back the valid proof of day d that was sent correctly to the device, thereby deceiving the device to operate on day j.

The preferred embodiment provides techniques that can perform device validation even if the device is clockless, ie, does not have a clock or does not have a secure clock.

The technology contemplates a validator, an entity that decides whether a particular device should be validated—that is, turned on or off—on a particular date in a sequence of dates. Specifically, but not limitatively, we assume that a specific date is a specific day in a chain of days. The device finally has secure memory components and a clock. Although not secure, at least when turned on the device can tell if a particular clock has been reset. For example, a device may tell that 24 hours have passed as long as it remains running. Verify that the software is preferably protected within the device (eg, running in a protected memory component, or burned into, or located within a firewall) to avoid being altered in any way. Note that some smart cards work in a similar manner. For example, they have protected memory components, they can have minimal power to hold certain values in (eg secure) memory, and have clocks, but not batteries to keep them running for any significant length of time. Thus, once inserted in the reader, the smart card's clock becomes active, and the card can accurately monitor the elapse of time (e.g. because the clock is also in secure memory), but once the card is taken out of the reader, the clock No longer works, although smaller values may be retained in secure memory.

Example 12:

In this method, the validator and the device share a key K. The key K is preferably located in a secure memory part of the device. From this key K, both the device and the validator are able to transmit a sequence of unpredictable (to a third party other than the party owning K) value corresponding to a sequence of dates. For example, for each day 1, 2... a series of values including V1 = H (K, 1), V2 = H (K, 2) ... where H is a one-way hash function, or encrypted with key K each time 1 , 2... the encryption function. On day j, if the Validator wants the device to be active for one more day, it publishes (eg sends to the Responder) the value Vj=H(K,j). Now assume that the device is turned on on day j after having been active on day d, and then turned off by day j. The device then has kept in memory the value Vd=H(K,d) or an indicator of the last day (eg d). The device will not be operated again until it has evidence of effectiveness after days d. Alternatively, the device itself keeps track of—as in a variable—the amount of time it has worked during the day d. Thus, when the device is turned off, it can remember not only d, but also say 6 hours and 10 minutes. Thus, when it is turned on again, it will continue to work for 17 hours and 50 minutes. Thereafter, it will require evidence of validity for the day after d. Now assume that the device is indeed turned on again on day j>d. The device then obtains a (so-called) proof of validity Vj for day j (eg, upon request from the responder, it was pushed with such a proof or received such a proof). Next, the device tries to see if Vj is a validity proof after the proof Vd currently in memory (or about days after day d in memory). For example, the device continues to generate Vd+1, Vd+2... using its key K until the value Vj is generated (or until a given number of days is exceeded - assuming we don't care at all how the device works after 10000 days). If that is the case, it will turn itself on for another 24 hours (i.e. keep the new Vj or j in memory, and run and monitor the clock appropriately so that after 24 hours of continuous on, a new value of Vj+1 or Vk, k>j).

The device can be turned off by not publishing or feeding back evidence of future validity, or by publishing or making it receive a special value like H(K, NO MORE) or a special value Vnomore kept in memory. A device can be suspended by posting or having it receive a special value such as H(K, suspend, j). The keys used for validity, revocation and suspension proofs may be the same or different.

This already provides a great deal of protection. Assume that the device was in normal use on day j-1, but was then stolen, and no evidence of validity for day j was ever published or made available for the device. Then, regardless of whether the device was turned off before being stolen, it will stop working at the beginning of day j. In fact, if it had been turned off, when restoring it would require proof of validity of the day j-1 days later to turn itself on normally, no such evidence appears. If it was open at the time of the theft, it will stop working after up to 24 hours.

In the worst case, the device is switched on (for example on day j-3), and thus credits possession of the validity evidence Vj-3, and is then switched off. Suppose the device is stolen at this time and its loss is not notified until day j-1, or the device is stolen on day j-1 and the enemy records the values Vj-2 and Vj-1 that the device may have seen. Then such an enemy can at most feed back these two values to the device and make it work for at most another two days.

Example 13:

This method works essentially as the method disclosed in Example 11, using a sequence of unpredictable values, published or made available to the device at each date (eg, non-limiting, day) in the sequence, the clock is not secure etc, but no keys are used in the device. For example, the device saves Xk and the result of iterating one (or more) one-way functions F k times based on the initial value X0 using the same variables as described above. Xk is then written to the firewall (eg in an immutable manner) or stored in a protected part of memory. The validity proof for day j is simply Xk-j, as in the underlying scheme of the present invention. Again, suspension and repeal can occur in a similar fashion.

RTC physical access structure

Multi-Privilege Management in Hybrid Environments

An enhanced access control system must answer two questions for each user. The first question is authentication or identification: "Are you who you say you are?" This question is usually asked directly or indirectly through an identification badge, key biometric or password. These provide reasonable answers to long-term user identification, but do not ask the more urgent confirmation question: "Are you currently allowed to do what you want?"

For example, an identification badge may tell you that Alice has been employed as an employee for the last 10 years, but cannot alone determine that she is still an employee with access to a computer server room.

For physical access control, a secure lock must authenticate to determine identity and then perform validation to determine if the user's current privileges allow entry. Some locks perform this validation through a wired network connection to a centrally hosted licensing authority. The whole physical access solution based on network wired locks has two big limitations. The cost of each wired lock includes the cost of security wiring, field control panels, and labor, totaling several thousand dollars per door. Areas of wired structures are limited to locks that are easily accessible through a permanent network. This prevents enhanced access control for locks on mobile or hard to reach ones such as cars, storage containers, utility cabinets and the like.

The real-time credential technology according to the preferred embodiment of the present invention provides a secure way to perform effective physical access confirmation to both wired and detached locks. This allows smart door locks to confirm the current user's privileges and permissions without requiring an expensive network connection to each lock.

This disclosure describes several structures that can be used to provide separate validation based on a number of independent user privileges. Each architecture provides interoperability with existing access control hardware and software for use in different kinds of installations. For each architecture, this article describes how real-time credentials provide additional flexibility while dramatically reducing the overall cost of high security.

In the following, all four structures described are characterized by the same RTC confirmation procedure. The main difference between these solutions is the process of authenticating users, which affects price and compatibility with existing access solutions.

Contactless ID/Memory

The first RTC confirmation structure is an access control environment based on a contactless ID card with read/write memory access. This is described using a common MIFARE ^™ standard contactless card as an example, but the validation solution can equally be used for any memory ID card.

When MIFARE ID cards are used in today's networked physical access environment, the lock reads the ID from the card and transmits it to a nearby panel or server, which checks for privileges and performs validation. The authentication process is the determination of the card ID, based on which the validation process is processed remotely.

The physical access solution of the present invention maintains compatibility with such wired doors and adds support for separate doors by using the card's read/write memory to hold a digitally signed "proof of confirmation" for the card . This evidence is periodically written to the card at any networked card reader, which can then be read at any separate lock to establish the user's current validity and permissions.

The following table shows the logical content of an RTC confirmation proof stored on the card, along with the storage requirements for each component:

Card ID: #123456 4 bytes

Status: card valid 1 byte

Start time: 8/4/03 09:00 4 bytes

End time: 8/5/04 08:59 4 bytes

Authorization: ACME Inc. 20 bytes

Privilege: R&D Laboratory 1 digit to 10 bytes

Parking 1 digit to 10 bytes

Cabinet 53 1 bit to 10 bytes

Terminal B 1 bit to 10 bytes

Digital signature 42 bytes

Total size: ~100 bytes

When a user enters a facility through a wired door, the door retrieves the user's entire proof of identification in the format described above and places it in a memory area on the card. Once evidence is loaded on the card, the detached lock can confirm the user's permission through the following steps:

(1) Perform standard authentication by retrieving the user's card ID;

(2) Retrieve RTC confirmation evidence from memory;

(3) verify that the digital signature matches the existing public key of the trusted institution;

(4) verify that the evidence is up to date (use start and end time);

(5) Verify that the card is valid;

(6) Evidence-based privilege checks for random access control requirements.

Separate locks are configured with a set of access control rules based on privileges rather than individual user IDs. For example, the lock can be configured to only allow the user to have "parking" privileges, and only during business hours. Since the privileges of individual users can be changed via RTC confirmation evidence, the lock itself does not need to be altered or erased to change access permissions when new users are added. Furthermore, the lock does not need to hold any keys or data, which means that individual locks can be disassembled without reducing the security of the overall system.

RTC validation evidences according to preferred embodiments of the present invention have certain characteristics that make them very effective for physical access control environments. Since certificates are digitally signed, they are proofs that cannot be forged and altered. Since proofs do not contain any keys, they can be public and transmitted without security risk. Certificates are small enough to be stored on low-end memory cards.

These features allow RTC confirmation evidence to be used in cards such as the MIFARE standard, while still providing high security cryptographic confirmation of thousands of unique user privileges per card.

cost. MIFARE 1k standard cards are available between $1 and $5 depending on the manufacturer and capacity. Separate locks based on MIFARE cards and RTC validation technology can be manufactured for under $500 per door. With this unit, individual doors or containers can be secured for under $1000.

safety. Simple ID authentication provides weaker protection against copying and forgery. Second and third factor authentication combined with PKI protection can be used to increase authentication security. Credential validation is protected by strong PKI encryption, preventing license forgery and modification.

Contactless shared secrets

RTC credential validation can also be used with ID cards such as HID's iClass, which performs validation using cryptographic information shared directly or indirectly with all readers. The lock will authenticate the card using a random challenge/response protocol that proves that the card knows the secret communication of its ID.

The RTC validation for a shared secret card is the same as for a simple ID card. When the user enters the wired door, the lock writes the current RTC confirmation evidence to the user's card. This evidence is then retrieved by a separate reader for offline validation.

cost. Contactless shared secret cards with memory are available for between $5 and $10, depending on manufacturer and capacity. Separate locks based on shared secret cards and RTC validation technology can be manufactured for under $500 per door. With this unit, individual doors or containers can be secured for under $1000.

safety. Shared secret authentication reduces the chance of duplication of a single card, but a single off-line card reader can allow the duplication of many cards. Credential validation is protected by strong PKI encryption, preventing license forgery and modification.

Contactless PKI

Cards capable of performing public key digital signatures provide the highest level of authentication security. This includes cards based on MIFARE PRO X chips as well as many high-end JavaCards. The lock can authenticate cards based on a challenge/response protocol without requiring any sensitive information in the lock. This greatly reduces the risk of key duplication.

The RTC confirmation for a public key card is the same as for a simple ID card. When the user enters the wired door, the lock writes the current RTC confirmation evidence to the user's card. This evidence is then retrieved by a separate reader for offline validation.

The card's public key will usually be represented by a digital certificate, which can be used for additional applications such as computer access and email security. High-end public key cards can support additional applications such as information security or stored value, which helps to reduce the overall cost per application.

cost. Contactless PKI cards are available for between $10 and $20, depending on the manufacturer and capacity. Separate locks based on MIFARE cards and RTC validation technology can be manufactured for under $500 per door. With this unit, individual doors or containers can be secured for under $1000.

safety. PKI cards can provide strong cryptographic authentication of locks with low risk of key compromise or card duplication. Credential validation is protected by strong PKI encryption, preventing license forgery and modification.

Techniques for Traversing a Sequence of Hash

H is a one-way hash function. A hash chain of length n is a collection of values x ₀ , x ₁ , . . . , x _n such that H( _xi )= _xi-1 . While xi _-1 is easily computed from _xi , computation in the opposite direction is infeasible due to the unidirectionality of H.

Here is a representation of a hash chain:

X ₀ (H)x ₁ (H)...(H)x _n-1 (H)x _n

In many applications (e.g., document validation and privilege management services), it is necessary to be able to traverse the hash chain, that is, to generate the values x ₀ , x ₁ in sequence during a certain period of time (such as outputting a value for a day of the year). , ... x _n (in the above chain, from left to right). Note that the left-to-right order makes this problem hard because of the unidirectionality of H. While it is easy to generate and output in the order x ₀ , x ₁ , . . . x _n by simply repeatedly applying H, the reverse order requires more time and/or memory.

Two obvious avenues are:

save only one value x _n , and, to output x _i , compute H ^n-1 (x _n );

All values x ₀ , x ₁ , ... x _n are saved and erased when they are output.

The first pass requires the storage of two hash values (one for x _n and the other for computing _xi ) and a total of n(n+1)/2 evaluations of H, or, on average, each output n/2 evaluations. The second pass requires the storage of n+1 hash values and a total of n evaluations of H, or on average, 1 evaluation per value output.

We are interested in solutions in the middle: providing a balance of other memory (number of hash values saved) versus time (number of evaluations of H required).

散列值，且至多每散列值输出

次H的计算。(见Don Coppersmithand Maruks Jakobsson，Almost Optimal Hash Sequence Traversal，in Matt Blaze，editor，Financial Cryptography：SixthInternational Conference(FC’02)，Southhampton，Bermuda，11-14，March 2002)。An algorithm has been proposed in the prior art, which leads to the following balance: Preserving

hash value, and output at most every hash value

The calculation of times H. (See Don Coppersmith and Maruks Jakobsson, Almost Optimal Hash Sequence Traversal, in Matt Blaze, editor, Financial Cryptography: Sixth International Conference (FC'02), Southhampton, Bermuda, 11-14, March 2002).

New algorithm with constant memory

Jakobsson's method requires storage on log ₂ n hash values and cannot be used when only a small amount of storage is available. Note that for a hash chain of length 365, this means 9 values need to be saved, and for a hash chain of length 1000000, this means 20 values need to be saved. We prefer to use algorithms that require less storage. Additionally, we want to be able to specify storage requirements independent of hash chain length. This way, the same amount of memory will be required to manage both short and long chains; thus, no new memory needs to be acquired if the hash chain changes.

In order to demonstrate the convenience of the algorithm. We call the value x _j the algorithm saves a pebble at position j. The pebble is then "allowed" to: (i) move to where another pebble was (this corresponds to the copy value), or, (ii) move one step to the left from its current position (this corresponds to evaluating H). Initially, the pebble may start at a random position on the hash chain.

Note that the number of pebbles corresponds to the number of saved hashes, and the amount of time it takes a pebble to move left corresponds to the number of H evaluations. Next, our goal is to come up with an algorithm that reduces the number of pebble steps (which we will call "cost") given a certain amount of pebbles.

Two Pebbles

Clearly, if x _n is not saved, a pebble is always needed at n, and when it is needed at the end of the traversal, there is no way to retrieve it and thus no way to output it. It is also clear that a pebble is always required at the current position i in order to be able to output x _i . Thus, at least two pebbles are required.

If only two pebbles are used, one of them must always stay at x _n , and the other has no choice but to start at x _n and move to x _i each time. Thus, the best algorithm for two pebbles takes n(n+1)/2 steps, or n/2 steps per output on average. For example, for a hash chain of length 1000000, the average number of steps per value output is 500000.

three pebbles

If we add a pebble to the absolutely necessary 2 pebbles, the result is a dramatic improvement in the number of steps we can take.

(注意，将有n/s sqrt{n}个间隔)。将卵石数3放在x_n，卵石数2在x_s。接着，使用上述的两卵石算法，使用卵石数1遍历点x₀...x_s(每次在x_s开始)。接着将卵石数2放在x_2s(通过在x_n开始并向左移动)，并再次使用两卵石的算法遍历x_s+1，...x_2s。继续以这种方式，对于长度s的间隔，每次均使用两卵石的算法。We will proceed as follows: Divide the hash chain into intervals of length s, where

(Note that there will be n/s sqrt{n} intervals). Put pebble number 3 at x _n and pebble number 2 at x _s . Next, use the above-mentioned two-pebble algorithm, using the pebble number 1 to traverse the points x ₀ ... x _s (starting at x _s each time). Next place the pebble number 2 at x _2s (by starting at x _n and moving to the left), and use the two-pebble algorithm again to traverse x _s+1 , ... x _2s . Continuing in this manner, for intervals of length s, the algorithm of two pebbles is used each time.

则没输出值的平均步骤数为

The total number of steps of the algorithm can be calculated as follows: using two pebbles to traverse each interval, we need s(s+1)/2 steps. Also, to move the pebble number 2 to the beginning of each interval before traversing, we need (ns)+(n-2s)+...+s+0(n/s)(n/2) steps. transfer

Then the average number of steps with no output value is

Thus, increasing to three pebbles compared to a minimum of two allows us to reduce the time per value output from n/2 to sqrt{n}. The reduction is actually dramatic: for example, for a hash chain of length 1000000, the average number of steps per value output is 1000 (whereas for two pebbles it takes 500000).

four pebbles

If we have other pebbles available, we can divide the hash chain into intervals again. This time, we will set s = |sqrt{n ^(2/3) }| and divide the whole chain into n/sn ^(1/3) intervals of length s.

Next we place pebble number 4 at n and use it as the starting point for pebble number 3, which will move to the starting point of each interval of size s, in order from left to right. At each interval, we will use the three-pebble traversal algorithm described above. That is, we also subdivide each interval into subintervals, and place pebble number 2 at the start of each subinterval, in order from left to right (pebble number 2 will start each time, and pebble number 3). Then pebble number 1 will traverse the subintervals, starting at pebble number 2 each time.

Thus, the cost of traversing each interval will be sqrt{s}, or |n ^(1/3) | per value output. Thus, we have to increase the cost of moving the pebble number 3 to the beginning of each interval. The pebble number 3 will be moved n/s times: first n steps, then n-2s steps, and so on, giving an average cost per value output of (n/s)/2n ^(1/3) /2.

Thus, the average number of steps output per value is |1.5n ^(1/3) |. Again, using a chain of length 1000000, the average number of steps per value output is 150.

roll out to more pebbles

A more general technique derived from the above example is as follows: given c pebbles, divide the hash chain into n ( ^1/ (c-1) each of length n ^{((c-2)/(c-1)) ))} intervals. A technique of c-1 pebbles is used on each of these intervals. The average cost per value output will be ((c-1)/2)n ^(1/(c-1)) }.

This generalization is believed to be valid not only for constant pebbles, but also, for example, for c=1+log ₂ n. In this case, using the equation n ^{1 /log2n} = 2, using our algorithm we calculate that the average cost per value output will be log ₂ n.

Worst-case cost of improvement

Even though the above technique achieves a good general case cost per output value, some output values will take longer to compute than others.

For example, take the example of 3 pebbles. Every time we traverse s pebbles, we have to reposition the pebble number 2. Thus, output values at the far left of the interval will take longer to compute; eg, to compute x _s+1 , we will need to take n-(s+1) steps. On the other hand, all other pebbles within the interval will be at most s steps.

Of course, in some applications this can present serious problems: the computing means involved have to be fast enough to handle these "bad" cases. But if it's already that fast, it doesn't seem to have a better "normal" situation: we'd rather need a powerful computing device that simply sits idle under normal conditions.

To prevent this problem, we need to make the worst-case output value cost close to the general-case output value cost. In the case of three pebbles, this can be achieved by adding only one extra pebble. Called Pebble "2a". Its job is to move ahead to where Pebble 2 will move next. For example, when pebble 2 is at point s, pebble 2a will start moving towards point 2s at point n. It will reach point 2s exactly when pebble 2 needs to be at point 2s - before value s is output.

步的最坏情况的成本。然而，注意，可做得更好：因为卵石1对于间隔左端的值较间隔右端的值将花更多的步骤，为减少最坏情况的成本，卵石2a应“慢慢地”起程并接着“加速”。这种方式，卵石1和2a所用的步骤总数将为常数。具体地，卵石2a首先花(n/s)/2步，接着花(n/s)/2+1步，以此类推，直到间隔的最后值被输出时的3(n/s)/2步。这将最坏情况的成本进一步减小到

Thus, when any given interval of size s is being traversed, pebble 2a will start at position n and move left to the beginning of the next interval. Note that pebble 2a requires n fewer steps to reach its destination. For Pebble 2a, the obvious approach is to take at most n/s steps for each output value in the interval. This results in output values per

The worst-case cost of the step. Note, however, that it can be done better: since Pebble 1 will take more steps for values at the left end of the interval than for values at the right end of the interval, to reduce worst-case cost, Pebble 2a should start "slowly" and then "accelerate". This way, the total number of steps taken by pebbles 1 and 2a will be constant. Specifically, Pebble 2a first takes (n/s)/2 steps, then (n/s)/2+1 steps, and so on, until 3(n/s)/2 when the last value of the interval is output step. This further reduces the worst-case cost to

It should be noted that the total number of steps and thus the average cost per output value does not increase with the addition of this extra pebble. This is because, the extra pebbles will not do any extra work, just slightly ahead of time. Thus, for a hash chain of length 1000000, the worst case cost would be 1500, while the general case cost per output value would be 1000.

This method can be extended to more pebbles. If we take the solution with 4 pebbles, and add pebbles 2a and 3a, which are moved ahead of time in place of pebbles 2 and 3, respectively, we reduce the worst-case cost to |2n ^1/3 |. Again using the example of a chain of length 1000000, the worst case cost would be 200, while the average case cost per output value would be 150.

Thus, in general, using 2c-2 pebbles, we can traverse the hash chain at an average cost per output value ((c-1)/2)n ^{1/(c-1)} , and for any given The output value of , the worst-case cost is (c/2)n ^{1/(c-1)} .

Again, this generalization is considered not only for constant pebbles, but also, for example, for c=1+log ₂ n. In this case, using _2log2n pebbles, our algorithm will traverse the hash chain at an average cost of _log2n per output value, with a worst-case cost of 1+ _log2n .

best solution

Below we describe, given any number c of pebbles, an algorithm for obtaining a provably optimal total (and thus average per output value) computational cost. Note, however, that for small values of c, the provably optimal solution will only have slightly fewer steps than the solution above.

Suppose we have c pebbles. We must save x _n , which occupies 1 pebble. Next, another pebble will be moved to x _k (some k will be determined below), which applies Hn-k times to x _n . Then, recursively, use the best solution on the c pebbles to output the values x _k+1 , . . . , x _n in order. This again amounts to traversing a shorter chain—of length nk, since the first k values have already been traversed.

Now, define F(c,n) to be the number of steps necessary to traverse a hash chain of length n while holding no more than c pebbles at any given time. Clearly, F(c,0)=0 for any c≧1, and F(0,n)=0 for any n. Next, in our above method, F(k,n)=min _k F(c-1,k)+F(c,nk-1)+nk, and k should be chosen such that F(c,n ) minimum.

For a particular c and n, finding the optimal point k is a simple matter of memoization (a.k.a. dynamic programming) recursion. We propose to implement this task in C language. Such sweet spots can be easily found in advance and then integrated in the hash traversal coding.

Implementation of our optimal solution for any amount of memory

           
    #include "stdio.h"

    int **table;

    int **ktable;

    int f(int r, int n)

    {

    int k, t_min=-2, t, k_min=-2, t1, t2; //-2 Stands for
infinity;

    //-1 stands for uninitialized

    if(table[r][n]!=-1)

    return table[r][n];

    if(n==0 && r>0){

    table[r][n] = 0;

    ktable[r][n] = 0;

    return 0;

    }

    if(r==0){

    table[r][N]=-2;

    ktable[r][n]=-2;

    return-2;
        <!-- SIPO <DP n="65"> -->
        <dp n="d65"/>
    }

    for(k=0; k<n; k++){

    t1=f(r-1,k);

    if(t1==-2)

    continue;

    t2=f(r,n-k-1);

    if(t2==-2)

    continue;

    t=t1+t2+n-k;

    if(t<t_min||t_min=-2){

    t_min = t;

    k_min=k;

    }

    }
    table[r][n]=t_min;

    ktable[r][n]=k_min;

    return table[r][n];

    }

    void main()

    {

    int max_r, max_n, i, j;

    printf("max balls:");
        <!-- SIPO <DP n="66"> -->
        <dp n="d66"/>
    scanf("%d", &max_r);

    printf("chain length:");

    scanf("%d", &max_n);table=(int**)malloc((max_r+1)*sizeof(int));ktable=(int**)malloc((max_r+1)*sizeof(int));

    if(table==NULL||ktable=NULL){

    printf("Out of memory!\n");

    retUrn;

    }

    for(i=0; i<=max_r; i++){

    table[i]=(int*)malloc((max_n+1)*sizeof(int));

    ktable[i]=(int*)malloc((max_n+1)*sizeof(int));

    if(table[i]==NULL||ktable[i]=NULL){

    printf("Out of memory!\n");

    return;

    }

    for(j=0; j<=max_n; j++)

    ktable[i][j]=table[i][j]=-1;

    }

    for(i=0; i<=max_r; i++)
        <!-- SIPO <DP n="67"> -->
        <dp n="d67"/>
    for(j=0; j<=max_n; j++)

    f(i,j);

    printf(″\nTable for F(r, n)--the number of steps needed:
\nn\\r″);

    for(i=0; i<=max_r; i++)

    printf("%6d", i);

    printf("\n");

    for(j=0; j<=max_n; j++){

    printf("%6d:", j);

    for(i=0; i<=max_r; i++)

    printf("%6d", table[i][j]);

    printf("\n");

    }

    printf(″\nTable for k--the optimal position to put the
first pebble:\n n\\r″);

    for(i=0; i<=max_r; i++)

    printf("%6d", i);

    printf("\n");

    for(j=0; j<=max_n; j++){

    printf("%6d:", j);

    for(i=0; i<=max_r; i++)

    printf("%6d", ktable[i][j]);
        <!-- SIPO <DP n="68"> -->
        <dp n="d68"/>
    printf("\n");

    }

    }

    \end{verbatim}

        

Secure physical access to private keys (live credentials in a KERBEROS-like setup)

In general, a scenario may include multiple doors and multiple users. In addition, access may be controlled by multiple agencies (each agency controls access through certain doors, sets of doors for different agencies may overlap). In most general cases, access is controlled by having the user present credentials to the door (verification of such credentials may require interaction between the user and the door, such as PIN entry, and message exchange between the door and the user's card). In the case of doors, it is especially important to support access security with minimal cost, without even connecting the door to the network or any particular server.

An important finding is that our RTC technique yields significant security, infrastructure, and cost benefits regardless of the credentials we use. RTC can be used in conjunction with public key cryptographic methods (certificates, public key signatures, PKI) and private key cryptographic tools (symmetric or private key signing and encryption, Kerberos-like systems, etc.).

Access control to separate gates using public key techniques has been proposed. Here, we describe how to apply these ideas to private key technology.

basic primitive

Encryption, signature, pseudorandom functions

In particular, private key encryption, private key signature (aka MAC), private key random function are typical private key primitives that we will use. For many of our purposes, these primitives can be used interchangeably. For example, a deterministic private key signature scheme (between two entities sharing the secret signing key SK) and a random function Fs (whose seed is shared between the two entities) can actually be considered equivalent. Both produce outputs that are unpredictable to third parties, who may know the corresponding inputs, but not SK or s. For example, the function FSK(x) that returns the digital signature of x with the key SK can be considered in practice to be a good enough pseudorandom function with the seed SK. On the other hand, the function Fs(x), which returns the value of x in a pseudorandom function F with seed s on the basis of input x, can be considered as a private key signature algorithm with key s.

One-way and one-way hash functions

We will also use additional basic primitives: the one-way function F and the one-way hash function H. In essence, a function F is one-way, if (1) given an input X, F(X) can be efficiently computed, and (2) given an F(X), where X has preferably been chosen sufficiently randomly With sufficiently unpredictable computation of X is practically impossible (eg, in principle, because too many values of X have to be tried, and there is no efficient way to narrow down the number of possible candidate values). A function H is a one-way hash function if it is one-way and (although it is better to make longer inputs match shorter inputs or arbitrarily long inputs, say 160 bits long) it is difficult to find two distinct inputs X and Y such that H(X)=H(Y).

In practice, we can construct other primitives using the one-way hash function H. For example, private key signatures can be constructed in the following simple way. To sign a message M with key SK, compute H(SK,M). That is, combine SK and M appropriately - eg, concatenate them - and then hash the result. Of course, to sign M and date M, the date d can be added to the combination, thus computing H(SK,M,d) instead. Similarly, a pseudorandom function can be constructed as follows. To generate the output of a pseudorandom function with seed s, based on input x, H(s,x) can be computed; ie, s and x can be suitably combined, and then a one-way hash function applied to the result.

Secure Physical Access

We only focus on new aspects arising from private key settings, and skip those ordinary aspects (eg, daily/normal computing aspects, etc.) that can be naturally adapted to new scenarios. We start with a simple scenario.

single agency

Let D be the door (with the mechanism described), A be the institution wishing to control D's access, and U be the user (possibly working for A), again, with a card CU, with the appropriate identifier, etc. Next, A can control D's access by sharing the key SK with D. If A wishes to authorize U to visit D on days d (time interval d), it computes a proof PUDd, hard for anyone other than A (and possibly D), but easy to verify for D. Let's see how this is done, both using private key encryption and private key signing.

Private key encryption solution (with possible proof of identity)

For example, PUDd may be an encrypted EUDd of a message specifying U and possibly D and d with a private encryption key SK according to some established private key encryption algorithm such as DES. On receipt of EUDd from U's card, D decrypts it with the key SK and if the result indicates U and the current day (time interval) d, the door is opened. The door can determine with its own lock whether its own time falls within the time interval d.

Here, as elsewhere, U is used to indicate a user and an appropriate identifier for U. If user U has a card associated with it (preferably securely), then U can be that card or its appropriate identifier. In the latter case, for example, the door's reader can get U from the card, and also EUDd, it decrypts EUDd with the key SK, and compares the decrypted U with what the card provided to make sure they are equal.

Note that EUDd proves to door D that user U is authorized to enter through it at time interval d, but this does not prove to D that it is indeed dealing with user U. Thus, we can add the basic scheme for U to provide its own identity to the gate. This can be accomplished in several ways. In particular, Agency A may only provide EUDd to U's card, and U's card is provided with a keypad, and transmit the EUDd to the door only if the correct PIN is entered on its keypad (and if the wrong PIN is entered more than a given number of times, the card may self-destruct or erase the associated non-permanent memory contents). This way, whenever the door receives EUDd, it knows it is receiving from U's card (since A only transmits EUDd to U's card) and it knows that the "user behind the card" must be U (unlike a stolen Malicious user of U's card vs.) because U's card will not work or transmit EUDd to D unless U's PIN has been entered on its keypad. A second way for U to prove his identity to D involves having U provide D directly with his own PIN. For example, door D may have its own keypad, and U uses it to enter his own PIN, PINu. A gate may have an internal way (like a table) to pin Nu to U, and thus may recognize that it is indeed dealing with U. However, if there are many doors in the system, it may not be practical to provide and update (eg, as new users join the system) tables for each door. Therefore, it is preferable to make the identifier of U directly be PINu. For example, EUDd may be EPINuDd. When user U approaches door D, he enters PINu to D's keypad and his card transmits EPINuDd to the door. The gate next checks that the entered PIN is equal to that specified in EPINuDd, in which case it is dealing with the correct user and that same user is authorized by A through gate D, without using any PIN user table: in fact , the keypad tells D that the user who knows PINu is in front of it, and EPINuDd tells D that the user who knows PINu is currently authorized by D. In a third way, instead of appearing directly in the EUDd, the user PIN can be securely integrated with the EUDd. For example, A might give EUDd to U's card encrypted with key PINu or a key K reconstructable from PINu (e.g., k=H(PINu) or K=H(PINu,d) or K=H(D , PINu, d) etc.). In this case, gate D will check that at time interval d, the PIN is securely bound to the user's authorization. For example, it decrypts EUDd using PINu and checks EUDd as properly authorized using the key SK it shares with Institution A.

use answerer

But: How can A easily and securely transfer EUDd to U's card? We propose to use responder. These are devices (such as servers or computer terminals/card readers capable of connecting to servers). Preferably, these Responders do not have to be vaulted or secured. Such protection can add substantial cost and inconvenience to the system, and it is critical to make the system work safely without protecting the responder. Ideally, institution A performs the update on day d of a series of dates. Each date preferably specifies a time interval (eg, one day). For example, d can be day d or the beginning of day d. During the update of d, A decides which user U should be authorized to access/pass D, and computes a proof verifiable by D. For example, in an encrypted shared key based system, this evidence could be the above-mentioned string EUDd, and can be verified because A and D share the secret key SK, with which A computes EUDd. All these proofs are then sent to the responder. These responders are preferably located in a convenient location. For example, in an airport system, responders may be located at the main entrance of the airport. User U then (eg, when arriving at work) obtains his own authorization through gate D from the responder. Preferably, U's card can authenticate itself to the responder to receive the EUDd. This is very convenient, because without wireless and other expensive systems, the user can obtain his daily authorization for all the doors he is authorized to pass through the main entrance (through which the user has to pass) on a particular day, and use the traditional Mechanisms such as inserting his own card into a card reader (eg, to prove that he is present to work). Thereafter, he is free to move around the airport and can easily pass through all the protected gates D for which he is authorized using the authorization EUDd he has obtained. But because of this convenience and the fact that the responder is preferably insecure, it is also possible for a malicious user to gain authorization from an honest user. It is therefore necessary to (1) prevent this from happening without protecting the responder, and/or (2) ensure that authorizations to honest users cannot be used by anyone else. The latter case can be sufficiently enforced by having the user enter a PIN at the door, preferably securely combined with the authorization released by the card, as already discussed. Thus, a malicious user V who obtains U's authorization EUDd from a responder cannot impersonate U at the door because it does not know U's PIN. The protection of the former can be strengthened by having the authority A send the authorization EUDd to the responder after encrypting it with a key SKCU in U's card CU and known to A. In this way, A essentially gives the responder an encrypted authorization EUDd' that can only be converted to an authorization EUDd by U's card, making it useless for a malicious V who downloads someone else's authorization for that day. Even if V makes its own cards any way it wants, V still doesn't know about SKCU.

Further, it is possible for A to share the key SKD with gate D and the key SKU with user U. Then PUDd may be the value EUDdk, including indications of user U, door D and day d, and some random secret k, all encrypted (by A) with key SKD. (Note that U cannot decrypt EUDdk in this case). In addition, U can receive Ek, k encrypted with SKU. (D and d may be known to U, or may be communicated to U—eg, by the same responder at the main gate.) This way, since U knows the SKU, U also obtains the secret k. To enter door D, card U may send EUDdk to D. D may respond with a random value q, and the card U then sends Eq, q encrypted with the secret k. Gate D can decrypt Eq, verify that the same q is used, and U is the same as specified in EUDdk, and the date d is the current date. If all checks are confirmed, U will pass. This mechanism can also be combined with the above-mentioned PIN mechanism to make it more secure. Additional challenge-response methods based on k are also possible. (In particular, D can compute and send Eq and ask U to send back the correct decrypted q.) Such a mechanism can provide security even if an attacker monitors the communication between the card and the door.

However, an enemy who sees the PIN entered by the user at the door can impersonate U after stealing U's card, at least during the time interval d, if U's card has EUDd in it. Thereafter, if U reports that his card has been stolen, A will no longer make EUDd available for U's card.

Private key signature solution

For example, PUDd could be a private key digital signature of a message specifying U and d (and possibly D) with a private key SK known to both A and D according to some established private key signature algorithm. In particular, H is a one-way hash function, then UDd=H(SK, U, d). On receipt of U from the card, the door's reader can sign U and d with its own private key SK and compare whether the result of this calculation matches the string PUDd available from the slave. Note that a door card reader carrying a lock may know the current date and thus not have to retrieve it from the card. This works as long as A grants access for all days at a time. Otherwise, the card also sends d (or the selected time interval) to the reader, then the reader signs the obtained U and d with SK, checks that the result is indeed equal to PUDd, and then detects that the current time (according to the clock of the door) is at d In the range. If yes, it is turned on.

Again, U may be required to enter a PIN as part of the transaction. In this case, the PIN can also be used as part of the U. For example, U may include u and PIN, where u is a character string identifying the user, and PIN is a password known to the user. In this case, the card transmits u and PUDd (possibly D or d and another number) to the door reader, the user enters the PIN to the door control integrated with the card reader or the card reader itself, and the card is read Machine reconstructs U=(u PIN), then signs Ud with SK to check whether PUDd is obtained. Again, it also checks that the current time is within the range of d if d is provided by the card. This method brings the user and their card together in a tighter way, making it difficult for an adversary who steals the card to use it without the proper PIN.

Of course, the same SK can be used for a group of doors, in which case, by authorizing U to scope one of them, A automatically grants him access to all doors. To allow maximum access intervals, each door D may have a key SKD.

Combining two methods

As an example of combining the two methods, U may receive from A (eg, using the mechanisms described above, in particular, using encryption) the key SKUd for day d. He then "proves" his identity and/or authorization to door D using the private key signature. That is, door D can send a random message m to card U; in response, card U can send m's signature: H(m, SKUd). Note that the computation of this signature may require PINu. Gate D then verifies the signature. This may require gate D to know SKUd (e.g., has received it directly from A, or computed from other information such as H(SKD,d,U), etc.) Alternatively, A may encrypt SKUd using a key shared with D, thus obtaining ESKUd. ESKUd can then be given to U (eg, as described above), and U can then send it to D along with the signature.

multiple institutions

As we have seen, for an organization/institution A, there is the ability to share a key SKD with a gate D to control which user U can access D at a given time interval d. This process can be extended so that multiple organizations A, B, C ... individually control access through gate D or a set of gates D1, D2, D3 ..., each organization X shares the secret key SKXD with gate D, then Use the solution above. For example, each organization X can select a SKXD and insert it into D's card reader. Each organization X may have to send a set of one or more to employees/hired workers/contractors/sub-contractors from door to door. In a facility with many doors, it may not be practical or wasteful to do this, as other organizations may have done so. Also, if there are or will be many institutions, the card reader will have difficulty keeping all these keys. In addition, appropriate precautions should be taken. Otherwise, there is nothing to prevent an enemy from inserting his own key into the door's card reader, and then, identifying it, he can use any of the methods described above to authorize himself or his accomplices access to the door. For these reasons, we propose the following solution. Note that the same approach can be applied to individual solutions.

first solution

As we have seen, a user can pass through a secure door if he or his card shares a key for a certain time interval. Therefore, in this case, the user and the gate share a session key. The Kerberos and Needham-Schroeder protocols provide mechanisms for ensuring that pairs of entities share secret session keys, and can be applied throughout the system here. However, these protocols are all based on a key distribution center, which is online and must be contacted whenever a shared session key is needed. Therefore, we wish to propose another, more convenient method. In the beginning, even for implementing a Kerberos/Needham-Schroeder based system, we need a way for a central authority to distribute keys to gates (which may be more difficult than distributing keys to other authorities).

We envisage that a special agency SA (eg, at an airport, the airport agency) can securely distribute keys to door readers. Preferably, the SA may be the only entity that can do that. For example, door card readers are delivered and manufactured without keys in them, so that once the first set of keys (possibly a single set of keys) is inserted, the card reader stores them for a long time and does not Other keys are accepted for future storage. In this way, by first inserting any key in the door reader (before, during, or shortly after installation), the SA ensures that no one else can install a key inside the door. Alternatively, a control PIN or key is required for storing other keys in the door reader. The door reader is delivered and manufactured without any control PIN or key, so that once the first control PIN or key (or possibly a set of keys) is inserted, the reader keeps them for a long time , and no other control PINs or keys will be accepted in the future. However, assuming the correct control PIN/key is entered, any new key can be inserted and stored in the reader. In this way, by first inserting any control PIN/key in the door reader (before, during, or shortly after installation), the SA ensures that no one else can insert and store the key in the door reader.

At this point, SA knows all the keys of the card reader of door D, eg, SKAD, SKBD, SKCD, etc. Instead of implementing Kerberos, it's simpler that SA now gives SKAD to Institution A, SKBD to Institution B, etc. Here, organization A/B/... can control user U's access to D, which is realized by private key encryption method or private key signature method. Note that these mechanisms can individually operate different sets of doors. For example, suppose

1. Door D1 has key SKXD1 in its card reader, and SA gives SKXD1 to institution X;

2. Door D2 has key SKXD2 in its card reader, and SA gives SKXD2 to institution Y; at the same time

3. SA does not give Y the key of door D1, and does not give X the key of door D2.

Institution X can then control access to door D1 and institution Y can control door D2 in a completely independent manner.

One turn solution

But even with the features available above, we can improve a system such as the one described above in some important ways. Right now:

key - memory size. While the door reader preferably holds a different key for each different organization that controls it, this drives up the number of keys that the reader should securely hold.

Add new controls. New control issues may occur when new mechanisms or new doors are introduced into the system. If door D does not hold a key for organization X, and subsequently wants X to gain control of D, the SA must insert the key for X in D's card reader. For example, if a new organization appears, SA must send a team of workers to insert SKXD in each door D that should be controlled by the new organization. However, such physical "travel" can be inconvenient. To avoid them, the SA could pre-install additional keys in the card reader of door D, and then combine them with new organizations that arise, or that must then control access through D. However, this strategy only exacerbates the situation described in the first bullet point. Furthermore, if a new door is introduced which will be controlled by some already existing authority, the SA will have to insert the new key in the door reader and then deliver the appropriate key to the already existing authority which must control the new door. mechanism. While doable, delivering keys is always problematic.

Take back control. Once the key SKXD is held in gate D and known to organization X, X will continue to control access through D, even if at some point control of D should be given exclusively to a different organization. To avoid this, SA should again engage in physical travel and remove SKXD from door D (eg by means of a control PIN/key mechanism).

Let us now describe how these additional improvements were brought about.

Basic System Profile

In the beginning, we can make the system work with a single key per door. For example, SA holds a single key SKD in gate D (tracking this information of course). This key can potentially be computed by the SA from an identifier of D uniquely known by the SA and a secret seed s: eg, SKD = H(s, D). SA then gives authority X control over D by giving X a key SKXD selected from SKD and X. For example, as a pseudorandom function with seed SKD evaluated at X (for simplicity we assume entities coincide with their appropriate identifiers). In particular, we can let SKXD=H(SKD,X). Institution A then authorizes user U to access D for time interval (eg days) d using SKXD, as before. In particular, by using SKXD as the signing key for the private key signature scheme: eg by computing SKXDUd = H(SKXD, U, d) and then having SKXDUd be saved in U's card. When U's card communicates with D's card reader, then the card provides (a) X and (b) SKXDUd and possibly other information such as d (and information about user U) to the card reader. On the basis of receiving this information, the reader calculates H(SKD, X) and then uses this result (equal to SKXD as stated) as the signing key of the same private key signature scheme and signs (U, d)-in In the above example, by hashing (U,d) after combining it with SKXD. If the result matches the value guarded by the card (SKXDUd according to it), if the time interval is correct with respect to the reader's clock (and if U enters the correct PIN, if the PIN is properly used in the above system) , the door opens.

Key storage. Increased control

Note that this single-key-per-door system not only minimizes key memory requirements, but also greatly simplifies the problem of adding control. Any time agency X needs to gain control of door D for the first time, SA need not physically go to D and insert (or facilitate X's insertion) a new D-X key in D's card reader. Instead, if D has a key SKD known to SA, SA simply computes a D-X key from SKD (e.g., SKXD=H(SKD,X)), and delivers (e.g., electronically) the D-X key to X.

take back control

For each door D and organization X authorized to control D for a time interval (eg, day) d, the SA is computed and its signature is made available. For example, the signature may be a private key signature on the key SKD shared by SA and gate D. In particular, the signature may be the value H(SKD, valid, X, d'). Note that even though signed as a private key, the signature itself can be published without any concern. In fact, using the above H-based private key signature implementation, if H is a secure one-way hash function, it is difficult to calculate SKD from H(SKD, valid, X, d'). Thus, when user U has the correct door permission for that day in his card, he can get SKXDUd and H(SKD, valid, X, d') for door D. The card reader at door D can then verify SKXDUd as before, and additionally determine that X has indeed controlled D at interval d' by hashing SKD, valid, X, and d', and check that the same value guarded by the card is in within d'. In fact, only SA (and D) knows the secret signing key SKD: Agency X only knows H(SKD,X) and computing SKD from H(SKD,X) and H(SKD,valid,X,d') is very difficult. Note that the time interval d and d' cannot be the same. For example, SA may be satisfied with granting X control over D on a weekly basis, while X may grant user access through D on a daily basis. Alternatively, the system may replace the use of SKXD described above with a time-dependent version of the key: eg, SKXDd = H(SKD, X, d). The SA will then have to deliver SDXDd to each institution X by time interval d. To regain control, the SA simply stops sending SKXDd for period d because its SA has decided to sever X's control over D.

It should also be noted that the system currently allows for some privacy, as SA does not have to know which user U was given access to D by X, nor their numbers. Of course, schemes can remove this privacy protection (eg, reporting or by using the Kerberos system).

Example 14:

Let us now outline our preferred implementation for enabling secure physical access in a system with a super-agency SA, multiple (preferably separate) doors D, multiple organizations X, multiple users U. The preferred embodiment minimizes key storage and makes it very easy to add and revoke organization X's control of door D.

In a preferred embodiment, SA authorizes organization X to control gate D at given time intervals. During this time interval, X itself may authorize user U to access D.

We envisage (and possibly other participants) taking an action on each date of a sequence of dates d corresponding to a sequence of time intervals. For example, d may be the start of a particular day and the corresponding time interval of a particular day. For simplicity, we can use d to represent dates and corresponding time intervals. (However, it should be understood that this is not limiting: for example, the date may be a specific day, and the time interval corresponds to a date after that day.) Specifically, but not limitatively, we may assume that each date /time interval is one day.

We describe the preferred embodiment using private key digital signatures. This has no limiting purpose. Our preferred embodiment should be considered to be implementable with any of the other private key systems described above. More specifically, we assume that private key signing is implemented using a one-way hash function H. This has no limiting purpose: H(SK, DATA) should always be considered as the digital signature of key SK with data.

We assume that SA shares key SKD with gate D. SA may also share key SKX with organization X. (SKD can be generated by A via the master key SK. It is similar for SKX. For example, SKD can be equal to H(SK, D), and SKX can be equal to H(SK, X). SA can then be secretly—or encrypted— Provide SKD for D. Similar for X.)

On each day d, if SA wishes to authorize organization X to access door D, it computes and causes X to receive the key SKXDd, which is securely bound to X, D, and verifiable by D (e.g., based on inputs X and d) for days d key.

For example, SKXDd=H(SKD, X, d), ie SA signs X, d with key SKD. SA then makes X receive SKXDd. The SA can cause X to receive SKXDd by sending SKXDd to X, preferably after encrypting it using a key SKX shared with X. Also preferably, SA sends the encrypted SKXDd to X by having it stored in the responder, from which X then downloads.

If X wishes to authorize user U to access D at time interval t within days d, X computes and causes U to receive the key SKXDdUt, which is a key securely bound to X, D, U, and t verifiable by D.

For example, SKXDdUt=H(SKXDd, U, t), ie X signs U, t with key SKXDd. X then causes U to receive SKXDdUt. X can cause U to receive SKXDdUt by sending SKXDdUt to U, preferably after encrypting it using the key SKU shared with U. Also preferably, X sends that encrypted SKXDdUt to U by having it stored in the responder, from which U then downloads.

If U wishes to access D at time interval t, U causes D to receive X, U, t (eg, U's card is transferred to D's card reader).

If D receives X, U, t on day d, it computes SKXDd from its key SKD and then computes SKXDdUt from SKXDd. D then verifies that the time interval t is indeed within the range of day d, and uses its own clock to verify that the current time is indeed within the range of time interval t. Furthermore, D verifies that it is dealing with U/U's card by means of a challenge-response mechanism using key SKXDdUt. If these verifications pass, D opens.

For example, D may compute SKXDd from its key SKD by computing H(SKD, X, d), and then compute SKXDdUt from SKXDd by computing H(SKXDd, U, t). For example, a challenge-response mechanism using key SKXDdUt may involve having D send a random string q and receive back an encryption of q with key SKXDdUt, or a digital signature of q with key SKXDdUt. Alternatively, D may send Eq, an encryption of q with key SKXDdUt, and must receive q back.

Note that the preferred approach should be understood to include the use of a PIN in cooperation with the above described approach. In particular, any of the PIN applications described in the previous sections may be used within the preferred solution. Note that the preferred scheme provides a great deal of flexibility, since d and t can be different. For example, SA can provide X to control D on week d, and X can authorize user U to access D on day t in week d. However, we can let d = t, in which case t need not be specified or used alone in the preferred system.

Kerberos method

In our secure access application, using the Kerberos method directly will not work well. It is most natural to implement all gates and SAs as the same area (for which SA acts as Ticket Granting Service (TGS)). Each organization and its employees will be in separate areas. The agency for each organization in the area may then serve as the Authentication Service AS (and possibly its own TGS). According to the Kerberos protocol, each user can be authenticated for the respective institution/AS by obtaining a ticket-granting ticket TGT for admission authorization. This ticket TGT is then sent by the user to the SA/TGS, together with a service authorization ticket for each door for which the requesting user is authorized. The SA/TGS then has to verify the user's eligibility and, if the user - if all is correct - provide a ticket for these service authorizations. Obviously, this protocol is very laborious and imposes a large burden on the SA. In particular, it is the SA's responsibility to verify to which door a particular user is authorized and to issue the respective tickets. Furthermore, it requires the SA to be online and work on the protocol in real time. Having a user have access to the SA also introduces additional security threats.

Kerberos ticket without protocol

In principle, we could "forgo" the Kerberos protocol and just use tickets. That is, all tickets can be pre-booked or pre-computed in advance, and users can obtain them at the time of main gate entry, without the need to participate in the appropriate Kerberos protocol.

However, many of the above-mentioned problems will remain - in particular, it should be natural for SA to delegate control of certain doors to specific agencies (but in this case, this control can be easily taken back, possibly in Subsequent points are restored).

Using RTC within Kerberos

One way to help with this is to use a real-time credential RTC. For example, we can use tickets in the above method. However, in this method we don't generate tickets on a daily basis. Instead, we can use a long-lived ticket to manage short-lived access control via the RTC passed in the ticket's authorization data field.

In this example, the RTC works correctly as in the example of the public key certificate. However, some optimizations are possible here.

Using the RTC described above brings a number of possible benefits. These include (but are not limited to):

1. Easy to manage

a. Now, SA is definitely rarely involved

b. Instead of a relatively large entry ticket, the user will need to acquire a very small RTC

c. The generation of RTC can be entrusted to the corresponding institution

d. Taking back control is easy: This can be accomplished in at least two ways. First, simpler and natural - no renewal by the SA when the ticket expires. A more precise mechanism would use two types of RTCs: RTCs issued by SA and RTCs issued by other agencies. Then, each day the SA needs to issue a single RTC for each establishment it keeps (or, it has to issue an RTC for each establishment-door pair where the establishment is authorized to open the door). Each establishment will also issue an RTC for each user (or, for each user-door pair where the user is authorized to open the door). NOTE: More traditional Kerberos methods require more tickets to be generated and passed over the wire protocol.

e.RTC allows for a clear separation of roles that facilitates many aspects of management and infrastructure.

2. Efficiency

a. Space: The RTC is substantially smaller than the corresponding ticket.

b. Time: Since they are very short (and they are few and only a small number of communication rounds), the communication will be very fast, enabling the user to move through the gate at a reasonable speed while getting the RTC.

c. Load distribution: RTCs can be distributed by non-secure responders. Replication of RTC is neither expensive nor dangerous.

3. Security

a. RTCs are not security sensitive, once they are generated they can be more easily managed (eg by insecure responders) and do not pose any threat to security.

b. Separation of tickets and authorization (via RTC) has more security in key management (when keys/tickets are actually generated and communicated).

c. SA Isolation: An SA never really needs to have a direct line of communication with any user.

Except Kerberos

It can be found that the above mechanisms benefit little from the core Kerberos features (this is mainly due to the fact that Kerberos is designed for different applications). Thus, here we explore how we can use RTC-based mechanisms, which are not directly about Kerberos. These mechanisms may be similar to private key encryption and private key signing above.

In these mechanisms, the special agency SA will share secrets with each organization A (B, C, . . . ) and each door D. For example, this can be achieved by using the method described above such that the SA needs to keep only a single secret s. The secret shared between SA and A may then be SKA = Hash(s, A). Similarly, the secret shared between SA and D is SKD = Hash(s, D). Note that A and D also need to store only one key SKA or SKD respectively. Furthermore, an additional key SKAD=Hash(SKD, A) corresponds to each organization-gate pair (A, D). This key can be easily calculated from SK and D. Giving SKAD to A is necessary but probably not sufficient for A to control access to the door. Furthermore, A may need to receive an RTC from SA (or from another party) for the current time period d. This RTC, called RTCAD, need not be secret and can prove that A is also on good terms with SA.

Each user U hired by A and authorized to enter door D may then receive from A the key SKAUD=Hash(SKAD, U). Note that SKAUD can be easily computed by A and D without any additional keys. Giving SKAUD to U is necessary but probably not sufficient for U to be able to open door D. Furthermore, U may need a separate RTC for the current time period d: RTCAUDd.

Note that this approach already dramatically simplifies the information flow: at the start of each time period d, the SA issues a single RTCAD for each organization A. Each organization A then sends a single TCAUDd for each user-gate pair. All of these RTCs are available to employees upon entering the main gate. Assuming that a user U is authorized to access 100 doors in the facility, the RTCAUDd requirement for all doors is less than 2KB - a manageable amount even on slow connections (typically, it only takes less than 1 second).

To open door D, user U needs to present RTCAd and RTCAUDd and perform authentication based on key SKAUD (the authentication can be of challenge-response type to protect the key). NOTE: Due to the relatively small number of RTCAd credentials that may be present in the system, validation of these credentials may not need to be done on a per-user basis. Instead, each gate may validate each RTCAd it receives and cache the results for validation by other users.

A special agency SA may wish to have better control over organizational access doors. To achieve this, instead of a per-organization credential RTCAd, the SA can issue an RTC for each organization door pair (A, D): RTCADd. Then, for SA, it is possible to delegate and reclaim control of each gate to each organization on a daily basis. Note that this at most doubles the amount of RTC data each user needs to receive (still keeping the required transition time under 1 second for the above example).

aggregate RTC

It can be seen that access control rights do not change dramatically from day to day. As such, many of the capabilities of the mechanisms described above are unused. We propose an RTC aggregation mechanism that can be used in relatively stable environments to improve even additional efficiency.

Example 15:

As an example, there are 100 organizations and each organization has access to 1000 doors. Thus, there are 100,000 organization-gate pairs, and thus RTCADd credentials will be issued and distributed by the SA on a daily basis. Furthermore, if each organization employs approximately 1000 people, this would result in 100 million RTCAUDd credentials to be issued and distributed by all organizations.

Let's group the AUD of all org-user-gate triplets into hierarchically arranged groups. These can be easily imagined, for example, as follows. Let all AUDs correspond to the leaves (ordered in a preferred way) of the symmetric binary tree network. Then, each node n of the tree corresponds to a set of AUDs where all AUDs correspond to leaves in the subtree of n. For each such node and time period d, let it have a corresponding credential RTCnd. Then for any AUD ancestor n, the validity of AUD in cycle d can be proved by any credential RTCnd. Thus, if all AUD groups remain valid on day d, a single credential RTCr is sufficient for the entire system, where r is the root of the tree.

In conclusion, if 100 AUD groups become invalid, at most 1500 credentials are enough to justify the whole system (which replaces 100000000). More generally, if there are k groups invalid, at most k(26-lg k) credentials are required for the proof of the whole system.

This approach results in a dramatic improvement, even though aggregated RTC requires more values to be kept in gates and/or users: in the above example, such overhead can result in at most a factor of 26 overhead in memory, saving communication Huge order in (4 or 5 in the example above). More generally, if a set of entities to be authorized (in our case, these are the AUD groups) protects N members, of which k are to be excluded, then at most k(1g N-lg k) are required Credentials are used to attest to the entire system, while the overhead for aggregation is at most lgN. Even more efficient group representations may exist (eg, while the above has been recognized as a subset covering method, we can also use subset distinguishing covering and state-of-the-art results based on it).

In this way, validation of the aggregated credentials can be optimized, such as by caching the results at least for larger groups.

RTC implementation and optimization

Many different implementations of real-time credentials are possible. The implementation of these RTCs also allows for many different optimizations. For example, real-time credentials can be implemented as follows: x ₀ is a random value, such as 20 bytes long. x _i is defined as x _i =Hash( _xi ). _xn is a public value fixed in some way (eg securely communicated from SA to door D by SA). Next, X _nd is the real-time credential RTCd of time period d. It can be verified by applying Hash() to x _nd d times and verifying that the result is equal to x _n . This is essentially how RTC is implemented in the case of public key certificates—for example, x _n may be included as part of the certificate.

It is also possible to use essentially the same implementation here. Instead of including x _n in the certificate, here we can include it as part of the Kerberos ticket. Alternatively, we can communicate it through some other secure means, such as encrypting with the key SKD of door D, etc.

Another possible implementation of RTCd is to simply set it equal to Hash(SKD, RTC, d), where RTC refers to the credential ID. For example, to enable organization A to have control over D on day d, a credential RTCADd should be used, where RTCADd may be set to RTCADd=Hash(SKAD,d). The credential for user U to access door D on day d, if issued by organization A, may be RTCAUDd=Hash(SKAD, U, d). This method allows credentials to be pre-issued just a specific date in advance, and does not grant access for any days outside the desired time period (even if these are non-contiguous).

Confirmation of the above credentials is straightforward. Note that the above credentials are essentially symmetric signatures with appropriate keys. In all of the above credentials, encryption can be used instead of Hash.

Note that we have made the system more efficient at every step. Suppose the airport has 1000 gates, 100 establishments, and 10000 possible workers, for simplicity, and assumes that controls are given on a daily basis. Then a Kerberos/Needham-Schroeder system where the central authority is involved in computing each gate-user key must involve 100 million keys per day. The system as outlined above only requires the SA to generate and deliver less than 100000 keys per day to all institutions.

Live Credentials in OCSP

We now describe the use of the real-time credential validation technique of the preferred embodiment of the present invention in an environment using the Open Certificate Status Protocol (OCSP) for digital certificate validation. This demonstrates how the inventive technique maintains compatibility with OCSP, while providing qualitatively higher security and scalability than traditional OCSP implementations.

Traditional OCSP implementation

CRLs can become very large because they collectively provide proof of revocation (and thus, indirectly, proof of validity) on many certificates. In contrast, OCSP provides proof of validity for individual certificates. OCSP services are typically implemented by OCSP responders. Such a responder is a server that, upon receiving a question from a client (aka certificate relying party) about the validity of a particular certificate issued by a particular CA, provides a digitally signed answer indicating the status of the certificate and the time of the answer. To achieve this, it is necessary for the OCSP responder to know the status of all CA's certificates, since only a CA can revoke its own certificates. Such knowledge is obtained very generally if the OCSP responder is the CA itself. Otherwise, some other form must be employed to keep the OCSP responder updated on the status of the CA's certificate. For example (cfr, U.S. Patent No. 5,717,758, Certificate-Based Certificate Revocation System), the CA can send its most recent CRL to the responder, and the responder can consult the signed document to deduce whether the certificate of interest is currently valid or has been revoked , and in its signed response, also specify the time and the time of the next update. (Here, it is natural for this update time to coincide with the date of the CA's next CRL, since CRLs can trigger different responses.)

Of course, a malicious responder could provide a fake signed answer about a particular CA's certificate, with or without consulting the latter's CRL. For certificate relying parties, to safely rely on the OCSP responder's digitally signed answer regarding a particular CA's certificate, OCSP envisages that the CA provide a responder certificate to the responder, a special digital certificate—signed by the CA—that essentially Other parties certify that the CA entrusts the responder to provide accurate evidence about its certificate.

Note that for this to work, each OCSP responder (and each CA) must have a privately signed key, and this key must be protected (ideally, by placing it in an electronic vault or by the server in an electronic vault use it).

Figure 2 shows the sequence of transactions in a cumbersome OCSP environment. The fact that the secret signing keys are protected is emphasized by placing them in thick "borders". In the case of signed data, the name of the signer is indicated immediately below. The figure shows the various PKI-sensitive components of the transaction, as indicated by the shaded boxes. The issuing authority itself has a private key SK1 which must be kept secure to prevent unauthorized certificate issuance and revocation. This key is used to sign the CRL, which is published to OCSP responders. Responder 1A's key must also be kept secure and used to sign Responder 1A's OCSP response.

Disadvantages of OCSP

Disadvantage 1: Calculation

Digital signatures are computation-intensive operations. The digital signature created by the responder based on each response is generated on request and is by far the most computationally intensive part of the validation operation: it can easily add anywhere from 50 milliseconds to 1 second to transaction time .

Even if the responder caches its digital signature on digital certificate C, and then sends the same signature when querying C until the next update, the answer to the first user of query C will be greatly delayed.

Con 2: Communication (vs. centralized implementation)

Assume a single acknowledgment server implements OCSP in a centralized fashion. All certificate validity queries would then actually have to be sent to it, and the server would be the main "network bottleneck" causing considerable congestion and delay, as shown in FIG. 3 . If a huge number of honest users suddenly interrogates the server, disruptive "denial of service" will likely occur.

Con 3: Security (if distributed implementation)

To prevent bottleneck problems that a centralized OCSP implementation might cause, a CA may consider distributing the request load generated by its certificate by distributing it among several OCSP servers (which are properly certified). In general, distributing the load of a single server to several servers (say 100), strategically located around the globe, will alleviate network congestion. However, in the case of OCSP, load distribution creates problems worse than it solves. Each of the 100 servers should have its own secret signing key in order to add its response to the certificate challenge it receives. Thus, compromising any one of 100 servers will compromise the entire system.

If a traditional OCSP responder is compromised, an attacker can do one of three things. First, it prevents the responder from issuing any responses. This type of attack is checkable on the certificate relying side, so it is not too serious. Second, it can sign a response using the discovered secret signing key, which indicates that the legitimate certificate has been revoked. Third, and most destructively, it can cause the responder to generate a signed response indicating that the revoked certificate is still valid. This type of false positive response may allow a terminated employee to regain access to the system, etc.

The best way to prevent responders from being compromised is to have it run from a secure electronic vault, have 24×7 monitoring, etc. Unfortunately, this is a costly option. A truly secure electronic library, meeting all the requirements of a financial CA, may cost more than $1M to build and $1M/year to run. Even if one is willing to pay such a fee, electronic libraries cannot be built overnight! If a CA needs several e-banks to ease the load on its current responders, it has to wait several months before a new one is built.

Furthermore, even if several expensive electronic libraries are in place, they may not be secure. This is because the OCSP mechanism requires the responder to receive requests from untrusted sources and serve them using its privately signed key. There is thus the possibility that a malicious agent would prefer to explore any weak spots beneath the operating system and thus expose the secret signing keys to exploit loopholes through armored concrete walls. In conclusion, without electronic vaults or sufficiently expensive perimeter protection responders, the potential for a security compromise is very high, but even if a truly secure building houses a responder, the responder can be vulnerable to software attacks: For sophisticated digital adversaries, OCSP Mechanisms make electronic vaults look very much like bins with "windows".

Disadvantage 4:: trust flow

OCSP has difficulty servicing certificate validity requests originating from different security domains. In the scenario shown in Figure 4, a responder run by organization #1 is able to provide a response about the status of the certificate from CA#1, but a responder run by another organization may not have enough information to provide a response about the " Foreign" certificate response. For example, the responder 2A run by the issuing authority CA2 does not know how to answer the request for the certificate of CA1.

This problem stemming from a lack of specific knowledge can be posed in one of two ways.

First, certificate relying parties from organization #2 may find that responders from organization #1 are asking them about the status of the certificate from CA #1. However, this limits performance because the responder from organization #1 may be geographically far from the interested certificate relying party in organization #2, and thus network time can significantly slow down the entire validation process.

The second is to allow a responder from organization #2 to respond with respect to a certificate from organization #1, by having CA #1 forward its CRL to the "foreign" responder. This does not pose a security threat because the CRL is digitally signed, and because the CA wishes to inform the largest possible audience about the validity of its own certificate. This provides the Responder of Organization #2 with sufficient information to answer the request for CA1's certificate from the certificate relying party. But for the certificate relying party, to really take Responder 2A's digitally signed answer seriously, CA1 should also prove that Responder 2A is trustworthy for answering the validity query of its own certificate. The whole process is shown in Figure 5.

This approach provides better scalability and performance, but it confuses the security and trust flow between the two organizations. In the above example, responder #2A authoritatively responds that certificate #321 of certificate relying party CA #1 is still valid. By responding incorrectly for any reason (misconfiguration, adversary attack, or outright spoofing), Responder 2A may lead to adverse outcomes for users from Organization #1. By allowing Responder #2A to make authoritative claims about its own certificate, Organization #1 relinquishes some of the trust it previously held.

As an example, consider an organization that is a credit card issuer. Bank #1 revokes user #321's card certificate, and it pays to ensure its responders are safe and secure. Responders from Bank #2 are misconfigured so that when the merchant certificate relying party asks User #321 for validity, they incorrectly respond that User #321 is valid. The merchant accepts the answer and allows the revoked user's transaction to proceed.

This type of trust delegation between organizations is acceptable in some circumstances, but it is not always useful for any large-scale leveling of traditional OCSP.

Live Credentials in OCSP

In light of the above problems, we wish to propose another certificate validation system, Real-Time Credentials (RTC), which addresses all the above-mentioned deficiencies of traditional OCSP while maintaining compatibility with the current OCSP standard. RTC technology is different from traditional OCSP because:

1. It does not delegate trust to external responders;

2. It centralizes all confirmation trusts to a single institution (the RTC institution); and

3. It distributes the query load from that single institution to any number of unprotected responders;

4. It does not reduce security even in distributed implementations relying on thousands of responders (even if these responders are not protected);

5. It dramatically improves response time to inquiries.

This provides fundamental improvements over traditional OCSP in terms of security, performance, scalability, and non-uniformity.

The RTC system includes the following steps:

CA Proof RTCA: The new system centers on the RTC Agency (RTCA). This is an entity that may or may not be aligned with a particular organization's CA. Preferably, each CA provides its own RTC with a special certificate, the RTCA certificate. The CA preferably digitally signs the certificate, indicating that it delegates and does authorize the RTCA to provide information about the validity of its own certificate. This certificate may bind a specific verification key PK (for which the RTCA holds a corresponding secret signed key) to the RTC authority (as identified by a specific identifier, OID number) and indicate in some way that the certificate essentially grants the RTC status, and may include other traditional certificate information and formats. In the case where two entities agree, it is still advantageous for them to have different signing keys, effectively such that in any case the CA only issues certificates and the RTC authority only manages them (ie certifies them as valid or revoked). There is such a situation that even if the CA and RTCA are consistent, the RTCA certificate can still be used. Preferably, there is only one RTC per CA, although for redundancy purposes it may be advantageous to have more than one, whether or not the same signing key is used.

RTCAs protect their signing keys: RTCAs must protect their signing keys, for example, by means of electronic vaults or secure facilities. (However, as we shall see, for certificate validation purposes, no additional electronic repository is necessary). The RTCA can be located in the same protected facility, with more than one server embedding its privately signed key, or keeping a copy of the key securely (e.g., in a bank's safe deposit box), or hosting more than one server, each The server has a secret signed key properly certified by the CA.

The CA notifies the RTCA of the status of its certificate. For example, it maintains an evaluation of any changes in certificate validity in an online/real-time manner (sends messages notifying RTCA certificate status changes whenever it occurs). Alternatively, it can send its CRL to the RTCA when generated.

RTCA independently signs the validity status of each certificate at a given interval, independently of any request: preferably periodically (or on any date in a sequence of dates), based on its current validation knowledge (e.g. based on the latest CRL of the CA) and independently At the request of any certificate relying party, RTCA processes each notable certificate of its CA and digitally signs a statement stating the status of the certificate. Thus, the result carries a time component indicating the next update for that certificate. If the period of the RTC depends on the CRL issued by the issuing CA, the update time can be the time of the next CRL. The time component may also indicate the issue time for the in-process CRL. So, in essence, RTCA precomputes a digital signature that indicates the status of each certificate at a given time interval T (eg, from the date of the latest CRL --- or from a sufficiently recent date --- to the date of the next CRL- -- or to a sufficiently recent date, in either case, to allow sufficient time to process all necessary information). This precomputation is performed independently of any certificate relying party requests for the certificate. In fact, it is preferred that the RTCA pre-computes all signed certificate state statements before any queries about certificate state made in the time interval, or completely before the time interval. In particular, the RTCA may precompute all of its signed statements about time interval T 1 minute before T starts. The fact that doing so will not "sync" with the CRL is less serious. CRLs themselves are not real-time, and information about a certificate's revocation and why it has been revoked can take considerable time. For example, a user may realize that their key has been compromised and thus request that their own certificate be revoked 1 day after that fact. Thus, in any case, the certificate is revoked with a delay of 1 day. Preferably, the statement of the validity of the certificate signed by the RTCA is in a standard OCSP format. That is, in essence, RTCA preferably precomputes OCSP-responses to OCSP requests that have not yet been generated. This is important because the OCSP software is already in place and it is very convenient to utilize the RTC system without modifying any existing certificate relying party software.

RTCA sends a signature of its precomputed validity status to unprotected responders: After precomputing this signature, RTCA makes it available to other parties, including certificate relying parties (e.g., in response to their requests), but, in particular , sent to the responder. These responders do not need to be protected. In fact, they handle RTCA signed messages, and these cannot be substantially modified or changed in an undetectable way. In fact, RTCA can easily send them to external responders (responders belonging to other organizations). RTCA can assist responders in handling their signatures by presenting them to the responders in a properly organized manner. For example, it can present the validity status of its signed certificates sorted by certificate serial number, or in any way, or ensure that each signed data has the same or suitably close length, etc. To ensure that all relevant precomputed responses have been received, the RTCA may sign and date the entirety of its responses (eg, all of these with respect to the same time interval and CA).

Also, RTCA preferably sends its own RTCA certificate to its responders. This transfer does not have to happen every update. In particular, it can only be performed at the beginning.

Responder saves RTCA pre-computed signature: The responder saves the received pre-computed RTCA signature for a sufficient time. Preferably, if these signatures are for a given time interval T, they keep them at least until the end of T. Preferably, responders (especially those belonging to the same organization as the RTCA) can be proactive and check that they have received the appropriate RTCA signatures correctly and in time. For example, Respondents may:

(1) Verify that the precomputed response for time interval T has been received at the beginning of T (or other appropriate time for T);

(2) verify the received RTCA signature (and possibly the appropriate RTCA certificate);

(3) Verify that it has received all signatures (such as less than the expected number of signatures, fewer than the final transmitted signatures, etc.);

(4) Verify that it has received an RTCA-signed statement of the validity of a certificate previously declared revoked; etc.

If either problem is detected, it can notify the RTCA or another appropriate entity.

The certificate trust asks the responder for validity status information: The certificate trust asks the responder for the validity status of the certificate, and they use the OCSP format for their requests.

The Responder answers the query with a precomputed response: When asked about the validity of a given certificate, the Responder retrieves the RTCA precomputed answer for that certificate from memory and returns it.

The responder may also forward the appropriate certificate of the RTCA that signed the precomputed response.

The certificate relying party verifies the precomputed answer (and RTCA certificate): the certificate relying party processes the received response to confirm the validity status of the certificate of interest. Preferably, if the response is in OCSP format, they use OCSP software for this processing. Preferably, they verify the appropriate RTCA certificates.

By this application, it should be understood that certificates can be of different types, and evidence of the current validity of CA certificates and CRTA certificates can be added and verified as needed.

Figure 6 shows the RTC system

Advantages of the RTC system

RTCA periodically produces digitally signed validity statements (evidence, since the statement cannot be forged) of all current certificates of the CA and distributes them to any interested responders. (Each proof is preferably constructed as a syntactically correct OCSP response, signed by the RTCA private key.) When a certificate relying party asks for the status of the certificate, the RTC responder can return the corresponding pre-generated response it has cached. The certificate trustee can verify the signature of RTCA. (Additionally, it can also verify the RTCA's certificate to ensure that it is dealing with a trusted RTC authority for a particular CA. Of course, all other certificates like this could be of a different class.)

Advantage 1: Calculation

A digital signature is a calculation of several types of operations. But the RTC system concentrates this difficulty on a single server (entity): RTCA. Therefore, it is very easy and relatively cheap to equip a single entity with a computer powerful enough to process all required digital signatures. In contrast, RTC responders perform only trivial computations. They essentially (1) store the RTCA signatures and (2) only perform fetch-forward operations in response to certificate relying party queries. Therefore, they can be implemented with very cheap hardware. Therefore, the total RTC cost can be significantly lower than that of OCSP. At the same time, the response time is very fast. In fact, the time taken by a very cheap RTC responder to retrieve and send a precomputed RTCA response is negligible relative to the time taken by an OCSP responder, since OCSP must perform digital signatures in response to certificate relying party requests.

Advantage 2: Communication

In an RTC system, responders can use trivial hardware and need not be secure. As a result, RTC responders are very cheap and, in fact, can be deployed in large numbers. That is, a distributed implementation of the RTC system can always be afforded. Thus, even if a huge number of certificate-validity requests are generated in a short period of time, the load can always be spread to many RTC responders, eliminating the risk of congestion and benign denial of service at no further cost . (Note that the workload of RTCA depends only on the number of certificates and is affected by the number of validity status requests. Thus, a single RCA can be used even if hundreds of millions of validity requests are expected.)

Advantage 3: Security

In an RTC system, only the RTCA (including the CA if it is a differently located entity) is protected. In fact, the responders do not hold any keys: they only hold the RTCA's digital signature, but for all security purposes it can be fully disclosed after being computed by the RTCA. In contrast, each OCSP responder has a secret signing key, compromising which can compromise the entire system. Therefore, securing a single point is preferred and easier than securing many equally important points.

Also, unlike in OCSP, certificate relying parties cannot easily stage software attacks. In effect, the RTC responder serves the request for a certificate relying party with a non-secret message. In fact, they don't have any keys and only need to store precomputed digital signatures. Thus, even if a certificate relying party succeeds in embedding some kind of Trojan horse challenge, it will not be able to reveal anything. At most it can reveal everything that the RTC responder knows, that is, the full and exact account of its certificate is valid and it is revoked at a given time interval. And this is not only non-secret information, but even information that the issuing authority would like to be generally known so that no one can incorrectly rely on one of its certificates.

Finally, note that software attacks cannot easily be staged by RTCA. In fact, despite the key used for secret signing, RTCA does not process requests from untrusted sources. This is because, RTCA does not answer any untrusted requests: it simply receives input from a CA (a very trusted source) and periodically outputs data (signed validity statements). Therefore, the ability to insert Trojan horses will be lost in the RTC system! In other words, in an RTC system, not only is a single electronic bank sufficient, but there are no "windows" of any kind.

Advantage 4: Trust Flow

In addition to these advantages, the RTC over OCSP approach enables considerable flexibility within heterogeneous PKI configurations involving multiple organizations. The diagram below shows how RTC over OCSP can be configured in a cross-CA environment.

Figure 7 shows how a responder from organization #2 can take over the response from organization #1 without transferring any trust from organization #1 to a responder in organization #2. Since RTC responders are simple, non-trusted relay messages, they can be widely distributed and mirrored without compromising the security of the overall system. The certificate relying party asks the responder of Organization 2 (Responder 2B) about the validity of Organization #1's certificate. Note that the response it gets back is convincing because it is digitally signed by the RTCA of organization #1 (RTCA1). Furthermore, the direct digital signature from the correct organization is preferably corroborated by the fact that the certificate relying party also has RTCA1's certificate (preferably signed by CA1), which guarantees that RTCA1 is indeed the proper RTC authority for Organization1.

In summary, Organization #1 enables Responders of Organization #2 to provide convincing proof of validity for Organization #1's certificate without relinquishing any amount of control over the validity status of its own certificate. That is, in an RTC system, trust can flow from one organization to another without any associated loss of security or control.

Advantage 5: Security inhomogeneity

Figure 7 shows an extreme case where responders are treated as explicit network infrastructure rather than as resolute trust points. It shows the extreme case of enabling heterogeneous responders to securely construct a simple RTC that can service requests on certificate status from many sources. This is similar to the service provided by the Internet's DNS infrastructure in that it allows a collection of heterogeneous name servers that apparently find and cache valid responses to queries.

This non-uniformity is a significant advantage of RTC systems over conventional OCSP. It allows a wide range of organizations to work with each other, so that certificate trustees from different organizations can mutually confirm certificates from other organizations in a safe, reliable, and effective manner.

Real Time Credentials (RTC) is a low-cost, secure, scalable, and fully valid certificate validation system. RTC may (1) provide an option to the Open Certificate Status Protocol (OCSP), and (2) work within and enhance OCSP. RTC systems offer significant advantages over OCSP even when exercising the option of maintaining compatibility with the OCSP standard to provide high quality security and scalability.

RTC optimization

2-party to 3-party certificate confirmation

U is the party with the certificate Cu. As part of the transaction with party V, U may send Cu to V (unless V already has one), and possibly perform additional tasks (such as revealing the digital signature on the public verification key attested in Cu, which belongs to U or passed Decrypt Random Challenge Encryption Identification). For transaction security, V can confirm the current validity of Cu and make the validity query reach the RTC responder. The Responder can answer this query by retrieving and returning the most recent RTCA signed statement on Cu. However, asking the RTC responder makes a 3-party transaction instead of a 2-party transaction, thereby increasing the desired U-V transaction time.

RTC can help notably since it is a predictable time interval.

That is, party U may at the beginning of each time interval T receive an RTCA-signed declaration Du that Cu is valid for T. U may receive Du in response to a request to it or may be pushed with Du. In each case, transacting with V during the interval T, U may forward Du to V, in addition to all other steps or tasks necessary for the transaction. Thus, the U-V transaction is significantly accelerated, since V does not have to invoke any third party in order to confirm the current validity of U's certificate.

In a sense, although "all time", which includes U acquiring Du, cannot be accelerated, U-V transactions will be. Note that saving does not need to be done all the time, only accelerating U-V transactions is still valuable. In fact, assume that RTCA statements are calculated at midnight and specify all day as their time interval. U can then obtain Du early in the day (when no real stress exists) and then forward it to V during time-sensitive U-V transactions during work hours, when time savings may be substantial. In addition, efficiency is gained, after obtaining and caching Du, if U forwards it throughout the day when transacting with several parties (eg 100). In this way, for example, a single certificate relying party query successfully replaces 100 certificate relying party requests.

Note that this optimization can also be implemented by the V side. That is, after obtaining the response Du from the RTC responder, the V party may give Du to U or make Du available to other parties in response to an inquiry about the validity of U's certificate Cu.

This optimization can also be applied in the preferred, OCSP-compatible implementation of the RTC. In fact, we propose to apply similar optimizations to traditional OCSP implementations as well. That is, a user requests and obtains an OCSP response for its own certificate, which is then forwarded to other transacting parties at appropriate intervals as part of its transaction. Alternatively, when the validity of U's certificate Cu is first queried by a certificate relying party, the OCSP responder computes its response Ru, returns it to the inquiring certificate relying party, and also forwards it to U so that U can Cache it, at least for a while, and may forward it as part of its Cu-based transaction.

Helpful certificate confirmation

Note that the RTC system can be implemented using the data found in a single certificate, saving additional certificates and/or response length. As we have seen, a CA may issue an RTCA certificate which authorizes a particular RTCA to provide an authoritative answer as to the validity of its own certificate. Ideally, the RTCA certificate specifies the public key that must be used to verify RTCA-signed responses. However, the CA may embed the RTCA within its own certificate. That is, the CA (with appropriate format, OID, etc.) can be included in the certificate Cu, as well as the public key PK that should be used to verify the digitally signed response as to the validity of Cu. In this way, the certificate relying party does not need to receive a separate RTCA certificate. When an RTC responder is queried for the latest Cu's proof of validity, it can only get a RTCA signed response. In fact, Cu indicates within it a public verification key that certificate relying parties can use to verify Cu's proof of validity. This can result in significant transmission and storage savings.

Similarly, certificate Cu may specify its own time interval. In this case, the RTCA response need not indicate the beginning and end of the interval T. Alternatively, if it is clear that the certificate has a validity interval that includes a full day, then this information need not be specified within the certificate, and the same savings are achieved in the RTCA response application.

Repeal alone

While RTC evidence of the validity or suspension of a particular certificate C should specify a time interval, the evidence of revocation need not specify any time interval: it has the ability to specify a single point in time. In fact, unlike validity and suspension, traditional revocation is an irreversible process. Thus, a single revocation time rt may be capable of proving a revoked certificate. And rt need not be the start of any time interval T. Therefore, once permanently repealed, RTCA does not have to send proof of repeal of C on all updated dates. In principle, the revocation proof could be sent once and then cached by the RTC responder and returned when the certificate relying party asks about C.

Note that RTCA can be notified immediately when certificate C has been revoked. For example, in the middle of the time interval T, where the RTCA has generated and forwarded C's validity proof to the RTC responder. Of course, no such proof of validity will be computed for C until the next update. Thus, better counter measurement involves prioritizing proof of revocation over proof of validity. That is, an honest certificate relying party sees both C's validity proof and C's revocation proof (at time t) at some time interval T, and treats C as revoked (after time t). However, some proof-relying parties may never see such evidence of revocation, and thus C may be considered valid until T ends. As we can see, such problems are unavoidable in the sense that even in traditional OCSP, news of C's repeal takes a certain amount of time to reach responders, and it may take even longer Come to realize that C should be repealed. However, these problems can be mitigated by having RTCA compute and send proof of C's revocation to all RTC responders as long as they are aware of the revocation. All functioning RTC responders will then erase any validity evidence for C from memory and replace it with the newly received revocation evidence. In this way, they will provide credential relying parties with accurate proof of the validity of C from then onwards.

System generality

A CA/RTCA/Responder/Participant/User can be any entity (such as a person, organization, server, device, computer program, computer file) or collection of entities.

Certificates should be construed to include all kinds of certificates, and in particular, graded and flat certificates (cfr. US Patent No. 5,420,927, incorporated herein by reference). Validity Status and Validity Status Evidence Cards contain the validity status and validity status evidence of certificates used for grading. Verifying the validity of the certificate C may include verifying the validity of the CA certificate, for the CA with the issuing C, and verifying the validity of the CRTA certificate, for the RTCA providing the signed response regarding the validity status of C.

While traditionally a certificate is a digitally signed document that binds a specific key to a specific user, US Patent 5,666,416 below (hereby incorporated by reference), certificates shall include all kinds of digitally signed documents. For example, a vendor acting as a CA may certify its price list (possibly along with date information) by digitally signing it. The validity status of the certificate is also critical. For example, a seller may want to demonstrate the current validity of a price list. The customer may thus wish to confirm the current validity of the price list document. In particular, RTC systems are ideal for proving the current validity of web pages. In fact, the RTCA that produces proof of current validity can be stored behind the web page itself. (In this case, the party may be considered a computer file.)

Sending data D (to party X) should be construed to include making D available (or making X receive D).

Three-factor authentication with real-time confirmation

The following is an efficient three-factor authentication with real-time confirmation and revocation, which is implemented to connect infrastructure without a certificate relying party. This works for physical access applications such as gates or logical applications such as file or application access. A physical access scenario is described below. Other applications are readily deduced from this model by those skilled in the art.

Example 16:

1. The user has credentials (physical tokens) stored on the wireless device. The token preferably has the ability to securely store digital certificates and private keys. Preferably, the token has a long-range (WAN) connection method (such as GPRS, SMS, paging, CDMA, GSM, etc.) and a short-range (PAN) connection method (such as Bluetooth, IR, RF, etc.). The token may also have one or more additional authentication factors (keypad for PIN or biometric feature reader). This example assumes that the token is a Bluetooth mobile phone.

2. The door has a control panel with a small CPU capable of performing standard PKI operations, and a short range (PAN) connection method is used for the physical token. This example assumes a Bluetooth enabled computer similar to our standard demo door.

3. The user is prompted to enter a PIN number into their mobile phone (or enter their own biometric information, if a biometric information reader is available). This prompt can occur once a day, when the user is attempting to go through the door for the first time, every few hours, randomly, based on the receipt of a special SMS message. The PIN (or biometric information) is used as a second authentication factor (the first being the credentials on the phone) and "unlocks" the phone for use in physical access applications.

4. Once the user is within range of the door (30 feet for Bluetooth), the phone and door recognize each other and begin the initial authentication and validation sequence:

4.1 (Optional) The door identifies itself to the phone by sending the door's credentials to the phone via Bluetooth. The phone checks the certificate and confirms the door using any of our standard methods. This solves the "rogue reader" problem and ensures the door is a legitimate reader before the phone discloses any information.

4.2 The phone sends the user's credentials to the door, which contains the user's biometric details. The phone also sends an RTC proof (preferably, or a confirmation token, ie a 20 byte validity proof, or a distributed OCSP proof) to prove its current validity. Evidence had previously been received by the WAN in normal CoreStreet fashion, as described in US Patent 5,666,416, issued September 9, 1997, entitled "Certificate Revocation System."

4.3 The door authenticates and confirms the user's certificate in the normal RTC way. A door can do this for multiple (or even all) phones in the current range (multiple employees may be in the vicinity of the door).

5. By the time the user reaches the door, the previous steps have been completed. The user scans their fingerprint (or other biometric feature) on a reader mounted on or near the door. The gate matches the biometric details with data held in all confirmed certificates in scope. If the biometric characteristics match, the door opens. Otherwise, the door remains closed.

It has the following advantages:

1. Strong discrimination (3 factors in this example, possibly more)

2. Clear to the user (just approach the door and open it, no card or PIN number to remember)

3. Real-time revocation and confirmation

4. No connection to the base structure at any gate is required—may be done at 30,000 feet or in the middle of the ocean

5. Can be built with standard hardware and software components

Step 4.1 is an independent invention of separate interest because it solves an existing problem (as identified by the Department of Defense) for which there is no other solution. This scheme can be extended by having "revocation evidence or service logins travel to and/or from other people's cards/phones to separate doors".

Protect Mobile Computing Resources

The preferred embodiment of the invention is based on a 20-byte, unforgeable, published "evidence". The 20-byte proof is cryptographically secured using a one-way function called a hash. The method is simple, does not require encryption and does not use digital signatures. These properties make the technology ideal for: large-scale deployments (up to 100 million); bandwidth-limited applications (such as wireless applications); offline validation (ie, no network connection is required).

Laptop theft is a serious problem imposing replacement costs, reduced productivity, and loss of irrecoverable data. Loss of control over sensitive/confidential data (sensitive operational information, advice to customers, emails, calendars, contact forms, pending mergers, new product IP, strategies, and launch plans, financial results, confidential compensation information ), and lost network and infrastructure details (such as usernames & passwords, dial-in numbers, IP address configuration, DNS naming rules, and major mail services).

In one embodiment, the present invention provides for leasing, ie a license to use for a specified time, where the lease duration is a configurable parameter. The technique of the present invention enhances the occurrence of effective "leases". Leases are 20 bytes, unforgeable "public tokens": valid tokens, suspension tokens, and revocation tokens. New leases are accepted automatically. The computer can be temporarily disabled and the system administrator or user can restore the laptop. Computers can be permanently disabled using possible defenses by the system administrator. Figure 8 illustrates system operation according to an embodiment of the present invention.

As long as the device is still entitled, valid lease tokens are generated by the central authority once a day. Obtaining a valid lease token on a protected device can be accomplished in many ways and is very clear to the end user. If a device is stolen, two things will happen: valid lease tokens cease to be generated (there is no way to extend beyond the day's use); and revocation tokens are propagated to the network (any connected implementing device is immediately unavailable). The stolen device is turned off for: a few seconds (best case, if push capability is achieved); a few hours (general case, as long as any network connection is made); a day (worst case, no connection possible).

The system is protected from both random thieves and insider thieves. There is no point in stealing the device because: the hardware is unusable; the software is unusable; and the data is unreadable. Similar to some cassette radio varieties, it is no longer usable as long as it is stolen, thus deterring theft.

The validity token is delivered by the following methods: wired network; wireless network; SMS wireless "push"; paging system; hand-held phone/PDA via infrared port; bluetooth device; 7G9L TC77 U8QL S2PS QK2Q EN9V PXXHXPUL″) such as fax, email, telephone call. Figure 9 is a schematic diagram of a stolen computer timeline.

Additional protection methods can be used, including: physical anchors for protection; asset tracking services for retrieval and as a deterrent; motion sensitive components and alarms as a deterrent; access keys as a deterrent and access control; Stalkerware obtained and used as a deterrent; and its data encryption to protect data only, potential attacks and consequences include:

Removing/surrounding software: possible with "administrative privileges", but extremely difficult after repeal. Optional BIOS/hardware countermeasures which provide almost 100% protection.

Replacement/reformatting of hard drives: All data loss is safe, and optional BIPS/hardware hooks prevent drive replacement.

Move the hard drive to another machine to read data: data can be encrypted.

Prevent Revocation Token Receipt: Delay the operation of the laptop until the lease expires (worst case).

Other embodiments of the invention will be apparent to those skilled in the art from practice or description of the invention disclosed herein. The specification and examples therein should be considered illustrative, with the true scope and spirit of the invention being indicated by the following claims.

Claims (21)

1, a kind of entity A that is used for is controlled the method that at least one user U visits at least one unconnected D, and door D has the device of definite current time, comprises step:

For each time interval d of a date sequence, make A produce digital signature SIGUDd, it indicates user U addressable door D during time interval d;

Make U during time interval d, receive and be used to present to a D with SIGUDd by D;

Make U that SIGUDd is presented to a D; And

D is opened in checking after following two: (i) SIGUDd indicates the digital signature of U at the A of the addressable door of time interval d D, and (ii) the current time really in time interval d.

2, method according to claim 1, wherein U has subscriber card and D has the card reader that is connected with electromechanical lock, and wherein U receives SIGUDd by SIGUDd being kept in its card, and reads and SIGUDd is presented to D by making it block card reader by D.

3, method according to claim 1, wherein A makes SIGUDd can be received by U during time interval d, it is realized by SIGUDd being inserted in the addressable database of U.

4, method according to claim 1, wherein SIGUDd is a public key signature, and wherein D preserves the PKI of A.

5, method according to claim 1, wherein D also verifies the identity information about U.

6, method according to claim 1 wherein is made up of one of at least following about the identity information of U: PIN and to the answer of the challenge of D.

7, have entity A, at least one unconnected door, and the user have in the access control system of subscriber card with access door, a kind of method that is used for unconnected D, it points out that to A specific user U attempts to visit D, comprises step:

Make D receive information IU from U, it indicates U and wishes access door D;

Make D at least temporarily preserve IU; And

For at least one subsequent user V, make D make V at least temporarily IU is kept in the card of V to be used to present to entity A.

8, method according to claim 7, wherein V presents to A with IU, and it is by transferring to IU the addressable database of A or information transmission being realized to A.

9, method according to claim 7, wherein IU comprise following one of at least: (i) offer the information that is used for access door D of U, and (ii) produce information with visit D by U.

10, method according to claim 7, wherein IU comprises the digital signature that is produced by U.

11, method according to claim 7, wherein IU comprises the digital signature of U.

12, a kind of method of controlling physical access comprises:

Check real time credentials, wherein real time credentials comprises the fixing first and the second portion of periodic modification, and wherein real time credentials is provided is the evidence of nearest voucher to second portion;

By in first, carrying out a computing and result and second portion being compared the validity of verifying real time credentials; And

Only when being verified as effective voucher, real time credentials just allows physical access.

13, method according to claim 12, wherein first is digitally signed by mechanism.

14, method according to claim 13, wherein mechanism provides second portion.

15, method according to claim 14, wherein second portion is provided by the entity beyond the mechanism.

16, method according to claim 12, wherein real time credentials is provided on the smart card.

17, method according to claim 12, wherein the user obtains the second portion of real time credentials in primary importance.

18, method according to claim 17, wherein the user is allowed to visit the second place that is different from and is located away from primary importance.

19, method according to claim 12, wherein the first of real time credentials represent uni-directional hash to small part, it repeatedly is applied to the part of the second portion of real time credentials.

20, method according to claim 19 is wherein repeatedly sent the time quantum that the back is passed corresponding to the first from real time credentials.

21, method according to claim 12 is wherein controlled physical access and is comprised the visit of control by door.

Images