0.1. ABSTRACT 1

This document is a draft of Raph Levien’s Ph.D. thesis in compact formatting, to minimize page count.

0.1 Abstract

This dissertation characterizes the space of trust metrics, under both the scalar assumption where each assertion is evaluated independently, and the group assumption where a group of assertions are evaluated in tandem. We present a quantitative framework for evaluating the attack resistance of trust metrics, and give examples of trust metrics that are within a small factor of optimum compared to theoretical upper bounds. We discuss experiences with a real-world deployment of a group trust metric, the Advogato website. Finally, we explore possible applications of attack resistant trust metrics, including using it as to build a distributed name server, verifying metadata in peer-to-peer networks such as music sharing systems, and a proposal for highly spam resistant e-mail delivery.

Chapter 1

Introduction

In today’s world of open, decentralized networks, the question of trust is becoming increasingly relevant. Most existing Internet protocols implement a naive policy of providing a relatively limited set of services, but trusting all users with them. Given that a significant fraction of Internet users are not trustworthy, the inevitable result is spam, denial of service attacks, cracking, and a host of other ills far too familiar to legitimate Internet users.

A number of approaches have been developed and deployed over the years, with varying degrees of success. The most basic is the model of passwordprotected accounts. This mechanism is almost universally deployed, but suffers from serious limitations, including the need for servers to manage the accounts, the need for users to keep track of a large number of passwords, and the relative lack of security provided by this model. Thus, there has been a sustained interest in more sophisticated models.

One such approach is the Public Key Infrastructure, or PKI [?]. Briefly, a PKI consists of various Certification Authorities (or CA’s) that issue certificates asserting a binding between a name and a public key. PKI’s suffer from two fundamental problems: the lack of useful meaning in the PKI’s underlying namespace, and the question of which CA to trust. Actual implementations of CA’s have proved themselves not worthy of absolute trust. Further, as the number of CA’s deployed scales up, the risk of any one of them being compromised scales accordingly. In part because of these two problems, PKI’s have met with limited success at best.

Spurred on by these limitations, much recent attention has been focussed on the explicit encoding and evaluation of trust relationships. A pioneering work in this area is the PolicyMaker framework of Matt Blaze[?]. A particularly interesting branch of this work is the concept of trust metrics, which are the primary focus of this thesis.

Trust metrics are based on the principle of local encoding of trust relationships, but granting trust on a global scale. These assumptions closely parallel the philosophy of peer to peer networks[?].

While the literature is rich with design proposals for trust metrics, there has been relatively little analysis of how well they work in practice. In Chapter 2, we show that, under assumptions similar to the Internet, the entire category of “scalar” trust metrics fails to resist easily-mounted attacks. Attacks against these poor trust metrics dot the literature[?], and have been used to argue (incorrectly) that a centralized identity service is needed[?].

While the outlook for scalar trust metrics is indeed bleak, we propose a new class, which we call group trust metrics, so called both because the trust metric is very well suited to evaluating membership in a group, and because this evaluation is done over the entire group of nodes, rather than individually for each node. While the group trust metric cannot prevent individual hostile nodes from being accepted as group members, it can place strict bounds on the number of hostile nodes so accepted.

I built a community website for free software developers, called Advogato, that uses this group trust metric to determine who belongs to the community. Acceptance by the trust metric confers privileges to post articles and comments, and to edit project information. At the time of this writing, the site has been in operation for about 18 months, and has built a trust graph of over 1000 active nodes. Advogato is notable for the extremely low level of trolls, spam, and other forms of abuse common to bulletin board type systems, thus providing strong anecdotal evidence that the trust metric is effective. Advogato is described in more detail in Chapter 4.

One interesting application of trust metrics is secure registration and lookup of public keys bound to names, essentially the same problem addressed by Public Key Infrastructures (PKI). The attack resistant properties of the trust metric avoid the single point of vulnerability common to most PKI designs. We present a detailed design for such an attack-resistant name service in Chapter 5. The desire to build a “better PKI” was the original motivation behind the work of this thesis.

Because the group trust metric is effective in resisting attack, it has many other interesting applications. One such is an attack-resistant system for distributing metadata, for example opinions about songs. Attack resistance can be useful for ensuring high quality of the metadata, but becomes particularly important when there are financial implications to the metadata system, for example to identify recipients of voluntary donations to artists who post their music to the Net. We propose a design for an attack resistant metadata system in Chapter 6. This design combines ideas from both the Advogato group trust metric and the PageRank algorithm used in Google.

Another intriguing application for group trust metrics is to provide a spam resistant infrastructure for e-mail. Spam is a huge problem, causing lots of wasted time for many, and most e-mail users feel hopeless in the face of it. We present a partial design for a communications infrastructure resistant to spam, yet highly permeable to legitimate email. This design uses a capacity constrained flow network where “stamps” are the commodity of flow. Rather than explicitly computing a flow in the network, the flow results from local activity. When capacity is exhausted, e-mail is no longer deliverable. This design has many appealing properties, but several aspects remain as open problems, particularly scaling. Chapter 7 presents this design and discusses some open issues.

6 CHAPTER 1. INTRODUCTION

Chapter 2

Trust Metrics

In this chapter, we review the literature of trust metrics, present a quantitative framework for analyzing the attack resistance of trust metrics. Finally, we prove tight upper and lower bounds on the attack resistance of trust metrics given the usual scalar assumptions.

2.1 The simplest trust metric

In this section, we present the simplest possible trust metric, which forms the basis of other trust metrics in the literature.

