UMAC: Message Authentication Code using Universal Hashing
RFC 4418

• Status
• IESG evaluation record
• IESG writeups
• Email expansions
• History

• Versions
• 07

Network Working Group                                    T. Krovetz, Ed.
Request for Comments: 4418                                CSU Sacramento
Category: Informational                                       March 2006

       UMAC: Message Authentication Code using Universal Hashing

Status of This Memo

   This memo provides information for the Internet community.  It does
   not specify an Internet standard of any kind.  Distribution of this
   memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (2006).

Abstract

   This specification describes how to generate an authentication tag
   using the UMAC message authentication algorithm.  UMAC is designed to
   be very fast to compute in software on contemporary uniprocessors.
   Measured speeds are as low as one cycle per byte.  UMAC relies on
   addition of 32-bit and 64-bit numbers and multiplication of 32-bit
   numbers, operations well-supported by contemporary machines.

   To generate the authentication tag on a given message, a "universal"
   hash function is applied to the message and key to produce a short,
   fixed-length hash value, and this hash value is then xor'ed with a
   key-derived pseudorandom pad.  UMAC enjoys a rigorous security
   analysis, and its only internal "cryptographic" component is a block
   cipher used to generate the pseudorandom pads and internal key
   material.

Krovetz                      Informational                      [Page 1]
RFC 4418                          UMAC                        March 2006

Table of Contents

   1. Introduction ....................................................3
   2. Notation and Basic Operations ...................................4
      2.1. Operations on strings ......................................4
      2.2. Operations on Integers .....................................5
      2.3. String-Integer Conversion Operations .......................6
      2.4. Mathematical Operations on Strings .........................6
      2.5. ENDIAN-SWAP: Adjusting Endian Orientation ..................6
           2.5.1. ENDIAN-SWAP Algorithm ...............................6
   3. Key- and Pad-Derivation Functions ...............................7
      3.1. Block Cipher Choice ........................................7
      3.2. KDF: Key-Derivation Function ...............................8
           3.2.1. KDF Algorithm .......................................8
      3.3. PDF: Pad-Derivation Function ...............................8
           3.3.1. PDF Algorithm .......................................9
   4. UMAC Tag Generation ............................................10
      4.1. UMAC Algorithm ............................................10
      4.2. UMAC-32, UMAC-64, UMAC-96, and UMAC-128 ...................10
   5. UHASH: Universal Hash Function .................................10
      5.1. UHASH Algorithm ...........................................11
      5.2. L1-HASH: First-Layer Hash .................................12
           5.2.1. L1-HASH Algorithm ..................................12
           5.2.2. NH Algorithm .......................................13
      5.3. L2-HASH: Second-Layer Hash ................................14
           5.3.1. L2-HASH Algorithm ..................................14
           5.3.2. POLY Algorithm .....................................15
      5.4. L3-HASH: Third-Layer Hash .................................16
           5.4.1. L3-HASH Algorithm ..................................16
   6. Security Considerations ........................................17
      6.1. Resistance to Cryptanalysis ...............................17
      6.2. Tag Lengths and Forging Probability .......................17
      6.3. Nonce Considerations ......................................19
      6.4. Replay Attacks ............................................20
      6.5. Tag-Prefix Verification ...................................21
      6.6. Side-Channel Attacks ......................................21
   7. Acknowledgements ...............................................21
   Appendix. Test Vectors ............................................22
   References ........................................................24
      Normative References ...........................................24
      Informative References .........................................24

Krovetz                      Informational                      [Page 2]
RFC 4418                          UMAC                        March 2006

1.  Introduction

   UMAC is a message authentication code (MAC) algorithm designed for
   high performance.  It is backed by a rigorous formal analysis, and
   there are no intellectual property claims made by any of the authors
   to any ideas used in its design.

   UMAC is a MAC in the style of Wegman and Carter [4, 7].  A fast
   "universal" hash function is used to hash an input message M into a
   short string.  This short string is then masked by xor'ing with a