Subject: Re: Last Call: 'Key Change Strategies for TCP-MD5' to Informational RFC (draft-bellovin-keyroll2385)

From: Fred Baker <[email-masked]>
Date: Mon, 2 Oct 2006 15:20:49 -0700

From my perspective, this draft sounds a lot like what Ran and I  
wrote for RIP key rollover a long time ago, but it is stated in  
simpler language. I like it from that perspective, and would suggest  
that it be generalized away from being specific to TCP-MD5, and made  
available to any such procedure (including IPSEC and others) that  
might include it by reference.

I would suggest that a key in the list actually has two timestamps  
(virtual or actual) associated with it - a point in time where the  
sender should start using it, and a point in time at which the key  
should be deleted from the list (eg neither send nor accept). The  
biggest problem I see in the algorithm as stated is that only one key  
is ever in use - when the sender starts sending the new key, it stops  
using the old key, and if the other guy hasn't been configured with  
it yet (as Iljitsch supposes) the connection immediately goes plop.  
What one wants to happen is more like the following.

Consider two systems interconnected by some protocol - an IPSEC SA,  
TCP, whatever. Let's call them Alice and Bob, and assume that all  
statements made about Alice and Bob are true of Bob and Alice - basic  
commutivity.

Alice has a list of keys consisting of some number of tuples - a key,  
a start date/time, and a delete date/time. Alice considers a key in  
the list to be "active" if its start time is in the past and its  
"delete" time is in the future. Bob has a similar list. In  
implementation, Alice may have one master list or separate lists per  
authorized peer - not my problem.

Whenever Alice sends a message (a TCP segment, a datagram within a  
IPSEC SA, whatever) to Bob, she sends the message as many times as  
necessary to use all active keys. In other words, if there are two  
active keys and she is using them for TCP, she sends the same TCP  
segment twice, once signed with one key and again signed with the  
other. One hopes that in the general case there is only one active  
key, and during a roll-over interval, there are two.

When Bob receives such messages, he checks them against all keys  
deemed to be active, and discards those that he doesn't accept.

In the general case, there is only one active key and they agree on  
it, so things work. During key rollover, there is presumably a period  
during which only Alice believes that there are two active keys, a  
period in which only Bob believes there are two active keys, and a  
period during which both Alice and Bob believe that there are two  
keys active. While Alice believes that there are two keys active, she  
will duplicate every relevant messages she sends. For the purposes to  
which we put TCP-MD5, one would expect that this should not be a  
heavy load, in either computation or bandwidth. Following your MRU  
algorithm, Bob's workload increases while both believe that there are  
two active keys, but that goes away when Alice stops sending using  
the old key.

An optimization could be done in Alice - if Alice believes that there  
are two active keys and is sending with both the new and the old, and  
accepts a message using the new key from Bob, she could decide that  
she no longer needs to send using the old. Stated more generally (N  
active keys, one of which is "old"), should Bob start using (and  
therefore Alice start receiving from Bob) an active key other than  
old key, Alice stops sending using the N-1 other keys and only uses  
the new key that Bob "selected".

