Internet DRAFT - draft-krovetz-umac-ae

draft-krovetz-umac-ae









CFRG Working Group                                            T. Krovetz
INTERNET-DRAFT                                            CSU Sacramento
Expires December 2005                                          June 2005


             The UMAC-AE Authenticated-Encryption Algorithm
                     <draft-krovetz-umac-ae-00.txt>

   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.

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   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/1id-abstracts.html

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

Abstract

   This document specifies UMAC-AE, a shared-key algorithm that
   simultaneously encrypts data using a block cipher in counter mode
   while also authenticating the data with UMAC.  At its peak rate,
   using AES as the block cipher, UMAC-AE encrypts and authenticates
   data at a cost of about 10% more than simple encryption.  UMAC is
   unencumbered by intellectual property claims and can be used freely.
   Pairing UMAC with a license-free block cipher, such as AES, provides
   fast and license-free authenticated encryption.







T. Krovetz                Expires December 2005                [Page 1]

INTERNET-DRAFT                   UMAC-AE                       June 2005


1  Introduction

   An authenticated-encryption scheme allows parties who share a key to
   communicate in a way that ensures both privacy and authenticity.
   UMAC-AE achieves both goals by combining proven and efficient
   methods.  Privacy is provided by a block cipher in counter-mode,
   while authentication of the encrypted data (along with optional
   unencrypted header data) is authenticated using UMAC.  Both counter-
   mode encryption and UMAC are efficient, provably-secure,
   parallelizable and have been well studied [Modes, NESSIE, UMAC99,
   UMAC00].  The composition of encryption and message authentication
   algorithms has also been well studied [Order]. Several other
   authenticated-encryption schemes have been proposed for
   standardization [NIST Modes].

   Both UMAC and counter-mode encryption require the services of a block
   cipher.  Typically, AES will serve this role, but any block cipher
   with a block length of at least 128 bits will suffice.  A single
   block cipher key is provided to UMAC-AE, and the key is safely used
   to initialize both encryption and authentication.  The user is
   required to supply a new nonce N for each encryption.  UMAC-AE allows
   a header H, or any other data that requires authentication but not
   encryption, to be specified when one encrypts.  UMAC-AE encryption
   protects the privacy of plaintext data M, and the authenticity of
   header H, nonce N, and M.  M and H can have any bitlength upto 2^54
   and 2^64 bits, respectively.  The ciphertext (C, T) one gets by
   encrypting M in the presence of H consists of a ciphertext C having
   the same length as M, plus an authentication tag T.  Communicating
   parties can choose to use 32-, 64-, 96- or 128-bit authentication
   tags, depending on their security needs.

   UMAC-AE has many nice properties.  UMAC-AE is on-line: one need not
   know the length of H or M to proceed with encryption, nor need one
   know the length of H or C to proceed with decryption.  UMAC-AE is
   parallelizable: both the encryption and authentication of data can be
   done in any order at the granularity of the block cipher's block
   length.  UMAC-AE enjoys provable security: the mode of operation is
   secure assuming that the underlying block cipher is secure.

   There are no known intellectual property restrictions on any aspect
   of UMAC-AE.  AES and UMAC are defined in other documents [AES, UMAC
   Spec].


2  Notation and Basic Operations

   There are two types of variables used in this specification, strings
   and integers.  String variables are always written with an initial



T. Krovetz                Expires December 2005                [Page 2]

