the O(N^2) problem

Mailman List Mirror (Read Only)
1

Bottom line first:

We need OOB metadata ("trust/distrust") information exchange that scales
better than the current O(N^2) nonsense, yet is not PKI.

And now, the details... which ended up longer reading than I intended.
My apologies. As Mark Twain said, "I didn't have time to write a short
letter, so I wrote a long one instead." :slight_smile:

When it comes to establishing trust:

* The current SMTP model is O(N^2);

* I posit that the current IP networking model is sub-O(N);

* PKI models are pretty much O(1).

Polynomial-order just doesn't scale well. It's mathematical fact, and
particularly painful when the independent variable is still increasing
quickly.

Many operators seem to reject PKI as "power in too few hands". I'll not
disagree with that.

Conclusion: What we need is something that scales better than O(N^2),
but that is not as "few trusted keepers of the world" as PKI.

Let's look to one of the current hot tickets: social networking. Who is
whose friend, who is in whose network, blah blah blah. (The junior high
students seem to grok the concept of trust being semi-transitive!)

Let's also draw upon operational lessons from a couple old-timers. I
recall using a critter known as "NNTP". And once upon a time, before my
days on the Internet, lived a funny little beast called "UUCP".

We track email quality from all mailservers that hit us. I can whip up
a list of MXes/organizations that I'm willing to "trust" -- and let's
leave that term imprecisely-defined for now.

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.

Let actual _content_ still be end-to-end, so that we do not simply
reincarnate NNTP or UUCP.

Alternatively:

I'm open to other suggestions.

Or, there's plan "C":

We continue to argue, banter, carp, fuss, grumble, moan, swear, whine,
et cetera (I decided against running the alphabet) over the problem.
Hey, it's worked/working great so far, right?

Eddy

2

Another alternative is something we've been working on that we call Perspectives:

http://www.cs.cmu.edu/~dwendlan/perspectives/

Warning: This is a work in progress. The Mozilla plugin is a little flaky and the paper is still being revised for the final revision for USENIX. The SSH code works pretty well. We haven't written an SMTP version yet.

The basic idea is pretty simple: Use multiple paths to a destination to figure out if you're likely getting to the right place. If you _and_ your friends all observe the same public key from a server, preferably for a long period of time, then trust it. Else scream bloody murder. Perspectives provides these "friends" in the form of notary servers who you can ask about the past and present keys supplied by an SSL or SSH server.

(An alternate way of viewing this is to think of Perspectives as a low-overhead, low-cost PKI.)

It's an interesting thought exercise to wonder if we could extend the model to "trust not to send spam" instead of simply "trust to be the owner of the key", but that same exercise applies with a PKI, too.

   -Dave

3

Bottom line first:

We need OOB metadata (“trust/distrust”) information exchange that scales
better than the current O(N^2) nonsense, yet is not PKI.

Not sure why PKI should be excluded, but, so far, this is too abstract
to know what the question is…

And now, the details… which ended up longer reading than I intended.
My apologies. As Mark Twain said, “I didn’t have time to write a short
letter, so I wrote a long one instead.” :slight_smile:

When it comes to establishing trust:

  • The current SMTP model is O(N^2);

I don’t see SMTP as even a “trust” model since there’s pretty much
nothing trustworthy in SMTP.

  • I posit that the current IP networking model is sub-O(N);

Again, I’m not seeing IP as a trust model, but, YMMV.

  • PKI models are pretty much O(1).

Polynomial-order just doesn’t scale well. It’s mathematical fact, and
particularly painful when the independent variable is still increasing
quickly.

Sure.

Many operators seem to reject PKI as “power in too few hands”. I’ll not
disagree with that.

Depends on the PKI. For example, the PGP/GPG Web of Trust concept
pretty much lets each individual build their own trust model to whatever
O(x) they choose where greater values of x require more effort and also
provide greater security/trust granularity and lower values of x involve
greater trust of others that you claim you can trust and less direct effort
on your part.

Let’s also draw upon operational lessons from a couple old-timers. I
recall using a critter known as “NNTP”. And once upon a time, before my
days on the Internet, lived a funny little beast called “UUCP”.

I remember UUCP. It was pretty much O(n^2).

We track email quality from all mailservers that hit us. I can whip up
a list of MXes/organizations that I’m willing to “trust” – and let’s
leave that term imprecisely-defined for now.

Uh, OK. Starting to understand what the question might be aiming
towards.

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.

Let actual content still be end-to-end, so that we do not simply
reincarnate NNTP or UUCP.

Now I’m lost again. You’ve mixed so many different metaphors from
interdomain routing to distance-vector computaton to store-and-forward
that I simply don’t understand what you are proposing or how one
could begin to approach implementing it or what problem you seem
to think it solves (although it sort of seems like you’re wanting to attack
the trustworthiness of email to battle SPAM through some mechanism
that depends only on the level of trust for the (source, arrival path)
tuple from whence it came.

What am I missing?

Owen

4

Looks like what various people in the industry call a "reputation system"

5

Stardate Mon, 14 Apr 2008, Suresh Ramasubramanian's log:

From: Suresh Ramasubramanian

Looks like what various people in the industry call a "reputation
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. :slight_smile:

Let's say I receive email from:

  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

  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@...> # 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@...> # 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@...> # 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@...>. 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

6

And dkim layered with some kind of reputation (if only a locally built
whitelist) wont scale for this?

7

The risk in a reputation system is collusion.

8

Multiple reputation systems, each with their own reputation .. Sed
quis custodiet ipsos custodes and all that ..

A lot of the "reputation" (aka "positive reputation") shall we say
work is heavily sender / ESP / bulk mailer etc driven. And the
negative reputation stuff (blocklists like spamhaus etc) have been
around rather a long time.

So quite a few ISPs tend to rely on trusted negative reputation
systems (aka they'd use spamhaus) and build positive reputation
(whitelists) on their own, possibly tying this to auth systems such as
dkim.

--srs

9

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.

10

Folks,

Same request as the Yahoo! Mail thread, can we go ahead and wrap this
up? Excellent points, intelligent positions, but definitely not
operational. This one might be great for ASRG, which has been a little
more active lately.

Best Regards,

Marty