Subject: [tcpm] question about TCP-AO and rekeying

From: Joe Touch <[email-masked]>
Date: Sat, 06 Jun 2009 11:46:11 -0700

Hi, all,

One open issue remaining is how to express what was formerly a database
with a particular structure (TAPD, previously TSAD) in ways that impact
rekeying and possibly future master key management protocols. We decided
at the last meeting in SFO to do as follows:

	- require that each segment match only one key
		- segments for established connections must match
		only one connection key
		- segments for new connections (SYNs) must match
		only one master key

Connection keys never overlap; there would never be two connection keys
with the same keyID and socket pair. The open issue focuses on master
keys, which would more likely be specified with wildcards, masks, or
ranges, esp. for remote port numbers, but also potentially for addresses
or local port numbers. This issue is particularly relevant for rekeying
- - adding new master keys that would result in new connection keys being
derived for existing connections - and how an endpoint would be able to
ensure uniqueness as above.

Do we need additional constraints to ensure that master key descriptions
never overlap?

As review, the previous description of keys as a database also implied,
by its structure, constraints on wildcards/masks/ranges. Each TAPD entry
was:

    a socket pair descriptor
        which may include wildcards or masks

    one or more MKTs, each of which includes:
        sendID
        recvID
        crypto info:
            master key
            MAC info
            KDF info

The TAPD was defined so that a segment matched at most one socket pair
descriptor, and that MKTs within that descriptor had distinct sendIDs
and recvIDs.

If we remove that data structure, it would most obviously be replaced
with MKTs with their own socket descriptors, i.e.:

    MKT
        socket pair descriptor (may include wildcards/masks)
        sendID
        recvID
        crypto info

The question that remains is whether MKTs that match a segment all have
identical socket pair descriptors, even down to their
wildcards/ranges/masks (which was previously required). If
not, then how do we ensure that MKTs don't interfere?

If we throw our hands up and say this is "implementation detail", then
IMO we could be hobbling any KMP, since there would be no common data
for the KMP to coordinate.

So how do we proceed? If we ensure that MKTs that all apply to a given
segment all share the same socket pair descriptor, why can't we call
that a data structure and describe it? (is the issue just that we call
it a database?) If not, how do we describe the MKTs so that we can
enable KMPs?

Please post thoughts to this list.

Thanks,

Joe

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 16 Jun 2009 06:18:06 -0700

At Sat, 06 Jun 2009 11:46:11 -0700,
Joe Touch wrote:
> 
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Hi, all,
> 

I don't understand why this is a problem. The invariant that
the system needs to enforce is that for any given packet 
there be at most one valid MKT with a given key-id, right?
There are a number of ways to enforce this, including:

1. Having some kind of database.
2. Tying MKTs to sockets directly at the time of instantiation
   (including half-open sockets).

> for the KMP to coordinate.

I don't see this. Obviously, any KMP will need some model for
how it thinks about keys and any particular implementation of
a KMP will need to interact with the system on which it is
implemented in order to match that model to the system's
implementation, but I don't see how that's a problem. It's
not like we're defining a C API for the KMP implementations
to call.

-Ekr

---

From: Joe Touch <[email-masked]>
Date: Tue, 16 Jun 2009 06:45:38 -0700

> there be at most one valid MKT with a given key-id, right?

KeyID doesn't come into play for outgoing packets, so we can ignore that.

However, the invariant is twofold:

	a) for a given packet, only one MKT applies

	b) for two endpoints with multiple MKTs,
	the *same* MKT applies.

The second invariant requires that either:

	a) no two MKTs have patterns that overlap

	b) MKTs are ordered identically on the two endpoints

If two endpoints solve this differently, a KMP could try to install the
same keys on the two ends and fail, either because one side would refuse
a new key (as overlapping), or because the two sides vary in how they
order the keys.

>    (including half-open sockets).

We need to ensure that both sides pick the same MKT. That needs to
happen at connection establishment (could be during socket
instantiation), but ALSO needs to happen for re-keying, FWIW. That
doesn't change the nature of the problem.