There are three inputs to this trust metric: a directed graph, a designated “seed” node indicating the root of trust, and a “target” node. We wish to determine whether the target node is trustworthy.

Each edge from s to t in the graph indicates that s believes that t is trustworthy. The simplest possible trust metric evaluates whether t is reachable from s. If not, there is no reason to believe that t is trustworthy, given the data available.

In a cryptographic implementation, each node corresponds to a public key, and each edge from s to t corresponds to a digitally signed certificate. In the usual terminology, s is the issuer, t is the subject. The certificate itself is some string identifying t, along with a digital signature of this string generated by s.

The simplest trust metric is also the weakest. If an attacker is able to generate an edge from any node reachable from the seed to a node under his control, then he can cause arbitrary nodes to be accepted. As the size of the reachable subgraph increases, the risk of any such attack increases as well. Thus, the primary focus in the literature is to present stronger trust metrics that (hopefully) resist attacks better, while still accepting most nodes that deserve trust.

Section 2.2, discusses a sampling of trust metrics previously published. Section 2.3, presents a quantitative notion of “attack resistance.”

2.2 Survey of the literature

All trust metrics include the three inputs described above: the trust graph, the seed node, or trust root, and the target. Some trust metrics add more detail to these inputs. Trust edges may contain some conditions or restrictions, for example that t is himself trustworthy, but cannot be trusted to vouch for other nodes. In addition, the target may be a richer assertion than merely whether a certain node is trustworthy. For example, edges may additionally identify a maximum dollar value, and the target may be an assertion that the target node can be trusted with a transaction of some dollar value.

Finally, there may be additional policies to be enforced by the trust metric, or parameters supplied. Often, these parameters control the overall strictness or tolerance of the trust metric.

The most general form of “trust management” system is represented by PolicyMaker[?], as certificates and policies can represent arbitrary computations in Turing-complete language. Applications of PolicyMaker tend to focus on the language of assertions rather than trust computations over the graph, but the fully general nature of the system allows the the latter to be implemented.

Monotonicity assumption: consistent with supplicant presenting signed certificates to verifier. Relationship to scaling: verifier only has access to small subset of entire trust graph.

Another relatively simple trust metric is similar to the simplest one, with the additional constraint that path lengths are bounded by some parameter k. Thus, all nodes within a distance of k edges from the seed are accepted. A variation of this trust metric is used in X.509 systems.

Perhaps the earliest published system resembling a modern trust metric is the Beth, Borcherding, and Klein[?]. This system contains a set of elaborate inference rules for deriving a “trustworthiness” value between 0 and 1, using both “direct trust” and “recommendation trust” relationships encoded on edges. However, further work by Reiter and Stubblebine[?] showed this trust metric to be no more secure than the simple reachability criterion described above. Note that the BBK trust metric is not monotonic.

A still earlier system is described by Tarah and Huitema[?], who suggest evaluating both certificates and “certificate paths.” They suggest several possible simple trust metrics, including the length of the certification path and the minimum of involved trust values along the path. However, because it evaluates only paths, rather than general graphs.

Reiter and Stubblebine[?] presented the first trust metric with the ability to resist nontrivial attacks. Briefly, this trust metric counts the number of nodeindependent paths of bounded length from the seed to the target. Thus, both the path length and the threshold for the minimum number of such paths are tunable parameters of the metric. A simple characterization of its attack resistance follows easily: an attacker must add “bad” edges to nodes under his own control to at least as many nodes as the threshold for the number of independent paths. Even though evaluation of this trust metric is an NP-complete problem, the experimental PathServer implementation seems to perform reasonably well in practice.

Maurer presented an intriguing trust metric based on randomized experiments[?]. Very briefly, each edge in the network has an associated probability. The result of the trust metric is the probability that the target is reachable from the seed in a subgraph of the original graph where each node is present with the probability given in the original graph.

Both implementation and analysis of the Maurer trust metric are challenging. However, we present an analysis below (Section 2.6) suggesting that fails to resist any non-trivial attack. To do so, we will first need to prepare a framework for quantitatively evaluating the attack resistance of a trust metric.

2.3 Framework for analysis

What does it mean to be attack resistant?

Given an attack of a certain cost, how many bad assertions will be accepted? How to quantify cost of attack? Node attack: number of nodes for which attacker can make arbitrary certs.

Corresponds to stealing the public key of victim.

Edge attack: number of certs. Corresponds to fooling the victim once.

Protection against node attack is a stronger property than protection against edge attack. Attack of a single node can correspond to an arbitrary number of edges.

Another factor in trust metric: how many certs are needed? At simplest, indegree of target node.

Flavors of attack: random victims, chosen victims.

2.4 Analysis: upper bounds

Strict upper bounds on effectiveness of trust metric. For node attack, if n nodes are attacked, entire system falls, where n is minimum indegree of target node.

Proof: attacker chooses target that is accepted (with minimum indegree), and chooses its predecessors as victims. Since indegree is n, attack is n nodes. Removing the original target, the graph is identical to the one in which the original target is accepted, so the trust metric can’t distinguish.

For edge attack, if n^{2} nodes are attacked, entire system fails. Choose target as above, then spoof inedges of predecessors of target.

2.5 Analysis: lower bounds

This section analyzes existing trust metrics.

Present simple flow-based metrics, and prove (using min-cut) that they almost exactly meet the upper bounds given above.

10 CHAPTER 2. TRUST METRICS

2.6 Analysis of Maurer’s trust metric

Analysis of Maurer: follow [?].