Cornell Data Exchange

Overview

When designing secure applications, it is not uncommon to assume some out-of-band mechanism for distributing keys or other secrets. Other applications without inherent security features could, given a key distribution system, employ symmetric key encryption to add a cryptographic access control mechanism. These applications motivated the development of the CODEX (the Cornell Data Exchange) key distribution system. CODEX is designed for applications with a moderate number of clients (tens or hundreds) requesting keys that change often but not continuously (on the scale of minutes to hours).

CODEX is an extension of the ideas implemented in COCA. It employs the RSA and ElGamal encryption schemes, as well as techniques such as threshold cryptography and proactive secret sharing. The COCA page contains a number of useful links for these topics.

Part of the development of CODEX was the creation of a general-purpose toolkit for the various primitives needed by the system. These primitives are discussed in the Implementation section, and the full source code is also available.

Since a random search on Google revealed that this project is now listed on Freshmeat, it is worth mentioning a few significant aspects of the implementation. First, the code is research-quality, not production-quality. The system employs spin-waiting, which can substantially impact the host on which a server runs. For an effective proactive-recovery system, servers must periodically be placed into a known-good state. This typically involves rebooting from clean (and, if necessary, patched) media and installing new server-specific public/private key pairs, as well as the proactive secret sharing procedure included in the implementation. If, at this point, you still trust the implementation and your operating system enough to use CODEX, be advised that there is currently no credentials mechanism in place. The existing policy object always accepts any credentials object as valid. Since the entire system depends on enforcing policies for access control, if you want to deploy a CODEX system (as opposed to using the libraries to build your own system) you must implement an actual policy/credentials mechanism.

Weak System Model

Any system model includes basic assumptions, and when these assumptions are violated the behavior of the system becomes ill-defined. When the system provides security guarantees, violating the assumptions negates all of these guarantees. Consequently, we prefer models which make as few assumptions as possible. For CODEX, as for COCA, the assumptions are:

Byzantine Failures

Participants may be corrupted by an adversary, and when corrupted may deviate arbitrarily from the protocols. This includes sending incorrect messages, disclosing secrets, or participating in any other attacks. We limit the adversary to compromising no more than 1/3 of all participating servers in any given time interval (defined as the time between executions of the recovery procedure).

Active Link Attacks

Adversaries can read, modify, insert, or delete messages on network links. Links are, however, fair in the sense that a message sent an infinite number of times is received an infinite number of times.

Asynchrony

No assumptions are made about the speed at which processors run or the latency of message delivery. Processing and message delivery times might be unbounded, and any assumption otherwise leaves the system potentially vulnerable to a number of denial-of-service attacks.

Key Features of CODEX

Byzantine Quorum Replication for Fault Tolerance

Critical online systems must be available to clients, and replication provides this availability by eliminating a single point of failure. Replication using Lamport's state machine approach provides a high degree of consistency but requires many rounds of communication between participants in order to process a single operation. In addition, when failures might be Byzantine and the system is asynchronous only probabilistic progress can be made. Byzantine quorums provide a weaker notion of consistency which requires much less communication, often a single round for an operation (plus an additional round if the participants themselves must certify correct processing). In many cases this level of consistency is sufficient.

Threshold Cryptography

A CODEX system has service-wide private keys (one for RSA and one for ElGamal) which can be used to (among other things) issue statements on behalf of the system. These private keys (individual servers have their own private keys) are split among the servers using secret sharing so that compromise of one server does not disclose the keys to an adversary. Threshold cryptography allows servers in CODEX to decrypt ciphertexts and sign messages using only the shares of the private keys. When private key operations are done in this way the shared private keys are never disclosed to any server or other party.

Proactive Recovery (and Proactive Secret Sharing)

Rather than rely on intrusion detection to determine whether a server has been compromised, the entire system can undergo a recovery procedure to return all servers to a known-safe state. This involves rebooting servers from clean media, generating new server public/private key pairs, and using proactive secret sharing to generate new and independent shares of all split secrets.

At-Most-Once Semantics

CODEX avoids inconsistencies in key values by enforcing at-most-once semantics for creating and writing keys. If a key name is successfully bound to an owner and set of access policies, that binding will be unique. Similarly, if a key value is successfully written to a key name, no other value can be written to that name. It is possible for two or more requests to perform the same operation on a given key name to interfere in such a way that neither can succeed, however. For writing a key value, this problem can be eliminated by only delegating write permissions to one client. For creating a key name, owner-based namespacing can be added so that two clients cannot issue conflicting requests.

Implementation of CODEX

CODEX is implemented as approximately 42K lines of C++ code. Most of this comprises a set of general utility packages that provide useful primitives. The basic packages are:

CODEX_Events

Single-threaded event-based concurrency package. Abstract event and activity (handler) classes are defined, as are a few useful subclasses. Events of different types can be queued together, and type rules ensure that an event will be handled by an appropriate activity.

CODEX_Quorum

Networking package. Sockets and servers (local and remote) are defined, and a mechanism is provided for managing quorums of servers. The specifics of networking are abstracted away (though to a certain extent they remain available). This package assumes POSIX-compliant sockets, but it would be relatively straight-forward to add more OS-specific versions.

CODEX_SSL

Specializes the sockets in CODEX_Quorum for OpenSSL's implementation of SSL and TLS.

CODEX_ASN1

Encapsulation of ASN.1 serializable structures. In addition to self-serializing classes corresponding to most of the basic ASN.1 types, an abstract base class from which all serializable classes are derived provides a consistent mechanism for creating new serializable classes. This package is used extensively by most of the higher-level packages.

CODEX_Ciphers

Cryptosystem implementations. The RSA and ElGamal cryptosystems are implemented, though not in the most efficient ways possible. A variant of RSA is also implemented, in which encryption involves selecting a random value r which is encrypted in the standard RSA fashion and the message is XORed with a hash value H(r). A few other classes and functions are also defined, such as a secure hash function base class and SHA-1 subclass.

CODEX_VSS

Verifiable secret sharing package. An easily extensible secret sharing architecture is defined, with combinatoric secret sharing and Feldman's VSS scheme as specific instances. This package is heavily templated, with the types of the secret sharing and verification schemes determining the behavior of shares and sets of shares.

CODEX_ThresholdCrypto

Threshold cryptography package. This is built on top of CODEX_VSS, and performs RSA and ElGamal private-key operations using shares of the keys. For ElGamal threshold decryption an additional proof class is defined that demonstrates correct computation.

CODEX_APSS

Asynchronous proactive secret sharing package. This implements Lidong Zhou's APSS protocol in the CODEX framework. Some of the code is specific to the CODEX_Server package which controls a general quorum member (and is not connected to the functionality of the key distribution service). CODEX_APSS is built on top of CODEX_VSS, and is capable of managing share refreshing for an arbitrary number of shared secrets. Currently, APSS is designed to use combinatoric secret sharing. Modifications might be needed in order to accomodate other schemes, such as Shamir's polynomial secret sharing, though these changes could likely be isolated to the secret sharing implementations.