Let K_1, K_2, ..., K_t be 4-byte strings
so that K_1 || K_2 || ... || K_t is a prefix of K.
//
// Perform NH hash on the chunks, pairing words for multiplication
// which are 4 apart to accommodate vector-parallelism.
//
Y = zeroes(8)
i = 1
while (i < t) do
Y = Y +_64 ((M_{i+0} +_32 K_{i+0}) *_64 (M_{i+4} +_32 K_{i+4}))
Y = Y +_64 ((M_{i+1} +_32 K_{i+1}) *_64 (M_{i+5} +_32 K_{i+5}))
Y = Y +_64 ((M_{i+2} +_32 K_{i+2}) *_64 (M_{i+6} +_32 K_{i+6}))
Y = Y +_64 ((M_{i+3} +_32 K_{i+3}) *_64 (M_{i+7} +_32 K_{i+7}))
i = i + 8
end while
Return Y
5.3. L2-HASH: Second-Layer Hash
The second-layer rehashes the L1-HASH output using a polynomial hash
called POLY. If the L1-HASH output is long, then POLY is called once
on a prefix of the L1-HASH output and called using different settings
on the remainder. (This two-step hashing of the L1-HASH output is
needed only if the message length is greater than 16 megabytes.)
Careful implementation of POLY is necessary to avoid a possible
timing attack (see Section 6.6 for more information).
5.3.1. L2-HASH Algorithm
Input:
K, string of length 24 bytes.
M, string of length less than 2^64 bytes.
Output:
Y, string of length 16 bytes.
Compute y using the following algorithm.
//
// Extract keys and restrict to special key-sets
//
Mask64 = uint2str(0x01ffffff01ffffff, 8)
Mask128 = uint2str(0x01ffffff01ffffff01ffffff01ffffff, 16)
k64 = str2uint(K[1...8] and Mask64)
k128 = str2uint(K[9...24] and Mask128)
//
// If M is no more than 2^17 bytes, hash under 64-bit prime,
// otherwise, hash first 2^17 bytes under 64-bit prime and
// remainder under 128-bit prime.
//
if (bytelength(M) <= 2^17) then // 2^14 64-bit words
//
// View M as an array of 64-bit words, and use POLY modulo
// prime(64) (and with bound 2^64 - 2^32) to hash it.
//
y = POLY(64, 2^64 - 2^32, k64, M)
else
M_1 = M[1...2^17]
M_2 = M[2^17 + 1 ... bytelength(M)]
M_2 = zeropad(M_2 || uint2str(0x80,1), 16)
y = POLY(64, 2^64 - 2^32, k64, M_1)
y = POLY(128, 2^128 - 2^96, k128, uint2str(y, 16) || M_2)
end if
Y = uint2str(y, 16)
Return Y
5.3.2. POLY Algorithm
Input:
wordbits, the integer 64 or 128.
maxwordrange, positive integer less than 2^wordbits.
k, integer in the range 0 ... prime(wordbits) - 1.
M, string with length divisible by (wordbits / 8) bytes.
Output:
y, integer in the range 0 ... prime(wordbits) - 1.
Compute y using the following algorithm.
//
// Define constants used for fixing out-of-range words
//
wordbytes = wordbits / 8
p = prime(wordbits)
offset = 2^wordbits - p
marker = p - 1
//
// Break M into chunks of length wordbytes bytes
//
n = bytelength(M) / wordbytes
Let M_1, M_2, ..., M_n be strings of length wordbytes bytes
so that M = M_1 || M_2 || ... || M_n
//
// Each input word m is compared with maxwordrange. If not smaller
// then ’marker’ and (m - offset), both in range, are hashed.
//
y = 1
for i = 1 to n do
m = str2uint(M_i)
if (m >= maxwordrange) then
y = (k * y + marker) mod p
y = (k * y + (m - offset)) mod p
else
y = (k * y + m) mod p
end if
end for
Return y
5.4. L3-HASH: Third-Layer Hash
The output from L2-HASH is 16 bytes long. This final hash function
hashes the 16-byte string to a fixed length of 4 bytes.
5.4.1. L3-HASH Algorithm
Input:
K1, string of length 64 bytes.
K2, string of length 4 bytes.
M, string of length 16 bytes.
Output:
Y, string of length 4 bytes.
Compute Y using the following algorithm.
y = 0
//
// Break M and K1 into 8 chunks and convert to integers
//
for i = 1 to 8 do
M_i = M [(i - 1) * 2 + 1 ... i * 2]
K_i = K1[(i - 1) * 8 + 1 ... i * 8]
m_i = str2uint(M_i)
k_i = str2uint(K_i) mod prime(36)
end for
//
// Inner-product hash, extract last 32 bits and affine-translate
//
y = (m_1 * k_1 + ... + m_8 * k_8) mod prime(36)
y = y mod 2^32
Y = uint2str(y, 4)
Y = Y xor K2
Return Y
6. Security Considerations
As a message authentication code specification, this entire document
is about security. Here we describe some security considerations
important for the proper understanding and use of UMAC.
6.1. Resistance to Cryptanalysis
The strength of UMAC depends on the strength of its underlying
cryptographic functions: the key-derivation function (KDF) and the
pad-derivation function (PDF). In this specification, both
operations are implemented using a block cipher, by default the
Advanced Encryption Standard (AES). However, the design of UMAC
allows for the replacement of these components. Indeed, it is
possible to use other block ciphers or other cryptographic objects,
such as (properly keyed) SHA-1 or HMAC for the realization of the KDF
or PDF.
The core of the UMAC design, the UHASH function, does not depend on
cryptographic assumptions: its strength is specified by a purely
mathematical property stated in terms of collision probability, and
this property is proven unconditionally [3, 6]. This means the
strength of UHASH is guaranteed regardless of advances in
cryptanalysis.
The analysis of UMAC [3, 6] shows this scheme to have provable
security, in the sense of modern cryptography, by way of tight
reductions. What this means is that an adversarial attack on UMAC
that forges with probability that significantly exceeds the
established collision probability of UHASH will give rise to an
attack of comparable complexity. This attack will break the block
cipher, in the sense of distinguishing the block cipher from a family
of random permutations. This design approach essentially obviates
the need for cryptanalysis on UMAC: cryptanalytic efforts might as
well focus on the block cipher, the results imply.
6.2. Tag Lengths and Forging Probability
A MAC algorithm is used to authenticate messages between two parties
that share a secret MAC key K. An authentication tag is computed for
a message using K and, in some MAC algorithms such as UMAC, a nonce.
Messages transmitted between parties are accompanied by their tag
and, possibly, nonce. Breaking the MAC means that the attacker is
able to generate, on its own, with no knowledge of the key K, a new
message M (i.e., one not previously transmitted between the
legitimate parties) and to compute on M a correct authentication tag
under the key K. This is called a forgery. Note that if the
authentication tag is specified to be of length t, then the attacker
can trivially break the MAC with probability 1/2^t. For this, the
attacker can just generate any message of its choice and try a random
tag; obviously, the tag is correct with probability 1/2^t. By
repeated guesses, the attacker can increase linearly its probability
of success.
In the case of UMAC-64, for example, the above guessing-attack
strategy is close to optimal. An adversary can correctly guess an
8-byte UMAC tag with probability 1/2^64 by simply guessing a random
value. The results of [3, 6] show that no attack strategy can
produce a correct tag with probability better than 1/2^60 if UMAC
were to use a random function in its work rather than AES. Another
result [2], when combined with [3, 6], shows that so long as AES is
secure as a pseudorandom permutation, it can be used instead of a
random function without significantly increasing the 1/2^60 forging
probability, assuming that no more than 2^64 messages are
authenticated. Likewise, 32-, 96-, and 128-bit tags cannot be forged
with more than 1/2^30, 1/2^90, and 1/2^120 probability plus the
probability of a successful attack against AES as a pseudorandom
permutation.
AES has undergone extensive study and is assumed to be very secure as
a pseudorandom permutation. If we assume that no attacker with
feasible computational power can distinguish randomly-keyed AES from
a randomly-chosen permutation with probability delta (more precisely,
delta is a function of the computational resources of the attacker
and of its ability to sample the function), then we obtain that no
such attacker can forge UMAC with probability greater than 1/2^30,
1/^60, 1/2^90, or 1/2^120, plus 3*delta. Over N forgery attempts,
forgery occurs with probability no more than N/2^30, N/^60, N/2^90,
or N/2^120, plus 3*delta. The value delta may exceed 1/2^30, 1/2^60,
1/2^90, or 1/2^120, in which case the probability of UMAC forging is
dominated by a term representing the security of AES.
With UMAC, off-line computation aimed at exceeding the forging
probability is hopeless as long as the underlying cipher is not
broken. An attacker attempting to forge UMAC tags will need to
interact with the entity that verifies message tags and try a large
number of forgeries before one is likely to succeed. The system
architecture will determine the extent to which this is possible. In
a well-architected system, there should not be any high-bandwidth
capability for presenting forged MACs and determining if they are
valid. In particular, the number of authentication failures at the
verifying party should be limited. If a large number of such
attempts are detected, the session key in use should be dropped and
the event be recorded in an audit log.
Let us reemphasize: a forging probability of 1/2^60 does not mean
that there is an attack that runs in 2^60 time; to the contrary, as
long as the block cipher in use is not broken there is no such attack
for UMAC. Instead, a 1/2^60 forging probability means that if an
attacker could have N forgery attempts, then the attacker would have
no more than N/2^60 probability of getting one or more of them right.
It should be pointed out that once an attempted forgery is
successful, it is possible, in principle, that subsequent messages
under this key may be easily forged. This is important to understand
in gauging the severity of a successful forgery, even though no such
attack on UMAC is known to date.
In conclusion, 64-bit tags seem appropriate for many security
architectures and commercial applications. If one wants a more
conservative option, at a cost of about 50% or 100% more computation,
UMAC can produce 96- or 128-bit tags that have basic collision
probabilities of at most 1/2^90 and 1/2^120. If one needs less
security, with the benefit of about 50% less computation, UMAC can
produce 32-bit tags. In this case, under the same assumptions as
before, one cannot forge a message with probability better than
1/2^30. Special care must be taken when using 32-bit tags because
1/2^30 forgery probability is considered fairly high. Still, high-
speed low-security authentication can be applied usefully on low-
value data or rapidly-changing key environments.
6.3. Nonce Considerations
UMAC requires a nonce with length in the range 1 to BLOCKLEN bytes.
All nonces in an authentication session must be equal in length. For
secure operation, no nonce value should be repeated within the life
of a single UMAC session key. There is no guarantee of message
authenticity when a nonce is repeated, and so messages accompanied by
a repeated nonce should be considered inauthentic.
To authenticate messages over a duplex channel (where two parties
send messages to each other), a different key could be used for each
direction. If the same key is used in both directions, then it is
crucial that all nonces be distinct. For example, one party can use
even nonces while the other party uses odd ones. The receiving party
must verify that the sender is using a nonce of the correct form.
This specification does not indicate how nonce values are created,
updated, or communicated between the entity producing a tag and the
entity verifying a tag. The following are possibilities:
1. The nonce is an 8-byte unsigned number, Counter, which is
initialized to zero, which is incremented by one following the
generation of each authentication tag, and which is always
communicated along with the message and the authentication tag.
An error occurs at the sender if there is an attempt to
authenticate more than 2^64 messages within a session.
2. The nonce is a BLOCKLEN-byte unsigned number, Counter, which is
initialized to zero and which is incremented by one following the
generation of each authentication tag. The Counter is not
explicitly communicated between the sender and receiver.
Instead, the two are assumed to communicate over a reliable
transport, and each maintains its own counter so as to keep track
of what the current nonce value is.
3. The nonce is a BLOCKLEN-byte random value. (Because repetitions
in a random n-bit value are expected at around 2^(n/2) trials,
the number of messages to be communicated in a session using
n-bit nonces should not be allowed to approach 2^(n/2).)
We emphasize that the value of the nonce need not be kept secret.
When UMAC is used within a higher-level protocol, there may already
be a field, such as a sequence number, which can be co-opted so as to
specify the nonce needed by UMAC [5]. The application will then
specify how to construct the nonce from this already-existing field.
6.4. Replay Attacks
A replay attack entails the attacker repeating a message, nonce, and
authentication tag. In many applications, replay attacks may be
quite damaging and must be prevented. In UMAC, this would normally
be done at the receiver by having the receiver check that no nonce
value is used twice. On a reliable connection, when the nonce is a
counter, this is trivial. On an unreliable connection, when the
nonce is a counter, one would normally cache some window of recent
nonces. Out-of-order message delivery in excess of what the window
allows will result in rejecting otherwise valid authentication tags.
We emphasize that it is up to the receiver when a given (message,
nonce, tag) triple will be deemed authentic. Certainly, the tag
should be valid for the message and nonce, as determined by UMAC, but
the message may still be deemed inauthentic because the nonce is
detected to be a replay.
6.5. Tag-Prefix Verification
UMAC’s definition makes it possible to implement tag-prefix
verification; for example, a receiver might verify only the 32-bit
prefix of a 64-bit tag if its computational load is high. Or a
receiver might reject out-of-hand a 64-bit tag whose 32-bit prefix is
incorrect. Such practices are potentially dangerous and can lead to
attacks that reduce the security of the session to the length of the
verified prefix. A UMAC key (or session) must have an associated and
immutable tag length and the implementation should not leak
information that would reveal if a given proper prefix of a tag is
valid or invalid.
6.6. Side-Channel Attacks
Side-channel attacks have the goal of subverting the security of a
cryptographic system by exploiting its implementation
characteristics. One common side-channel attack is to measure system
response time and derive information regarding conditions met by the
data being processed. Such attacks are known as "timing attacks".
Discussion of timing and other side-channel attacks is outside of
this document’s scope. However, we warn that there are places in the
UMAC algorithm where timing information could be unintentionally
leaked. In particular, the POLY algorithm (Section 5.3.2) tests
whether a value m is out of a particular range, and the behavior of
the algorithm differs depending on the result. If timing attacks are
to be avoided, care should be taken to equalize the computation time
in both cases. Timing attacks can also occur for more subtle
reasons, including caching effects.
7. Acknowledgements
David McGrew and Scott Fluhrer, of Cisco Systems, played a
significant role in improving UMAC by encouraging us to pay more
attention to the performance of short messages. Thanks go to Jim
Schaad and to those who made helpful suggestions to the CFRG mailing
list for improving this document during RFC consideration. Black,
Krovetz, and Rogaway have received support for this work under NSF
awards 0208842, 0240000, and 9624560, and a gift from Cisco Systems.
Appendix. Test Vectors
Following are some sample UMAC outputs over a collection of input
values, using AES with 16-byte keys. Let
K = "abcdefghijklmnop" // A 16-byte UMAC key
N = "bcdefghi" // An 8-byte nonce
The tags generated by UMAC using key K and nonce N are:
Message 32-bit Tag 64-bit Tag 96-bit Tag
------- ---------- ---------- ----------
<empty> 113145FB 6E155FAD26900BE1 32FEDB100C79AD58F07FF764
’a’ * 3 3B91D102 44B5CB542F220104 185E4FE905CBA7BD85E4C2DC
’a’ * 2^10 599B350B 26BF2F5D60118BD9 7A54ABE04AF82D60FB298C3C
’a’ * 2^15 58DCF532 27F8EF643B0D118D 7B136BD911E4B734286EF2BE
’a’ * 2^20 DB6364D1 A4477E87E9F55853 F8ACFA3AC31CFEEA047F7B11
’a’ * 2^25 5109A660 2E2DBC36860A0A5F 72C6388BACE3ACE6FBF062D9
’abc’ * 1 ABF3A3A0 D4D7B9F6BD4FBFCF 883C3D4B97A61976FFCF2323
’abc’ * 500 ABEB3C8B D4CF26DDEFD5C01A 8824A260C53C66A36C9260A6
The first column lists a small sample of messages that are strings of
repeated ASCII ’a’ bytes or ’abc’ strings. The remaining columns
give in hexadecimal the tags generated when UMAC is called with the
corresponding message, nonce N and key K.
When using key K and producing a 64-bit tag, the following relevant
keys are generated:
Iteration 1 Iteration 2
----------- -----------
NH (Section 5.2.2)
K_1 ACD79B4F C6DFECA2
K_2 6EDA0D0E 964A710D
K_3 1625B603 AD7EDE4D
K_4 84F9FC93 A1D3935E
K_5 C6DFECA2 62EC8672
...
K_256 0BF0F56C 744C294F
L2-HASH (Section 5.3.1)
k64 0094B8DD0137BEF8 01036F4D000E7E72
L3-HASH (Section 5.4.1)
k_5 056533C3A8 0504BF4D4E
k_6 07591E062E 0126E922FF
k_7 0C2D30F89D 030C0399E2
k_8 046786437C 04C1CB8FED
K2 2E79F461 A74C03AA
(Note that k_1 ... k_4 are not listed in this example because they
are multiplied by zero in L3-HASH.)
When generating a 64-bit tag on input "’abc’ * 500", the following
intermediate results are produced:
Iteration 1
-----------
L1-HASH E6096F94EDC45CAC1BEDCD0E7FDAA906
L2-HASH 0000000000000000A6C537D7986FA4AA
L3-HASH 05F86309
Iteration 2
-----------
L1-HASH 2665EAD321CFAE79C82F3B90261641E5
L2-HASH 00000000000000001D79EAF247B394BF
L3-HASH DF9AD858
Concatenating the two L3-HASH results produces a final UHASH result
of 05F86309DF9AD858. The pad generated for nonce N is
D13745D4304F1842, which when xor’ed with the L3-HASH result yields a
tag of D4CF26DDEFD5C01A.
References
Normative References
[1] FIPS-197, "Advanced Encryption Standard (AES)", National
Institute of Standards and Technology, 2001.
Informative References
[2] D. Bernstein, "Stronger security bounds for permutations",
unpublished manuscript, 2005. This work refines "Stronger
security bounds for Wegman-Carter-Shoup authenticators",
Advances in Cryptology - EUROCRYPT 2005, LNCS vol. 3494, pp.
164-180, Springer-Verlag, 2005.
[3] 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.
[4] L. Carter and M. Wegman, "Universal classes of hash functions",
Journal of Computer and System Sciences, 18 (1979), pp. 143-
154.
[5] Kent, S., "IP Encapsulating Security Payload (ESP)", RFC 4303,
December 2005.
[6] T. Krovetz, "Software-optimized universal hashing and message
authentication", UMI Dissertation Services, 2000.
[7] M. Wegman and L. Carter, "New hash functions and their use in
authentication and set equality", Journal of Computer and
System Sciences, 22 (1981), pp. 265-279.
Authors’ Addresses
John Black
Department of Computer Science
University of Colorado
Boulder, CO 80309
USA
EMail: jrblack@cs.colorado.edu
Shai Halevi
IBM T.J. Watson Research Center
P.O. Box 704
Yorktown Heights, NY 10598
USA
EMail: shaih@alum.mit.edu
Alejandro Hevia
Department of Computer Science
University of Chile
Santiago 837-0459
CHILE
EMail: ahevia@dcc.uchile.cl
Hugo Krawczyk
IBM Research
19 Skyline Dr
Hawthorne, NY 10533
USA
EMail: hugo@ee.technion.ac.il
Ted Krovetz (Editor)
Department of Computer Science
California State University
Sacramento, CA 95819
USA
EMail: tdk@acm.org
Phillip Rogaway
Department of Computer Science
University of California
Davis, CA 95616
USA
and
Department of Computer Science
Faculty of Science
Chiang Mai University
Chiang Mai 50200
THAILAND
EMail: rogaway@cs.ucdavis.edu
Full Copyright Statement
Copyright (C) The Internet Society (2006).