Subject: [tcpm] tcp-auth-opt issue: unique connection keys

From: Joe Touch <[email-masked]>
Date: Wed, 30 Jul 2008 15:42:38 -0700

Eric has raised the point that we should expect the TCP-AO system
(TCP-AO and its required key management system [KMS]) to ensure unique
connection keys.

draft-01 outlines the information that would be used to provide this
information (i.e., derivative of the ISN, etc.).

Eric raised concerns about whether this function can reasonably be
external to TCP-AO (e.g., inside the KMS) or inside the KMS, and about
the vagueness of the description. The current document was intended as a
starting point for that discussion, FWIW.

One observation is that the KMS manages keys for connections - i.e., the
socket pair (addr/port pair) - but has no info on ISNs. It can establish
keys for that socket pair in the TSAD, but cannot generate appropriate
session keys in advance of a connection being established.

Let's assume that the KMS includes the socket pair in the connection key
when it inserts it into the TSAD (or that this can occur trivially for
wildcard source port entries by re-hashing with the appropriate port
when the first packet instantiates the entry). As a result, the ISNs are
the only missing component to the connection key.

As was suggested before, use ISNs as follow:

	SYN (without ACK) - use src_ISN from SYN, dst_ISN=0
	all other packets - use src_ISN, dst_ISN from first SYN rec'd

There are (at least) two ways to achieve this:

1) prepend src_ISN, dst_ISN to each incoming packet for MAC calculation

2) overwrite the TSAD keys established by the KMS
	i.e., on first SYN emitted
		key=hash(key, src_ISN)
	on SYN-ACK received
		key=hash(key, dst_ISN)

#1 has the advantage that it appears to work for simultaneous open, in
which the SYNs are keyed based on different ISN info in each direction,
but are received properly

#2 reduces the per-packet cost by the length of two ISNs, by investing
in the hash at connection establishment. However, it appears to prohibit
simultaneous open. Can anyone suggest a solution that supports
simultaneous open?

- -----

Comments?
_______________________________________________
tcpm mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/tcpm

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 30 Jul 2008 17:18:09 -0700

At Wed, 30 Jul 2008 15:42:38 -0700,
Joe Touch wrote:
> 
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 

Why does this prohibit simultaneous open? Because you're assuming
that there's only one possible key for a given host/port quartet?

-Ekr

---

From: Joe Touch <[email-masked]>
Date: Wed, 30 Jul 2008 23:29:49 -0700

Eric Rescorla wrote:
| At Wed, 30 Jul 2008 15:42:38 -0700,
| Joe Touch wrote:
|> -----BEGIN PGP SIGNED MESSAGE-----
|> Hash: SHA1
|>
|> Eric has raised the point that we should expect the TCP-AO system
|> (TCP-AO and its required key management system [KMS]) to ensure unique
|> connection keys.
|>
|> draft-01 outlines the information that would be used to provide this
|> information (i.e., derivative of the ISN, etc.).
|>
|> Eric raised concerns about whether this function can reasonably be
|> external to TCP-AO (e.g., inside the KMS) or inside the KMS, and about
|> the vagueness of the description. The current document was intended as a
|> starting point for that discussion, FWIW.
|>
|> One observation is that the KMS manages keys for connections - i.e., the
|> socket pair (addr/port pair) - but has no info on ISNs. It can establish
|> keys for that socket pair in the TSAD, but cannot generate appropriate
|> session keys in advance of a connection being established.
|>
|> Let's assume that the KMS includes the socket pair in the connection key
|> when it inserts it into the TSAD (or that this can occur trivially for
|> wildcard source port entries by re-hashing with the appropriate port
|> when the first packet instantiates the entry). As a result, the ISNs are
|> the only missing component to the connection key.
|>
|> As was suggested before, use ISNs as follow:
|>
|> 	SYN (without ACK) - use src_ISN from SYN, dst_ISN=0
|> 	all other packets - use src_ISN, dst_ISN from first SYN rec'd
|>
|> There are (at least) two ways to achieve this:
|>
|> 1) prepend src_ISN, dst_ISN to each incoming packet for MAC calculation
|>
|> 2) overwrite the TSAD keys established by the KMS
|> 	i.e., on first SYN emitted
|> 		key=hash(key, src_ISN)
|> 	on SYN-ACK received
|> 		key=hash(key, dst_ISN)
|>
|> #1 has the advantage that it appears to work for simultaneous open, in
|> which the SYNs are keyed based on different ISN info in each direction,
|> but are received properly
|>
|> #2 reduces the per-packet cost by the length of two ISNs, by investing
|> in the hash at connection establishment. However, it appears to prohibit
|> simultaneous open. Can anyone suggest a solution that supports
|> simultaneous open?
|
| Why does this prohibit simultaneous open? Because you're assuming
| that there's only one possible key for a given host/port quartet?

