the O(N^2) problem
Edward B. DREGER
eddy+public+spam at noc.everquick.net
Mon Apr 14 05:57:22 UTC 2008
Stardate Mon, 14 Apr 2008, Suresh Ramasubramanian's log:
SR> From: Suresh Ramasubramanian
SR> Looks like what various people in the industry call a "reputation
SR> system"
I started responding; Suresh's reply came as I was doing so, and put it
very succinctly. Reputation system, but inter-"network". Perhaps an
example would work better than my vague descriptions. :-)
Let's say I receive email from:
From: <owen at ...>
Received: from ... (owen.delong.sj.ca.us [192.159.10.2])
Should I trust the message? I don't "know" you. However, I _do_ know
From: <owen at ...>
Received: from ... (trapdoor.merit.edu [198.108.1.26])
and trapdoor.merit.edu vouches for you. Elaborating, using "trust
paths", *not* SMTP or routing paths:
<owen at ...> # distrust metric: initially 0
owen.delong.sj.ca.us # distrust metric: still 0
trapdoor.merit.edu # dm: 1 (it mostly believes your MX)
mail.everquick.net # dm: 2 (more or less trust NANOG)
versus
<owen at ...> # dm: 0
malicious.host.domain.tld # dm: 0 (trying to impersonate)
trapdoor.merit.edu # dm: 10 (doesn't yet trust above host)
mail.everquick.net # dm: 16 (after whatever local mods)
or
<somenewaddress at ...> # dm: 0
owen.delong.sj.ca.us # dm: 0 (your MX can vouch)
trapdoor.merit.edu # dm: 1 (more or less believes your MX)
mail.everquick.net # dm: 2 (more or less trust NANOG)
IOW, I receive email from an unrecognized address from your MX. Do I
trust it? I mostly trust trapdoor.merit.edu, which mostly trusts your
MX, which totally trusts <somenewaddress at ...>. Therefore, I conclude
that I largely trust the message.
For such a system to scale, it would need to avoid OSPF-style
convergence. Similarly, I would not want to query, for the sake of
example, 15k different "trust peers" each time I needed to validate a
new <host,address> tuple. (Hence the interdomain routing and d-v calc
references.)
Therefore, one would find the locally-optimal solution at each "trust
hop", a la interdomain routing.
Perhaps PGP/GPG would be the best analogy. (When I said "PKI", I should
have stated CA-based PKI; my original wording was excessively broad, and
should have explicitly excluded PGP.)
Eddy
--
Everquick Internet - http://www.everquick.net/
A division of Brotsman & Dreger, Inc. - http://www.brotsman.com/
Bandwidth, consulting, e-commerce, hosting, and network building
Phone: +1 785 865 5885 Lawrence and [inter]national
Phone: +1 316 794 8922 Wichita
________________________________________________________________________
DO NOT send mail to the following addresses:
davidc at brics.com -*- jfconmaapaq at intc.net -*- sam at everquick.net
Sending mail to spambait addresses is a great way to get blocked.
Ditto for broken OOO autoresponders and foolish AV software backscatter.
More information about the NANOG
mailing list