ISW'98 no.23

[23]

Using Independent Corroboration to Achieve Compromise Tolerance*

Clifford Kahn
EMC² Corporation, Hopkinton MA 01748
kahn_clifford@emc.com

When an application cannot observe its world directly, but must decide what is happening based on reports from observers that are vulnerable to compromise, the application can demand independent corroboration. This reduces the effects of such compromises. But the application must have a means of judging the independence of different observers. A model of independent corroboration is required, and we briefly present one. Independent corroboration can contribute to survivability of a number of applications, and we consider several.

Independent corroboration is just one of several approaches to compromise tolerance. For context, this paper first discusses the value of compromise tolerance, the precise meaning of compromise tolerance, and some existing approaches to compromise tolerance. Then the paper presents a model and some applications of independent corroboration.

1. Value of Compromise Tolerance

The first line of defense against penetration attacks is to harden the components so they are difficult to penetrate. Compromise tolerance can offer a strong second line of defense. Even a successful penetration of a component need not necessarily compromise the system as a whole.

A compromise-tolerant system may tolerate compromises not only of components, but also of the system's human operators. In that case, compromise tolerance provides a crucial defense against insider attacks by the operators. For example, an operator may tamper with the operating system of a component host, but the system as a whole may tolerate this.

A compromise-tolerant system may often be able to span administrative boundaries. If an administrative domain should be compromised, the system tolerates it. Thus, administrative domains can cooperate without complete trust.

In sum, compromise tolerance is a second line of defense against penetrations and a first line of defense against insider attacks, and enables cooperative action (to fight intrusions, for example).

2. What Is Compromise Tolerance?

A system is fault tolerant if keeps operating, perhaps at a degraded level, in the presence of faults.¹ Faults can be defined as failures of components of the system.² So we will say that a system is compromise tolerant if it keeps operating, perhaps at a degraded level, in the presence of compromised components or operators.

In ordinary usage, to compromise is:

1. to expose to suspicion, discredit, or mischief; 2. to reveal or expose to an unauthorized person and especially to an enemy; 3. to cause the impairment of.³

In technical usage, compromise includes both accidental and intentional misuse. We will say that a component is compromised if the component is misused or is under the control of an adversary of its owner. Events that can compromise a component include:

penetration
attack by an insider
accidental misuse, such as a system administrator publishing the password file, or such as a user accidentally knocking over a computer

We will say that a person is compromised if he or she is an adversary or is under the control of an adversary.

Compromise tolerance is one of several factors that make up information survivability. Others are:

Resistance to unintended faults (reliability) and to deliberate compromises of components (security)
Fault tolerance
Resilience (recovering quickly or at least predictably after a system failure).

3. Existing Approaches to Compromise Tolerance

We briefly survey several existing ways of achieving compromise tolerance in different applications.

Voting. If a number of agents would observe an event, and an absolute majority of the agents say that the event happened, then one can accept the majority assertion. Compromising or squelching a minority of the agents will not change the vote.

General interactive consistency. When a number of agents must reach agreement, Byzantine agreement and related algorithms let them do so without appointing a single trusted vote counter. These algorithms have no single point of compromise.

Byzantine quorum systems. Quorum systems are a well-known technique for implementing fault-tolerant replicated data. Quorum systems have been extended to environments in which some data repositories can be arbitrarily corrupted.⁴

State machine replication. A service is implemented with multiple identical, deterministic servers. Each is initialized to the same state. A Byzantine protocol ensures that all servers receive the same inputs from clients. Clients conduct a vote among the servers to decide which servers to believe.

Web of trust. If principal A authenticates principal B through a chain of intermediaries, each vouching for the key of the next, then each intermediary is a point of vulnerability. If compromised, any intermediary can pass off an impostor as B. A solution to this is to have redundancy. One can require two non-overlapping chains. More generally, one can require a trust mesh rather than a chain, and have criteria for acceptance of a mesh.⁵

Don't trust, verify. In some applications agent A makes an assertion to agent B, who verifies it before acting on it. If A lies it cannot cause much damage. At worst it causes B to waste resources checking on a false assertion.

Of course, whether B can directly verify the assertion depends on the application. One such application is a system for tracing attacks through the Internet.⁶ If a detector observes an attack, it notifies its topologically neighboring detectors. Each of them studies the packets going by to look for signs of the same attack, and takes action if it sees the signs. If a detector reports a false attack, then its neighbors will not see signs of it and little harm will be done. Thus such a tracing system can tolerate compromised detectors.

Thwarting bad routers. The Internet was originally designed to be fault tolerant, but not compromise tolerant. A malicious router can send false routing messages to its peers and so cause great disruption. There has been work on allowing routers to automatically recognize and quarantine a misbehaving peer.⁷

Separation of duty. An old and widely practiced idea is separation of duty among humans. This limits the damage a compromised human can do. For example, an employee cannot approve his or her own expense report.⁸

Separation of keys. Different parties can hold different parts of a cryptographic key. All of the parties, or k out of n, must jointly sign something for the signature to be cryptographically valid. If fewer than k are compromised, no harm is done.

4. Independent Corroboration