The difference between #1 and #2 is that #2 overwrites the TSAD entries
with the hash. Yes, the issue with simultaneous opens is the need for
multiple keys per "host/port quartet" (can we call that a socket pair,
as per 793?).

<individual hat on>
We could also keep multiple keys just in case there's a simultaneous
open, until at least the SYN-ACK is received on a given side (at which
point we can drop the extra keys).

E.g.:
	origkey = as installed by KMS
	SYNkey = hash(origkey, src_ISN) computed when SYN is sent
		before an incoming SYN is rec'd (by either side)
	connkey = hash(origkey, src_ISN, dst_ISN)
		computed when the ack of the SYN is rec'd or
		an incoming SYN is ack'd

only the connkey can overwrite the origkey in the TSAD. for space
reasons, we don't want to keep too many keys around.

If we prepend the ISNs to the data, we avoid separate calls to the MAC
algorithm during the three-way handshake, but we keep reprocessing the
ISNs for each packet sent.
<individual hat off>

So at this point both #1 and #2 could support simultaneous opens. Which
method is preferable and why?

Comments?

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 31 Jul 2008 01:19:41 -0700

At Wed, 30 Jul 2008 23:29:49 -0700,
> reasons, we don't want to keep too many keys around.

This seems like unnecessary concreteness about the implementation.
The question isn't what's stored in the database but rather what
keys are used to protect the packets. Given that at least in the
manual key management mode the "origkey" is going to sit around
for years, it's a little weird to talk about it being "replaced".

> ISNs for each packet sent.

The performance advantage of either choice seem to be rather slight.

> method is preferable and why?

As I indicated in my previous comments, you could probably
cryptographically tolerate only one master MAC key and just use
differentiating prefixes rather than separate keys. Convention
is to use separate keys, though, in my experience, so this
probably requires less analysis. 

-Ekr

---

From: Joe Touch <[email-masked]>
Date: Thu, 31 Jul 2008 01:29:17 -0700

Eric Rescorla wrote:
...
|> The difference between #1 and #2 is that #2 overwrites the TSAD entries
|> with the hash. Yes, the issue with simultaneous opens is the need for
|> multiple keys per "host/port quartet" (can we call that a socket pair,
|> as per 793?).
|>
|> <individual hat on>
|> We could also keep multiple keys just in case there's a simultaneous
|> open, until at least the SYN-ACK is received on a given side (at which
|> point we can drop the extra keys).
|>
|> E.g.:
|> 	origkey = as installed by KMS
|> 	SYNkey = hash(origkey, src_ISN) computed when SYN is sent
|> 		before an incoming SYN is rec'd (by either side)
|> 	connkey = hash(origkey, src_ISN, dst_ISN)
|> 		computed when the ack of the SYN is rec'd or
|> 		an incoming SYN is ack'd
|>
|> only the connkey can overwrite the origkey in the TSAD. for space
|> reasons, we don't want to keep too many keys around.
|
| This seems like unnecessary concreteness about the implementation.
| The question isn't what's stored in the database but rather what
| keys are used to protect the packets. Given that at least in the
| manual key management mode the "origkey" is going to sit around
| for years, it's a little weird to talk about it being "replaced".

There is state in a few different places:

	KMS keys, which could persist for years in the static case

	connection keys, which persist only during the connection

