=Paper=
{{Paper
|id=Vol-190/paper-1
|storemode=property
|title=Konfidi: Trust Networks Using PGP and RDF
|pdfUrl=https://ceur-ws.org/Vol-190/paper01.pdf
|volume=Vol-190
|authors=David Brondsema and Andrew Schamp
|dblpUrl=https://dblp.org/rec/conf/mtw/BrondsemaS06
}}
==Konfidi: Trust Networks Using PGP and RDF==
https://ceur-ws.org/Vol-190/paper01.pdf
Konfidi:∗ Trust Networks Using PGP and RDF
†
David Brondsema Andrew Schamp
dave@brondsema.net schamp@gmail.com
ABSTRACT rating system for reputation within certain domains, such as eBay
Trust networks have great potential for improving the effectiveness online auctions, may be of some limited use. However, unless there
of email filtering and many other processes concerned with the va- is a system to verify the raters, they may also be susceptible to ma-
lidity of identity and content. To explore this potential, we propose licious users who manipulate ratings. Even if such systems can be
the Konfidi system. Konfidi uses PGP connections to determine au- guarded against such attacks, one should not have to base their trust
thenticity, and topical trust connections described in RDF to com- in another person on ratings given by people that they neither know
pute inferred trust values. Between yourself and some person X nor trust.
whom you do not know, Konfidi works to find a path of crypto- In this paper, we present a system that combines the a trust net-
graphic PGP signatures to assure the identity of X, and estimates a work with the PGP web-of-trust. We describe some difficulties in
trust rating by an algorithm that operates along the trust paths that integrating the networks, and analyze various strategies for over-
connect you to X. The trust paths are formed from public person- coming them. We then describe our structure for representing trust
to-person trust ratings that are maintained by those individuals. We data, and our methods for making trust inferences on this data. Fi-
discuss the design of the network and system architecture and the nally, we discuss the our proof-of-concept software for putting this
current state of implementation. trust to use.
Keywords 2. RELATED WORK
Semantic web, trust network, FOAF, RDF, OpenPGP, PGP, GPG, We have incorporated into our project a number of existing tech-
reputation, propagation, distributed, inference, delegation, social nologies designed to serve various purposes. We introduce them
network here, and explain later in the paper how we have integrated them.
We also include a discussion of related academic research on the
relevant topics.
1. INTRODUCTION
As internet-based communication grows, it has experienced rapid 2.1 Representing Trust Relationships
growth of unscrupulous users taking advantage of the system to There seems to be a general lack of psychological research on
send spam and propagating viruses to users. This gives rise to two ways of representing trust relationships between individuals and
questions: How can one be sure that a message really comes from procedures for inferring unspecified trust values. We found no
the indicated sender? How can one be sure that the sender can be recommendations for a particular scheme for modeling trust re-
trusted to send good messages? lationships or networks mathematically. Most work on this topic
There have been a number of attempts to answer either one ques- in the fields of mathematics and computer science adopts an arbi-
tion or the other. The OpenPGP encryption system [IETF, 1998] trary model appropriate to the algorithm under consideration. Guha
(hereafter PGP) has developed a web-of-trust which can help pro- points out [Guha et al., 2004] that there are compelling reasons for
vide verification of an individual’s identity; however, it does not a trust representation scheme to express explicit distrust as well as
allow the expression of any additional information about that in- trust.
dividual’s trustworthiness on matters other than personal identifi-
cation. As for the second question, one answer that is growing in 2.2 Trust Networks and Inferences
popularity is that of creating a network of trust between individuals There are several different propagation strategies for weighted,
who know one another and have good reason to trust their estima- directed graphs [Richardson et al., 2003] [Abdul-Rahman & Hailes,
tions of others. However, these systems can be subject to problems; 1999] [Guha et al., 2004]. For the most part, however, the work is
suppose someone impersonating a trusted party provides incorrect concerned with mathematical description of the networks and their
data boosting the reputation of an untrustworthy party. A simple operations, and do not have much in the way of practical applica-
∗Konfidi is the Esperanto term for trust. A universal concept in a tion. While these issues are of interest and relevance, they concern
universal language seemed appropriate for what we hope will be- only the subsystem and do not discuss the design of a larger infras-
come a universal system. tructure.
†Both authors did the majority of this work as students at Calvin Jennifer Golbeck, at the University of Maryland, is doing work
College. on trust systems [Golbeck, 2005a] that is similar to our work on
this project. Like us, she uses a Resource Description Framework
Copyright is held by the author/owner(s).
WWW2006, May 22–26, 2006, Edinburgh, UK. (RDF) [W3C, 2005a] schema with the Friend of a Friend (FOAF)
. [Brickley, 2005a] RDF schema to represent trust relationships and
1
a rating system1 . She has created TrustMail [Golbeck, 2005b], a phishing by assuring authenticity through cryptographic data in
modified email client that uses her trust network. She is more con- DNS records. These approaches limit their applicability to domain-
cerned with an academic approach than a pragmatic one, since this related data such as email or webpages and do not address any is-
field is still growing rapidly and she emphasizes her research on sues of trust, since DNS records must be assumed to be authentic.
other applications and implications of semantic social networks. Also, the granularity of the system is too coarse: cryptographic
Golbeck suggests an important distinction between belief in state- keys are normally created on a per-domain, not per-address, basis.
ments and trust in people [Golbeck & Hendler, 2004]. While net-
works of both kinds can be created, the latter are usually smaller 2.4.1 Trust Inference Using Headers
and more connected. Golbeck argues that in a combined network of Boykin and Roychowdhury discuss ways to infer a relationship
trust in people and of belief in statements, a path composed of trust based on existing data [Boykin & Roychowdhury, 2004]. They
edges and terminating with a belief edge is equivalent to, and on suggest scanning the From:, To: and Cc: headers and building a
average smaller than, one composed entirely of belief edges. Thus, whitelisting database based on relationships indicated by the recip-
a trust network comprising mostly trust edges allows for simpler ients. This seems to work fairly well, but there is often not enough
traversal. data to make the spam/not-spam decision because it is based only
on the user’s own previously received messages. They clearly state
2.3 The Semantic Web a cryptographic solution would be ideal to verify the sender’s iden-
In addition to Golbeck, a number of others have explored the tity.
usefulness and implications of expressing trust relationships in the
Semantic Web. 2.4.2 Trust Inference Using PGP
The FOAF project is an RDF vocabulary that can be used to rep- One approach would be for a Mail User Agent (MUA) to find a
resent personal data and interpersonal relationships for the Seman- path from any PGP-signed email’s sender to the recipient.3 There
tic Web. Users create RDF files describing Person2 objects which are some MUA plugins, such as Enigmail [Brunschwig & Sara-
can specify name, email address, and so on, but more importantly, vanan, 2005], that implement some of this. Enigmail uses PGP to
they can express relationships between Person objects. There are sign emails and validate any emails that are received with a PGP
a number of tools in development for processing FOAF data and signature, fetching keys from the keyserver when necessary. If
traversing references between FOAF RDF files. These tools can there is a short enough path of signatures from the recipient to the
aggregate information because RDF often uses uniform resource sender, the signature is considered “trusted”. It does not fetch keys
indicators (URIs) to identify each individual object. in an attempt to find such a path; you must already have the keys lo-
Dan Brickley has made a practical attempt to investigate the use cally that form the path. Fetching all the keys along the path would
of FOAF, particularly the mbox sha1 property, to automatically be necessary, but is problematic for reasons explained later.
generate email whitelists. By hashing the sender’s email address Using this approach to filter spam would require that most users
using SHA1, privacy is protected (and the address cannot be gath- digitally sign email messages, and it depends on users to be aware
ered by spiders), and so users can share whitelists of mbox sha1s of known spammers and avoid signing their keys. However, the
of addresses they know not to send spam. Then for all incoming recommended PGP keysigning practices require only the careful
mail, the sender’s address is hashed and the whitelist searched for verification of the key-holder’s identity, and a signed key does not
the resulting value, and then is filtered accordingly. This use of entail anything about trustworthiness in other areas. Furthermore,
FOAF is promising, but since it is decentralized, it is difficult for if the identification requirements for keysigning are met, even by a
updates to propagate [Brickley, 2005b]. No effort is taken in this spammer, it would be unfair to refrain from signing that spammer’s
project to verify the sender’s identity. key4 . Whether a user should be trusted to send good email, and
not spam, is information over and above that expressed in the PGP
2.4 Email Filtering web-of-trust itself, so another system would be required to encode
Filtering email to reduce unsolicited email has received consid- such information.
erable attention in many areas. Domain-level solutions, such as Another serious flaw in this approach is this: because key sig-
Sender Policy Framework (SPF) [Wong, 2004] and DomainKeys natures are listed with the signed key and not the signing key, the
Identified Mail (DKIM) [DKIM, 2005], are designed mostly to pre- MUA must search for a path between users that can only be con-
vent phishing (emails with a forged From: address to trick users structed from the sender to the recipient. Since these paths would
into divulging personal information) and also assume that a do- have to be built starting from the sender, a spammer or other ma-
main’s administrator can control and monitor all its user’s activi- licious user could generate a large number of fake keys that are
ties. Greylisting and blacklisting often have too many false posi- inter-signed, and then use these keys to sign their sender’s key. This
tives and false negatives. User-level filtering, which Konfidi does could inundate the client’s search domain making such a search
in the context of email, is not very common. Challenge-response impractical. A deluge of false information would put undue strain
mechanisms to build a whitelist are tedious for the sender and re- on the clients and keyserver infrastructure, and would amount to
ceiver and do not validate authenticity. Content-level testing is the a denial-of-service, of sorts. Existing keyserver infrastructure pro-
most common, but Bayesian filtering and other header checks are vides no effecient way to tell which keys a particular key has signed,
reactionary and must be updated often, and are becoming less ef- which would allow searches in the reverse direction that are not
fective as spammers create emails that look ever more legitimate, susceptible to this misuse.
attempting either to fool the filter or to distort the probabilities.
There has been some work to bring authentication to email through 2.5 PGP Web of Trust
the domain-level efforts of SPF and DKIM. Their goal is to prevent 3
In the web-of-trust, nodes are PGP keys and edges are key signa-
1
Though both our ontologies and ratings are different in significant tures. Paths are made when the recipient has signed someone’s key,
ways, which we will address later. who has signed another key, and so on all the way until a signature
2 is found on someone who has signed the sender’s key
According to RDF standards, the names of objects are capitalized,
4
while the names of properties remain lowercase. In fact, such positive identification might be of use.
2
1. Client Request Konfidi Server
2. PGP Search
PGP
3. PGP Result Sync Key Server
Pathfinder
Client
Frontend
4. Trust Search
5. Trust Result TrustServer Sync FOAFServer
6. Response
Figure 1: Konfidi Architecture
Wotsap [Cederlöf, 2005] is a tool to work with the PGP web- Konfidi trust network that is built from data kept up-to-date
of-trust. From a keyserver it creates a data file with the names, by the FOAFServer.
email addresses, and signature connections of all keys from the 5. The TrustServer responds with the inferred trust value or an
largest strongly connected set of keys, but no cryptographic data. appropriate error message.
For technical reasons, it does not include all keys or even all reach- 6. The Frontend combines the responses of the Pathfinder and
able keys. Wotsap includes a python script to use this data file to the TrustServer, and sends them back to the client.
find paths between keys and generate statistics.
In the remainder of this section, we discuss the underlying data
2.6 Summary structure for representing trust, how it is implemented in these steps,
This related work forms many of the building blocks, both tech- and the rationale for the system design.
nical and theoretical, for our work. A proper system should deter-
mine authenticity through a decentralized network and determine 3.1 Trust Ontology
trust in a topic through a similar network topology. We integrate In the current research on trust inference networks, there seem
PGP, RDF and FOAF, and design ideas from Golbeck, Guha, and to be two general kinds of representations: one that uses discrete
others. We are extending FOAF with an RDF trust ontology to rep- values for varying levels of trust, and one which uses a continu-
resent our trust network, which ties into the PGP web-of-trust to ous range of trust values. Both return an answer in the same range
verify authorship and identity. We expanded Golbeck’s trust ontol- as their domain. Either kind of representation could be roughly
ogy to a relationship-centered model with values in a continuous mapped onto the other, however, a continuous range would allow
range which represent trust and distrust. more finely-grained control over the data. Further, the inferred trust
values returned by searches would not have to be rounded to a dis-
3. KONFIDI crete level, which would lose precision.
In our representation, trust is considered as a continuum of both
Konfidi refers to the trust network design, the ontology used to trust and distrust, not a measure of just one or the other. For exam-
encode it, and the software to make it usable. The central idea ple, if Alice trusts Bob at some moderate level (say, .75 of a scale
is that between yourself and person X whom you do not know, of 0 to 1), then it seems that she also distrusts him at some minimal
there is a path of PGP signatures to assure the identity of X. An level (say, .25). If Alice trusts Bob neutrally, then she trusts him
estimated trust rating can then be computed by some algorithm that about as much as she distrusts him. If she distrusts him completely,
operates along the trust paths that connect you to X. Figure 1 shows then she doesn’t trust him at all. But in all of these cases, there is a
the components of the Konfidi architecture and how they relate to trade-off between trust and distrust. Only in the extreme cases are
external components and one another. The numbered paths indicate either of them eliminated completely. Our trust model represents
the steps in the process: a range of values from 0 to 1, treating 0 as complete distrust, 1 as
complete trust, and 0.5 as neutral. This also makes many propaga-
1. A client makes a request to the Konfidi server, indicating the tion algorithms simpler, as we’ll discuss later.6
source and the sink.5
2. The frontend passes the request to the PGP Pathfinder, which 3.1.1 Distrust
verifies that some path exists from the source to the sink in The choice of representation is closely related to the concern
the PGP web-of-trust. that it an account of distrust. If the trust network contained val-
3. The Pathfinder returns its response. ues ranging from neutral trust to complete trust, then everyone in
4. If thre is a valid PGP web-of-trust connection, the frontend the network is trusted, explicitly or by inference, on some level at
passes the request to the TrustServer, which traverses the
6
Considering trust in this range naturally evokes the possibility of
5
Source is defined as the entity at the beginning of a desired path, applying probability theory, however, such approaches are beyond
and usually the one making the request. Sink is defined as the entity the scope of this paper. Further consideration is merited, and might
to which the path leads be implemented strategically as discussed in Section 3.2.3.
3
or above neutral. If the system makes a trust inference between Al- of the information, that avoids the pitfalls of the PGP web-of-trust
ice and Bob at one level, but Alice really trusts Bob at a different implementation as discussed in Section 2.4.2. Trust relationships
level, she can explicitly state this previously implicit trust to have a also have trust items specified. See Section 3.1.4 for a specific
more accurate result (for herself and for others who build inference description of the structure.
paths through her to Bob). But, suppose that Alice feels strong neg- Because the trust relationship is represented as its own object,
ative feelings about Bob. In this case, she would still only be able other attributes may be added as the need arises, such as the dates
to represent this relationship as one of neutral trust. So, the trust the relationship began, annotations, etc.
network must account for distrust in some reasonable way.
3.1.3 Trust Topics
If other attributes about a trust relationship could be expressed,
Dave Frank in addition to the rating values, then a system like Konfidi would
Joe
be useful in many wider scopes than email spam prevention. To
describe this, an attribute of trust topic is used. A natural feature of
Elaine
interpersonal trust relationships is that there can be many different
aspects of the same trust relationship.
Clara
For example, suppose Bob is a master chef, but is terribly gullible
about the weather forecast. Alice, of course, knows this, and so
wants to express that she trusts Bob very highly when he gives
Alice advice for making souffle, but she does not trust him at all when
Bob
Spam he volunteers information about the likelihood of the next tornado.
mer
Suppose she only knows Bob in these two capacities. Any trust
inference system should not average the two trust values and get
a somewhat neutral rating for Bob, for that would lose important
Trust Link information about each of those two trust ratings, the only informa-
tion that made these ratings useful in the first place.
Suppose also that, given only the above trust ratings, the system
tried to make an inference on a subject that was not specified. Per-
Figure 2: An Example Trust Network haps Alice has some general level of trust for Bob that should be
used when there is no specific rating for the topic in question. See
One of the difficulties of using explicit distrust in an inference the discussion in Future Work for our proposal for a hierarchical
network is that it is unclear how inferences should proceed once system of topics that might account for this situation. As the num-
a link of distrust has been encountered. Consider a trust network ber of topics rises, the amount of information stored increases in
like that depicted in Figure 2. Suppose Alice distrusts Bob, and size. However, since trust topics and values are attributes of the
Bob distrusts Clara. As Guha points out [Guha et al., 2004], there trust relationship, they need not be represented as additional edges
are at least two possible interpretations of this situation. On the in the graph, they can be stored as additional information attached
one hand, Alice might think something like “the enemy of my en- to existing edges.
emy is my friend” and so decide to put trust in Clara. On the other
hand, she might realize that if someone as scheming as Bob dis- 3.1.4 OWL Schema
trusts Clara, then Clara must really be an unreliable character, and As the FOAF project grows in popularity, an infrastructure is
so decide to distrust her. Further, suppose Bob expressed trust for growing to support it, as mentioned in Section 2.3. Like FOAF,
Elaine. At first consideration, it might seem reasonable to simply Konfidi also uses RDF to represent trust relationships, so that it
distrust everyone that Bob distrusts, including Elaine. But suppose can take advantage of the infrastructure, and since the specifica-
there were another path through different nodes indicating some tion of trust relationships fits in naturally alongside existing FOAF
minimal level of trust for Elaine. Which path should be chosen as properties. In addition to the FOAF vocabulary, there is a vocab-
one which provides the correct inference? Since Konfidi represents ulary called WOT which describes web-of-trust resources such as
trust on an interval, and concatenates (combines trust path ratings) key fingerprints, signing, and assurance [Brickley, 2005c]. Because
values by multiplication, any distrust will make the computed score Konfidi’s vocabulary makes use of FOAF and WOT vocabulary el-
drop quickly below the minimum threshold. This effectively stops ements, then it can take advantage of the established standards and
propagation along a path when distrust is encountered. make the extensions compatible with existing FOAF-enabled tools.
Konfidi uses the Web Ontology Language (OWL) [W3C, 2005b]
3.1.2 Data Structure to define the RDF elements that make up the Konfidi trust ontol-
Golbeck’s ontology represents trust as a relationship between a ogy. OWL builds on the existing RDF specification by providing
person and a composite object comprising a topic, a person, and a a vocabulary to describe properties and classes, and their relations.
rating7 . However, this representation requires trust relationships to The Konfidi trust ontology provides two objects and five properties,
be in the context of a person. Accordingly, it may be difficult to which, in conjunction with the existing FOAF and WOT vocabu-
associate additional information with the trust relationship. laries, are sufficient to describe the trust relationships that Konfidi
In our schema, we represent each trust relationship as an object, requires.
and the trusting person and the trusted entity (typically a person) are The primary element is Relationship, which represents a
associated with that object. Each relationship goes one-way from relationship of trust that holds between two persons. There are two
truster to trusted, but since the truster is responsible for the accuracy properties that are required for every Relationship, truster
and trusted, which indicate the two parties to the relationship.
7 Both truster and trusted have foaf:Person objects as
Subject, trusted Person, and Value according to her termi-
nology their targets. These Person objects should also contain at least
4
one wot:fingerprint property specifying the PGP fingerprint between a frontend which listens for requests and dispatches them,
of a public key held by the individual the Person describes. This and two internal components, one to search the PGP web-of-trust
property is required for verification; if no fingerprint is avail- and another to query against Konfidi’s trust network. This sepa-
able, then Konfidi cannot use the relationship. In general, any ob- ration, in addition to simplifying the design by encapsulating the
ject described in RDF with a resource URI can be the trusted different functions, also allows for increased flexibility and scala-
party, such as specific documents or websites, but for simplicity in bility. Each part is loosely coupled to the other parts, with a simple
our examples, we will focus on persons. which may be defined in API for handling communications between them.
the same file, inline, or in external documents indicated by their
resource URIs. Because it does not matter where the foaf:Per- 3.2.1 Frontend
son data is stored, users may keep files indicating trust relation- Like the FOAFServer described in Section 4, the TrustServer’s
ships separate from main FOAF files. However, to ensure authen- frontend is a web service, using the REST architecture to receiving
ticity, any file containing one or more Relationship objects and answering queries. It runs on the Apache web server, using
must have a valid PGP signature from a public key corresponding the mod python framework. Queries are passed in using HTTP’s
to the fingerprint of each Person listed as a truster in GET method, and responses are returned in XML, which a client
that file. As described in Section 4, flexibility in data location can application may parse to retrieve the desired data.
have a number of advantages. When a query is received, the Frontend passes the source and
In addition to truster and trusted, each Relationship sink fingerprints to the PGP Pathfinder, and, if a valid path is found,
requires at least one about property, which relates the trust Re- to the TrustServer10 . The Frontend then builds the response docu-
lationship to a trust Item. A Relationship is not limited ment to return to the client. The client may, for simplicity, request
in the other properties it can have, so the schema can be extended to only the trust rating value instead of the full XML document.
include auxiliary information about the relationship, such as when
it began, who introduced it and so on without having an effect on 3.2.2 PGP Pathfinder
the requirements of Konfidi. Each Item has two properties be- As mentioned in Section 2.4.2, the PGP web-of-trust is not suffi-
longing to it. The topic property specifies the subject of the trust cient in itself for determining trust. However, it is necessary for the
according to a trust topic hierarchy8 and the rating property in- proper operation of Konfidi because it is required to verify the iden-
dicates the value, according to the 0-1 scale of trust (specified in tity of the sink. Verifying that the document’s signing key matches
Section 3.1.2) that is assigned to the relationship on that topic. the key of the sink in the Konfidi trust network ensures that when
A Relationship may have more than one Item that it is Konfidi finds a topical trust inference path from source to the sink,
about. For example, remember the example given above, in which it is valid. If the author of a document were not identified correctly,
Alice trusts Bob highly about cooking, and distrusts him somewhat someone might forge the trust data, and Konfidi would return an
about the weather. This might be represented in our ontology as incorrect result.
something like the following9 : The Konfidi trust network is not coupled to the PGP web-of-
trust for two reasons. First, the set of people one might wish to
indicate trust for in Konfidi will likely not be the same as the set of
those whose keys you are able to sign. For example, a researcher
in Sydney may work closely with another in Oslo, and so trust that
person’s opinion highly in matters relating to their research. But it
- may be some time before they are able to meet in person to sign
.95 each other’s keys directly. However, a valid path in the PGP web-
of-trust may already exist connecting them.
Second, requiring users to sign the key of each person they want
to add to their Konfidi trust networks adds additional difficulty
which should otherwise be avoided. In keeping with the recom-
- mended practices for PGP, two individuals must meet in person and
.35 verify photo identification before they are to sign each other’s keys.
If this had to be done every time a Konfidi trust link were added,
the extra hassle might entice users to grow lax in their keysign-
ing policy, failing to properly complete such requirements. This
attitude, when widespread would substantially weaken the web-of-
trust. By keeping the PGP web-of-trust separate from the Konfidi
For RDF corresponding to some of the network depicted in Fig- trust network, the strength of the web-of-trust will not be weakened
ure 2, see Appendix B. See Appendix A for the full OWL source needlessly.
code of the schema. Usability becomes an additional advantage of separating the two
trust networks. Aunt Sally can still use Konfidi to indicate trust
3.2 The Konfidi Server if she and only one other person, say, a more technically savvy
The Konfidi server handles requests for trust ratings, verifies that nephew, sign each other’s keys. She will then be connected to
a PGP connection exists, and traverses the internal representation the PGP web-of-trust within a reasonable distance of other fam-
to find a path. Since these three tasks are so distinct, all of Kon- ily members which she is likely to include in her trust network.
fidi is divided into three parts. Figure 1 shows the relationships Now there is no need to teach Aunt Sally the requirements for key
8 10
yet to be developed Strictly speaking, either query is optional. The PGP backend may
9
That is, supposing that the objects alice123 and bob1812 are be skipped to run tests on large sets of sample data, and the trust
defined elsewhere in the same file, and cooking, and weather backend may be skipped if the system is to be used as an interface
are defined as part of the topic hierarchy. to the PGP web-of-trust only.
5
signing, and explaining why they must be done for each person she [Gamma et al., 1995], for the trust propagation algorithm. This
wishes to add to her Konfidi trust network. The system is easier to allows additional propagation strategies to be used as they are de-
use, and the web-of-trust is less likely to be compromised11 . veloped. The algorithm we present is the one that seemed most
The frontend uses drivers in a Strategy pattern [Gamma et al., intuitive to us; we expect there are ones that more accurately re-
1995], so that different subsystems for doing PGP pathfinding can flect the human understanding of trust. It does simple multiplica-
be interchanged as they are developed. The current version utilizes tive propagation over each link in a path. It uses a breadth-first
the Wotsap pathfinder [Cederlöf, 2005] described in Section 2.5. search, prioritized to follow whichever path has highest value after
each iteration, to find the shortest path between source and sink, if
3.2.3 TrustServer one exists:
The Konfidi trust backend is responsible for storing the internal
representation of the Konfidi trust network, incorporating updates function findRating(source, sink):
into the network, and responding to queries about the nodes in the keep a priority queue of all paths
network. until the sink is found
The TrustServer can register with a FOAFServer as a mirror to find the path with the highest rating
receive notification whenever a FOAF record with trust informa- find the link not already seen
tion is added or altered. This can also allow it to synchronize concatenate ratings from path and link
with the FOAFServer after a period of down time in which new add the path and rating to the queue
records have been added. The TrustServer currently assumes that return the path rating
the FOAFServer has verified the signatures of the FOAF records The concatenation algorithm used simply multiplies trust ratings
it stores, freeing it from the computational burden of fetching the along each step in the path, with a fall-off of x1/2 to keep the ratings
signing keys and verifying the signature. See Section 4 for more from falling too quickly:
explanation of the FOAFServer and its functions.
When it updates a record, the TrustServer parses the RDF input r = n−1 1/2
Q
i=0 Rating(i, i + 1)
data and adds the relevant information to its internal representation
of the trust network, which is a list of all foaf:Person records where Rating returns the rating on the edge of two adjacent
indexed by fingerprint and links to each Person marked as trusted, nodes.
along with topic and rating data. The updated data will then be Figure 3 shows an example of how the PGP web-of-trust and
available for subsequent queries. This scheme accomplishes the the Konfidi trust network might be combined. According to the
goal of having trust links available in the proper direction, from algorithm, Dave’s inferred trust of Clara on the topic of email is
source to sink, and avoiding one species of bogus data attack, as 0.81/2 ∗ 0.91/2 ∗ 0.71/2 = 0.71.
discussed in Section 2.4.2. Note that while most PGP edges are two way, the usual outcome
Let m be the number of persons, n the number of trust edges, from a keysigning event, trust edges are more likely to be one way
l the average length of a path between two persons, k the average only. The trust edges are labeled to indicate trust rating and topic,
number of topics per relationship, o the number of persons being to show how a certain path through the network could yield a low
updated, and p the number of edges being updated. This repre- rating for the spammer. The RDF data of this labeled network can
sentation requires O((m + n) ∗ k) space to store and on average, be found in Appendix B.
O(m ∗ l) time to search, and O(o + p) time to update. On the other
hand, a representation of a completely solved network, storing the
trust values between any two individuals, requires O(m2 ∗k) space, Dave Frank
Joe
but makes trust queries take a maximum of O(1) time. However,
such a representation requires O(m2 ∗ l ∗ k) time to solve, which it Elaine
must do again after every update, since it must recompute the value
0.8
for every pair. Email Clara
The tradeoff between storage space and query time makes it
0.7
hard to settle on a representation. Perhaps a compromise between Email
a “live” system that incorporates incremental updates with slow
Alice 0.0
queries, and a system that updates its network several times a day, Bob Email
0.9 Spam
rather than on each update, could provide better performance. Most Email mer
users will not need up-to-date links with every user, since their
queries will most likely be over a rather limited subset of the net-
work. Caching of previously computed trust values on the user’s Trust Link PGP Link
end, with periodic updating, might also make a difference.
It may also be advantageous to store trust links going the other
direction, perhaps for local representation analysis, or auxiliary in-
formation like name or email address. Other information, such as
when the record was last updated, could allow for record caching Figure 3: Combined Trust Network
that might improve performance.
Because of the apparent lack of psychological research on trust
representations, we have again implemented the Strategy pattern 4. FOAFSERVER
11
While the effects of individual keys being compromised on the The Konfidi server uses data from PGP keyservers to act on iden-
web-of-trust as a whole would be restricted to the key’s neighbor- tity trust. To act on topical trust, we need a similar data store. This
hood in the web, as this happened with greater frequency, the use- is not necessarily within the scope of Konfidi, but is a necessary
fulness of the entire web would be undermined. prerequisite. We created the FOAFServer to fulfill this need.
6
The FOAFServer is a web service that stores and serves FOAF desktop software for users to create, sign, and upload their FOAF
files that include trust relationships as specified by our trust ontol- documents. See Section 4 for a summary of the FOAFServer HTTP
ogy. A separate FOAF file is stored for each person, identified by interface.
their PGP fingerprint. All FOAF files must be PGP signed by the
owner to prevent false data from being submitted and to prevent 5.3 Konfidi Clients
unauthorized modification of someone else’s data. When a FOAF Only the Command Line Email Client has been written yet, but
file is requested, the PGP signature is included so that it may be most clients will work similarly, depending on the context in which
verified by a client. they are used. We expect that to make Konfidi widely popular as
Multiple FOAFServers will be available for public use and will a method of stopping spam, a plugin or extension for every major
synchronize their contents. Like the SKS PGP Keyserver[Minsky, MUA will need to be written.
2004], anti-entropy reconciliation will be used, in which, at each
time of synchronization, servers synchronize the entire database re- 5.3.1 Command Line Email Client
gardless of the current states. There is a trade-off between computa- This client is designed to be invoked from a mail processing dae-
tion and communication expenses. This is preferred to the rumor- mon, such as procmail [Guenther & van den Berg, 2001]. It reads
mongering reconciliation used by traditional PGP keyservers, in a single email message from standard in, adds several headers, and
which only the most recent updates are pushed to other servers, writes the message back to standard out. By doing this, a MUA can
since this does not allow servers to be out of communication for an filter the message based on the value of the added headers.
extended period of time. Synchronization data will be PGP signed The client does the following tasks:
to maintain trusted secure communication channels everywhere. 1. determines the source’s PGP fingerprint (normally from a
Since the primary function of the FOAFServer is data storage, it configuration file)
may hold FOAF files that are not related to trust. A FOAF server 2. removes any existing X-Konfidi-* and X-PGP-* headers13
may be configurable to act as one that is used for trust relationships,
3. stops, if the message is not multipart/signed using PGP
pet information, or résumés. Moreover, RDF features a seeAlso
4. stops, if the PGP signature does not validate
tag so a single FOAF file hosted on a FOAF server may refer to
more FOAF data hosted elsewhere. This gives the owner flexibility, 5. stops, if the From: header is not one of the email addresses
including encrypting or limiting access to a FOAF file hosted under listed on the key used to create the signature
his or her direct control. 6. queries the Konfidi server with the topic “email” and the fin-
Our FOAFServer is built with the Apache HTTP Server and gerprints of the source (recipient) and sink (signing party)
mod python using principles of REST architecture. Various clients 7. receives the computed trust value from the Konfidi server
can retrieve and set data using HTTP PUT and GET methods on The client adds the following headers to the email:
URIs like http://domain.org/foafserver/9BB3CE70.
PUT requests must be Content-Type:multipart/signed Header Value
and GET requests are served with a content appropriate to the re-
X-PGP-Signature: valid, invalid, etc
quest’s Accept: header. A web form for uploading FOAF files
X-PGP-Fingerprint: the hexadecimal value
and their signatures is also provided.
X-Konfidi-Email-Rating: decimal in [0-1]
Synchronization has not been implemented yet. Currently the
X-Konfidi-Email-Level: *s for easy matching
TrustServer listens on a port for filenames that it should load into
e.g., -Level: *******
its memory. When someone updates a file via the FOAFServer, it
X-Konfidi-Client: cli-filter 0.1
sends the filename to the TrustServer update listening port so the
TrustServer reloads it. Thus currently the FOAFServer and Trust- If the client stops at any point, it will still add appropriate headers
Server must run on systems with access to the same filesystem. before writing the message to standard out.
5. CLIENTS 6. FUTURE WORK
There are a number of things to be done to develop Konfidi
The PGP, FOAF, and Konfidi servers each have clients which
from a proof-of-concept to a useful system.14 As we’ve mentioned
end-users use to view and modify the data.
above, one thing we need most is a good base of psychological and
5.1 PGP Clients sociological research backing up our trust representation and prop-
agation, or suggesting a new one. Unfortunately, we must leave
Many clients have already been written to interact with PGP key- this to the experts in psychology. The rest of the system can be de-
servers with the Horowitz Key Protocol (HKP), a standard, yet un- veloped in its absence, so long as it is understood that we have just
documented12 , set of filenames and conventions using HTTP. The approximated how trust might work.
server itself also provides web forms to search for and view keys. As we’ve said, a trust system is only as useful as it is trusted.
It may be useful to integrate a PGP client with other Konfidi clients Thus, a system of secure communication between every different
to provide a more cohesive user interface to the system. component is required, most likely using PGP multipart/signed data.
Many MUAs have plugins or extensions to send multipart/- It is hard to say how a user’s trust in a system like Konfidi can be
signed PGP emails. Users should use these for Konfidi to be represented within itself, but that may have implications, too.
useful for email filtering. In addition to plugins at the level of the user’s MUA, Konfidi
could be incorporated into the email infrastructure at the Mail Trans-
5.2 FOAF Clients fer Agent (MTA) level. Thus, a system could check Konfidi and add
The FOAFServer provides some web forms to allow users to up- query results to every email message that it delivers to the user.
load FOAF documents and PGP signatures. We plan to develop 13
This is done in case a spammer sends an email with invalid head-
12 ers in an attempt to get past the filter.
Expired Internet-Draft draft-shaw-openpgp-hkp-00.txt
14
does document the protocol Development is ongoing at http://www.konfidi.org/
7
As the scope of Konfidi naturally expands to include things other Golbeck, Jennifer. 2005b. TrustMail. http://trust.
than email, other clients will be developed. One possible client is a mindswap.com/trustMail.shtml.
web browser extension to query pages when they are visited. This
would work with server extensions that allows PGP signatures to be Golbeck, Jennifer, & Hendler, James A. 2004. Accuracy of Met-
associated with webpages and served as multipart/signed. rics for Inferring Trust and Reputation in Semantic Web-Based
For trust topics to be really useful, some sort of hierarchy is in Social Networks. Pages 116–131 of: Engineering Knowledge
order. Topics ought to standardized so that it is clear in what cir- in the Age of the Semantic Web, 14th Interational Conference,
cumstances they apply, and how they relate to one another. So, for Proceedings.
example, if Alice trusts Bob about internet communication in gen- Guenther, Philip, & van den Berg, Stephen R. 2001. Procmail Web-
eral, then if a query is made about email (a descendant of internet site. http://www.procmail.org.
communication) and no explicit email rating is given, then Konfidi
traverses up the hierarchy until some more general trust rating is Guha, R., Kumar, Ravi, Raghaven, Prabhakar, & Tomkins, Andrew.
found, and applies that. 2004. Propagation of Trust and Distrust. Pages 403–412 of:
Proceedings of WWW 04ACM, for ACM.
7. CONCLUSIONS
IETF. 1998. OpenPGP Message Format. http://www.ietf.
With further research into psychological models of trust and so- org/rfc/rfc2440.txt.
cial implications of widespread accountability, Konfidi promises
to be a useful tool to bring distant trusted subjects into one’s own Minsky, Yaron. 2004. SKS Keyserver. http://www.nongnu.
realm of trusted subjects. Significant work remains to be done with org/sks/.
Konfidi, even to apply it to email communication, but we believe it
is a desirable and necessary system in a globalizing society. Richardson, M., Agrawal, R., & Domingos, P. 2003. Trust Man-
agement for the Semantic Web. Pages 351–368 of: Proceedings
of the Second International Semantic Web Conference.
8. ACKNOWLEDGMENTS
We would like to thank Keith Vander Linden for advising us on W3C. 2005a. Resource Description Framework (RDF). http://
this project and giving feedback on drafts of this paper, and Earl www.w3.org/RDF/.
Fife, Jeremy Frens and Harry Plantinga for their advice on specific
matters. W3C. 2005b. Web Ontology Language (OWL). http://www.
w3.org/2004/OWL/.
References Wong, Meng Weng. 2004. SPF Website. http://spf.pobox.
Abdul-Rahman, Alfarez, & Hailes, Stephen. 1999. Relying On com/.
Trust To Find Reliable Information. In: Proceedings 1999 Inter-
nation Symposium on Database, Web and Cooperative Systems
(DWACOS’99).
Boykin, P. Oscar, & Roychowdhury, Vwani. 2004. Personal
Email Networks: An Effective Anti-Spam Tool. http://www.
arxiv.org/abs/cond-mat/0402142.
Brickley, Dan. 2005a. friend of a friend (foaf) project. http://
www.foaf-project.org/.
Brickley, Dan. 2005b. RDF for mail filtering: FOAF
whitelists. http://www.w3.org/2001/12/rubyrdf/
util/foafwhite/intro.html.
Brickley, Dan. 2005c. WOT RDF Vocabulary. http://xmlns.
com/wot/0.1/.
Brunschwig, Patrick, & Saravanan, R. 2005. Enigmail Website.
http://enigmail.mozdev.org/.
Cederlöf, Jörgen. 2005. Wotsap: Web of Trust Statistics
and Pathfinder. http://www.lysator.liu.se/˜jc/
wotsap/.
DKIM. 2005. DKIM Website. http://mipassoc.org/
dkim/.
Gamma, E., Helm, R., Johnson, R., & Vlissides, J. 1995. De-
sign Patterns: Elements of Reusable Object-Oriented Software.
Addison-Wesley.
Golbeck, Jennifer. 2005a. Computing and Applying Trust
in Web-based Social Networks. University of Mary-
land. http://trust.mindswap.org/papers/
GolbeckDissertation.pdf.
8
APPENDIX
A. OWL TRUST SCHEMA
]>
Trust: A vocabulary for indicating trust relationships
2006-03-23
This is the description
Andrew Schamp
Dave Brondsema
v1.0
4
2
0.00
1.00
9
B. EXAMPLE TRUST NETWORK
]>
Alice
demo-alice@brondsema.net
386847DB8862E2262DB3F94EEA6E22F638E76598
Bob
demo-bob@brondsema.net
CA1C7BC2FA3AC95EA8AA3E7A1FF947DCC5D954BE
Clara
demo-clara@brondsema.net
BB5B0D92A23D31CA559C3D86FF9BD44ADCD8155F
demo-spammer@brondsema.net
ACC267992DDC9AF005D4E24F5013CB50882EC55C
-
0.90
-
0.70
10
-
0
11