Cornell Data Exchange

Michael A. Marsh, Institute for Advanced Computer Studies, University of Maryland

Fred B. Schneider, Department of Computer Science, Cornell University



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.

Return to top

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.

Return to top

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.

Return to top

Publications

Return to top

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 (with links into the documentation):

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.
More advanced utilities include:
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.
A few additional packages provide the key service functionality and low-level functions such as unified exception types.

Return to top

Getting the Source Code

Please see the README file for general installation instructions. CODEX requires GCC 3.0.4 or later and OpenSSL 0.9.7a or later.

The CODEX source code is extensively documented. This documentation is produced directly from the source using doxygen, and can be generated locally for convenient access.

CODEX is released under a BSD-style license, which permits use and modification without restriction so long as proper attribution is included. Because CODEX employs strong cryptography, its export is controlled by the U.S. Export Administration Regulations. Export and reexport are permitted, under License Exception TSU (Technology and Software—Unrestricted) for category ECCN 5D002 (Information Security—"Software") pursuant to EAR section 740.13(e), except to the following countries and their nationals:

All others may download the source code (current version 1.2) here. Note that "reexport" involves transfer of the product from one foreign country (or national) to another, so exporting this code through an intermediate country to a prohibited country is still prohibited by U.S. export regulations.

Previous Releases

Note on version 1.2: The only difference between this version and version 1.1 is that this version should compile with the 4.X series of g++. This required a very hack-ish approach, the result being no backwards compatibility with older compilers. You might also need to update your version of OpenSSL. This was the only way to get things to compile with less than a week's work, and took an entire day to get to this point.

Return to top


The latest version of this page can be found at http://www.umiacs.umd.edu/~mmarsh/CODEX

The CODEX logo is a set of legal texts (codices of regulations) in a locked bookcase (protected from tampering).

Last updated on May 18, 2005. Please send your comments to mmarsh at umiacs dot umd dot edu.