In a public key infrastructure, a certificate specifies a binding between a name and a public key or other attributes. Over time, public keys and attributes might change---a private key might be compromised, leading to selection of a new public key, for example. The old binding and the certificate that specifies that binding then become invalid. A certification authority (CA) attests to the validity of bindings in certificates by digitally signing the certificates it issues and by providing a means for clients to check the validity of certificates. With an on-line CA, principals can check the validity of certificates just before using them. COCA (Cornell On-line Certification Authority) is such an on-line CA.
COCA uses cryptographic schemes, such as threshold cryptography and proactive secret sharing. Some introduction to such schemes, with simple examples for illustration, can be found in lecture notes (Secret Sharing and Distributed Services and Replication Management) of CS 513 (System Security). You can find more on threshold cryptography from Professor Desmedt's home page. IBM Haifa maintains a great page for proactive security. A list of related projects can be found at the PASIS web page.
For a secure service, any assumption we make constitutes a vulnerability of the system, because an adversary can disrupt the service by invalidating that assumption. For example, for a service that relies on a synchronous assumption stipulating a bound on message processing time and message transmission delay, an adversary might launch denial of service attacks to delay message processing or message delivery, thereby compromising the service. COCA thus assumes a weak system model as follows:
While a service that relies on a weak system model is desirable for security, designing such a service is often challenging because of the weak system model. For example, it is known that designing protocols that work in an asynchronous system is hard, and even impossible in certain cases.
COCA achieves availability through replication and employs a dissemination Byzantine Quorum System, instead of a replicated state machine, for coordinating replicas. New protocols are designed so that the use of a Byzantine quorum system in the service is transparent to clients.
Replication improves availability, but it also increases the chance of secret disclosure when the replicated service maintains a certain secret (e.g., a service private key). COCA employs threshold cryptography, so that servers store shares of the service private key and use these shares to compute signatures for messages without reconstructing the service private key. An adversary can reconstruct the service private key only if it obtains enough shares from compromised servers.
Even with threshold cryptography, a mobile adversary, which compromises a server for a short period of time and then move on to the next victim, is able to compromise enough servers over a long period of time, thereby obtaining enough shares to reconstruct the service private key. COCA defends against such attacks by proactive recovery, which periodically reconstitutes the states of servers without any trace of prior compromise. An essential part of proactive recovery is proactive secret sharing, which involves refreshing shares on servers. A new proactive secret sharing scheme is designed to work in an asynchronous system model.
While COCA already exhibits reduced vulnerability to denial of service attacks due to weak assumptions in the system model. COCA further deploys defense mechanisms (e.g., request authorization, resource management, and caching) against denial of service attacks.
A prototype of COCA has been implemented with about 35,000 lines of new C source on top of OpenSSL, a cryptographic toolkit. The prototype has been deployed with 4 servers on a local area network and on the Internet, with servers located at Cornell University, Dartmouth College, University of California at San Diego, and University of Tromsų in Norway.
Performance measurements have been carried out to evaluate the feasibility of the service and the effectiveness of the optimization we have performed. We also assessed the effectiveness of the defense mechanisms against denial of service attacks by measuring the performance of COCA under simulated denial of service attacks. Please see our paper for details.