Re: Autonomous System Sanity Protocol

Tony Li <> Sun, 27 April 1997 09:26 UTC

Received: from cnri by id aa15522; 27 Apr 97 5:26 EDT
Received: from by CNRI.Reston.VA.US id aa05529; 27 Apr 97 5:26 EDT
Received: from mailing-list by (8.6.9/1.0) id TAA10862; Sun, 27 Apr 1997 19:16:41 +1000
Received: from munnari.OZ.AU by (8.6.9/1.0) with SMTP id SAA10833; Sun, 27 Apr 1997 18:55:28 +1000
Received: from by munnari.OZ.AU with SMTP (5.83--+1.3.1+0.56) id IA21093; Sun, 27 Apr 1997 18:55:27 +1000 (from
Received: from ( []) by (8.8.5/8.8.5) with ESMTP id BAA21349; Sun, 27 Apr 1997 01:55:24 -0700 (PDT)
Received: (from tli@localhost) by (8.7.6/8.7.3) id BAA01355; Sun, 27 Apr 1997 01:55:12 -0700 (PDT)
Date: Sun, 27 Apr 1997 01:55:12 -0700 (PDT)
Message-Id: <>
From: Tony Li <>
In-Reply-To: <> (
Subject: Re: Autonomous System Sanity Protocol
Precedence: bulk

   However, the fundamental difference between *connectivity* information
   and *reachability* information comes into play - the latter is not
   useful to you *until* it has been processed (i.e. not just replicated)
   through someone else (i.e. path selection is *inherently* a distributed
   computation, in which you use someone else's partial computation
   results), whereas connectivity information is only used *without* being
   touched in any way be the people who pass it on - so there is no way any
   errors/malice on their part can mess it up. Either you have it as the
   source sent it - or you don't.

True.  However, let's recall the problem that we're trying to solve.  We
are _NOT_ trying to solve Radia's Byzantine failures.  [Not that it's not a
worthy and interesting problem in its own right.  It's just not the failure
at hand.]  

   How you find out, authoritatively, the public key for X is definitely a
   hard one. 

Agreed.  Unfortunately, that's a basic requirement for ANY of these
schemes.  I don't claim to know enough about security to solve that

   But it isn't impossible - in fact (admittedly,
   without working out the details) in a top-down system, the same
   framework that works for DNS should work for addresses too, no?

The architecture is believably the same.  It's not clear that the
mechanisms would suffice.  Note that top-down or bottom-up assignment
generally doesn't seem to make a difference as far as I can tell.  It looks
like the leaf has some address space and to authenticate that, you have to
be able to walk delegations back to a well known root.

       > It can certainly prevent all unilateral bad information,
       > i.e. based on someone incorrectly configuring their routers (or
       > software/hardware bugs).


   Because routing data is never modified/updated/added-to on its way to
   you, merely copied. You can be *guaranteed* that what you get is what
   the original sender sent. So there's no way anyone between you and the
   source can mess the data up, right?

Again, it's irrelevant to the problem at hand.  You lack the delegation

   The other thing a single site, either confused/malicious, can try and do
   is inject bogus data (i.e. saying "I'm X and I'm connected to A, B, C
   ...  <ad infinitum>"). But this doesn't work because the data will not
   match up - i.e. A is not also reporting that they are connected to X. So
   you can trivially filter that out.

Again true.  Again not relevant.

       it's trivial to inject bad information and have it propagate
       throughout the immediate map.

   Well, it would depend on the protocol design. If you can't have a link
   between X and Y unless each end reports connectivity to the other, you
   can't have unilateral announcements. (I don't know enough details of,
   e.g. OSPF to know if it would work to have only one end of a link
   announce it - anyone know?)

You are correct: you cannot fake bilateral connectivity and unilateral
connections should be ignored in the SPF.  However, you can still trivially
fake the prefixes in the LSA and then sign the LSA.  Game over.

Are you sure you understand the problem Noel?  Let's take a clear example.
This is the LSA for MIT:

	Hi, we're MIT, we have connectivity to BBN Planet, Harvard and
	Cerfnet.  We have prefixes 18/8, 36.0/9 and 36.128/9.
						Jeff Schiller

Now, you're correct, the connectivity information would show up as bogus
because the other sides wouldn't claim connectivity.  However, what
authenticates the prefix assignments?  Just because it appears to be
correctly signed by Jeff, do you take it verbatim?  I don't.  That would
subvert all of Stanford.  [You may argue that this is a good thing.  ;-)]
For security, I want to see

	MIT is assigned 18/8.
			Jon Postel
Until then, there's no protection.