Internet Engineering Task Force David A. McGrew
INTERNET-DRAFT Cisco Systems, Inc.
Expires May, 2002 November, 2001
The Truncated Multi-Modular Hash Function (TMMH)
<draft-mcgrew-saag-tmmh-01.txt>
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]