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

From: mcgrew <[email-masked]>
Date: Wed, 02 Jan 2008 07:06:49 -0800

Hi Sean,

Thanks for your comments, more inline:

On 12/27/07 11:00 PM, "Sean Shuo Shen" <[email-masked]> wrote:

> Dear David,
> I read the draft-irtf-cfrg-fast-mac-requirements and believe the draft gives
> good security and efficiency description for TCP AO MAC. I have a few
> thoughts according the following issues in the draft:
> 
> 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.

Agreed, it is true that in some cases the nonce need not be carried
explicitly along with the MAC value, but instead can be reconstructed by the
receiver using other information.  It is also possible to use "Partially
Implicit Nonces", in the terms of Section 3.2.1 of draft-mcgrew-auth-enc,
which trades off nonce size against protocol robustness.  Perhaps this is
worth investigating for TCP-AO, though I still think that nonceless MACs
should be favored because of their simplicity.

However, the implicit nonce idea does nothing to address the fact that
nonce-based algorithms are undesirable whenever it is difficult to ensure
nonce coordination, i.e. when key management is absent.

> 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.

I'm optimistic that worthwhile nonceless MACs can be made.  For example,
UMAC can easily be turned into a nonceless MAC by changing its definition
from

MAC = AES(K, Nonce) (+) Hash(Message)

To 

MAC = AES(K, Hash(Message))

The latter form is actually closer to the initial version of UMAC.

MACs of this form don't meet requirement R6, though.

> 
> 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.

I agree, I didn't mean to imply in the requirements draft that TCP AO would
find incrementality useful.  That feature seems more useful in a
data-storage context than a communications context.   Brian and I included
that feature in the list because it is a desirable property of a
general-purpose MAC.

>  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, while the length of BGP
> part (that part that will change) will be ranged from 19 to 4096 bytes. Thus
> difference of packets is not small. Please let me know if there are good
> ways to use incrementality in BGP or other scenarios.

I think you hit the nail on the head here.  In many communication protocols,
it is possible (in principle at least) for the MAC to pre-process the
headers, but in practice the gains often are not worth the effort.

> 
> Thank you and happy new year to all!

Thanks, and wishing you the same!

Best regards,

David

> Regards,
> 
> Sean
> 
> -----Original Message-----
> From: mcgrew [mailto:[email-masked]]
> Sent: Thursday, December 20, 2007 11:50 PM
> To: Brian Weis
> Cc: [email-masked]; [email-masked]
> Subject: [Cfrg] Re: [saag] TCP-AO MAC algorithms
> 
> Hi Brian,
> 
> I've cross-posted to CFRG to tie the TCP Auth work in with
> draft-irtf-cfrg-fast-mac-requirements draft.
> 
> On 12/18/07 4:23 PM, "Brian Weis" <[email-masked]> wrote:
> 
>> Greetings,
>> 
>> The TCPM WG seeks advice from SAAG on which MACs to include as
>> required MACs for the TCP Authentication Option (draft-ietf-tcpm-tcp-
>> auth-opt-00). Two MACs with differing internal constructions are
>> desired.
> 
> I assume that the reason for having two mandatory-to-implement MACs is to
> ensure algorithm agility.
> 
>> 
>> In my opinion, it is also important that MACs defined by an Internet
>> standard as required to be implemented be based on NIST-approved
>> algorithms and modes, and also be generally available in both
>> software and cryptographic hardware.
>> 
>> The following two MACs are reasonable recommendations that taken
>> together easily meet the above criteria: HMAC-SHA-1 and AES-CMAC. I
>> propose that these be the algorithms provided to the TCPM WG.
>> 
>> Brian
> 
> Sounds like reasonable choices to me.
> 
> It would be good to have a MAC that performs exceptionally well in software,
> along the lines of what we've targeted in
> draft-irtf-cfrg-fast-mac-requirements, but if the choice of MACs has to be
> made *today*, there may not be a suitable candidate that has been
> sufficiently specified and/or reviewed.  I expect that MACs that will be
> more suitable for use in TCP Authentication will be developed (candidates
> include [1] and [2]).  I trust that there is a path for the adoption of new
> MACs in TCP Auth.
> 
> Probably the biggest open question is the length of the MAC.  The CMAC
> specification states that lengths 64 bits and higher are acceptable, but
> that smaller values "shall only be used in conjunction
> with a careful analysis of the risks" [1].  It would be good to do this
> analysis for TCP Auth, of course, but it is encouraging that AES-128-CMAC
> could be used with a 64-bit tag and still meet the conformance goals that
> you outlined. 
> 
> Best regards, 
> 
> David
> 
> 
> [1] J. Black and M. Cochran, "MAC Reforgeability",
> http://eprint.iacr.org/2006/095
> 
> [2] D.J. Bernstein, "Polynomial evaluation and message authentication",
> http://cr.yp.to/antiforgery/pema-20071022.pdf
> 
> [3] M. Dworkin, NIST Special Publication 800-38B, "Recommendation for Block
> Cipher Modes of Operation: The CMAC Mode for Authentication"
> http://csrc.nist.gov/publications/nistpubs/800-38B/SP_800-38B.pdf
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Stephen Kent <[email-masked]>
Date: Wed, 2 Jan 2008 10:37:16 -0500

