The Advogato trust metric is not attack-resistant
The project for the graduate algorithms class I took in Fall was to compare two algorithms for a problem of our choice. I chose to compare two trust metrics, the Advogato trust metric and Google's PageRank. Trust metrics attempt to solve the following problem: "Given a directed graph where an edge from A to B means 'A trusts B', whom should I trust?".
In the case of Advogato, the nodes are Advogato accounts and the edges are explicit certifications. In the case of Google, the nodes are web pages and the edges are links.
A good trust metric makes it difficult for an attacker to gain a large amount of trust. More specifically, we might want the amount of trust an attacker gains to be at most linear in the cost of the attack. It helps to think in terms of "bad" nodes, which are controlled by the attacker, "confused" nodes, which trust bad nodes, and "good" nodes, which are neither bad nor confused.
Proving a statement about the cost of an attack requires assuming something about the cost of compromising or confusing each node. Advogato assumes that the cost of confusing a node is closely related to the node's capacity, which is a function of the node's distance from the root. PageRank assumes that the cost of confusing a page is closely related to the page's popularity, which is in turn estimated by the page's PageRank score.
I discovered a problem with Advogato's security proof: it bounds the trust by the final capacities of the confused nodes rather than their capacities before the attack. An attacker can confuse a single expensive (high-capacity) node and many cheap (capacity 1) nodes, then tell the expensive node to trust the cheap nodes. Now there are many confused nodes with substantial capacity, and the attacker can get get an amount of trust equal to a constant times the square of the cost of the attack.
PageRank does not have this problem. The PageRank score gained by the attacker is bounded by a small constant times the total PageRank-score-before-attack of the confused pages, no matter where the attacker makes confused or bad nodes link.
For more details, you can read my paper for the algorithms class.
May 27th, 2005 at 7:14 am
Your counterproof depends on a particular interpretation of the attack model.
It’s not explicitly stated in Levien’s proof exactly how much control the attacker has over “confused” nodes. If the attacker can only convince confused nodes to trust “bad” nodes, then Levien’s proof holds. If, however, the attacker can convince confused nodes to trust arbitrary other nodes, then your proof holds. The former assumption might be reasonable because the attacker controls the “bad” nodes, and can use their behavior to influence other users’ perceptions of them; the attacker does not have the same control over perception of non-bad nodes.
Levien’s proof isn’t very explicit about the attacker’s influence over confused nodes. His definition of a confused node states only: “The confused nodes themselves represent valid accounts, but may contain certificates to the bad nodes.” This could reasonably mean that the confused nodes are assumed to be valid in every way except for their certification of bad nodes.
May 27th, 2005 at 10:35 am
Matt, I think my attack still works even if the confused nodes can only be made to trust bad nodes (rather than any nodes the attacker chooses). Instead of making the expensive confused node trust the cheap confused nodes directly, the attacker would make the expensive confused node trust one of his nodes, which would in turn trust each of the cheap confused nodes. This makes the attack more expensive, but not more than 4 times as expensive.
May 27th, 2005 at 11:15 am
Ah, that’s right. Nice work!
June 2nd, 2005 at 4:23 am
Google (stanford) and yahoo! (one of the author of the paper is from Yahoo!) are going for trustRank http://moloko.itc.it/paoloblog/archives/2005/04/26/from_pagerank_to_trustrank.html
However this is still a Global trust metri while I’m trying to push “local trust metrics”
see http://moloko.itc.it/trustmetricswiki/moin.cgi/LocalTrustMetric and http://moloko.itc.it/paoloblog/archives/2005/04/30/paper_accepted_at_aaai05_controversial_users_demand_local_trust_metrics_an_experimental_study_on_epinionscom_community.html