North American Network Operators Group
Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Re: the O(N^2) problem

  • From: David Andersen
  • Date: Sun Apr 13 22:50:22 2008

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

On Apr 13, 2008, at 8:36 PM, Edward B. DREGER wrote:


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." :-)

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?