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]