Independent corroboration is a valuable tool when the designer thinks some event Q may occur, and if it does the designer expects evidence of it to be observed and reported by a number of reporters. The number of bona fide reports is expected to be greater than one but far less than all potential reporters. There is some chance that some reporters will be compromised and so will report Q even when Q is false. If Q actually occurs, the reporters reporting it will probably have some measure of independence. Thus, if one is compromised, others may avoid compromise. Under this set of circumstances, independent corroboration can greatly boost the reliability of information.

We lack space to define our model⁹ in full. To simplify, there is a set of agents {a,b,c,...} and a set of influences {i,j,...}. Influences may represent vulnerabilities, institutions with which agents are affiliated, or connections such as marriages. Each influence and each agent has a numeric trust level. For each influence-agent pair there is a numeric weight, measuring how much influence the influence has on the agent. We then map these into a probabilistic model. For each influence there is an independent, Boolean random variable that says whether the influence is friendly or hostile. For each agent there is a similar random variable, but it is not independent. We assume that a friendly agent will not report Q unless Q is true, and that a hostile agent is likely to lie. Now, given a set of reports from agents, we can determine the posterior probability that Q is true.

5. Some Applications

Intrusion detection. It is desirable for automatic tools to recognize the nature and scope of a widespread attack, even one that spans organizations. For example, if a malicious piece of mobile code attacks various sites, analyzers should automatically collaborate to figure this out and to rapidly shut down the attack.¹⁰ If such collaboration is to happen across organizations, then some way of achieving compromise tolerance, such as independent collaboration, is needed.

Distributed sensing. Seismic, meteorological, and other data must be gathered in multiple countries, and often has military significance. If a source may be motivated to falsify data, then independent corroboration may have a place.

Banking. If a bank were compromised, it might steal a great deal of money very fast, from other banks and their customers. An automatic response would be desirable. Other banks' detection systems may observe peculiar transactions and may become suspicious. These other banks would need to pool their observations in order to confirm the existence of an improper pattern of transactions. Since the other banks compete, they can have only partial trust in each other. A bank might abuse the defense system by falsely accusing another. So such an automatic response system would need independent corroboration.

Spam. If many people independently identify an e-mail message as spam, then an automatic system could advise mail servers to mark the message as spam. Each recipient's mailer would handle the spam marking according to user preferences. Or the automatic system could take stronger action, suppressing further transmission and delivery of that message.

Blacklisting a particular message is not always enough. An adversary may send out many variants of the same message, to defeat the anti-spam system. When this happens, the anti-spam system can blacklist the sender, so that all mail from that sender is marked as spam. If a given Internet Service Provider allows spam to be sent from many different accounts, then the anti-spam system can blacklist the ISP.

However, the anti-spam system is subject to abuse. The system must not act until many independent sources identify a message as spam.

6. Conclusion

Independent corroboration is one of a family of techniques for achieving compromise tolerance. The technique applies to applications that take information from sources that may be compromised. There must be some redundancy and independence among the information sources.

In an implementation, a trust engine may automatically judge whether independent corroboration exists. The trust engine must be given information about potentially compromising connections, common vulnerabilities, or other clues about how independent various information sources are from each other.

* This paper describes results of the Methodology for Trust for Network Survivability project. The work was done while the author was at The Open Group Research Institute. See http://www.camb.opengroup.org/RI/secweb/mtns
Effort sponsored by the Defense Advanced Research Projects Agency (DARPA) and Rome Laboratory, Air Force Materiel Command, USAF, under agreement number F30602-97-1-0248. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation hereon.
The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies and endorsements, either expressed or implied, of the Defense Advanced Research Projects Agency (DARPA), Rome Laboratory, or the U.S. Government.

1: A Conceptual Framework for System Fault Tolerance, section 2.2.3. 3/30/95. http://hissa.ncsl.nist.gov/chissa/SEI_Framework/framework_6.html
2: Op. cit., section 3.2.1
3: Merriam-Webster WWWWebster Dictionary, http://www.m-w.com/cgi-bin/dictionary
4: D. Malkhi and M. Reiter. Byzantine quorum systems. In Proc. 29th ACM Symposium on Theory of Computing, pages 569-578, May 1997.
5: M. K. Reiter and S. G. Stubblebine. Toward acceptable metrics of authentication. In Proc. 1997 IEEE Symposium on Security and Privacy, pages 10-20, May 1997.
6: Dynamic Cooperating Boundary Controllers Program at Boeing Research
7: S. Cheung and K. Levitt. Protecting Routing Infrastructures from Denial of Service Using Cooperative Intrusion Detection. In Proc. New Security Paradigms Workshop, 1997.
8: R. Simon and M. Zurko. Separation of Duty in Role-Based Environments. In Proc. Computer Security Foundations Workshop, September 1996.
9: C. Kahn. Tolerating Penetrations and Insider Attacks by Requiring Independent Corroboration. To appear in Proc. 1998 New Security Paradigms Workshop, September 1998.
10: Stopping mobile adversaries is a goal of the Methodology for Trust for Network Survivability (MTNS) project, http://www.camb.opengroup.org/RI/secweb/mtns

Back to the Table of Contents

[23]