Is IPsec really unsuitable for BGP?

| Comments (5) |
One of the hot topics in IETF Security right now is how to fix/replace the aging TCP-MD5 (RFC 2385 mechanism for protecting BGP sessions. TCP-MD5 uses manually configured shared symmetric keys on both ends. One obvious approach is to use IPsec, but there's been a lot of resistance to that from the operators and the router vendors. At IETF 66, Brian Weis gave a talk trying to explain some of the concerns. Some of it makes sense, but in other places it represents a number of misunderstandings about cryptography and communications security.

The need for rekeying
Slide #8 argues that rekeying traffic keys is important. There are actually two issues here:

  1. Key exhaustion.
  2. Compromise recovery.

The key exhaustion issue is supposedly that you can't use the same cryptographic key to protect too much data. (Weis calles this "overuse"). This was true with old ciphers--lots of known plaintext gave cryptanalysts leverage. It's very slightly true for small-block block ciphers like DES, where you start to get small amounts of leakage at around 2^32 blocks (2^35 bytes) in CBC mode. Resistance to this kind of attack goes up with the block size so as a practical matter AES is immune (the limit is 2^64 blocks/2^68 bytes). As far as I know, this isn't a practical issue for MAC algorithms like HMAC-MD5.

The compromise recovery issue is real; whenever people who have access to the authentication keys quit you obviously have to worry about them posing as you. It wasn't entirely clear to me what Weis meant, but this problem can't be solved by rekeying the traffic keys because the attacker can impersonate you when forming a new connection with new traffic keys. You need to replace the authentication keys.

Pre-Shared Public Keys
Slide 9: If you want to use public key cryptography for session key establishment, there are two basic choices:

  1. Put the keys into some kind of PKI.
  2. Pre-shared public keys.

This talk argues that it's not practical to have all the keys for your BGP peers in a single PKI. I'm not convinced this is true, but it's mostly a religious issue and I mostly try to avoid arguing with people who have PKI allergy. I do want to address the pre-shared public key issue.

Weis's argument for why you can't have pre-shared public keys is:

  • Results in twice as many keys being exchanged in the secret key case
    • Routers may have a limited amount of NVRAM or flash available, and public keys are relatively large
The first statement is mostly correct. In order to establish mutual authentication between A and B using pre-shared public keys, you need an out-of-band exchange where A sends B his public key (or fingerprint) and vice versa. It's not clear why this is really a big deal. After all, people do this routinely with SSH public key authentication.

The second statement (about NVRAM) is basically wrong. It's of course true that public keys are generally larger than symmetric keys (actually, with elliptic curve cryptography you can have them only about 2-3 times as large as symmetric keys or even down to 25% larger if you're willing to have a shared group), but this fact is mostly irrelevant because there's no need to store the public keys in NVRAM. You can just store a digest of the public key, which need be no larger then the symmetric key you would otherwise have stored (as small as 80 bits is secure here under most reasonable assumptions). During the initial crypto handshake the peer provides its public key and you can compute the hash and compare it to the stored value. The only additional storage is your key pair which is order 200-500 bytes.

One real advantage of PK-based authentication that doesn't get talked about a lot is routine exposure of the keying material. If you use manual key mangement to share a symmetric key with a peer, the operators (i.e., the guy with access to the keyboard) pretty much necessarily has to know the symmetric key because he has to type it in. By contrast, if you use PK-based authentication then you never need to see the private key, which lowers the chance that it will get written on a post-it or sent around on a fax, thus lowering the exposure risk when employees leave. Sure, a malicious employee with the root password can usually get the key out of the router, but the router software can be designed to make this difficult and if necessary you can store the key in a hardware security module. This option isn't available with symmetric-key systems.

Performance of Public Key Cryptography
The other argument this presentation makes against public key is performance:

  • Public key operations are computationally expensive
    • Supporting public key operations from many peers requires customers to buy blades/boxes that they don't otherwise need.

