Silvio Micali s Fast ValidationRevocation

Silvio Micali's Fast Validation/Revocation

A certificate authority (CA) must keep an up-to-date list of all certificates revoked in a certificate revocation list (CRL). It goes without saying that the CA must make it easy for registration authorities to revoke any given certificate (but prove that they have the right to do so). With CRLs, relying parties have the burden of checking this list each time a certificate is presented. Best practices call for a certificate deployment point (CDP) URL to be embedded in each certificate. A CDP is a pointer to the location of the CRL on the Internet, accessible programmatically by any relying party's applications. CRLs are usually updated once per day because the process of generating them is non-trivial. When an organization is dealing with a compromised key or a rogue employee, once-per-day updates can mean a huge loss during that day of compromise. Currently, almost no one checks revocation lists at all. Although the sponsoring CAs obediently create CRLs, and numerous tools can and do process them, there are so many unsolved problems with them that, in our view, CRLs on the Internet are a technological failure.

Online Certificate Status Protocol (OCSP) was an attempt to create a much finer granularity protocol for essentially real-time revocation checking. But like CRLs, the information provided must be signed by the originating CA, which is an expensive operation to perform in real time. The best case on an unloaded system of moderate speed is 26ms response time for a single OCSP request in our tests. In our view, this makes OCSP so limited in scope that it will continue to be only a bit player in revocation solutions. We expect to see very little deployment of OCSP in the future.

Web Services Security must have a workable revocation, and the existing technologies are not strong enough. In our opinion, there is much promise in emerging revocation techniques that are scalable and respond in microseconds, such as Silvio Micali's technique based on chains of hashed secret codes.

The CA generates a secret random 20-byte value X . Using X as input to hash function H , you generate X ₁ = H ( X ). Then you use the output of the previous hash computation as input to the next until you achieve X ₃₆₅ . Finally, you insert the value X ₃₆₅ into the certificate before it is signed by the CA:

C = SIG _CA ( serial no ., PK _U , U, issue date, expiration date, X ₃₆₅ )

This process is shown in Figure A.2.

Figure A.2. Silvio Micali's fast certification validation scheme.

This certificate is valid on the day it is signed by virtue of the fact that X ₃₆₅ indicates this is a valid certificate. On the next day, the CA reveals X ₃₆₄ .

Validity Check

To check the validity of this certificate on the next day, you take the revealed X ₃₆₄ and compute one hash computation using X ' ₃₆₅ = H ( X ₃₆₄ ), and if the new X ' ₃₆₅ = X ₃₆₅ stored in the certificate, this certificate is still valid. In general, on day D before expiration, the CA reveals X _D , from which the correct number of hashes is performed to reach X ₃₆₅ . If the value matches what is in the certificate, it is still a valid certificate. Only the CA knows the starting point; nowhere along the chain can you compute backwards because these are one-way non-reversible hash functions. Furthermore, the intermediate values can always be openly revealed and published. The cost to the CA is a table lookup. The cost to the relying party is a few hashes.

Revocation

Revocation will be a binary check; either the certificate is revoked, or it is not. Initially, the CA generates a random 20-byte value Y and from this computes Y ₁ = H ( Y ). Y ₁ is stored in the certificate before it is signed:

C = SIG _CA ( serial no. , PK _U , U, issue date, expiration date, X ₃₆₅ , Y ₁ )

Although the certificate is valid, the revocation sentinel revealed by the CA is 0 because H (0) Y ₁ for any Y ₁ . But as soon as this certificate is revoked, the CA reveals Y as the revocation sentinel.

The beauty of this scheme is that the proofs do not need to be signed, so they can be posted on insecure sites all over the Internet or even published in the Wall Street Journal . We believe this scheme or something like it will be essential to broad-based secure Web services.

This information has been used with permission from Silvio Micali: U.S. Patent nos. 6,292,893; 5,960,083; 5,793,868; 5,666,416; and others.