SINTRA - Distributing Trust on the Internet
SINTRA, the Secure intrusion-tolerant replication
architecture, provides synchronization and coordination of a distributed
system in a secure and fault-tolerant way.
Replication is a proven way to enhance the availability of a component or a
subsystem. SINTRA provides replication at the level of services, by
distributing them on physically separate nodes linked by a wide-area
network. It is targeted at secure directories, file systems, and trusted
security services. The protocols of SINTRA are secure and tolerate
malicious insiders, providing a correct service whenever a sufficient majority
of the machines is correct.
SINTRA uses the state-machine replication approach and provides several
coordination protocols like agreement and atomic broadcast.
Such protocols are well-known in environments with non-malicious faults, i.e.,
where crashes and network packet losses occur. The novelty of SINTRA is
to also tolerate malicious actions originating within the system,
such as nodes infected by viruses.
Requests to a SINTRA service are processed by all nodes in a replicated way
and clients infer the result of an operation from the majority of the answers
they receive. SINTRA ensures that all nodes process the same sequence of
requests, which keeps their state synchronized at all times, and that clients
can infer the correct answer, even though a certain number of nodes may be
faulty.
SINTRA is targeted at services distributed over the Internet, like Grid
computing; it uses an asynchronous system model, which makes it by design
resilient against network outages or denial-of-service attacks. A number of
novel protocols for agreement and fault-tolerant broadcast are implemented in
SITNRA and have been demonstrated on the Internet for the first time. In
particular, SINTRA provides a practical protocol for randomized
Byzantine agreement and a new protocol for secure atomic
broadcast. Cryptography, in particular threshold
cryptography, plays an important role in those protocols.
Some of this work has been part of the EU-funded research project
MAFTIA: Malicious- and Accidental-Fault Tolerance for Internet
Applications, from Jan. 2000 to Feb. 2003.
More information
SINTRA is documented in the papers listed below:
If you desire more information,
please contact us!
Publications
A correctly working Domain Name System (DNS) is essential for the
Internet. Due to its significance and because of deficiencies in its current
design, the DNS is vulnerable to a wide range of attacks. This paper presents
the design and implementation of a secure distributed name service. The
service is able provide fault tolerance and security even in the presence of a
fraction of corrupted servers, avoiding any single point of failure. It
further solves the problem of storing zone secrets online in a way that does
not leak them to a corrupted server, while still supporting secure dynamic
updates. The service uses state-machine replication and threshold
cryptography. Results are presented from experiments performed using a
prototype implementation on the Internet in realistic setups. The results show
that the design achieves the required assurances while servicing most frequent
requests in reasonable time.
-
Christian Cachin and Asad Samar.
Secure distributed DNS.
Proceedings of DSN-2004, Firenze (IT), June 2004.
(PDF)
Modeling complexity in secure distributed computing
This position paper for the Bertinoro Workshop on Future Directions in
Distributed Computing describes the need for refining the traditional
system model of distributed computing in order to model cryptographic
protocols. In order to deal with the computational limitations of an
adversary, a new approach based on complexity theory and modern
cryptography is proposed. The approach has been developed for describing
our replication protocols.
-
Christian Cachin.
Modeling complexity in secure distributed computing.
International Workshop on Future Directions in Distributed Computing (FuDiCo),
Bertinoro, Italy, June 2002.
(PDF)
Verifiable secret sharing is an important primitive in distributed
cryptography. With the growing interest in the deployment of threshold
cryptosystems in practice, the traditional assumption of a synchronous network
has to be reconsidered and generalized to an asynchronous model. This paper
proposes the first practical verifiable secret sharing protocol for
asynchronous networks. The protocol creates a discrete logarithm-based sharing
and uses only a quadratic number of messages in the number of participating
servers. It yields the first asynchronous Byzantine agreement protocol in the
standard model whose efficiency makes it suitable for use in
practice. Proactive cryptosystems are another important application of
verifiable secret sharing. The second part of this paper introduces proactive
cryptosystems in asynchronous networks and presents an efficient protocol for
refreshing the shares of a secret key for discrete logarithm-based sharings.
-
Christian Cachin, Klaus Kursawe, Anna Lysyanskaya, and Reto Strobl.
Asynchronous verifiable secret sharing and proactive cryptosystems.
In Proc. 9th ACM Conference on Computer and Communications Security
(CCS), 2002.
(Extended version (PDF))
A report about the implementation of the SINTRA prototype, which
provides fault-tolerant synchronization of a distributed system in the
presence of malicious attacks. The protocols in SINTRA provide reliable
broadcast, atomic broadcast, and agreement in the presence of malicious
faults, among others; they exploit novel techniques based on public-key
cryptography. SINTRA uses TCP/IP for point-to-point communication and is
written in Java.
Contains performance measurements of SINTRA on the Internet, with nodes at IBM
labs in Zurich, New York (Watson), Tokyo, and California (Almaden). The
latency of an atomic broadcast with 1024-bit public keys and seven servers is
about three seconds over the Internet, but we expect to reduce this time
to under one second with optimized protocols.
-
Christian Cachin and Jonathan A. Poritz.
Secure intrusion-tolerant replication on the Internet.
In Proc. Intl. conference on dependable systems and networks
(DSN-2002), Washington DC, USA, June 2002.
Extended version (PDF).
This paper contains an in-depth discussion and motivation of our approach to
secure service replication, with respect to previous fault-tolerant protocols
used for similar tasks. It also discusses novel general failure patterns and
corresponding protocols, that allow for realistic modeling of real-world trust
assumptions, beyond (weighted) threshold models.
-
Christian Cachin.
Distributing trust on the Internet.
In Proc. Intl. conference on dependable systems and networks
(DSN-2001), Gothenborg, Sweden, June 2001.
Extended version (PDF)
available from
http://www.zurich.ibm.com/~cca/.
This work describes how to build reliable broadcast protocols in an
asynchronous network with Byzantine failures. It presents a new formal model
based on modern cryptography, and a new protocol for atomic broadcast based on
multi-valued Byzantine agreement, among other things.
-
Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and
Efficient Asynchronous Broadcast Protocols. In Joe Kilian, editor,
Advances in Cryptology - Crypto 2001, Lecture
Notes in Computer Science, vol. 2139, Springer-Verlag, 2001.
Preliminary version available as Research Report RZ 3317,
IBM Research, January 2001; full version available
available from Cryptology ePrint
Archive, Report 2001/006.
An important prerequisite for such a service is Byzantine agreement. We have
designed a new protocol for Byzantine agreement that works in a completely
asynchronous network and makes use of cryptography, specifically of threshold
signatures and coin-tossing protocols. These cryptographic protocols have
practical and provably secure implementations in the ``random oracle'' model.
-
Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in
Constantinople: Practical asynchronous Byzantine agreement using cryptography.
In Proc. 19th ACM Symposium on Principles of Distributed Computing (PODC
2000), Portland, OR, pages 123-132, July 2000. Full version available
from Cryptology ePrint Archive, Report 2000/034.
Another important primitive for these protocols are efficient
threshold-cryptography protocols. This work presents a practical threshold
signature scheme based RSA.
-
Victor Shoup. Pratical threshold signatures. In Bart Preneel, editor,
Advances in Cryptology - EUROCRYPT 2000, number 1807 in Lecture
Notes in Computer Science, pages 207-220. Springer-Verlag, May 2000.
Distributed key generation
The basis of many distributed protocols are secure protocols to jointly generate
a public key and shares of the corresponding secret key.
This work presents a protocol that allows one the distributively generate shares
of primes and safe primes. This allows one for instance to jointly generate RSA keys.
-
Joy Algesheimer, Jan Camenisch, and Victor Shoup.
Efficient computation modulo a shared secret with application to the generation
of shared safe-prime products.
In Moti Yung, editor, Advances in Cryptology - CRYPTO 2002,
Lecture Notes in Computer Science. Springer Verlag, 2002.
(PDF)
Links