> not like we're defining a C API for the KMP implementations

If we don't specify some level of commonality, we can't expect to ever
define such an API.

Joe

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 16 Jun 2009 22:45:51 -0700

At Tue, 16 Jun 2009 06:45:38 -0700,
> 	b) for two endpoints with multiple MKTs,

I don't see that this is true. As I understand the current design
there's no reason that both sides can't use different MKTs
indefinitely.

> If we don't specify some level of commonality, we can't expect to ever

I don't consider the design of such an API in IETF 
either necessary or desirable.

-Ekr

---

From: Joe Touch <[email-masked]>
Date: Tue, 16 Jun 2009 23:24:55 -0700

Eric Rescorla wrote:
...
> there's no reason that both sides can't use different MKTs

Each side can use a different MKT to transmit. However, if side A uses
MKT X to transmit, then side B needs to know to use MKT X to receive. If
side A matches MKT X on transmit and side B matches MKT Y on receive,
then there's a problem for that connection.

So let's rephrase, recognizing that there are two MKTs at any given time
(one for transmit on each side, and the same pair for receive on the
opposite side).

b) for two endpoints, if a given packet matches MKT on one side during
transmit, it must match the corresponding MKT on the other side during
receive.

Joe

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 17 Jun 2009 07:09:39 -0700

At Tue, 16 Jun 2009 23:24:55 -0700,
> transmit, it must match the corresponding MKT on the other side during

Right, but this doesn't require ordering or non-overlapping, as far as
I can tell.  It merely requires that at any time there only be one MKT
corresponding to any given socketpair/key-id.
       
-Ekr

---

From: Joe Touch <[email-masked]>
Date: Wed, 17 Jun 2009 08:41:52 -0700

> corresponding to any given socketpair/key-id.

That is only possible with either non-overlapping or ordering to resolve
overlaps. Note that the MKT has to be unique for incoming packets given
a socketpair/keyid. For outgoing SYNs, the MKT has to be unique within
just a socketpair, because the keyid hasn't been determined yet.

If we prevent overlaps altogether, we may impact utility. We won't be
able to have things like:

	A -> B use MKT X

	A -> * use MKT Y

	* -> * use MKT Z

In this case, A->B matches all three, but having a default 'catchall'
can be very useful, if not expected.

If we allow overlap resolution, then we need to ensure that both sides
resolve to the same result.

Joe

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 17 Jun 2009 09:15:18 -0700

At Wed, 17 Jun 2009 08:41:52 -0700,
Joe Touch wrote:
> overlaps.

I don't see why this is true. Any time a new key is entered, you
find all other keys that overlap with it and verify that they
have distinct key-ids. If so, the entry fails. If that's what
you mean by "prohibit overlaps", yes, I think we should
prohibit overlaps. 

If what you mean is that two MKTs with different key-ids can't overlap
the same socket pair space, I don't see a problem with that.

-Ekr

---

From: Joe Touch <[email-masked]>
Date: Wed, 17 Jun 2009 09:20:07 -0700

Eric Rescorla wrote:
> have distinct key-ids.

That is a very expensive operation that I am hoping we can avoid.

> If so, the entry fails. If that's what

That is a problem for outgoing SYNs. For those, either the connection
has to know a-priori which ID to use, or we need to make sure MKTs can't
overlap at all (ignoring keyIDs).