I think the "delete" timer addresses the security issues ("what if  
Bob never gets it sorted out - should we still trust him?").  The  
duplicate traffic during the inevitable rollover period in which the  
two disagree on state addresses the operational issues that Iljitsch  
raised ("what if Alice starts sending at a time that Bob is unable or  
unwilling to receive using the new key - I don't want to lose  
connectivity through a misconfiguration"). The proposed optimization  
is unnecessary but attractive, especially if one is asking "but what  
about the duplicate traffic - isn't that a problem?". Traffic  
duplication can in this way be limited to a few messages in the  
immediate vicinity of the key rollover event, ideally within an RTT.  
Imagine both Alice and Bob decided a new key was active  
simultaneously - to the microsecond. I should think that the next  
time one of them sent a TCP segment, he/she would send two, the Ack  
would go back using the new key, and it would be over. More  
realistically, the duplicate traffic might last for a few seconds,  
perhaps a few minutes, or (Iljitsch's time zone question) an hour.  
But one could configure an overlap period of 12 hours, and know that  
it would be contained to as small an interval as possible.

_______________________________________________
Ietf mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ietf

---

From: "todd glassey" <[email-masked]>
Date: Mon, 2 Oct 2006 15:45:48 -0700

----- Original Message ----- 
From: "Fred Baker" <[email-masked]>
To: "Steven M. Bellovin" <[email-masked]>
Cc: "Iljitsch van Beijnum" <[email-masked]>; <[email-masked]>;
<[email-masked]>
Sent: Monday, October 02, 2006 3:20 PM
Subject: Re: Last Call: 'Key Change Strategies for TCP-MD5' to
InformationalRFC (draft-bellovin-keyroll2385)

> might include it by reference.

Fred -

> (virtual or actual)

Depending on how the policy model defines 'virtual timestamps' - they by
that may need more actual data in the 'stamp' itself than a single signed or
secured point in time.

> associated with it - a point in time where the
> should be deleted from the list (eg neither send nor accept).

You need one for the creation of the KEY too. You actually want three at
minimum and if the KEY is to be allowed a period of validity sometimes four
time stamps can be useful for specifying that range.

> The

---

From: Jefsey_Morfin <[email-masked]>
Date: Tue, 03 Oct 2006 01:18:52 +0200

I like it. Any security issue in having the same content sent twice 
with old and then new key?
jfc

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Mon, 2 Oct 2006 22:17:23 -0400

> with old and then new key?

Probably not a problem for an authentication-only key.  If it were a
secrecy key, there'd be some cause for concern, though using a different
IV would mitigate it somewhat.

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 3 Oct 2006 12:36:28 +0200

On 3-okt-2006, at 0:20, Fred Baker wrote:

This is also a good way forward, and it has the advantage that it's  
more general than my suggestion which requires changes to the client  
protocol.

> should be deleted from the list (eg neither send nor accept).

I don't quite see what happens when the new key isn't present on both  
systems and timestamps start to expire, but that should be solvable  
in one way or another.

Suggestion: don't start sending ALL traffic with all keys, just throw  
in a copy of a packet signed with the new key once in a while and  
keep using just the old key for most traffic until a packet with the  
new key is received from the other side.

---

From: Fred Baker <[email-masked]>
Date: Tue, 3 Oct 2006 04:41:11 -0700

On Oct 3, 2006, at 3:36 AM, Iljitsch van Beijnum wrote:

> I don't quite see what happens when the new key isn't present on  
> both systems and timestamps start to expire, but that should be  
> solvable in one way or another.

The purposes of the TCP-MD5 protocol is to ensure that two TCPs that  
don't have the same keys can't communicate. I think it accomplishes  
that, sooner or later.

Your concern is that it might be too frisky getting there. I'm  
proposing that you be in control of how quickly you get there by how  
you set the "delete" timer.

> Suggestion: don't start sending ALL traffic with all keys, just  
> throw in a copy of a packet signed with the new key once in a while  
> and keep using just the old key for most traffic until a packet  
> with the new key is received from the other side.

Well, one approach to my "optimization" would be start sending all  
new traffic with the new key, but retransmit with the old key. That  
*does* require at least an operational change to the protocol  
implementation, although not a change to the protocol itself. It also  
means that during the period that only Alice thinks there are two  
active keys, we can't move very quickly.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 3 Oct 2006 14:19:08 +0200

On 3-okt-2006, at 13:41, Fred Baker wrote:

> The purposes of the TCP-MD5 protocol is to ensure that two TCPs  
> that don't have the same keys can't communicate. I think it  
> accomplishes that, sooner or later.

> proposing that you be in control of how quickly you get there by  
> how you set the "delete" timer.

Well, sure, if your intent is to make sure you stop communicating  
with your peer when they don't implement a new key, that will  
certainly work.

My concern is the case where this happens by accident because of some  
operator error or miscommunication between the two ASes involved.  
What happens today in this case is that the session goes down  
immediately after the operator configures the new key. This means the  
issue can be resolved rightaway.

In a system where old keys are retired at some point in time AFTER  
the configuration change, it's much harder to resolve any issues.  
This is made worse by the fact that the time when the problem occurs  
can't be predicted reliably: you never know whether your timestamp  
will determine the change or the one set by the other side, and if  
the other side didn't put in the right key they could also very  
easily have put in the wrong timestamp, even without NTP or timezone  
problems.

So I think most operators would prefer to do a key rollover where the  
old key remains valid indefinitely and is removed manually rather  
than automatically after some time.

>> throw in a copy of a packet signed with the new key once in a  
>> while and keep using just the old key for most traffic until a  
>> packet with the new key is received from the other side.

> new traffic with the new key, but retransmit with the old key.

This is exactly the kind of complexity that is best avoided... It  
would be much better to have the key rollover mechanism function  
autonomously without having to be aware of higher layer state.

---

From: Fred Baker <[email-masked]>
Date: Tue, 3 Oct 2006 06:07:36 -0700

On Oct 3, 2006, at 5:19 AM, Iljitsch van Beijnum wrote:

> So I think most operators would prefer to do a key rollover where  
> the old key remains valid indefinitely and is removed manually  
> rather than automatically after some time.

Somehow I can't imagine any real implementation NOT having this  
capability. So you set the delete timer for "next year"... You're in  
control of it.

I guess I'm making a suggestion, and if it is not reasonable then  
Steve and his working group have to decide that. You raised a  
concern, that the roll-over procedure could cause unintended outages.  
I suggested an approach that doesn't cause unintended outages and  
puts you in control of what your network does.

What it sounds like you're arguing for is turning the procedure off,  
doing the change manually with the other operator on the phone, and  
taking the outage when if happens. If that is indeed what you want,  
then I think you want a nerd-knob that will allow you to choose your  
destiny by turning the procedure off. For the rest of the world, I  
can think of folks that change keys on a daily or weekly basis, or at  
least tell me they do, and are really in hope of a way to automate  
that in a reliable fashion. I think Steve is trying to accomplish  
that for them; I certainly am.

Yes, by the way - the folks I'm thinking of are indeed concerned that  
equipment that used to be under their control might become available  
to someone else. In such a case, they would prefer that the keys be  
destroyed and that communication cease.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Tue, 3 Oct 2006 20:17:48 +0200

> capability. So you set the delete timer for "next year"... You're  
> in control of it.

That sounds good, especially if the default is "infinity".

> Steve and his working group have to decide that.

I don't think Steve has a working group for this.

> What it sounds like you're arguing for is turning the procedure  
> off, doing the change manually with the other operator on the  
> phone, and taking the outage when if happens.

You mean like how things are done today?  (-:

Actually I proposed something else in my original message in this  
thread and also earlier in a message to Steve, on the NANOG list  
IIRC: have BGP speakers announce to the other side that they have a  
new key along with a hash over the key and when both sides have the  
same new key, do the rollover without delay. This means the rollover  
always happens when the new key is configured on the second end but  
only if the keys match.

In any situation where it's possible that both ends set up different  
keys, I believe it's important to have the resulting outage happen  
immediately rather than later. BGP already provides plenty of ways to  
shoot yourself in the foot, we should take care not to introduce new  
ones.

> I can think of folks that change keys on a daily or weekly basis,  
> or at least tell me they do, and are really in hope of a way to  
> automate that in a reliable fashion.

Well, my expience is pretty much the opposite: in the commercial ISP  
world here in Europe, key changes are rare. Nevertheless, "reliable"  
is the operative word here.

If a key change is required this often, wouldn't it make more sense  
to protect the BGP session with IPsec? That is vastly superior to TCP- 
MD5 in all respects other than ease of initial setup.

---

From: Joe Abley <[email-masked]>
Date: Tue, 3 Oct 2006 14:39:16 -0400

On 3-Oct-2006, at 14:17, Iljitsch van Beijnum wrote:

> Well, my expience is pretty much the opposite: in the commercial  
> ISP world here in Europe, key changes are rare.

ISC has deployed (I think) almost 40 nodes of F now across six  
continents, and there's peering at pretty much all of those  
locations. That adds up to a fair number of sessions.

Those who look after those nodes now on a daily basis might report  
different recent experience, but when I was doing that work I don't  
believe I ever saw a request from a peer to change a key on a working  
session.

So, your experience in Europe matches my experience in Europe, Asia,  
North America, South America, Australasia and Africa.

Having said that, I certainly support the idea that changing keys is  
a good idea, so long as people continue to use the TCP MD5 option on  
their BGP sessions. Mechanisms to make it easier to change keys are  
surely a good idea in that context.

Whether or not the TCP MD5 option is worth using at all is a  
different question.

Joe

---

From: Pekka Savola <[email-masked]>
Date: Wed, 4 Oct 2006 13:13:22 +0300 (EEST)

On Sat, 30 Sep 2006, Iljitsch van Beijnum wrote:
>> The IESG has received a request from an individual submitter to consider
>> the following document:
>
>> - 'Key Change Strategies for TCP-MD5 '
>>   <draft-bellovin-keyroll2385-03.txt> as an Informational RFC
...
> The problems start when BOTH sides implement the new mechanism. In that case, 
> new keys will remain unused for some time, and then become active at some 
> hard-to-determine time in the future. (Neither side knows for sure when the 
> other side will switch to the new key.) This means that there will be a 
> problem in the case where the new key isn't present on both sides, for 
> instance because one side wasn't configured with the new key in a timely 
> fashion, despite out-of-band agreement to do so, the keys configured on both 
> sides don't match.

Having read the draft, I do have similar concerns with "double-ended" 
operations.  The draft mentions that the new key should only be used 
when it's "at a point where it is reasonably certain that the other 
side would have it installed, too".  This is not very exact language, 
and I wonder how implementations would handle this.  Some other parts 
of the document also include suggestions which may make it harder to 
test the interoperability of various different mixes of 
implementations.

One possibility could be that an implementation once it's configured 
with a new key MUST always immediately send a TCP probe to figure out 
whether the other end supports the configuration key.  This ensures 
that at least one operator is still on-line when a key change occurs.
If not, go to dormant mode, waiting for the other end to probe.

A TCP probe should be something that will be acknowledged without 
extra code if received with a working key, but which does not need to 
be retransmitted with a different key if it fails.  An example of this 
would be an additional KEEPALIVE BGP message (which would be 
application-specific), a TCP SYN to the application port (where you 
terminate the probed connection after it was established) or something 
similar.

I'm also not sure if the time interval to change the key would be 
needed.  The only benefit is failure to change the session to a new 
key within that period would trigger some kind of alert.  But if the 
implementation already reports which keys are used and when, the 
operators could just monitor whether a change took place or not. In 
any case, a working BGP session with the old key is always better than 
a failed BGP session with a new key.

FWIW, we haven't seen the need to ever change TCP-MD5 keys either. 
This feature has likely been requested by networks which fail to 
fulfill the assumptions of [1], i.e., they do not have filtering [or 
GTSM] capabilities at edges and hence the attack vector to send 
TCP-RST to the network's BGP sessions is basically the whole world.

[1] draft-savola-rtgwg-backbone-attacks-02.txt

-- 
Pekka Savola                 "You each name yourselves king, yet the
Netcore Oy                    kingdom bleeds."
Systems. Networks. Security. -- George R.R. Martin: A Clash of Kings

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Wed, 4 Oct 2006 10:30:22 -0400

On Wed, 4 Oct 2006 13:13:22 +0300 (EEST), Pekka Savola <[email-masked]>
wrote:

> and I wonder how implementations would handle this.

My intention, actually, was that operators would do that.  "Attention
customers: we will be installing the 2007 BGP key on January 15.  Please
install the new key on your end before then." -- and then you actually do
your end on Jan 20 or thereabouts.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 5 Oct 2006 13:34:52 +0200

> your end on Jan 20 or thereabouts.

My perspective:

First of all, you NEVER want to bother a customer with requiring some  
kind of change from them. It sucks up unbelievable amounts of time  
and effort that are better spent elsewhere. Second, in this case,  
when the customer connection is reset or redirected by an attacker,  
that's the customer's problem, not the service provider's problem. So  
it's the customer who should decide if and when key changes need to  
happen, not the service provider. Third, you never want to say to a  
customer "we are going to make a change, as of this date you can do  
such-and-such". What you want to do is make the change on your end  
BEFORE informing the customer (in cases where both ends must change  
and one end can change without problems first, such as in this  
example). Then, the customer can make the change at their end  
immediately when they get your message. Last but not least, if you  
say you're going to remove the old situation so that they'll be down  
if they haven't made the change at their end at that point, you do  
this on the date that you announce, so that they can correlate any  
problems with the announcement. (All of this assumes that you have a  
reliable and secure way to communicate with the right people in the  
customer organization by the way, which isn't always the case.)

As a customer, I would want to be the one that sees the change happen  
when I'm logged in to the router, so I'd probably say to the service  
provider that I want to change keys and please let an engineer call  
me when she or he is ready to make the change so I can monitor from  
my side. But I'd probably install the new key beforehand so that if  
they don't call me and make the change anyway, the session stays up.

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Thu, 5 Oct 2006 11:46:20 -0400

...

I don't know that I agree with the details of your scenario, but that's
irrelevant to my larger point: it isn't the implementation that decides,
it's people.

I also agree that it's better that everything be completely automated.  As
the I-D says, this is advice on an interim solution until we can engineer
and deploy something better.

---

From: Iljitsch van Beijnum <[email-masked]>
Date: Thu, 5 Oct 2006 20:15:22 +0200

See my reply below, but all in all, I think it would be a good idea  
to either find a working group or create a list with security,  
transport and inter-domain routing people and people who actually  
implement this stuff and work on this to make it as good as it can be  
without losing sight of the goal of providing something that's better  
than we have today that can be implemented in the short term.

> irrelevant to my larger point: it isn't the implementation that  

Sure. If people want to do this in the manner that you describe, who  
am I to object to that, unless I'm a customer. Obviously I can't  
speak on behalf of anyone else, but I'm pretty certain that my  
scenario is closer to what most people in the commercial BGP speaking  
world do than the one that you described. However, my scenario  
doesn't fit well with the mechanism outlined in the draft.

> and deploy something better.

Yes, you've said this before. However, I don't find the draft as it  
is now acceptable, because it can make operational problems persist  
for much longer than they would in the absense of this mechanism.

I've outlined a solution to this, which, in my opinion, wouldn't  
delay implemenation of the mechanism. Yes, it would mean adding some  
BGP exchanges, but since implementation of the mechanism as outlined  
in the draft already requires touching the TCP-MD5 code and the  
addition of new configuration options, I don't think this is much of  
an extra burden.

Alternatively, there's Fred's suggestion, which doesn't require  
touching BGP although some details need to be worked out to make sure  
there are no ill side effects.

---

From: Pekka Savola <[email-masked]>
Date: Thu, 5 Oct 2006 22:42:10 +0300 (EEST)

On Thu, 5 Oct 2006, Iljitsch van Beijnum wrote:
> implement this stuff and work on this to make it as good as it can 
> be without losing sight of the goal of providing something that's 
> better than we have today that can be implemented in the short term.

FWIW, a list already exists (it hasn't been very widely announced) but 
has been very low volume lately.

https://rtg.ietf.org/mailman/listinfo/bts