I don't buy this argument. Remember that the underlying assumption here is that you're going to pre-configure your associations with all your peers (that's what you get when you don't use PKI or other central authentication systems). So, as a practical matter this limits you to no more than a thousand or so peers (the benchmark number on this slide is 1000). Any reasonable processor can do order 100 RSA-based key exchanges per second (this not very fast laptop will do 160). So, we're talking under 20 seconds of CPU time even under fairly pessimistic assumptions. And since this cost only needs to be incurred very occasionally (either when an authentication key changes or after a router reboot--and these are inherently very expensive even without the public key operations).

So what?
So, what point am I making here? Certainly it's quite possible that IPsec is inappropriate for an application like BGP. In particular, it's known that configuring IPsec can be fairly difficult and the UIs that vendors give you aren't anything to write home about. But I don't think the particular technical objections being raised here are very convincing.

5 Comments

As you say, the opex of deploying IPSEC on routers in even a moderately a sizable iBGP mesh is prohibitive; the opsec and logistical issues of deploying it with eBGP peers is also prohibitive. Also, SPs who've deployed MD5 keying tend not to change the keys once they've deployed it due to the opex and downtime associated with re-keying (there are newer features on most mainstream routers which allow for hitless rekeying, but SPs also don't update router OSes unless they've a compelling reason to do so, and after a long and thorough testing cycle).

With regards to the CPU impact of IPSEC, it's important to realize that even larger routers in many cases don't process IPSEC (and the requisite GRE tunnels inside the IPSEC) in hardware, but ratehr in software on the main system route processor - and even on platforms which offer hardware IPSEC and GRE processing, this functionality requires additional modules or blades which a) increase platform cost and b) often occupy a slot which could be used to terminate customer circuits or for other, more directly revenue-generating functions. So, the operational impact of doing this is also prohibitive in many cases.

Couple these factors with key-management hassles (although PKI is more widely deployed now than ever, one doesn't tend to find it much outside the defense and financial sectors), and it's pretty easy to see why IPSEC for BGP isn't something SPs are rushing to implement, and why both the sBGP and soBGP proposals are viewed as controversial by many.

One other comment - advocates of encryption for BGP (or any of the various IGPs, for that matter) haven't really made a clear case as to what the actual benefits of doing so really are. After all, if a miscreant is in a posiiton to listen to (and perhaps alter or inject) routing-protocol announcements in the first place, the network operator has bigger problems which simply encrypting the routing-protocol sessions won't address.

Authentication makes a lot of sense, and it's generally recognized as a BCP (although some take issue with the performance impact of TCP MD5 authentication on older platforms; again, SPs don't just upgrade routers unless they've a really good reason to do so, and previous-generation equipment is often grandfathered into various places in the topology once it has been superseded by newer hardware in the core, the peering edge, etc.). iACLs are also quite useful in restricting access to routing infrastructure from unauthorized nodes, and in combination with MD5 keying, is a BCP, as well.

I personally don't know of a single real-world security incident of any type which would've been avoided or mitigated in terms of impact by having encrypted sessions for any routing protocol. The only scenario which comes immediately to mind is perhaps listening to routing protocols in order to gain a clearer understanding of the network topology, but again, if an attacker is able to gain a foothold which would allow eavesdropping on routing protocol traffic in the first place, the network operator has problems which encryption of routing-protocol sessions won't address.

It seems to me that performance is irrelevant here. On any machine that might be involved in BGP, the overhead from doing all the crypto anyone could possibly want should be negligible. Even in software. And, once a session is established, IPsec should be no more expensive than the ad-hoc solution you have in place now.

Hoav - you are mistaken in your assertions about crypto overhead. The DoS vector it opens up (referred to in the presentation cited by Mr. Rescorla) is quite real.

The adversary can inject BGP messages? I thought we had big trouble if he could even read them. Now I am confused about the threat model. (Also, are we talking about DoS due to IKE overhead or to AH/ESP overhead?)

Leave a comment