the O(N^2) problem

[Edward B. DREGER]

Bottom line first

We need OOB metadata ("trust/distrust") information exchange that scale
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 shor
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, an
particularly painful when the independent variable is still increasin
quickly

Many operators seem to reject PKI as "power in too few hands". I'll no
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 i
whose friend, who is in whose network, blah blah blah. (The junior hig
students seem to grok the concept of trust being semi-transitive!

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

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

Here's what I propose

Establish a "distrust protocol". Let path weight be "distrust". Th
"trust path" is of secondary importance to "path weight", although no
completely irrelevant. SMTP endpoint not in graph? Fine; have som
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 networ
that dwarfs even a 50M-user provider

Let actual _content_ still be end-to-end, so that we do not simpl
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

Edd
-
Everquick Internet - http://www.everquick.net
A division of Brotsman & Dreger, Inc. - http://www.brotsman.com
Bandwidth, consulting, e-commerce, hosting, and network buildin
Phone: [phone] Lawrence and [inter]nationa
Phone: [phone] Wichit
_______________________________________________________________________
DO NOT send mail to the following addresses
***@brics.com -*- ***@intc.net -*- ***@everquick.ne
Sending mail to spambait addresses is a great way to get blocked
Ditto for broken OOO autoresponders and foolish AV software backscatter

[David Andersen]

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

-Dav

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


> Bottom line first

> We need OOB metadata ("trust/distrust") information exchange that
> scale
> 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
> shor
> 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, an
> particularly painful when the independent variable is still increasin
> quickly

> Many operators seem to reject PKI as "power in too few hands". I'll
> no
> 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 i
> whose friend, who is in whose network, blah blah blah. (The junior
> hig
> students seem to grok the concept of trust being semi-transitive!

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

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

> Here's what I propose

> Establish a "distrust protocol". Let path weight be "distrust". Th
> "trust path" is of secondary importance to "path weight", although no
> completely irrelevant. SMTP endpoint not in graph? Fine; have som
> 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
> networ
> that dwarfs even a 50M-user provider

> Let actual _content_ still be end-to-end, so that we do not simpl
> 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

[Owen DeLong]

[Suresh Ramasubramanian]

On Mon, Apr 14, 2008 at 10:34 AM, Owen DeLong <***@delong.com> wrote

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

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

[Suresh Ramasubramanian]

On Mon, Apr 14, 2008 at 11:27 AM, Edward B. DREGE
<eddy+public+***@noc.everquick.net> wrote
> For such a system to scale, it would need to avoid OSPF-styl
> convergence. Similarly, I would not want to query, for the sake o
> example, 15k different "trust peers" each time I needed to validate
> new <host,address> tuple. (Hence the interdomain routing and d-v cal
> references.

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

[Suresh Ramasubramanian]

On Mon, Apr 14, 2008 at 11:50 AM, Steven M. Bellovi
<***@cs.columbia.edu> wrote
> The risk in a reputation system is collusion

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

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

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

--sr
--
Suresh Ramasubramanian (***@gmail.com

[Joe Greco]

> The risk in a reputation system is collusion

/One/ risk in a reputation system is collusion

Reputation is a method to try to divine legitimacy of mail based on factor
other than whether or not a recipient authorized a sender to send mail. T
a large extent, the majority of the focus on fighting spam has been to tr
to do this sort of divination by coding clever things into machines, but it
should be clear to anyone who has ever had legitimate mail mysteriously go
missing, undelivered, or delayed that the process isn't without th
occasional falsing

There are both positive (whitelist) and negative (DNSBL, local This-Is-Spam
etc) reputation lists, and there are pros and cons to each

Consider, for example, Kevin Day's example of the Group-B-Objectionabl
scenario. This is a nonobvious issue that can subvert the reputation o
a legitimate mailer

On the flip side, what about someone who actually wants to receive mai
that an organization such as Spamhaus has deemed to be hosted on a spamm
IP? (And, Steve and the Spamhaus guys, this is in no way a criticism o
the job you guys do, the Internet owes you a debt of gratitude for doin
a nearly impossible job in such a professional manner

There are risks inherent with having any third party, specificall
including the ISP or mailbox provider, trying to determine the nature o
the communications, and filtering on that basis

This is why I've been talking about paradigms that eliminate the need fo
third parties to do analysis of e-mail, and rely on the third parties t
simply implement systems that allow the recipient to control mail. Ther
are a number of such systems that are possible

However, the current systems of divining legitimacy (reputation, filtering
whatever) generate results that loosely approximate the typical mail tha
the average user would wish to receive. Users have been trained to conside
errors in the process as acceptable, and even unavoidable

It's ridiculous when systems like Hotmail silently bitbucket e-mail fro
a sender (and IP) that has never spammed, and have ONLY sent transactiona
e-mail and customer support correspondence, and the individually compose
non-HTML REPLIES to customer inquiries are eaten by Hotmail, or tossed i
the spam folder. Nice. (I know, we all have our stories

... J
--
Joe Greco - sol.net Network Services - Milwaukee, WI - http://www.sol.ne
"We call it the 'one bite at the apple' rule. Give me one chance [and] then
won't contact you again." - Direct Marketing Ass'n position on e-mail spam(CNN
With 24 million small businesses in the US alone, that's way too many apples

[Edward B. DREGER]

I received an off-list request: "Could you clarify what precisely yo
are trying to secure?" I fear that perhaps I am still too vague

When one accepts an email[*], one wishes for some sort of _a priori
information regarding message trustworthiness. DKIM can vouch fo
message authenticity, but not trust. (A valid DKIM signature shows tha
selected headers/content have not been forged, but does not vouch fo
content.

If I receive email from someone I trust, there's a good chance it'
something I want. If from someone who someone I trust trusts, there'
still a good chance. As the chain lengthens, trust becomes a bi
dicier

What I propose is orthogonal to DKIM

I've also been asked to set up a separate mailing list. I'll do that
and stop pollu^H^H^H^H^Htrying to elaborate on NANOG

[*] Discussion limited to one example, but could be expanded

Edd
-
Everquick Internet - http://www.everquick.net
A division of Brotsman & Dreger, Inc. - http://www.brotsman.com
Bandwidth, consulting, e-commerce, hosting, and network buildin
Phone: [phone] Lawrence and [inter]nationa
Phone: [phone] Wichit
_______________________________________________________________________
DO NOT send mail to the following addresses
***@brics.com -*- ***@intc.net -*- ***@everquick.ne
Sending mail to spambait addresses is a great way to get blocked
Ditto for broken OOO autoresponders and foolish AV software backscatter

[Rich Kulawiec]

On Mon, Apr 14, 2008 at 01:41:50PM +0000, Edward B. DREGER wrote
> When one accepts an email[*], one wishes for some sort of _a priori
> information regarding message trustworthiness. DKIM can vouch fo
> message authenticity, but not trust.

At the moment, this problem can't be solved on an Internet scale, becaus
there are on the order of 10e8 fully-compromised systems out there. Man
different estimates have been proferred over the years; the most recen
I've seen is from Rick Wesson at Support Intelligence, who offered 40
as his guesstimate; if there are 800M systems on the 'net, that'd be abou
320M. But the exact number is unknowable and in some sense unimportant
the difference between 128M and 172M doesn't matter for the purpose o
this discussion. And I believe there is widespread concurrence tha
whatever the number is, it's going up

The new owners of those systems can do anything with them they want
including forging (and cryptographically signing) outbound mail message
using any SMTP authorization credentials present on it, or any SMTP acces
implied by its network location(s). (They can also, if they wish, arrang
to conceal incoming replies to this traffic from the former owners.

Until that problem's solved (and I don't see any solution for it o
the horizon) then it will undercut any number of interesting approache
worthy of significant discussion, not just this one. It's the elephan
in the room, and until it's banished, it will keep getting in the way

---Rs

[Tony Finch]

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 o
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 notio
of "trust" is not useful in the context of spam

> Here's what I propose

> Establish a "distrust protocol". Let path weight be "distrust". Th
> "trust path" is of secondary importance to "path weight", although no
> completely irrelevant. SMTP endpoint not in graph? Fine; have som
> 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 networ
> that dwarfs even a 50M-user provider

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

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

Tony
--
f.anthony.n.finch <***@dotat.at> http://dotat.at
HEBRIDES: SOUTHWEST VEERING NORTHWEST 5 OR 6, THEN EAST 4 OR 5. MODERATE. RAI
OR SHOWERS. MODERATE OR GOOD

[Martin Hannigan]

Folks

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

Best Regards

Mart

-
Martin Hannigan http://www.verneglobal.com
Verne Global Datacenters e: ***@verneglobal.co
Keflavik, Iceland p: [phone]