BGP to doom us all

Thu Apr 3 19:06:31 UTC 2003

From: Stephen Kent <kent at bbn.com>
Subject: Re: BGP to doom us all
Date: Wed, 2 Apr 2003 18:15:05 -0500

Folks,

I was not subscribed to the workshop list when Randy forwarded this message
at the beginning of last month.  However, I would like to respond to the
issues raised in the text.

Steve
----

> From: Iljitsch van Beijnum <iljitsch at muada.com>
> To: Avi Freedman <freedman at freedman.net>
> Cc: <nanog at merit.edu>
> Subject: Re: BGP to doom us all
> Date: Sat, 1 Mar 2003 21:09:14 +0100 (CET)
>
>
> On Sat, 1 Mar 2003, Avi Freedman wrote:
>
>>  Re: S-BGP in particular, I think that the analysis on S-BGP has been...
>>  limited.  Ironic for a security protocol that I haven't seen any
>>  real analysis of the effect on router CPUs when *under attack*.  I
>>  am not saying "oh, the authentication will drive things way too high".
>>  I'm just saying that we don't know because the simulations have used
>>  very conservative parameters.
>
> My two cents:
>
> By looking at the packet formats I estimate that the memory requirements
> for S-BGP are about 4 times those of regular BGP (mind you - just the
> BGP table, RIB and FIB remain the same). This gets us pretty close to
> common 32-bit CPU address space limits.

Whie it is true that the size of UPDATE messages grows considerably under
S-BGP, the amount of extra space needed in RIBs is a function of the
implementation approach that one adopts, and so it is hard to translate the
space occupied by RAs in an UPDATE into the extra RIB space that will be
used. Obviously, if a router has many peers, then the increase in the Adj
and Loc RIB sizes will be magnified, and no fanout number was provided in
the comment above. But it does not seem likely that we would really be close
to 32-bit address space limits based on our analysis and some (limited)
implementation experience.

> For receiving updates: you are expected to check the validity of each
> hop in each AS path in the global routing table using a public key
> signature verification. A Pentium-class CPU can do a few thousand of
> those per second, so that adds several minutes of pure CPU time to the
> initialization of each full feed. This means crypto hardware.