The former (connection knows the ID requires apps be rewritten to select
the ID before the SYN is sent. I hope we don't expect apps to be
rewritten to use TCP-AO on their connections.

The latter (MKTs don't overlap socket pairs at all) defeats the use of
less specific MKTs as a catchall, and more specific MKTs within that.
This means more constraints than just "one packet -> one MKT", e.g., it
may require that MKTs overlap only as subsets (which is efficient to check).

Joe

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 17 Jun 2009 16:28:13 -0700

At Wed, 17 Jun 2009 09:20:07 -0700,
> That is a very expensive operation that I am hoping we can avoid.

It's not a very expensive operation unless you have a truly
fantastic number of keys, which can only happen if you
have an automatic key management protocol which can 
be designed not to create this situation. 

> overlap at all (ignoring keyIDs).

I'm sorry, but I don't see why. 

-Ekr

---

From: Joe Touch <[email-masked]>
Date: Wed, 17 Jun 2009 21:52:16 -0700

> I'm sorry, but I don't see why. 

So let's consider outgoing SYNs.

Consider a system with two MKTs:

	MKT alpha	from ANY:ANY to JOE:80	KEYID=4

	MKT beta	from ANY:ANY to ANY:ANY	KEYID=5

So my web client wants to connect to JOE:80. The web client has not been
modified to indicate a desired KEYID; I doubt many apps will be so
modified. So I'll need to ensure that the socket pair of the SYN matches
only one MKT.

That means I can't have default keys, like beta.

So what I'm wondering is whether we:

	a) require MKTs to be unique per {socketpair,ID} tuple

	b) require MKTs to be unique per socketpair

We either need (b), or we need something else that says "first match"
and establishes an ordering to MKTs, or "best match", etc.

Joe

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 17 Jun 2009 22:16:22 -0700

At Wed, 17 Jun 2009 21:52:16 -0700,
> That means I can't have default keys, like beta.

Why on earth would you want to do this? The misquote Dr. Strangelove,
"the whole point of a cryptographic key is lost unless you keep it
a secret. Why would you tell the world?"

Since almost every other machine on the Internet isn't going to 
have key beta, you're going to get packets that aren't protected
with AO, in which case you'll have to discard them. Configuring
your system this way is mostly useful for breaking TCP.

-Ekr

---

From: Joe Touch <[email-masked]>
Date: Wed, 17 Jun 2009 22:19:30 -0700

Eric Rescorla wrote:
> your system this way is mostly useful for breaking TCP

It's a bit overgeneralized above, but clamp it down a bit more and it
might still make sense, e.g.:

	alpha		from ME:ANY to JOE:BGP KEYID=6
	beta		from ME:ANY to JOE:ANY KEYID=7

I.e., I may want to lock BGP with a different key than other connections
between the two, but OK to use a single key for the rest.

Joe

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 18 Jun 2009 06:57:20 -0700

At Wed, 17 Jun 2009 22:19:30 -0700,
> between the two, but OK to use a single key for the rest.

Why would you want to do this?

The configuration you propose would still leave you vulnerable to
packet injection by someone who knew key alpha. 

Going up a level, I'm skeptical of this entire line of argument.
The existing rationale for this technology (BGP DoS prevention)
doesn't really justify engineering for extensively complicated
key use policies.

-Ekr

---

From: Joe Touch <[email-masked]>
Date: Thu, 18 Jun 2009 07:08:29 -0700

Eric Rescorla wrote:
...
> doesn't really justify engineering for extensively complicated

The policy above would be used to utilize a stronger key/algorithm for
BGP, and a weaker one for other exchanges - such as would be used to
protect the transport of other protocols used in tandem with BGP, e.g.,
SNMP or DNS (each over TCP).

I agree that non-overlap is necessary to avoid injection. The trouble is
that there are different ways to avoid non-overlap which we are
currently leaving as "implementation dependent". If we leave them open,
I am concerned that KMPs will not be able to ensure that two endpoints
will pick corresponding MKTs for a given segment.

If we all want to leave that open, that's fine. IMO probably means KMP
is DOA, but that may be where this is all headed anyway.

Joe

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 18 Jun 2009 21:33:28 -0700

At Thu, 18 Jun 2009 07:08:29 -0700,
> SNMP or DNS (each over TCP).

Well, remember that this technology really only makes sense as 
an anti-DoS measure. Otherwise you might as well use TLS.
So, I'm not overly concerned with the idea that people want
to use it as a generic communication protection measure for
arbitrary TCP-based protocols *and* that they want to
use this clumsy a key management scheme.

> will pick corresponding MKTs for a given segment.

Really? I would imagine this is precisely the invariant that some
putative KMP would enforce.

-Ekr

---

From: Joe Touch <[email-masked]>
Date: Thu, 18 Jun 2009 23:39:12 -0700

