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, . [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, . [GH05] Gilbert, G. and H. Handschuh, "The Poly1305-AES message- authentication code", Pages 32-49 in Proceedings of FSE 2005, Springer , February 2005, . [GMAC] McGrew, D. and J. Viega, "Galois/Counter Mode of Operation (GCM)", Submission to NIST modes of operation, May 2005, . [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, . [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", . [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]