[an error occurred while processing this directive]

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!


Secure distributed DNS

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)

Asynchronous verifiable secret sharing and proactive cryptosystems

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))

Secure intrusion-tolerant replication on the Internet (SINTRA)

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).

Distributing trust on the Internet

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/.

Secure asynchronous broadcast protocols

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.

Asynchronous Byzantine agreement

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.

Threshold signatures

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)


[an error occurred while processing this directive]