In the papers we published, we explicitly noted that initialization could be
a problem, and suggested that initialization after a crash would benefit
from a restoral strategy (using NV storage for the Loc RIBs) or from a
deferred evaluation strategy. We have thought more about this latter
strategy, and a variant of it also is attractive for any router with many
peers. The observation is that when you have many peers, most of the UPDATEs
that are received will not result in generation of UPDATEs, and thus one
need not evaluate the signatures, since they didn't influence operation
(i.e., didn't result in the generation of UPDATEs). This is true both in
steady state operation as well as during initialization. Thus one could mark
each Adj RIB entry to indicate whether it had been verified, or not. If the
router is too busy to verify an UPDATE, then so long as that UPDATE does not
change the notion of best route for the prefixes it contains, one can defer
(perhaps forever) the signature verification process. (We do preform other,
quick checks to weed out bad UPADTEs upon receipt.) Using the strategy, we
anticipate that one can significantly reduce the number of signature
validation operations that need to be performed, with proportionally greater
savings at routers with the most peers.

Still, we do think that use of crypto hardware is desirable in the long run,
since it allows for better protection of the private key used by a router,
and it offers greater capacity to deal with floods of UPDATEs during worst
case scenarios. If routers need to be equipped with additional memory
anyway, then making provision for a crypto chip would be a reasonable update
to a processor board when the memory size changes were made. Modern crypto
chips are capable of very high (10's of thousands/second) signature
processing rates, but one must pay close attention to the fine print, since
there most of the figures do not include the time to load a new signature
key into the chip.

> For sending updates: you must include the identity of the receiver in
> each update (and then sign the update, unless I remember incorrectly).
> That means sending out updates to a large number of peers (such as on a
> public internet exchange) becomes a rather expensive operation, even
> discounting the crypto.

I'm not sure why this is a "rather expensive operation, even discounting the
crypto."  Certainly the bigger UPDATEs take up more TCP queue space, and
maybe there is some concern over the need to generate a distinct UPDATE per
peer.  However, there is a provision to place more than one next hop AS # in
a route attestation, to reduce the need to generate different UPDATEs for
each peer, so long as the UPDATE would otherwise be the same. We have not
explored the implications of this in detail, but it does suggest a possible
way to reduce the signature generation burden.  Also, note that S-BGP uses
DSA, which provides very efficient signature generation, which is the crypto
operation one performs when generating (vs. consuming) an UPDATE.

> However, there is an alternative to S-BGP: soBGP (secure origin BGP, see
> URL in my sig for links). Unlike S-BGP, soBGP mainly focusses on the
> origin of a route. At first sight this would make soBGP less secure than
> S-BGP, but it looks like S-BGP can't protect the entire path under all
> circumstances anyway. Also, soBGP is a more open protocol, which can
> easily be extended with additional security checks. And a big plus for
> soBGP is that unlike S-BGP, where the security information is stored in
> path attributes (which means you can easily bring down an existing
> router by sending it S-BGP info, no filtering on unknown attributes
> AFAIK), this information is exchanged using a new type of message.
> This makes it possible to offload the security processing to an external
> box.

S-BGP does detect and reject attempts to propagate unauthorized paths within
contiguous regions of ASes that use S-BGP. By this we mean that if an AS
tries to modify a path that has been passed to it by an AS executing S-BGP,
or to create a bogus path from scratch, other S-BGP ASes will detect the
tampering. So I am at a loss to understand the comment "but it looks like
S-BGP can't protect the entire path under all circumstances anyway."

The latest version of soBGP, according to a discussion with some Cisco folks
at the IETF in SF, will address the secure path vulnerability, not just
secure origin advertisements. However, soBGP is not an architecture, at this
time; it is really a collection of mechanisms. It is more "open" in that
some of the hard decisions have not been made. For example, I was told that
one could distribute digitally signed topology data via repositories, or via
some extension to BGP for inband distribution. I asked which mechanism was
the mandatory default, and the answer was neither. This does not ensure
interoperability, because if one AS decides to distribute this info only via
a repository, and other ASes decide to receive it only inband, the data will
not be propagated! There are several "you could do A or you could do B"
aspects to the soBGP design, which make it impossible to analyze completely,
or to compare with S-BGP, at least for now.

I don't understand the assertion about bringing down an S-BGP router based
on "sending it S-BGP info ...." If this is a reference to an implementation
vulnerability concern, then it needs to be addressed, as do the many other
implementation vulnerabilities that are present in routers today and which
make them vulnerable to flooding of UPDATEs or other management
traffic. Also, S-BGP can be implemented using an ancillary processor
associated with a router, an option we proposed several years ago, but which
was not well received by most operations folks. In soBGP, if the processing
is performed at some distant device, issues about availability of these
devices and timeliness of processing arise. One thing that any design should
avoid is a loss of sync between security data being propagated and UPDATEs
that are to be verified based on that security data.

> The problem with fully protecting the path (such as S-BGP wants to do)
> is that the only way to do this well is to have the source say which
> paths are good, but this is simply too much information. Without this,
> it becomes possible for someone who legitimately received the route to
> propagate it even though the source didn't intend this. Also, giving the
> source full control makes dynamic rerouting (like 9/11 emergency
> transit) much, much harder. Obviously we all want routes we know are
> good, and don't want routes we know are bad. That's wat S-BGP and soBGP
> can do. But what if we can't determine if routes are good or bad? If you
> reject the routes you break a lot of connecitvity. If you don't, nobody
> will bother jumping through all the hoops to make their route
> authenticity verifiable. I really don't envy the first operator to
> deploy (S-|so)BGP...

This paragraph seem to be just plain wrong. S-BGP relies on prefix "owners"
to announce origin ASes via a repository system, consistent with the fact
that these binding change slowly. S-BGP requires each AS along a path to
sign a route attestation as the means of authorizing the next hop AS(es) to
advertise the prefix(es) in the UPDATE. The reason S-BGP carries route
attestation data in UPDATEs is to match the dynamic characteristics of route
advertisements. Thus a 9/11 emergency or a Baltimore train tunnel fire can
be accommodated, merely by having the affected ASes sign new route
attestations and insert them into UPDATEs. This is precisely why we do not
include a repository distribution option for this data (as soBGP does),
since repository distribution would not be responsive enough for such
conditions.  Only if access lines from subscribers are lost and the
subscribers are rehomed to ISPs with whom they have had no prior
relationship would repository distribution of data (address attestations) be
involved. We have assumed that there are enough other hurdles to this sort
of rehoming that the repository mechanism would be viable. We did have a
facility for inband distribution of address attestations in emergencies, and
we could revive that feature, if it really is necessary.

There is no concept of "good" vs. "bad" routes in S-BGP. Only "authorized"
vs. "unauthorized." If by "source" Iljitsch means "origin AS" then there is
a disconnect between what BGP does and what is said here, since BGP in no
way suggests that an origin AS can control the advertisement of a route
beyond the immediate neighbors to which the route is advertised. S-BGP is
consistent with the semantics of BGP, as we understand them. if this is an
allusion to other path attributes, e.g., community info, then note that
S-BGP can provide protection for them too, selectively.

Steve