Anoher issue to keep in mind is that a nonce-less MAC avoids the FIPS 
evaluation problems that would arise from attempts to make use of the 
TCP sequence number as an input to the nonce generation process.

Steve

---

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

Hi David,

>nonce coordination, i.e. when key management is absent.

If a nonce is used for MAC and requires a key, I think it's reasonable to
let the nonce key updated together with the hash key, similar as some other
security schemes in which encryption keys and integrity protection keys are
generated/renewed synchronously. Though the key management solution for TCP
AO is not proposed yet, adding nonce key generation/distribution together
with hash key won't affect much on overall performance. 

>MACs of this form don't meet requirement R6, though.
Yes, I agree. 

Regards

Sean

---

From: Sean Shuo Shen <[email-masked]>
Date: Fri, 04 Jan 2008 10:01:03 +0800

Hi Stephen,
Can you talk more details about the FIPS evaluation problem?

Sean

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Stephen Kent
Sent: Wednesday, January 02, 2008 11:37 PM
To: mcgrew
Cc: [email-masked]; Sean Shuo Shen; [email-masked]
Subject: Re: [saag] [Cfrg] Re: TCP-AO MAC algorithms

Steve
_______________________________________________
saag mailing list
[email-masked]
http://mailman.mit.edu/mailman/listinfo/saag

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Fri, 4 Jan 2008 03:05:07 +0000

On Fri, 04 Jan 2008 10:01:03 +0800

> Can you talk more details about the FIPS evaluation problem?
The issue is what the assurance boundary is.  If the TCP sequence
number is cryptographically significant, the entire process by which
it's set (including original generation and anything else in the stack
or kernel that could touch it) has to be part of the evaluation, too.

It is, I think, less of an issue for TCP-AO, since I suspect that
that's not very likely to be done by a dedicated hardware module.
Still, as a matter of design principle one should keep
security-critical matters separate.

> TCP sequence number as an input to the nonce generation process.

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

---

From: Sean Shuo Shen <[email-masked]>
Date: Fri, 04 Jan 2008 11:35:17 +0800

Thank you Steven.

>or kernel that could touch it) has to be part of the evaluation, too.

The isn generation of some windows versions and linux is not random enough
and is vulnerable (like RST attack). So the seq num can not be a source for
randomness. But if a seq num is used just as an index instead of a random
seed, it is not cryptographically significant and I don't think it will
affect the cryptographic strength. What do you think, Steven?

Regards

Sean

---

From: "Steven M. Bellovin" <[email-masked]>
Date: Fri, 4 Jan 2008 04:32:50 +0000

On Fri, 04 Jan 2008 11:35:17 +0800
Sean Shuo Shen <[email-masked]> wrote:

> >it's set (including original generation and anything else in the
> >stack or kernel that could touch it) has to be part of the
> >evaluation, too.
> 
> The isn generation of some windows versions and linux is not random
> enough and is vulnerable (like RST attack). So the seq num can not be
> a source for randomness. But if a seq num is used just as an index
> instead of a random seed, it is not cryptographically significant and
> I don't think it will affect the cryptographic strength. What do you
> think, Steven?
> 
The questions to ask are (a) what are the consequences if there's a
collision or repetition; (b) what are the consequences if the enemy
can predict the value; (c) can the enemy cause such things, with some
probability; and (d) if the answer to the previous questions indicates
potential trouble, what are the assurances that trouble won't happen?

For example -- in a straight RFC 793 TCP, the approximate value of an
ISN is knowable; after all, that's how sequence number attacks are
launched.  If RFC 1948 sequence numbers are used, the ISN of a new
instance of a connection 4-tuple is approximately knowable. The sequence
numbers of subsequent packets in a connection are 100% knowable.  The
answer to (c) is yes, the attacker will generally know it.  Is this a
problem?  

I've lost track of what specific algorithm is being discussed here, so
I won't try to answer in detail, but in general these are the kinds of
questions that have to be answered.

---

From: Stephen Kent <[email-masked]>
Date: Fri, 4 Jan 2008 09:38:27 -0500

>Can you talk more details about the FIPS evaluation problem?

Sure.

FIPS 140-x evaluation of crypto modules generally will NOT encompass 
implementation of mechanisms used for anti-replay, e.g., the sequence 
numbers used in IPsec or in TCP. This is because these mechanisms are 
not part of a crypto algorithm definition. However, if these same 
values are used as inputs to crypto algorithms, e.g., a MAC algorithm 
or a confidentiality algorithm such as counter mode encryption, THEN 
they become part of the evaluated code/hardware base. So, if one were 
to use TCP sequence numbers in a MAC algorithm, and the algorithm 
required the numbers to be unique, then all aspects of TCP sequence 
number management would become part of the evaluated code base. In 
general, one tries to minimize the size of the evaluated code and 
hardware, to increase likelihood that the evaluation will succeed, to 
reduce the need for re-evaluation when any of the evaluated 
code/hardware changes, etc.

This observation caused IPsec to decide to NOT reuse its anti-replay 
sequence numbers for counter-mode encryption. Rather IPsec requires 
carriage of the counter-mode, per-packet value in each packet header.

Steve

---

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

Thank you, Stephen,

>carriage of the counter-mode, per-packet value in each packet header.

Here I agree that carrying the nonce (or an index/counter for nonce) with
the MAC is a good way for a nonce MAC algorithm to get express pass from
fips.

Sean