Method for authentication item

Details Method for authentication item Method for authentication item

1998-01-22

2001-05-01

Swann, Tod (Department: 2132)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C713S157000

Reexamination Certificate

active

06226743

ABSTRACT:

FIELD OF THE INVENTION
The present invention is in the general field of digital signature for authentication purposes.
BACKGROUND OF THE INVENTION
The wide use of public key cryptography requires the ability to verify the authenticity of public keys. This is achieved through the use of certificates (that serve as a mean for transferring trust) in a Public Key Infrastructure (PKI). A certificate is a message signed by a publicly trusted authority (the certification authority, whose public key authenticity may be provided by other means) which includes a public key and additional data, such as expiration date, serial number and information regarding the key and the subject entity.
When a certificate is issued, its validity is limited by an expiration date. However, there are circumstances (such as when a private key is revealed, or when a key holder changes affiliation or position) where a certificate must be revoked prior to its expiration date. Thus, the existence of a certificate is a necessary but not sufficient evidence for its validity, and a mechanism for determining whether a certificate was revoked is needed.
A typical application is a credit card system where the credit company may revoke a credit card, temporarily or permanently, prior to its expiration, e.g. when a card is reported stolen or according to its user's bank account balance.
PRIOR ART DISCUSSION
Certificate Revocation List (CRL)
A CRL is a signed list issued by the CA identifying all revoked certificates by their serial numbers. The list is concatenated with a time stamp (as an indication of its freshness) and signed by the CA that originally issued the certificates. The CRLs are sent to the directory on a periodic basis, even if there are no changes, to prevent the malicious replay of old CRLs instead of new CRLs.
As an answer to a query, the directory supplies the most updated CRL (the complete CRL is sent to the merchant).
The main advantage of the scheme is its simplicity.
The main disadvantage of the scheme is its high directory-to-user communication costs (since CRLs may get very long). Another disadvantage is that a user may not hold a succinct proof for the validity of his certificate.
A reasonable validity expiration period should be chosen for certificates. If the expiration period is short, resources are wasted reissuing certificates. If the expiration period is long, the CRL may get long, causing high communication cost and difficulties in CRL management. Kaufman et al. [15, Section 7.7.3] suggested reissuing all certificates whenever the CRL grows beyond some limit. In their proposal, certificates are marked by a serial number instead of an expiration date. (Serial numbers are incremented for each issued certificate. Serial numbers are not reused even when all certificates are reissued). The CRL contains a field indicating the first valid certificate. When all certificates are reissued, the CRL first valid certificate field is updated to contain the serial number of the first reissued certificate.
Certificate Revocation System
Micali [18) suggested the Certificate Revocation system (CRS) in order to improve the CRL communication costs. The underlying idea is to sign a message for every certificate stating whether it was revoked or not, and to use an off-line/on-line signature scheme [
11
] to reduce the cost of periodically updating these signatures.
To create a certificate, the CA associates with each certificate two numbers (Y
365
and N) that are signed along with the ‘traditional’ certificate data. For each certificate, the CA chooses (pseudo) randomly two numbers N
0
and Y
0
and computes (using a one-way function ƒ) Y
365
=ƒ
365
(Y
0
) and N=ƒ(N
0
). (Actually, a stronger assumption on ƒ is required, e.g. that ƒ is one-way on its iterates, i.e. that given y=ƒ
i
(x) it is feasible to find x′ such that y=f(x′). This is automatically guaranteed if ƒ is a one-way permutation).
The directory is updated daily by the CA sending it a number C for each certificate as follows:
1. For a non-revoked certificate, the CA reveals one application of ƒ, i.e. C=Y
365-i
=ƒ
365-i
(Y
0
), where i is a daily incremented counter, i=0 on the date of issue.
2. For a revoked certificate, C=N
0
.
Thus the most updated value for C serves as a short proof (that certificate x was or was not revoked) that the directly may present in reply to a user query x.
The advantage of CRS over CRL is in its query communication costs. Based on Federal PKI (Public Key Infrastructure) estimates, Micali [18] showed that although the daily update of the CRS is more expensive than a CRL update, the cost is CRS querying is much lower. He estimated the resulting in 900 fold improvement in total communication costs over CRLs.
Another advantage of CRS is that each user may hold a succinct transferable proof of the validity of his certificate. Directory accesses are saved when users hold such proofs and presents them along with their certificates.
The main disadvantage of this system is the increase in the CA-to-directory communication (it is of the same magnitude as directory-to-users communication, where the existence of a directory is supposed to decrease the CA's communication). Moreover, since the CA's communication costs are proportional to the directory update rate, CA-to-directory communication costs limit the directory update rate.
The complexity of verifying that a certificate was not revoked is also proportional to the update rate. For example, for an update once an hour, a user may have to apply the function, ƒ, 365×24=8760 times in order to verify that a certificate was not revoked, making it the dominant factor in verification.
Certificate Revocation Trees
Kocher [16] suggested the use of Certificate Revocation Trees (CRT) referred to also as authentication tree, in order to enable the verifier of a certificate to get a short proof that the certificate was not revoked. A CRT is a hash tree with leaves corresponding to a set of statements about certificate serial number X issued by a CA, CA
X
. The set of statements is produced from the set of revoked certificates of every CA. It provides the information whether a certificate X is revoked or not (or whether its status is unknown to the CRT issuer). There are two types of statements: specifying ranges of unknown CAs, and, specifying certificates range of which only the lower certificate is revoked. For instance, if CA
1
revoked two certificates X
1
<X
2
, than one of the statements is:
if CA
x
=CA
1
and X
1
≦X<X
3
then X is revoked if X=v
To producer the CRT, the CRT issuer builds a binary hash tree [17] with leaves corresponding to the above statements
A proof for a certificate status is a path in the hash tree, from the root to the appropriate leaf (statement) specifying for each node on the path the values of its children.
The main advantage of CRT over CRL are that the entire CRL is not needed for verifying a specific certificate and that a user may hold a succinct proof of the validity of his certificate.
The main disadvantage of CRT is in the computational work needed to update the CRT. Any change in the set of revoked certificates may result in re-computation of the entire CRT.
LIST OF CITED PRIOR ART
U.S. Pat. No. 4,309,569 (hereinafter the Merkle patent)
[1] A. V. Aho, J. E. Hopcroft, J. D. Ullman. “Data Structures and Algorithms”. Addision-Wesley, 1983.
[2] R. G. Seidel., C. R. Aragon “Randomized Search Trees”. Proc. 30th Annual IEEE Symp. on Foundations of Computer Science, pp. 540-545, 1989.
[6] M. Bellare, P. Rogaway. “Collision-Resistant Hashing: Towards Making UOWHFs Practical”. Advances in Cryptology—CRYPTO '97, Lecture Notes in Computer Science, Springer-Verlag, 1997.
[11] S. Even, O. Goldreich, S. Micali. “On-Line/Off-Line Digital Signatures”. Journal of Cryptology, Springer-Verlag, Vol. 9

Affiliated with

Also associated with

Rating

Method for authentication item does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for authentication item, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for authentication item will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2553157