North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Re: the O(N^2) problem

  • From: Tony Finch
  • Date: Mon Apr 14 10:56:02 2008

On Mon, 14 Apr 2008, Edward B. DREGER wrote:
>
> When it comes to establishing trust:
>
> * The current SMTP model is O(N^2);

In practice it's O(N): small-to-medium-sized email systems rely on
external reputation providers (blacklists or anti-spam service providers)
rather than creating their own reputation databases.

> * PKI models are pretty much O(1).

PKI gives you authentication but not reputation. The cryptographic notion
of "trust" is not useful in the context of spam.

> Here's what I propose:
>
> Establish a "distrust protocol".  Let path weight be "distrust".  The
> "trust path" is of secondary importance to "path weight", although not
> completely irrelevant.  SMTP endpoint not in graph?  Fine; have some
> default behavior.
>
> Let _trust_ be semi-transitive, a la BGP -- a technology that we know,
> understand, and at least sort of trust to run this crazy, giant network
> that dwarfs even a 50M-user provider.

Sadly this doesn't work. BGP's transitive trust does not prevent spammers
and hackers and other bad actors from getting IP connectivity. NNTP's
transitive trust doesn't prevent spammers from getting usenet
connectivity.

You can't go much further than a hop or two before measures of reputation
become too diluted to be useful. This is partly because the diameter of
the network is quite small, so you rapidly end up with a huge population
that only has a reasonable reputation on average. (Much like large
providers are only reasonably non-spammy - they're too big to be squeaky
clean.) Note that the model of anti-spam service providers and reputation
providers is effectively a two-hop model.

Tony.
-- 
f.anthony.n.finch  <[email protected]>  http://dotat.at/
HEBRIDES: SOUTHWEST VEERING NORTHWEST 5 OR 6, THEN EAST 4 OR 5. MODERATE. RAIN
OR SHOWERS. MODERATE OR GOOD.