Cornell Data Exchange
When designing secure applications, it is not uncommon to
assume some out-of-band mechanism for distributing keys or
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
It employs the RSA and ElGamal encryption schemes, as well as
techniques such as threshold cryptography and proactive secret
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
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
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.
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
For CODEX, as for
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
Links are, however, fair in the sense that a message sent
an infinite number of times is received an infinite number
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.
- 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
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
Threshold cryptography allows servers in CODEX to decrypt
ciphertexts and sign messages using only the shares of the
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
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.
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:
More advanced utilities include:
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
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.
Specializes the sockets in CODEX_Quorum for OpenSSL's implementation
of SSL and TLS.
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
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
A few other classes and functions are also defined, such as
a secure hash function base class and SHA-1 subclass.
A few additional packages provide the key service functionality
and low-level functions such as unified exception types.
Verifiable secret sharing package.
An easily extensible secret sharing architecture is defined, with
combinatoric secret sharing and Feldman's VSS scheme as specific
This package is heavily templated, with the types of the secret
sharing and verification schemes determining the behavior of
shares and sets of shares.
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.
Asynchronous proactive secret sharing package.
This implements Lidong Zhou's APSS protocol in the CODEX
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
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