Subject: Re: [saag] [Cfrg] Re: TCP-AO MAC algorithms

From: Sean Shuo Shen <[email-masked]>
Date: Wed, 02 Jan 2008 12:41:44 +0800

Hi, Joe

>> 
>> 1. interface:
>> I agree that MAC interface without a nonce may make implementation
easier.
>> But nonce may not expand the size of MAC because it can be generated by
both
>> sides of a TCP connection. For example, the nonce in UMAC can simply be a
>> counter from 0 to a certain upper bound. Even if nonce requires
randomness,
>> a PRFed value of a counter or sequence number (I remember Joe Touch
>> mentioned in Vancouver that key generation of TCP AO should not use any
>> bytes of TCP packets, but I think nonce should be ok.) can provide
>> randomness. Noticing the good performance of MACs like UMAC, maybe we
should
>> keep the door open to MACs with nonce.

>The TCP fields must not be used as a nonce for the MAC; although they do
>change, the ways they change are not ensured to be predictable (e.g.,
>TCP can validly send overlapping segments). As such, a per-packet nonce
>would need to be sent in the TCP option field, and there is insufficient
>space to do that on a per-packet basis (which is why there is no such
>field in TCP-AO).

I think I may need to clarify what I said: if a random nonce is needed for
TCP MAC, a PRFed value of sequence number provides randomness, for example:
nonce=F_K2(seq num), K2 is the key for the pseudo random function F. K2 is
different from the hash function key K1. (Actually, in UMAC, the nonce
itself does not require randomness at all, the nonce processing part of UMAC
already create randomness). The distribution/rekeying of K2 will be done
together with K1. 
I don't get why you hope sequence number be predictable here. Both sides
will know the sequence number from the TCP header and calculate the
nonce=F_K2(seq num), they are not predicting either the sequence number or
the nonce.

>> 2. incremental MAC
>> I understand the use of incrementality for virus protection but can not
see
>> the benefit of incrementality for TCP AO, at least in the BGP situation.
In
>> tcpm-tcp-auth-op, the MAC is computed over "TCP pseudo header + TCP
header +
>> TCP data", the first two parts (totally about 32 bytes or more for ipv4,
60
>> bytes or more for ipv6) are fixed for a connection, 

>The TCP sequence number varies during a connection, but it can wrap
>around. It's entirely possible to have two segments that have the same
>sequence number at different times in a connection, however. This is why
>we probably need to explicitly require that the connection key change
>whenever the sequence number rolls over (through the ISN).

Does this have anything to do with incrementality of MAC?  
The connection key (hash function key) should change whenever the sequence
number rolls over, so does the key for pseudorandom function, actually,
that's exactly what UMAC requires. The distribution/rekeying of PRF key
should be done together with the hash function key and it won't require much
work from future TCP-AO key management scheme (by the way, anything
available yet? ). 

Sean

---

From: Joe Touch <[email-masked]>
Date: Tue, 01 Jan 2008 22:01:41 -0800

> nonce=F_K2(seq num), they are not predicting either the sequence number or

I'm not at all clear on hashing a single 32-bit number to generate a
useful nonce. If you're using it to index a nonce generate by some other
means, perhaps - but that assumes some other source of randomness is
used to create a sequence of nonces (K2, above). In that case, K2 would
need to be managed and updated when the seqnum rolls over as well.

However, there is no rule that the seqnum is used only once until
rollover. TCP can retransmit a segment, and the retransmitted segment
can be longer or shorter than the original transmission. For this
reason, I don't believe seqnum is useful as a nonce, or to derive a
nonce, for crypto purposes.

> that's exactly what UMAC requires. 

It's not clear why UMAC then needs to treat the nonce field differently
from the rest of the segment - unless the nonce itself is ensured
nonrepeated for that key set. If that's the case, then, as noted above,
seqnum isn't a viable source of that nonce.

> The distribution/rekeying of PRF key

TCPM is asking for the key management protocol to come out of SAAG -
that's why we're having that discussion here.

Joe

---

From: Sean Shuo Shen <[email-masked]>
Date: Wed, 02 Jan 2008 16:49:09 +0800

>need to be managed and updated when the seqnum rolls over as well.

In the example: nonce=F_K2(seq num). The randomness comes from the K2, seq
num is used to let PRF gives different pseudo random integers each time. And
as I said above, K2 does need be managed and updated just as the hash
function key does. 
( Similarly, in crypto algorithms like PRF_HMAC_SHA1 or the nonce processing
part of UMAC, the randomness comes from the key, not from some input
counter, non-secret pad or strings.)
 
>nonce, for crypto purposes.

