Internet Engineering Task Force David A. McGrew INTERNET-DRAFT Cisco Systems, Inc. Expires May, 2002 November, 2001 The Truncated Multi-Modular Hash Function (TMMH) Status of this Memo This document is an Internet Draft and is in full conformance with all provisions of Section 10 of RFC-2026. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and 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. 1. Abstract TMMH is a `universal' hash function suitable for message authentication in the Wegman-Carter paradigm, as in the Stream Cipher Security Transform. It is simple, quick, and especially appropriate for Digital Signal Processors and other processors with a fast multiply operation, though a straightforward implementation requires storage equal in length to the largest message to be hashed. 2. TMMH TMMH is a simple hash function which maps a key and a message to a hash value. There are two versions of TMMH: TMMH/16 and TMMH/32. TMMH/16 uses sixteen bit unsigned words as a basic data unit, while TMMH/32 uses thirty-two bit unsigned words. TMMH can be used as a message authentication code, as described in Section 5. McGrew [Page 1] Internet Draft Truncated Multi-Modular Hash (TMMH) November, 2001 The key, message, and hash value are all octet strings, and the lengths of these quantities are denoted as KEY_LENGTH, MESSAGE_LENGTH, and TAG_LENGTH, respectively. The values of KEY_LENGTH and TAG_LENGTH MUST be fixed for any particular fixed value of the key, and must obey the alignment restrictions described below. The parameter MAX_HASH_LENGTH, which denotes the maximum value which MESSAGE_LENGTH may take, is equal to KEY_LENGTH - TAG_LENGTH. 3. TMMH/16 For TMMH/16, KEY_LENGTH and TAG_LENGTH MUST be a multiple of two. The key, message, and hash value are treated as a sequence of unsigned sixteen bit integers in network byte order. (In this section, we call such an integer a word.) If MESSAGE_LENGTH is odd, then a zero byte is appended to the message to align it on a word boundary, though this process does not change the value of MESSAGE_LENGTH. The words of the key are denoted as K[1], K[2], ..., K[KEY_WORDS], and the words of the message (after zero padding, if needed) are denoted as M[1], M[2], ..., M[MSG_WORDS], where MSG_WORDS is the smallest number such that 2 * MSG_WORDS is at least MESSAGE_LENGTH, and KEY_WORDS is KEY_LENGTH / 2. If MESSAGE_LENGTH is greater than MAX_HASH_LENGTH, then the value of TMMH/16 is undefined. Implementations MUST indicate an error if asked to hash a message with such a length. Otherwise, the hash value is defined to be the length TAG_WORDS sequence of words in which the j-th word in the sequence is defined as [ [ K[j] * MESSAGE_LENGTH +32 K[j+1] * M[1] +32 K[j+2] * M[2] +32 ... K[j+MSG_WORDS] * M[MSG_WORDS] ] modulo p ] modulo 2^16 where j ranges from 1 to TAG_WORDS. Here, TAG_WORDS is equal to TAG_LENGTH / 2, and p is equal to 2^16 + 1. The symbol * denotes multiplication and the symbol +32 denotes addition modulo 2^32. 3.1 Test Vectors This section provides test vectors which can be used to test an implementation of TMMH/16. The key, message, and outputs are McGrew [Page 2] Internet Draft Truncated Multi-Modular Hash (TMMH) November, 2001 expressed as octet sequences, with each octet in hexadecimal. KEY_LENGTH: 10 TAG_LENGTH: 2 key: { 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc } message: { 0xca, 0xfe, 0xba, 0xbe, 0xba, 0xde } output: { 0x9d, 0x6a } KEY_LENGTH: 10 TAG_LENGTH: 2 key: { 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc } message: { 0xca, 0xfe, 0xba } output: { 0xc8, 0x8e } KEY_LENGTH: 10 TAG_LENGTH: 4 key: { 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc } message: { 0xca, 0xfe, 0xba, 0xbe, 0xba, 0xde } output: { 0x9d, 0x6a, 0xc0, 0xd3 } 3.3 Implementation Notes The reduction modulo p can be implemented without the explicit use of a division operation, as it is close to 2^16 (See Section 3.1 of [MMH] for details). The reduction modulo 2^16 can be implemented by truncating all but the lower sixteen bits of a higher-precision value. 4. TMMH/32 TMMH/32 is defined analogously to TMMH/16, but with a thirty-two bit word size, with the following differences: * a word is four bytes in length, and the message is padded with as many zero octets as needed to make the message terminate on a word boundary, * the addition operations are done modulo 2^64, * TAG_WORDS is equal to TAG_LENGTH / 4, and MSG_WORDS is the smallest number such that 4 * MSG_WORDS is at least MESSAGE_LENGTH. * the prime p is 2^32+15 and the last modular reduction is modulo 2^32 (rather than 2^16). McGrew [Page 3] Internet Draft Truncated Multi-Modular Hash (TMMH) November, 2001 4.1 Test Vectors This section provides test vectors which can be used to test an implementation of TMMH/32. The notation is as in Section 3.1. KEY_LENGTH: 12 TAG_LENGTH: 4 key: { 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc, 0xba, 0x98 } message: { 0xca, 0xfe, 0xba, 0xbe, 0xba, 0xde, 0xde, 0xed } output: { 0x43, 0x3f, 0x20, 0xed } KEY_LENGTH: 12 TAG_LENGTH: 4 key: { 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc, 0xba, 0x98 } message: { 0xca, 0xfe, 0xba, 0xbe, 0xba } output: { 0x20, 0xdc, 0xf6, 0x37 } 5. Using TMMH as a Message Authentication Code TMMH can be used to make a Wegman-Carter type message authentication code. To use TMMH to compute the authentication tag of a message, the TMMH hash value of that message is computed, then that value is combined with a pseudorandom string of TAG_LENGTH octets. The combining operation is word-wise addition modulo 2^16 (for TMMH/16) or 2^32 (for TMMH/32). The pseudoranom strings MUST NOT be correlated with each other nor with the messages they protect. A message/authentication tag pair can be verified as follows. Compute a new authentication tag using the algorithm above, and compare it to the tag associated with the message. If the two are equal, then the message/tag pair is valid; otherwise, it is not. 6. Open Questions The alignment restriction on TAG_LENGTH could be eliminated by computing larger hash values, then truncating them to the desired length. This generalization might be desirable for uses in which word alignment is unimportant and limitations on tag sizes are severe. It is not clear if there is significant motivation for this case. McGrew [Page 4] Internet Draft Truncated Multi-Modular Hash (TMMH) November, 2001 7. Security Concerns TMMH/16 is ((0.009568)^TAG_LENGTH)-Delta Universal with respect to subtraction modulo 2^16, and TMMH/32 is ((0.006114)^TAG_LENGTH) -Delta Universal with respect to subtraction modulo 2^32. This property enables TMMH to be used as a message authentication code in the Wegman-Carter paradigm [WC81]. These security claims for TMMH follow from the derivations in [MMH]. The interested reader should adapt Definition 2 of that document to TMMH as a starting point. The cyclic use of the words of the key is known as a Toeplitz construction, and is known to be secure (see Section 2.4 of [MMH] and the references therein). 8. History The second draft corrects one of the test vector cases, adds a section on using TMMH in a MAC, makes some scattered corrections and clarifications, and removes references to other Internet Drafts. TMMH is an extension on the MMH hash function [MMH]. Unlike the function introduced in that seminal work, TMMH can deal efficiently and securely with variable-length messages, and is defined for both sixteen and thirty-two bit words. The PacketCable Security specification includes a MMH variant for RTP authentication [PC]. This variant uses an insecure mechanism for message lengths less than the maximum value, and is not interoperable with TMMH. To the best knowledge of the authors, this specification is not covered by any patents [H01]. 9. Acknowledgments Thanks are due to Doug Smith, Scott Fluhrer, Mats Naslund and der Mouse for their comments and corrections. McGrew [Page 5] Internet Draft Truncated Multi-Modular Hash (TMMH) November, 2001 9. Contact Information Questions and comments about this Internet Draft SHOULD be directed to: David A. "I'm not gonna pay a lot for this Presentation Layer" McGrew Cisco Systems, Inc. mcgrew@cisco.com The discussion list for the Security Area Advisory Group is: saag@mit.edu 10. References [B97] Bradner, S., Key words for use in RFCs to Indicate Requirement Levels, RFC 2119, March 1997. [WC81] M. Wegman and L. Carter, New hash functions and their use in authentication and set equality, J. of Computer and System Sciences, vol. 22, 1981. [H01] Halevi, S. Personal communication, May, 2001. [MMH] Halevi, S., and Krawczyk, H. MMH: Software Authentication in the Gbit/second rates, Fast Software Encryption Workshop, 1997. Also available online at http://www.research.ibm.com/people/s/shaih/pubs/. [PC] The PacketCable Security Specification, PKT-SP-SEC-I03-010626, Sections 9.8.1 and 9.8.2. Available online at http://www.packetcable.com/specifications.html McGrew [Page 6]