INTERNET-DRAFT                   UMAC-AE                       June 2005


   upper-case letter while integer variables are written in all lower-
   case.  Functions, except for the simple ones defined in this section,
   are written in all upper-case.  Whenever a variable is followed by an
   underscore ("_"), the underscore is intended to denote a subscript,
   with the subscripted expression requiring evaluation to resolve the
   meaning of the variable.  For example, when i = 2, then M_i refers to
   the variable M_2.

   The following operations are used throughout the definition of UMAC-
   AE.

     c^i            The integer c raised to the i-th power.

     ceil(x)        The smallest integer no smaller than x.

     bitlength(S)   The length of string S in bits (eg, bitlength(101) =
                    3).

     zeros(n)       The string made of n zero-bits.

     S xor T        The string that is the bitwise exclusive-or of S and
                    T.  Strings S and T must have the same length.

     S[i]           The i-th bit of the string S (indices begin at 1).

     S[i..j]        The substring of S consisting of bits i through j.

     S || T         The string S concatenated with string T (eg, 000 ||
                    111 = 000111).

     str2num(S)     The non-negative integer whose binary representation
                    is the string S.  More formally, if S is t bits long
                    then str2num(S) = 2^{t-1} * S[1] + 2^{t-2} * S[2] +
                    ... + 2^{1} * S[t-1] + S[t].

     num2str(n,i)   The i-bit string S such that str2num(S) = n.


3  UMAC-AE Parameters

   UMAC-AE requires the services of a block cipher and of UMAC.  The
   selection of a block cipher defines the following constants and
   functions.

     BLOCKLEN         The length of the plaintext block that the block
                      cipher operates on.





T. Krovetz                Expires December 2005                [Page 3]

INTERNET-DRAFT                   UMAC-AE                       June 2005


     KEYLEN           The block cipher's key length, in bits.

     ENCIPHER(K,P)    The application of the block cipher on P (a string
                      of BLOCKLEN bits) using key K (a string of KEYLEN
                      bits).

   As an example, if AES is used with 192-bit keys, then BLOCKLEN would
   equal 128 (because AES employs 128-bit blocks), KEYLEN would equal
   192, and ENCIPHER would refer to the AES function.

   We note that the definition of UMAC involves the use of a block
   cipher [UMAC spec]. Hence, in UMAC-AE a block cipher is used for two
   purposes: as the basis for the counter-mode encryption of data and as
   part of the internal operation of UMAC.  The present specification of
   UMAC-AE uses the same block cipher for both purposes. Unless
   specified otherwise, AES with 128-bit keys shall be used as the block
   cipher.

   AES and UMAC are defined in other documents [AES, UMAC Spec].


4  Encryption: UMAC-AE-ENCRYPT

   This function computes a ciphertext and authentication tag when given
   a message, header, nonce and key.

   Function name:
     UMAC-AE-ENCRYPT
   Input:
     K, string of KEYLEN bits                 // Key
     N, string of BLOCKLEN - 48 bits          // Nonce
     H, string of no more than 2^64 bits      // Header
     M, string of no more than 2^54 bits      // Plaintext
     taglen, integer 32, 64, 96 or 128        // Tag length requested
   Output:
     C, string of length equal to M           // Ciphertext
     T, string of taglen bits                 // Authentication tag

   Compute C and T using the following algorithm.

     //
     // Break M into blocks
     //
     m = max(1,ceil(bitlength(M) / BLOCKLEN))
     Let M_1, M_2, ..., M_m be strings such that M = M_1 || M_2 || ...
       || M_m and bitlength(M_i) = BLOCKLEN for all 0 < i < m.

     //



T. Krovetz                Expires December 2005                [Page 4]

INTERNET-DRAFT                   UMAC-AE                       June 2005


     // Initialize auxiliary data
     //
     UMACKey = ENCIPHER(K,zeros(BLOCKLEN))
     ctr = 0

     //
     // Encrypt blocks
     //
     for i = 1 to m do
        ctr = ctr + 1
        Temp = ENCIPHER(K, N || num2str(ctr, 48))
        C_i = M_i xor Temp[1..bitlength(M_i)]
     end for
     C = C_1 || C_2 || ... || C_m

     //
     // Compute authentication tag
     //
     hpadlength = (256 - (bitlength(H) mod 256)) mod 256
     cpadlength = (256 - (bitlength(C) mod 256)) mod 256
     UMACData = H || zeros(hpadlen) || C || zeros(cpadlen) ||
                num2str(bitlength(H), 64) || num2str(bitlength(C), 64)
     T = UMAC(UMACKey, UMACData, N, taglen/8)



