One document matched: draft-irtf-cfrg-fast-mac-requirements-00.txt
Network Working Group D. McGrew
Internet-Draft B. Weis
Intended status: Informational Cisco Systems
Expires: May 1, 2008 October 29, 2007
Requirements on Fast Message Authentication Codes
draft-irtf-cfrg-fast-mac-requirements-00
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on May 1, 2008.
Copyright Notice
Copyright (C) The IETF Trust (2007).
Abstract
This memo outlines requirements guiding the development of a fast
Message Authentication Code (MAC) algorithm suitable for use with
many IETF protocols, but in particular routing protocols that use a
MAC for packet authentication.
It is widely conjectured that secure MACs that are fast in software
are possible, and many interesting MACs have appeared in the
literature. Nevertheless, none of these MACs have seen broad
McGrew & Weis Expires May 1, 2008 [Page 1]
Internet-Draft Fast MAC Requirements October 2007
adoption, and none are a good match for the routing protocol case.
We hope that this memo brings together MAC designers and MAC users
for a fruitful discussion.
Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Throughput . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4. Security . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5. Incremental Verification . . . . . . . . . . . . . . . . . . . 6
6. Example Usage: Routing Authenticaton . . . . . . . . . . . . . 6
7. Requirements for a fast Software MAC . . . . . . . . . . . . . 7
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7
9. Security Considerations . . . . . . . . . . . . . . . . . . . 7
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8
10.1. Normative References . . . . . . . . . . . . . . . . . . 8
10.2. Informative References . . . . . . . . . . . . . . . . . 8
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10
Intellectual Property and Copyright Statements . . . . . . . . . . 11
McGrew & Weis Expires May 1, 2008 [Page 2]
Internet-Draft Fast MAC Requirements October 2007
1. Introduction
There are a number of Message Authentication Codes (MACs) that are
relatively fast, but these MACs do not meet all of the requirements
of some applications. This memo outlines desirable attributes for a
fast MAC, and describes a particularly demanding application in which
no current MAC appears to be satisfactory. These desirably
attribututes are given as requirements. We invite comments on both
the requirements and their relative priority.
We first review existing MACs. Unfortunately, some MACs are still in
use even though they have known security deficiencies. The "TCP MD5
Signature Option" [RFC2385] construction is in this category.
HMAC [RFC2104] constructs a MAC out of a collision-resistant hash
function, such as SHA-1. HMAC is a pseudorandom function, so it is
also suitable for other purposes such as key derivation. It has
proven popular, and it is in widespread use, though its design is not
ideal for high-speed hardware, its performance is worse on short
messages, and many cryptographers believe that more efficient designs
are possible. Additionally, HMAC performance suffers when its
underlying hash function changes to a "wider" hash function, so the
current interest in replacing HMAC-MD5 and HMAC-SHA-1 with HMAC-SHA-
256 and HMAC-SHA-512 is likely to motivate the consideration of
alternative MACs.
There are many designs for MACs that use the Wegman-Carter "universal
hashing" paradigm [WC81]. Informally speaking, this method minimizes
computational cost by doing the bulk of the message-processing using
functions that have good combinatorial properties. LFSR-hash [LFSR]
is a hardware-oriented Wegman-Carter style MAC; most designs since
then have been software-oriented, including UMAC [RFC4418], POLY1305
[POLY1305], VMAC [I-D.krovetz-vmac].
A number of block cipher modes of operation act as MACs, including
CMAC [FIPS.800-38B], which is the modern version of CBC-MAC. Because
the block cipher invocations in this MAC cannot be pipelined or
parallelized, some other MAC modes have appeared, including XORMAC
[XORMAC] and GMAC [GMAC], the latter of which is a Wegman-Carter
style MAC.
Many of the more recent MAC designs have MAC-generation algorithms
that require that a nonce is provided as input, including LFSR-hash,
UMAC (though an early version did not), POLY1305, GMAC, and VMAC. In
this regard, they differ from HMAC.
McGrew & Weis Expires May 1, 2008 [Page 3]
Internet-Draft Fast MAC Requirements October 2007
2. Interface
It is desirable for a MAC to support the simplest possible interface,
viz., one involving a message, a key, and a MAC value, and no other
parameters. A new MAC that uses this interface could be used as a
drop-in replacement for HMAC and "MD5 signature" (used by the TCP MD5
Signature Option [RFC2385]). Some MACs with impressive performance
have not seen broad adoption. We suspect that one of the reasons for
this is their use of nonces, which complicates their use as
replacements for MACs with simpler interfaces. It is worth noting
that a MAC with the simple interface can be built out of a MAC that
requires a nonce, by incorporating nonce generation into the MAC-
generation algorithm, and carrying the nonce within the MAC itself.
This may prove fruitful in some cases, though it does have the
undesirable property that it expands the size of the MAC.
In applications in which there is no key management protocol
available, it is particularly undesirable to use a MAC that requires
that each invocation of the MAC generation algorithm to use a
distinct nonce value. This is because, in many situations, it is
difficult to maintain the state needed to generate and maintain
unique nonces. It may be acceptable in these applications to use a
random nonce. In some other applications, it is desirable to
minimize the number of bytes required by a MAC. In these cases, it
is unappealing to incorporate a nonce into the MAC.
In most applications of message authentication, there is a need for
anti-replay protection. The data used to provide this security
service may be directly useable as a nonce. However, not all
applications fall into this category. In particular, environments in
which there are multiple senders that share a single MAC key may have
trouble coordinating nonce values to ensure their uniqueness. The
methods that are used to coordinate anti-replay information may be
insufficiently secured from the point of view of nonce management.
In these environments MACs that do not require nonces are desirable.
Another useful property for MACs is incrementality [BGG95]; i.e., the
ability to take a MAC computed for a given message and to generate a
MAC for a slightly different message more efficiently than just
running the MAC-generation algorithm on the new message. XORMAC can
be used as an incremental MAC, as can GMAC [GMAC-INCR].
3. Throughput
In most applications it is desirable to minimize the computational
cost of a MAC. Ideally, performance should be good across all
implementation environments: hardware circuits, field-programmable
McGrew & Weis Expires May 1, 2008 [Page 4]
Internet-Draft Fast MAC Requirements October 2007
gate arrays, and software implementations on all sorts of processors.
This goal is hard to meet, especially considering the diversity of
processors. Modern high-end processors typically support operations
on 64-bit data values with multiple pipelines, and sometimes provide
circuits for performing special operations in parallel (usually ones
related to video processing). Often multiple processors work
together in parallel. However, many software environments lack this
sort of high-performance hardware support. Processors that operate
on 32 bits at a time, or even 8 bits at a time, are still common.
Some environments lack support for floating-point operations. Also,
the speed and size of random access memory varies considerably in
different environments.
It seems to be difficult to design a MAC that provides excellent
performance in both hardware and software. The Galois/Message
Authentication Code (GMAC) is efficient in pipelined hardware, and
provides good performance in software, though only by trading off
some storage for better performance. Nonetheless, it may be possible
to provide considerably better performance in some software
environments by taking advantage of fast integer multiplications.
Clearly it is best for a MAC to perform well in all implementation
environments. However, we believe that a message authentication code
that performs exceptionally well in software, but only adequately
well in hardware, would prove useful. Ideally, the computational
cost of evaluating a MAC should be proportional to the length of the
message, so that the cost of processing ten 16 byte messages is equal
to the cost of processing a single 160 byte message, for example.
4. Security
Some MACs offer a performance-security tradeoff, for example by
having a variable output size. It is an open question as to when it
is acceptable to use relatively low security levels. We guess that
32-bit and 64-bit MACs are acceptable in some situations, though such
MACs could probably have relatively limited applicability. If a
short MAC is used, the MAC should retain a high level of security
even if an adversary is able to craft a successful forgery. More
specifically, the attacker's probability of successfully forging a
message should not significantly change after the attacker succeeds
in forging one or more messages. This property is needed to ensure
that an n-bit MAC can be safely used to process a number of messages
close to 2^n (or perhaps greater than that number). MACs that use
the LFSR-hash approach, such as GMAC, UMAC, and VMAC, do not have
this property. In applications that lack dedicated key management,
it is desirable that a MAC provide a high security level even after
it processes a very large amount of data.
McGrew & Weis Expires May 1, 2008 [Page 5]
Internet-Draft Fast MAC Requirements October 2007
5. Incremental Verification
Some devices (e.g., sensors) would benefit from the ability to
dynamically trade-off throughput and security. Incremental
Verification is the idea that the verifier of a MAC could choose the
security level of a validation as part of such a performance-security
tradeoff. For example, a device under DoS attack could choose low-
security verification as a means of reducing CPU utilization. Such a
low-security verification could be used as a "filtering" mechanism,
to be followed by a high-security check. Note that a MAC incremental
verification is distinct from an incremental MAC, as described in
Section 2.
6. Example Usage: Routing Authenticaton
Routing protocols typically use a MAC to provide message integrity.
One common method is the TCP MD5 Signature Option[RFC2385], which
uses "MD5 Signature"; standards work is underway with the goal of
replacing this option with a more secure and easier to use option
[I-D.bellovin-tcpsec] [I-D.bonica-tcp-auth]
[I-D.touch-tcpm-tcp-simple-auth] [I-D.weis-tcp-auth-auto-ks]. MACs
currently in use are based on "MD5 Signature", HMAC-SHA1 or HMAC-MD5.
Some modes of AES (E.g., AES-CMAC) could also be used. However, all
of these algorithms are computationally expensive in software, which
limits the number of secure connections that a particular router can
support. In some cases, the MAC verification process itself can be
used by an attacker to propagate a Denial of Service (DoS) attack. A
strong MAC algorithm that requires less computation by a router is
desirable.
Routers often implement routing protocols in software in such a way
that hardware acceleration of a MAC algorithm is not optimal. In
some cases (e.g., TCP), efficient processing of the option containing
the MAC requires that it be done on a route processor rather than in
an ASIC or FPGA. As a consequence, routers often implement the MAC
algorithm in software, resulting in the over-subscription of the CPU
and the filling of the input queues to the route processor. A faster
MAC algorithm could greatly increase the number of secure connections
to routing peers that a router can support. A faster MAC algorithm
not requiring a nonce would user fewer protocol header bytes, which
leaves more space for routing protocol data to be included in each
packet. Such a method should be suitable for use as a TCP option, as
well as the OSPF, EIGRP, IS-IS, and other routing protocols. We
estimate that a MAC algorithm suitable for use by routing protocols
would be at least an order of magnitude faster than HMAC-MD5, and
would not use more than 1K of memory per key (including internal key
scheduling tables and/or expanded key space).
McGrew & Weis Expires May 1, 2008 [Page 6]
Internet-Draft Fast MAC Requirements October 2007
7. Requirements for a fast Software MAC
R1. The MAC MUST have a simple interface; in particular, it
SHOULD NOT require a nonce.
R2. The MAC SHOULD provide throughput at least five times that of
HMAC-MD5 in common software environments.
R3. The MAC SHOULD be at least as efficient as HMAC-MD5 in common
hardware environments.
R4. The MAC SHOULD be compact; that is, it should have a forgery
probability close to 1/2^n, where n is the number of bits in the
MAC.
R5. The MAC MAY provide a security/performance tradeoff.
R6. If the MAC can have a short output value, then MAC SHOULD be
difficult to forge even after an adversary has succeeded in
perpetrating one or more forgeries.
R7. Efficient software implementations of the MAC SHOULD NOT
require more than one kilobyte of RAM for each key that is in use.
R8. The MAC SHOULD include "incremental verification"
Of the MACs described above, the only ones that do not require a
nonce (R1) are HMAC and CMAC, neither of which meet the aggressive
performance goals that we identified (R2 and R3). None of the
fastest MACs (UMAC, POLY1305-AES[GH05], VMAC, GMAC) meet the goal
that repeat forgeries are unlikely when the MAC is short (R6).
8. IANA Considerations
This document makes no request of IANA.
Note to RFC Editor: this section may be removed on publication as an
RFC.
9. Security Considerations
This memo describes requirements for the development of a
cryptographic algorithm. Security considerations are included
throughout the memo.
McGrew & Weis Expires May 1, 2008 [Page 7]
Internet-Draft Fast MAC Requirements October 2007
10. References
10.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
10.2. Informative References
[BGG95] Bellare, M., Goldreich, O., and S. Goldwasser,
"Incremental cryptography and application to virus
protection", In Proceedings of the Twenty-Seventh Annual
ACM Symposium on theory of Computing.STOC '95 , May 1995,
<groups.csail.mit.edu/cis/pubs/shafi/1995-stoc.pdf>.
[FIPS.800-38B]
National Institute of Standards and Technology,
"Recommendation for Block Cipher Modes of Operation: The
CMAC Mode for Authentication", FIPS PUB 800-38B, May 2005,
<http://csrc.nist.gov/publications/nistpubs/800-38B/
SP_800-38B.pdf>.
[GH05] Gilbert, G. and H. Handschuh, "The Poly1305-AES message-
authentication code", Pages 32-49 in Proceedings of FSE
2005, Springer , February 2005,
<http://cr.yp.to/papers.html#poly1305>.
[GMAC] McGrew, D. and J. Viega, "Galois/Counter Mode of Operation
(GCM)", Submission to NIST modes of operation, May 2005,
<http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/
gcm/gcm-revised-spec.pdf>.
[GMAC-INCR]
McGrew, D., "Efficient Authentication of large, dynamic
data sets using Galois/Counter Mode (GCM)", 3rd
International IEEE Security in Storage Workshop ,
December 2005,
<http://ieeeia.org/sisw/2005/PreProceedings/10.pdf>.
[I-D.bellovin-tcpsec]
Bellovin, S., "Problem Statement and Requirements for a
TCP Authentication Option", draft-bellovin-tcpsec-01 (work
in progress), July 2007.
[I-D.bonica-tcp-auth]
Bonica, R., "Authentication for TCP-based Routing and
Management Protocols", draft-bonica-tcp-auth-06 (work in
progress), February 2007.
McGrew & Weis Expires May 1, 2008 [Page 8]
Internet-Draft Fast MAC Requirements October 2007
[I-D.krovetz-vmac]
Dai, W. and T. Krovetz, "VMAC: Message Authentication Code
using Universal Hashing", draft-krovetz-vmac-01 (work in
progress), April 2007.
[I-D.touch-tcpm-tcp-simple-auth]
Touch, J. and A. Mankin, "The TCP Simple Authentication
Option", draft-touch-tcpm-tcp-simple-auth-03 (work in
progress), July 2007.
[I-D.weis-tcp-auth-auto-ks]
Weis, B., "Automated key selection extension for the TCP
Enhanced Authentication Option",
draft-weis-tcp-auth-auto-ks-03 (work in progress),
October 2007.
[LFSR] Krawczyk, H., "LFSR-based Hashing and Authentication",
Proceedings of the 14th Annual Conference on Advances in
Cryptology (CRYPTO'94). Lecture Notes in Computer
Science, vol. 839, pp. 129-139, Springer , 1994.
[POLY1305]
Bernstein, D., "The Poly1305-AES message-authentication
code", <http://cr.yp.to/mac/poly1305-20050329.pdf>.
[RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-
Hashing for Message Authentication", RFC 2104,
February 1997.
[RFC2385] Heffernan, A., "Protection of BGP Sessions via the TCP MD5
Signature Option", RFC 2385, August 1998.
[RFC4418] Krovetz, T., "UMAC: Message Authentication Code using
Universal Hashing", RFC 4418, March 2006.
[WC81] Wegman, M. and J. Carter, "New hash functions and their
use in authentication and set equality", Journal of
Computer and System Sciences, 22:265-279 , none 1981.
[XORMAC] Bellare, M., Guerin, R., and P. Rogaway, "XOR MACs: New
Methods for Message Authentication Using Finite
Pseudorandom Functions", Proceedings of the 15th Annual
Conference on Advances in Cryptology (CRYPTO '95), Lecture
Notes in Computer Science, vol. 963, pp. 15-28, Springer ,
1995.
McGrew & Weis Expires May 1, 2008 [Page 9]
Internet-Draft Fast MAC Requirements October 2007
Authors' Addresses
David A. McGrew
Cisco Systems
170 W. Tasman Drive
San Jose, California 95134-1706
USA
Phone: +1 408 525 8651
Fax:
Email: mcgrew@cisco.com
URI:
Brian Weis
Cisco Systems
170 W. Tasman Drive
San Jose, California 95134-1706
USA
Phone: +1 408 526 4796
Fax:
Email: bew@cisco.com
URI:
McGrew & Weis Expires May 1, 2008 [Page 10]
Internet-Draft Fast MAC Requirements October 2007
Full Copyright Statement
Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
McGrew & Weis Expires May 1, 2008 [Page 11]
| PAFTECH AB 2003-2026 | 2026-04-24 03:16:51 |