Eric Rescorla wrote:
...
> putative KMP would enforce.

If that's where we put that logic, what happens when we don't have a
KMP? How do we know that both ends will do the same thing with a set of
manually entered keys?

Joe

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 19 Jun 2009 06:21:34 -0700

At Thu, 18 Jun 2009 23:39:12 -0700,
> KMP? How do we know that both ends will do the same thing with a set of

It was my understanding that the consensus was that we were not 
going to design a system that attempted to prevent user error.

Given that typographical errors in key entry seem far more likely
than this kind of misconfiguration, if our intent is to prevent
user error, then we should be attacking that first.

-Ekr

---

From: Joe Touch <[email-masked]>
Date: Fri, 19 Jun 2009 08:40:26 -0700

Eric Rescorla wrote:
...
> going to design a system that attempted to prevent user error.

Oh, absolutely, agreed.

This is the kind of error where two ends install the keys correctly, but
internally the two implementations resolve overlap in different ways, so
keying fails.

> user error, then we should be attacking that first.

As above, this isn't a user error issue. This is a case where leaving
something to the implementer is what is causing the problem.

Joe

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 19 Jun 2009 09:16:14 -0700

At Fri, 19 Jun 2009 08:40:26 -0700,
> something to the implementer is what is causing the problem.

Then I don't understand what you're talking about.

The user installs two MKTs, one of which covers all ports and
one of which covers port 521 (randomly chosen). Either of these
MKTs is valid and either end can use either one to secure
the connection independently. It doesn't matter what the
prioritization schemes are on either end.

If you're saying that the installation of a more specific MKT
should not only take priority over but actually disable a
less specific MKT for that port, then I think that's a pretty
clear bug.

-Ekr

---

From: Joe Touch <[email-masked]>
Date: Fri, 19 Jun 2009 09:26:22 -0700

> prioritization schemes are on either end.

If we just require that each segment maps to exactly one MKT, then one
end can do this by:

	- first entered, first picked

The other end can do this by:

	- longest match

So both sides are complying with "match only one MKT", but users can
easily install keys on both ends that would still not work.

> less specific MKT for that port, then I think that's a pretty

I'm saying that the way in which we resolve overlapping MKTs matters.

a) disallow entry of overlapping MKTs

	this means that valid MKTs for a connection might not
	be able to be entered if there are more general
	keys entered

	this also incurs computation during key entry (manual
	or otherwise); is there a standard efficient alg. for
	determining overlap? Note that we could be talking about
	masks, ranges, etc.

b) allow overlapping MKTs

	this means we need to indicate the resolution mechanism
	i.e., longest match, ordered match, etc.

Joe

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 19 Jun 2009 09:47:24 -0700

At Fri, 19 Jun 2009 09:26:22 -0700,
> 	i.e., longest match, ordered match, etc.

OK, I fear we're talking past each other.

My claim is that the system must enforce the following invariant:

* There must be only one MKT defined that matches any given set
  of parameters: (s-ip, d-ip, s-port, s-port, key-id).

This includes wildcards and ranges.

Therefore there is never any ambiguity about which MKT a given
packet is associated with. The only ambiguity is which MKTs
an outgoing packet might be protected with, because of priority.
However, those MKTs will always have distinct key-ids so there
is no confusion.

I believe that that corresponds to your choice (a). However,
I don't see either of the issues you raise as problems:

- If you have a more general MKT that matches a connection,
  you can enter a new MKT that is more specific. It merely
  must have a new key-id. This is just a generalization of
  how you update keys with the same level of specificity.

- I'm not concerned about the computational cost at key 
  entry. Checking whether a new MKT has overlap with an
  existing MKT is a linear process in the number of 
  existing MKTs [*]. It's certainly not going to be a 
  problem with the number of keys you can plausibly manually
  enter. I agree that it would be nice if the KMP prevented
  this intentionally, rather than having a check at 
  installation time. 

In any case, I don't really see how we can get away from
doing this kind of checking. Let's say for the sake of
argument that we *never* allowed ranges. I.e., all 
MKTs had to be fully specified or be a wildcard. Even
then you'd need to do a table lookup to verify that
no two MKTs exactly matched each other including key-id.