5  Decryption: UMAC-AE-DECRYPT

   This function takes as input a ciphertext, header, authentication
   tag, nonce and key, and returns a plaintext and a determination as to
   whether the given tag is valid for the given ciphertext, header,
   nonce and key.

   Function name:
     UMAC-AE-DECRYPT
   Input:
     K, string of KEYLEN bits                 // Key
     N, string of BLOCKLEN - 48 bits          // Nonce
     H, string of no more than 2^64 bits      // Header
     C, string of no more than 2^54 bits      // Ciphertext
     T, string of 32, 64, 96 or 128 bits      // Authentication tag
   Output:
     M, string of length equal to C           // Plaintext
     V, boolean                               // Validity indicator

   Compute M and V using the following algorithm.

     //



T. Krovetz                Expires December 2005                [Page 5]

INTERNET-DRAFT                   UMAC-AE                       June 2005


     // Break C into blocks
     //
     m = max(1,ceil(bitlength(C) / BLOCKLEN))
     Let C_1, C_2, ..., C_m be strings such that C = C_1 || C_2 || ...
       || C_m and bitlength(C_i) = BLOCKLEN for all 0 < i < m.

     //
     // Initialize auxiliary data
     //
     UMACKey = ENCIPHER(K,zeros(BLOCKLEN))
     ctr = 0

     //
     // Compute authentication tag
     //
     hpadlength = (256 - (bitlength(H) mod 256)) mod 256
     cpadlength = (256 - (bitlength(C) mod 256)) mod 256
     UMACData = H || zeros(hpadlen) || C || zeros(cpadlen) ||
                num2str(bitlength(H), 64) || num2str(bitlength(C), 64)
     ValidTag = UMAC(UMACKey, UMACData, N, bitlength(T)/8)

     //
     // Decrypt blocks
     //
     for i = 1 to m do
        ctr = ctr + 1
        Temp = ENCIPHER(K, N || num2str(ctr, 48))
        M_i = C_i xor Temp[1..bitlength(C_i)]
     end for
     M = M_1 || M_2 || ... || M_m

     //
     // Compute results
     //
     if T = ValidTag then
        V = true
     else
        V = false
     end if


6  Security Considerations

   UMAC-AE achieves two security properties, message privacy and message
   authenticity.  Privacy is "indistinguishability from random bits",
   meaning that an adversary is unable to distinguish UMAC-AE
   encryptions from an equal number of random bits.  Authenticity is
   "authenticity of ciphertexts", meaning that an adversary is unable to



T. Krovetz                Expires December 2005                [Page 6]

INTERNET-DRAFT                   UMAC-AE                       June 2005


   produce any valid (N,H,C,T) quadruple that it has not already
   acquired.  The privacy and the authenticity guarantee depend on the
   underlying block cipher being secure in the sense of a strong
   pseudorandom permutation.  Thus if UMAC-AE is used with a block
   cipher that is not secure as a strong pseudorandom permutation, the
   security guarantees vanish.  The need for the strong pseudorandom
   permutation property means that UMAC-AE should be used with a
   conservatively designed, well-trusted block cipher, such as AES.

   The privacy properties of UMAC-AE degrade as per s^2 / 2^BLOCKLEN,
   where s is the total number of blocks that the adversary acquires,
   while the authenticity guarantees degrade as does t / 2^taglen, where
   t is the number of UMAC-AE invocations.  The consequence of these
   formulas is that the proven security vanishes when s becomes as large
   as 2^{BLOCKLEN/2} or t becomes as large as 2^{taglen - 32}.  Thus the
   user should never use a key to generate an amount of ciphertext that
   is near to, or exceeds, 2^{BLOCKLEN/2} blocks or invokes UMAC-AE
   anything near 2^{taglen - 32} times.  Block ciphers typically have
   blocksizes of 64 or 128 bits, and the above restriction is a
   significant one if the blocklength is not more than 64 bits.
   Therefore UMAC-AE has been designed to work with a block cipher
   having a blocklength of at least 128 bits.  The mode may then be used
   to encrypt upto 2^48 blocks (2^56 bits) or 2^{taglen - 32} total
   applications, keeping an adversary's chance to do damage at no more
   than about 2^{-32}.

   It is crucial that, as one encrypts strings, one does not repeat a
   nonce.  The security definitions assume this, for both privacy and
   authenticity.  The implementor must ensure that, with overwhelming
   probability, this assumption is achieved by the implementation that
   uses UMAC-AE.  The nonce need not be secret, and a counter may be
   used for it.  If two parties send UMAC-AE-encrypted messages to one
   another using the same key, then the space of nonces used by the two
   parties should be partitioned so that no nonce that could be used by
   one party to encrypt could be used by the other to encrypt.  For
   example, one party could send data with odd nonces while the other
   sends data with even nonces.

   When a ciphertext decrypts as "invalid" it is the implementor's
   responsibility to make sure that no information beyond this fact is
   made adversarially available.

   UMAC-AE encryption produces a tag T of 32, 64, 96 or 128 bits.  The
   length taglen of the tag used impacts the adversary's ability to
   forge: it will always be trivial for the adversary to forge with
   probability 2^{-taglen}.  It is up to the application designer to
   choose an appropriate value for taglen.  For typical applications,
   the value should be 64 or more.  The taglen value should be