Thank you for pointing out the situation when a seq num is used again before
rollover. Since both sides of a tcp connection know the header length of TCP
and IP headers, also know the total length of the IP datagram, they can
calculate the length of the segment that TCP transmitted. Therefore the
nonce can be calculated as: nonce=F_K2(seq num, segment length), where
segment length=ip_total_length - 4 * tcp_header_length - 4 *
ip_header_length. In case TCP retransmit a segment (same starting byte) with
different size, a different nonce will be generated. The nonce will be same
only when the exact same segment is retransmitted. 

>seqnum isn't a viable source of that nonce.

Yes, the nonce can be ensured nonrepeated as described above.

Sean

---

From: Joe Touch <[email-masked]>
Date: Wed, 02 Jan 2008 07:29:21 -0800

>>>>> 1. interface:
...
> only when the exact same segment is retransmitted. 

I presume you're looking for a nonce that would be unique per unique
segment. It would be preferable to insert either that nonce or an index
thereto in the MAC itself, than to make assumptions of the uniqueness of
any fields of the TCP segment or a hash that would be derived from them.

Joe

---

From: Joe Touch <[email-masked]>
Date: Wed, 02 Jan 2008 08:27:29 -0800

> any fields of the TCP segment or a hash that would be derived from them.

FWIW, it might be possible for TCP to retransmit a segment with the same
offset and size but with different options. In particular, if the user
sets an option between a segment's initial transmission and subsequent
retransmission, this could occur. I'm checking to see if this could also
occur with TCP flags (e.g., FIN if a user closes a connection while data
is outstanding).

For these reasons, and because of the potential to constrain the
evolution of TCP, I would urge the MAC computation to treat the
non-zeroed TCP header and pseudoheader fields as opaque.

Joe

---

From: Sean Shuo Shen <[email-masked]>
Date: Fri, 04 Jan 2008 09:59:02 +0800

Hi Joe, 
>> any fields of the TCP segment or a hash that would be derived from them.
 
Yes, I am discussing the possibility that unique nonce are generated by both
sides without carrying extra info in MAC. Inserting an index (like a
counter) or even the nonce itself certainly can make life easier, if we
don't care the extra bytes together with the MAC.

>non-zeroed TCP header and pseudoheader fields as opaque.

I also believe some other bits in TCP header might be different even if the
TCP is retransmitting the same segment. But all of these changes can easily
be included in the PRF input when the nonce is calculated (it won't be heavy
work compared with the calculation of MAC) to make sure different nonces are
used when the authenticated content changes. 

Regards

Sean

---

From: Joe Touch <[email-masked]>
Date: Thu, 03 Jan 2008 21:44:30 -0800

Sean Shuo Shen wrote:
...
> used when the authenticated content changes. 

Steve B. suggests not corrupting the FIPS boundary by using TCP header
info. I am suggesting not limiting TCP design by making assumptions
about the TCP header's uniqueness in each transmitted segment.

We thus have two reasons not to do this; I hope that's sufficient reason
to either have a shorter MAC coupled with an explicit nonce, a longer
overall option field, or to seek algorithms that avoid the need for nonces.

Joe

---

From: Sean Shuo Shen <[email-masked]>
Date: Fri, 04 Jan 2008 15:22:20 +0800

>info. 
The FIPS boundary does matter only if the use of TCP header info is
cryptographic significant. For example, using seq num as a random seed
definitely is not a good idea. However, in a calculation like:
nonce=PRF(key, seqnum and other header info)
The seqnum et.al. are to provide difference of input to get different
output. It works like a index and totally allowed to be predictable (it can
even be a counter just like the nonce processing part of umac: PRF(key,
counter)). 
When we are not using a seqnum as a random source we don't have to worry
it's not random enough.

>I am suggesting not limiting TCP design by making assumptions
In a tcp transmission, as long as the MAC protected content are different,
there will be enough difference in tcp header (seq num et.al., actually, the
possible difference in option field or other bits are also good to
contribute difference here). This difference will be good enough for both
sides to generate different nonce for MAC calculation. It's not to make any
assumption here. 

>overall option field, or to seek algorithms that avoid the need for nonces.
The two ways mentioned above both have the advantage of simple
implementation. But implicit nonce generated by both sides is also
achievable, and the benefit of it will be: less bytes in MAC transmission,
more randomness (from PRF key, not from seqnum), more variety.

Sean

---

From: Joe Touch <[email-masked]>
Date: Fri, 04 Jan 2008 07:49:30 -0800

> When we are not using a seqnum as a random source we don't have to worry

I don't know what FIPS boundary requirements consider, but I would
expect it would include any required property of the fields. In this
case, it would be the presumed uniqueness of the fields on a per-segment
basis, which AFAICT cannot be assumed.

