Re: Autonomous System Sanity Protocol

RADIA PERLMAN <> Sat, 26 April 1997 21:07 UTC

Received: from cnri by id aa00121; 26 Apr 97 17:07 EDT
Received: from by CNRI.Reston.VA.US id aa14567; 26 Apr 97 17:07 EDT
Received: from mailing-list by (8.6.9/1.0) id GAA09960; Sun, 27 Apr 1997 06:57:47 +1000
Received: from munnari.OZ.AU by (8.6.9/1.0) with SMTP id GAA09931; Sun, 27 Apr 1997 06:53:56 +1000
Received: from by munnari.OZ.AU with SMTP (5.83--+1.3.1+0.56) id UA10560; Sun, 27 Apr 1997 06:53:53 +1000 (from
Received: from INET-SJF-Message_Server by with Novell_GroupWise; Sat, 26 Apr 1997 13:53:52 -0700
Message-Id: <>
X-Mailer: Novell GroupWise 4.1
Date: Sat, 26 Apr 1997 10:52:53 -0700
Subject: Re: Autonomous System Sanity Protocol
Precedence: bulk

(Note: I removed IETF from the distribution list. Hope all the interested people are on big-internet.)

Re: Also, do you know if Perlman's thesis is available on the net?

No, it's not available on the net. I've been promising to write an informational RFC. That would probably be the easiest thing. I no longer have softcopy. So it wouldn't be the actual thesis, it would be a rewritten thing, possibly clearer now that I've had a few years of explaining it, and I won't have to ask whether there's a problem with copyright. It's also summarized in both my books (Interconnections: Bridges and Routers, chapter 11, and Network Security: Private Communication in a Public World, pp 462-465) Gee. 4 pages. It really is a simple scheme.

I can also mail hardcopy of the thesis, but only to people who really really want to read it and soon. Otherwise, I'd rather people waited until I wrote the RFC. If you want me to mail hardcopy, email me your postal address. If I get more than, say, 20 responses, I don't promise to mail them out. If anyone has the appropriate tools for automatic conversion from hardcopy into softcopy, that would be nice (provided I check with MIT about copyright).

Maybe the topic of small changes to what's deployed to ameliorate various types of Byzantine failures, mabye a BOF would be appropriate? Or a research group?

Anyway, some thoughts...

Having an authoritative database of all the potential links, and the routing algorithm only tells you which of those things are currently unreachable, might be nice. That database could be signed, and then replicated without concern for integrity protection, but unfortunately parts of the topology want to remain secret from other parts. (e.g., BGP has "don't pass this information to neighbor N", presumably because people want it).

Maybe rather than passing around the authoritative database, there can be a tool that queries all the configured information at boundaries, or a hierarchy of such tools that explore their own portion of the topology, for sanity?

A Byzantine failure of a true router can't be solved with having routers sign messages, because the compromised router will be able to generate a legitimate signature to prove he's one of the good guys.

BGP is actually somewhat like a link state protocol, in that the entire path is given. If each router signs its path to D, then when router R chooses among the routes given by each of its neighbors, it chooses one, and can preserve that neighbor's signature, and then add its own. So there would be a signature for each BGP-hop. I don't think that solves too much, though, since the problem is a legitimate router being misconfigured rather than having malicious people inject messages.