T. Krovetz                Expires December 2005                [Page 7]

INTERNET-DRAFT                   UMAC-AE                       June 2005


   determined at session setup and should be dictated by the message
   recipient.  The taglen value is not authenticated by the UMAC-AE
   algorithm and one must ensure that an attacker can not convince a
   recipient to employ unreasonably short authentication tags.

   The UMAC-AE encryption scheme reveals in the ciphertext the length of
   the plaintext.  Sometimes the length of the plaintext is a valuable
   piece of information that should be hidden.  For environments where
   "traffic analysis" is a concern, techniques beyond UMAC-AE encryption
   (typically involving padding) would be necessary.


7  Acknowledgments

   Thanks to Hugo Krawczyk for valuable comments.  This document shares
   some text with "draft-krovetz-ocb-00.txt", an Internet-Draft written
   by Ted Krovetz and Phil Rogaway.


Appendix - Test Vectors

   These are not yet available.


References

Normative References

   [AES]        FIPS-197, "Advanced Encryption Standard (AES)", National
                Institute of Standards and Technology, 2001.

   [UMAC Spec]  T. Krovetz (Editor), "UMAC: Message authentication code
                using universal hashing", Internet-Draft, draft-krovetz-
                umac-03.txt, 2004.

Informative References

   [Modes]      M. Bellare, A. Desai, E. Jokipii, P. Rogaway, "A
                concrete security treatment of symmetric encryption:
                Analysis of the DES modes of operation", Proceedings of
                38th Annual Symposium on Foundations of Computer
                Science, 1997.

   [NESSIE] New European Schemes for Signatures, Integrity, and
                Encryption, http://www.cryptonessie.org/.

   [NIST Modes] NIST Computer Security Resource Center, Symmetric Key
                Block Cipher Modes of Operation,



T. Krovetz                Expires December 2005                [Page 8]

INTERNET-DRAFT                   UMAC-AE                       June 2005


                http://www.nist.gov/modes/.

   [Order]      H. Krawczyk, "The order of encryption and authentication
                for protecting communications", Advances in Cryptology -
                CRYPTO 2001, Lecture Notes in Computer Science,
                Springer, 2001.

   [UMAC00]     T. Krovetz, "Software-optimized universal hashing and
                message authentication", UMI Dissertation Services,
                2000.

   [UMAC99]     J. Black, S. Halevi, H. Krawczyk, T. Krovetz, and P.
                Rogaway, "UMAC: Fast and provably secure message
                authentication", Advances in Cryptology - CRYPTO '99,
                LNCS vol. 1666, pp. 216-233, Springer-Verlag, 1999.


Author Contact Information

   Author's Address

     Ted Krovetz
     Department of Computer Science
     California State University
     Sacramento CA 95819
     USA

     EMail: tdk@acm.org


Full Copyright Statement

   Copyright (C) The Internet Society (2005).  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 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.








T. Krovetz                Expires December 2005                [Page 9]