> sides to generate different nonce for MAC calculation. It's not to make any

If there were no assumption, then I would agree, but the above indicates
a clear assumption that we cannot clearly ensure.

> more randomness (from PRF key, not from seqnum), more variety.

Again, I feel that a good MAC doesn't depend on a nonce for variety.

Joe

---

From: Sean Shuo Shen <[email-masked]>
Date: Sat, 05 Jan 2008 14:45:08 +0800

>a clear assumption that we cannot clearly ensure.
Ok we discussed:
nonce=PRF(key, index) . 
index =segment length + tcp header without dport&sport. The index can
include all the tcp header including options, but the fields (like port
numbers) that won't change within a connection can be omitted, fields that
are set to be zero in mac culculations can also be omitted.
The problem is:
In a tcp connection, before a seqnum rollover (when rollver happens, both
hash key and PRF key need to be renewed), index must be different when the
authenticated content described in tcpm-tcp-auth-opt-00 is different. Hence
the calculation nonce=PRF(key, index) will give different values.
Proof: 
When the authenticated content changes, there are just two cases: seqnum
changes or not. 
If seqnum changes the index changes.
If seqnum does not change, segment length either changes or not:
	If segment length changes, index changes;
	If segment length does not change, changes can only come from TCP
header
 	including option, in this case, the index also changes.
Thus in all cases, the index must change when authenticated content changes,
hence different nonce value are produces. Done.

If a statement is proved, it is not an assumption. Of course a proof needs
other assumptions, just like we can not play Euclidean Geometry without
assuming Parallel Postulate, we can not play Real Analysis without assuming
Axiom of Choice. Here we should agree that a PRF produces different values
given different input, this is not an assumption which we should deeply
argue before using it. Just like, although we know a hash function is not
injective, we still believe it produces different tags for different
messages because of the small probability of collision, without believing
this the MAC protection for tcp makes no sense.

>Again, I feel that a good MAC doesn't depend on a nonce for variety.
Nonce is one way, of course not the only way, to contribute variety. 

Sean

---

From: Joe Touch <[email-masked]>
Date: Sat, 05 Jan 2008 08:48:38 -0800

...
>  	including option, in this case, the index also changes.

Please indicate the proof for this. First, it requires that the rest of
the system enforce the "no reuse of keys during seqno rollover"; second,
it requires that TCP implementations not allow the socket data to change
between initial transmission and retransmission.

Although I wouldn't think such data changes would be useful, I wouldn't
want to require FIPS validation of that property, since it creeps down
into the socket layer.

Joe

---

From: Sean Shuo Shen <[email-masked]>
Date: Mon, 07 Jan 2008 20:43:27 +0800

Hi Joe,

>between initial transmission and retransmission.
First, I remember somewhere it is said that the MAC key should be renewed
when sequence number rollover, in your first email you also mentioned that
"This is why we probably need to explicitly require that the connection key
change whenever the sequence number rolls over (through the ISN)." I believe
you are giving a reasonable and achievable requirement (hash key renewing
during rollover). If hash key renewing during rollover is doable, nonce key
renewing during rollover is also doable and it's not an extra requirement.
The way to renew keys is out of the scope of our discussion. I don't think
we have to give a key management scheme before talking about MAC algorithms.

Second, maybe there is a misunderstanding here. What I mean is: the nonce
generation algorithm can guarantee that nonce is different when the MAC
protected data are different (because some mac algorithms require different
nonce when hashing different messages). If the MAC protected data (I assume
this is what you mean by "socket data") are same between transmission and
retransmission, it is totally fine for nonce to be same. So I did not
require that TCP implementations not allow the socket data to change between
initial transmission and retransmission.
Regards

Sean

---

From: Joe Touch <[email-masked]>
Date: Mon, 07 Jan 2008 06:54:53 -0800

> we have to give a key management scheme before talking about MAC algorithms.

It all depends on whether key reuse during rollover is prohibited 
outright or just recommended against. If the former, I agree it's 
sufficient to roll over the nonce key at the same time. It's the latter 
case that's the issue, and whether to make this something FIPS 
certification relies upon.

> retransmission, it is totally fine for nonce to be same.

That depends on whether the nonce is used to provide replay protection. 
If it is, then it can't be the same if the entire segment is the same.

Joe

---

From: Sean Shuo Shen <[email-masked]>
Date: Tue, 08 Jan 2008 08:44:14 +0800

>certification relies upon.
Key reuse during rollover is prohibited.

>If it is, then it can't be the same if the entire segment is the same.
The nonce here is not used against replay attack. 

Sean