-Ekr

[*] At worst. You can actually do much better using good
data structures.

---

From: Joe Touch <[email-masked]>
Date: Fri, 19 Jun 2009 10:06:36 -0700

Eric Rescorla wrote:
...
> This includes wildcards and ranges.

That one is a lot easier, since you're including the key-id. That's
available only for either established connections (e.g., bound to the
socket after connection establishment for outgoing, or indicated in the
segment for incoming).

For the initial outgoing SYNs from legacy applications, we need the MKT
match to be unique per:

	(s-ip, d-ip, s-port, d-port)

This is the case that's causing the problem for two cases:

a) overlapping MKT patterns, as would be used for catch-alls vs. more
specific patterns (which we could prohibit, but I would like to try not to)

b) identical MKT patterns, as would be used when a a primary and backups
are added

The TSAD/TAPD had a notion of grouping MKTs together when patterns
overlapped, so that (b) would allow selection of a 'currently designated
primary' to be used for outgoing SYNs. Getting rid of that structure -
which you claimed was an implementation issue - is omitting structure in
the key groupings that allows (b), and also enables (a).

If we omit the TSAD/TAPD, how do we express the notion that a given key
is preferred for outgoing SYNs?

Joe

---

From: Eric Rescorla <[email-masked]>
Date: Sat, 20 Jun 2009 08:35:48 -0700

At Fri, 19 Jun 2009 10:06:36 -0700,
> This is the case that's causing the problem for two cases:

You've said that before, but I don't understand why you think it's a
problem. If there are two valid MKTs for a given packet, each side can
pick whichever one they want independently and everything will work.

The match only needs to be unique in the sense that you can't protect
a single packet with two keys. It does not need to be unique and
deterministic in the sense that each side needs to be unambiguously
determine that the *same* key applies to each packet.

> is preferred for outgoing SYNs?

We don't. The implementations do it however they want (and I can think of
a number of plausible implementations) . As long as a valid key is selected,
things will work.

-Ekr

---

From: "Eddy, Wesley M. (GRC-MS00)[Verizon]" <[email-masked]>
Date: Mon, 22 Jun 2009 12:16:16 -0500

Since this thread has turned into ping-pong between Joe and
Eric, I'll break that pattern by putting in my assessment as
a WG participant ...

I think Eric's explanation that if multiple MKTs can be
matched to the outgoing SYN, then we can pick from them in
an implementation-dependent way, as long as we pick one key,
makes sense.  Yes, we can add complexity to disambiguate
how that selection is made as part of our spec (TSAD/TAPD),
but after reading the thread, I don't see clear value in that.

---------------------------
Wes Eddy
Network & Systems Architect
Verizon FNS / NASA GRC
Office: (216) 433-6682
---------------------------

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 22 Jun 2009 11:09:09 -0700

At Mon, 22 Jun 2009 12:16:16 -0500,
> but after reading the thread, I don't see clear value in that.

I note that if we don't like this, then the problem isn't 
particular to overlap. Even if we only allowed exact matches
and prohibited overlap, we still have the question of how
to deal with two keys that have been inserted for the same
connection. For instance, say we have some connection
which is operating on key A.

Then Alice injects B and C in that order. Bob injects C and B
in that order. I thought we'd agreed that that was OK and that
we were happy to end up with a setting in which we had C in
one direction and B in the other. If not, we need some 
more sophisticated ordering rule.

-Ekr

---

From: Joe Touch <[email-masked]>
Date: Mon, 22 Jun 2009 14:17:59 -0700

> but after reading the thread, I don't see clear value in that.

That's fine - as per my other post that's in my outbox queue.

Joe

---

From: Joe Touch <[email-masked]>
Date: Mon, 22 Jun 2009 10:59:12 -0700

Eric Rescorla wrote:
...
> a number of plausible implementations) . As long as a valid key is selected,

OK. I'll update the doc based on the descriptions of this exchange shortly.

Joe