In the above example, the question is how many keys are kept for a
single connection (i.e., is one stored and it overwritten, or are two
kept, etc.), or whether they are computed on-the-fly for every packet
that goes out.

|> If we prepend the ISNs to the data, we avoid separate calls to the MAC
|> algorithm during the three-way handshake, but we keep reprocessing the
|> ISNs for each packet sent.
|
| The performance advantage of either choice seem to be rather slight.
|
|> So at this point both #1 and #2 could support simultaneous opens. Which
|> method is preferable and why?
|
| As I indicated in my previous comments, you could probably
| cryptographically tolerate only one master MAC key and just use
| differentiating prefixes rather than separate keys. Convention
| is to use separate keys, though, in my experience, so this
| probably requires less analysis.

The differences in the alternatives discussed so far:

A- precomputed keys
	require additional per-connection key storage space

B- on-the-fly
	1- if ISN is hashed into the key used for a packet,
	this requires an additional full MAC computation
	per packet

	2- if ISN is prepended to the data, this requires
	a longer MAC computation

which of these is more efficient depends on:
	- saving computation vs. storage
	- the length of the connection

Overall, if this is encoded into TCP-AO, we need to encode (and fix as
static) this choice. We could extend the TSAD API to outsource this
issue, but (as Eric noted) this complicates the TSAD API.

Question to the WG:

	- is the WG comfortable selecting and fixing a mechanism
	for using the ISNs for key uniqueness inside TCP-AO,
	or would it prefer to push this to the KMS?
		(my impression is that keeping this inside TCP-AO
		seems to be preferable, please speak up if otherwise)

	- which of the above mechanisms is preferable?
	i.e., A, B1, or B2

Comments?

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 31 Jul 2008 01:44:08 -0700

At Thu, 31 Jul 2008 01:29:17 -0700,
> issue, but (as Eric noted) this complicates the TSAD API.

I must be missing something. Our job is to specify what bits go
into the MAC. Why do we have to specify when these computations
are done beyond that? It seems like implementations should be
allowed to make whatever time/space tradeoffs they feel are
most appropriate. In particular, why should we require one of
A and B(1), since they produce the same data on the wire?

It's worth noting at this point that implementations of HMAC often
adopt the time/space tradeoff of precomputing the first round of HMAC
computations (to digest the keys) and using that instead of the key.
If you were working with prepending ISNs, you might also include
the ISNs in that state. When we talk about key storage, I would hope we aren't
precluding that sort of optimization.

-Ekr

---

From: Joe Touch <[email-masked]>
Date: Thu, 31 Jul 2008 02:03:21 -0700

Eric Rescorla wrote:
...
|> The differences in the alternatives discussed so far:
|>
|> A- precomputed keys
|> 	require additional per-connection key storage space
|>
|> B- on-the-fly
|> 	1- if ISN is hashed into the key used for a packet,
|> 	this requires an additional full MAC computation
|> 	per packet
|>
|> 	2- if ISN is prepended to the data, this requires
|> 	a longer MAC computation
...
| I must be missing something. Our job is to specify what bits go
| into the MAC. Why do we have to specify when these computations
| are done beyond that? It seems like implementations should be
| allowed to make whatever time/space tradeoffs they feel are
| most appropriate. In particular, why should we require one of
| A and B(1), since they produce the same data on the wire?

Point taken. So then it's between A/B1 and B2.

| It's worth noting at this point that implementations of HMAC often
| adopt the time/space tradeoff of precomputing the first round of HMAC
| computations (to digest the keys) and using that instead of the key.
| If you were working with prepending ISNs, you might also include
| the ISNs in that state. When we talk about key storage, I would hope
we aren't
| precluding that sort of optimization.

It depends on whether that precomputation is impacted by the use of ISNs
in the MAC; that's the only reason there's an A/B1 vs. B2 difference
noted above. How we specify the computation may affect whether it can be
precomputed or needs storage/recomputation.

We can jump up to the level of specifying the computation only (which
allows implementation flexibility), but we need to know (AFAICT) the
impact on these optimizations and whether we care...