ISO/IEC 9797-3:2011

INTERNATIONAL ISO/IEC
STANDARD 9797-3
First edition
2011-11-15
Information technology — Security
techniques — Message Authentication
Codes (MACs) —
Part 3:
Mechanisms using a universal hash-
function
Technologies de l'information — Techniques de sécurité — Codes
d'authentification de message (MAC) —
Partie 3: Mécanismes utilisant une fonction de hachage universelle

Reference number
©
ISO/IEC 2011
©  ISO/IEC 2011
All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized in any form or by any means,
electronic or mechanical, including photocopying and microfilm, without permission in writing from either ISO at the address below or
ISO's member body in the country of the requester.
ISO copyright office
Case postale 56  CH-1211 Geneva 20
Tel. + 41 22 749 01 11
Fax + 41 22 749 09 47
E-mail copyright@iso.org
Web www.iso.org
Published in Switzerland
ii © ISO/IEC 2011 – All rights reserved

Contents Page
Foreword . iv
Introduction . v
1  Scope . 1
2  Normative references . 1
3  Terms and definitions . 1
4  Symbols and abbreviated terms . 2
5  General model . 4
6  Mechanisms . 5
6.1  Introduction . 5
6.2  UMAC . 5
6.2.1  Description of UMAC . 5
6.2.2  Requirements . 5
6.2.3  Notation and auxiliary functions . 5
6.2.4  Key preprocessing . 9
6.2.5  Message preprocessing. 9
6.2.6  Message hashing . 9
6.2.7  Layered hash-functions . 10
6.2.8  Finalization . 12
6.3  Badger . 12
6.3.1  Description of Badger . 12
6.3.2  Requirements . 12
6.3.3  Notation and auxiliary functions . 13
6.3.4  Key preprocessing . 13
6.3.5  Message preprocessing. 14
6.3.6  Message hashing . 14
6.3.7  Finalization . 16
6.4  Poly1305-AES . 16
6.4.1  Description of Poly1305-AES . 16
6.4.2  Requirements . 16
6.4.3  Key preprocessing . 16
6.4.4  Message preprocessing. 16
6.4.5  Message hashing . 17
6.4.6  Finalization . 17
6.5  GMAC . 18
6.5.1  Description of GMAC . 18
6.5.2  Requirements . 18
6.5.3  Notation and auxiliary functions . 18
6.5.4  Key preprocessing . 19
6.5.5  Message preprocessing. 19
6.5.6  Message hashing . 19
6.5.7  Finalization . 19
Annex A (normative) Object Identifiers . 20
Annex B (informative) Test Vectors . 22
Annex C (informative) Security Information . 24
Bibliography . 25

© ISO/IEC 2011 – All rights reserved iii

Foreword
ISO (the International Organization for Standardization) and IEC (the International Electrotechnical
Commission) form the specialized system for worldwide standardization. National bodies that are members of
ISO or IEC participate in the development of International Standards through technical committees
established by the respective organization to deal with particular fields of technical activity. ISO and IEC
technical committees collaborate in fields of mutual interest. Other international organizations, governmental
and non-governmental, in liaison with ISO and IEC, also take part in the work. In the field of information
technology, ISO and IEC have established a joint technical committee, ISO/IEC JTC 1.
International Standards are drafted in accordance with the rules given in the ISO/IEC Directives, Part 2.
The main task of the joint technical committee is to prepare International Standards. Draft International
Standards adopted by the joint technical committee are circulated to national bodies for voting. Publication as
an International Standard requires approval by at least 75 % of the national bodies casting a vote.
Attention is drawn to the possibility that some of the elements of this document may be the subject of patent
rights. ISO and IEC shall not be held responsible for identifying any or all such patent rights.
ISO/IEC 9797-3 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 27, IT Security techniques.
ISO/IEC 9797 consists of the following parts, under the general title Information technology — Security
techniques — Message Authentication Codes (MACs):
 Part 1: Mechanisms using a block cipher
 Part 2: Mechanisms using a dedicated hash-function
 Part 3: Mechanisms using a universal hash-function
iv © ISO/IEC 2011 – All rights reserved

Introduction
In an IT environment, it is often required that one can verify that electronic data has not been altered in an
unauthorized manner and that one can provide assurance that a message has been originated by an entity in
possession of the secret key. A MAC (Message Authentication Code) algorithm is a commonly used data
integrity mechanism that can satisfy these requirements.
This part of ISO/IEC 9797 specifies four MAC algorithms using universal hash-functions: UMAC, Badger,
Poly1305-AES and GMAC.
These mechanisms can be used as data integrity mechanisms to verify that data has not been altered in an
unauthorized manner. They can also be used as message authentication mechanisms to provide assurance
that a message has been originated by an entity in possession of the secret key. The strength of the data
integrity mechanism and message authentication mechanism is dependent on the length (in bits) and secrecy
of the key, on the length (in bits) of a hash-code produced by the hash-function, on the strength of the hash-
function, on the length (in bits) of the MAC, and on the specific mechanism.
[7]
NOTE A general framework for the provision of integrity services is specified in ISO/IEC 10181-6 .
© ISO/IEC 2011 – All rights reserved v

INTERNATIONAL STANDARD ISO/IEC 9797-3:2011(E)

Information technology — Security techniques — Message
Authentication Codes (MACs) —
Part 3:
Mechanisms using a universal hash-function
1 Scope
This part of ISO/IEC 9797 specifies the following MAC algorithms that use a secret key and a universal
hash-function with an n-bit result to calculate an m-bit MAC based on the block ciphers specified in
ISO/IEC 18033-3 and the stream ciphers specified in ISO/IEC 18033-4:
a) UMAC;
b) Badger;
c) Poly1305-AES;
d) GMAC.
2 Normative references
The following referenced documents are indispensable for the application of this document. For dated
references, only the edition cited applies. For undated references, the latest edition of the referenced
document (including any amendments) applies.
ISO/IEC 9797-1, Information technology — Security techniques — Message Authentication Codes (MACs) —
Part 1: Mechanisms using a block cipher
ISO/IEC 18031, Information technology — Security techniques — Random bit generation
ISO/IEC 18033-3, Information technology — Security techniques — Encryption algorithms — Part 3: Block
ciphers
ISO/IEC 18033-4, Information technology — Security techniques — Encryption algorithms — Part 4: Stream
ciphers
3 Terms and definitions
For the purposes of this document, the terms and definitions given in ISO/IEC 9797-1 and the following apply.
3.1
empty string
string of symbols of length zero
© ISO/IEC 2011 – All rights reserved 1

3.2
key
sequence of symbols that controls the operation of a cryptographic transformation
3.3
nonce
number used once
3.4
prime number
positive integer greater than 1 which has no integer divisors other than 1 and itself
3.5
tag
result of a MAC algorithm, adjoined to a possibly encrypted message to provide integrity protection
3.6
universal hash-function
function mapping strings of bits to fixed-length strings of bits, indexed by a parameter called the key, satisfying
the property that for all distinct inputs, the probability over all keys that the outputs collide is small
[4]
NOTE Universal hash-functions were introduced by Carter and Wegman , and their application in MAC algorithms
[10]
was first described by Wegman and Carter .
4 Symbols and abbreviated terms
The following notation is used in this part of ISO/IEC 9797:
th
bit(S,n) Returns the integer 1 if the n bit of the string S is 1, otherwise returns the integer 0 (indices
begin at 1).
bitlength(S) Length of a string S in bits.
bitstr2uint(S) The non-negative integer whose binary representation is the string S. More formally, if S is t
t-1 t-2 1
bits long then bitstr2uint(S) = 2 * bit(S,1) + 2 * bit(S,2) + . + 2 * bit(S,t-1) + bit(S,t).
NOTE Bit strings are treated big-endian, i.e. the first bit is the most significant.
blocklen Block length of the underlying block cipher in octets.
ceil Rounding-up operation, i.e. if x is a floating-point number, then ceil(x) is the smallest integer n
with n  x.
Enc(K, X) Encryption of a plaintext block X under a key K using a block cipher Enc.
floor Rounding-down operation, i.e. if x is a floating-point number, then floor(x) is the largest integer
n with n  x.
H Hash value.
K Master key.
K Encryption key.
E
K Hash key.
H
keylen Block cipher key length in octets.
2 © ISO/IEC 2011 – All rights reserved

log Binary logarithm function.
M Message.
MAC Message authentication code.
max Largest value amongst those given as argument.
N Nonce.
octetlength(S) Length of a string S in octets (where S is assumed to have bitlength a multiple of 8).
8 16 8n-8
octetstr2uint(S) The non-negative integer defined as S[0] + 2 * S[1] + 2 * S[2] + . + 2 * S[n-1], where n =
octetlength(S).
NOTE Octet strings are treated little-endian, i.e. the first octet is the least significant.
n
prime(n) Largest prime number smaller than 2 , for any positive integer n.
NOTE The prime numbers used in this part of ISO/IEC 9797 are listed in Table 1.
Table 1 — Prime numbers
n prime(n) prime(n) in hexadecimal format
32 2 - 5 0x FFFFFFFB
36 2 - 5 0x 0000000F FFFFFFFB
64 2 - 59 0x FFFFFFFF FFFFFFC5
128 2 - 159 0x FFFFFFFF FFFFFFFF FFFFFFFF FFFFFF61
130 2 - 5 0x 00000003 FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFB

S[i] The i-th octet of the string S (indices begin at 0).
NOTE The specification for UMAC in 6.2 uses a starting index of 1 rather than 0.
S[i.j] The substring of S consisting of octets i through j.
taglen Length of the tag, in octets.
uint2bitstr(x,n) The n-octet string S such that bitstr2uint(S) = x.
uint2octetstr(x,n) The n-octet string S such that x = octetstr2uint(S).
X| Left-truncation of the block of bits X: if X has bit-length greater than or equal to s, then X| is
s s
the s-bit block consisting of the left-most s bits of X.
s s
X| Right-truncation of the block of bits X: if X has bit-length greater than or equal to s, then X| is
the s-bit block consisting of the right-most s bits of X.
X>>1 Right shift of a block of bits X by one position: the leftmost bit of Y = X>>1 will always be set to
zero.
|X| The length of X in bits.
zeropad(S,n) For positive integer n, the string S is padded with zero-bits to the nearest positive multiple of n
octets. Formally, zeropad(S,n) = S || T, where T is the shortest string of zero-bits (possibly
empty) so that S || T is non-empty and n divides octetlength(S || T).
© ISO/IEC 2011 – All rights reserved 3

 Bit-wise exclusive-OR operation on bit-strings. If A, B are strings of the same length then
AB is the string equal to the bit-wise logical exclusive-OR of A and B.
 Bit-wise logical AND operation on bit-strings. If A, B are strings of the same length then AB is
the string equal to the bit-wise logical AND of A and B.
+ Addition of two 32-bit strings, resulting in a 32-bit string. More formally, S + T =
32 32
uint2bitstr(bitstr2uint(S) + bitstr2uint(T) mod 2 , 4).
+ Addition of two 64-bit strings, resulting in a 64-bit string. More formally, S + T =
64 64
uint2bitstr(bitstr2uint(S) + bitstr2uint(T) mod 2 , 8).
*  Multiplication operator on integers.
* Multiplication of two 64-bit strings, resulting in a 64-bit string. More formally, S * T =
64 64
uint2bitstr(bitstr2uint(S) * bitstr2uint(T) mod 2 , 8).
NOTE The operations + , + and * correspond well with the addition and multiplication operations that are
32 64 64
performed efficiently by modern computers.
|| Concatenation of two bit strings. If A and B are bit strings of lengths a and b respectively, then
A || B is the bit string of length a+b whose left most (first) a bits are the bits of A, and whose
rightmost (last) b bits are the bits of B.
n
0 String consisting of n zero-bits.
n
1 String consisting of n one-bits.
{ } A bit-string with zero length.
 Multiplication in the field GF(2 ). The defining polynomial that determines the representation
128 2 7 128
of GF(2 ) is 1   .
NOTE Let U and V be 128-bit blocks. Then the 128-bit block W = U  V can be computed as follows:
a) Let W = 0 and Z = U.
b) For i = 1, 2, …, 128, perform the following two steps:
1) If bit(V,i) = 1 then let W = W  Z;
2) If bit(Z,128) = 0 then let Z = Z>>1; otherwise let Z = (Z>>1)  (11100001 || 0 ).
Variables in capital letters denote strings; variables in small letters are integers.
5 General model
Message authentication codes based on universal hashing makes use of an encryption algorithm (block
cipher or stream cipher). This type of message authentication codes has the special property that their
security can be proven under the assumption that the encryption algorithm is secure.
MAC algorithms based on universal hashing require a master key K, a message M and a nonce value N as
input. A MAC is computed using the following sequence of steps:
1) Key preprocessing. The master key K is used to generate a hash key K and an encryption key K .
H E
2) Message preprocessing. The input message M is encoded into the necessary input format for the
hash-function.
4 © ISO/IEC 2011 – All rights reserved

3) Message hashing. The encoded message is hashed under the control of the hash key K , using a
H
universal hash-function. The result is a hash value H of fixed, short length.
4) Finalization. The hash value H is encrypted under the control of the encryption key K . The result is
E
the message authentication code MAC.
For all mechanisms presented in this part of ISO/IEC 9797, the length of the input message is expected to
consist of an integer number of octets.
NOTE For all universal-hash based MAC algorithms, it is of utmost importance that a different nonce is used for each
new message that is authenticated under the same key. If this security requirement is not met, the security of the
algorithm is severely reduced.
6 Mechanisms
6.1 Introduction
In this clause, four mechanisms using a universal hash-function are specified.
6.2 UMAC
6.2.1 Description of UMAC
UMAC is a family of four MAC algorithms optimized for different output bit-lengths, denoted by UMAC-32,
UMAC-64, UMAC-96, and UMAC-128. UMAC can be used with any block cipher from ISO/IEC 18033-3. If the
block cipher used has key length |K| bits and block length |B| bits, then UMAC uses a |K|-bit key K, and the
length of the nonce N is between 8 and |B| bits. Depending on which member of the UMAC family is used, the
length of the MAC produced is 32, 64, 96, or 128 bits. This is represented by the parameter taglen, which can
be 4, 8, 12 or 16 octets, respectively. The length of the input message shall be less than 2 octets. The
message input to the UMAC function shall contain a whole number of octets, i.e. the bitlength shall be a
multiple of 8. If the bitlength is not a multiple of 8, this mechanism shall not be used.
[2]
NOTE 1 The version of UMAC specified here must not be confused with earlier versions of the UMAC algorithm, e.g. .
NOTE 2 If the input to the MAC function contains a whole number of bytes, then the function specified here is identical
[6]
to that described in RFC 4418 .
6.2.2 Requirements
Before the use of UMAC, the following parameters shall be agreed upon:
 A block cipher standardized in ISO/IEC 18033-3. The choice of a block cipher determines the key length
|K| and the block length |B|.
 A tag length, taglen, which shall be either 4, 8, 12 or 16 octets.
 The length of the nonce, which shall be between 8 and |B| bits.
6.2.3 Notation and auxiliary functions
6.2.3.1 Operations on strings
In contrast to the remainder of this part of ISO/IEC 9797, the specification of UMAC uses a starting index of 1
when numbering elements in a sequence. Thus, for UMAC, S[i] denotes the ith octet of the string S, where
i  1.
© ISO/IEC 2011 – All rights reserved 5

6.2.3.2 Auxiliary function KDF
This key-derivation function generates pseudorandom bits. It returns numoctets output octets.
INPUT: Master key K, (keylen)-octet string
index, a non-negative integer less than 2
numoctets, a non-negative integer less than 2
OUTPUT: Y, (numoctets)-octet string
a) n = ceil(numoctets / blocklen)
b) Set Y to the empty string
c) for i = 1 to n do
1) T = uint2bitstr(index, blocklen-8) || uint2bitstr(i, 8)
2) T = Enc(K, T)
3) Y = Y || T
d) Y = Y[1.numoctets]
e) Output Y
[8]
NOTE The key-derivation function KDF uses a block cipher in counter mode as defined in ISO/IEC 10116 .
6.2.3.3 Auxiliary function PDF
This pad-derivation function takes a key and a nonce and returns a pseudorandom padding sequence for use
in tag generation. A pad of length 4, 8, 12, or 16 octets can be generated.
INPUT: Master key K, (keylen)-octet string
Nonce N, string of length 1 to blocklen octets
Tag length taglen, the integer 4, 8, 12 or 16
OUTPUT: Y, (taglen)-octets string
a) PDFnonce = N
b) if (taglen = 4 or taglen = 8)
1) index = bitstr2uint(N) mod (blocklen/taglen)
2) PDFnonce = N  uint2bitstr(index, octetlength(N))
c) padlen = blocklen - octetlength(PDFnonce)
padlen*8
d) PDFnonce = PDFnonce || 0
e) K' = KDF(K, 0, keylen)
f) T = Enc(K', PDFnonce)
g) if (taglen = 4 or taglen = 8)
1) Y = T[ (index * taglen) + 1 . (index * taglen) + taglen ]
6 © ISO/IEC 2011 – All rights reserved

h) else
1) Y = T[1 . taglen]
i) Output Y
NOTE Padding sequences generated using nonces that differ only in their last bit (when generating 8-octet pads) or
last two bits (when generating 4-octet pads) are derived from the same block cipher encryption. This allows caching and
sharing a single block cipher invocation for sequential nonces.
6.2.3.4 Auxiliary function NH
NH ("Non-linear Hash-function") is a universal hash-function.
[2]
NOTE The NH universal hash-function was introduced by Black et al. .
INPUT: Key, 1024-octet string
Msg, string of octets, whose octet length is an integer multiple of 32 and less than or equal to
OUTPUT: Y, 8-octet string
Break Msg and Key into 4-octet blocks:
a) t = octetlength(Msg) / 4
b) Divide Msg into 4-octet strings M , M , ., M , so that Msg = M || M || . || M .
1 2 t 1 2 t
c) Let K , K , ., K be 4-octet strings so that K || K || . || K is a prefix of Key (the leftmost 4t octets of
1 2 t 1 2 t
Key).
d) Y = 0
e) i = 1
f) while (i < t) do
1) Y = Y + ( (M + K ) * (M + K ) )
64 i+0 32 i+0 64 i+4 32 i+4
2) Y = Y + ( (M + K ) * (M + K ) )
64 i+1 32 i+1 64 i+5 32 i+5
3) Y = Y + ( (M + K ) * (M + K ) )
64 i+2 32 i+2 64 i+6 32 i+6
4) Y = Y + ( (M + K ) * (M + K ) )
64 i+3 32 i+3 64 i+7 32 i+7
5) i = i + 8
g) Return Y
NOTE This routine is applied directly to every bit of input data, and therefore optimized implementation of it yields
great benefit. It can be performed on the 4-octet blocks, pairing words for multiplication which are 4 apart to accommodate
vector-parallelism.
6.2.3.5 Auxiliary function ENDIAN-SWAP
The function ENDIAN-SWAP converts a string of 4-octet words from little-endian to big-endian, or vice versa.
INPUT: S, string with length divisible by 4 octets
© ISO/IEC 2011 – All rights reserved 7

OUTPUT: T, string S with each 4-octet word endian-reversed
a) n = octetlength(S) / 4
b) Let S , S , ., S be strings of length 4 octets so that S || S || . || S = S.
1 2 n 1 2 n
c) Set T to the empty string
d) for i = 1 to n do
1) Let W , W , W , W be octets so that W || W || W || W = S
1 2 3 4 1 2 3 4 i
2) S = W || W || W || W
Reversed 4 3 2 1
3) T = T || S
Reversed
e) Output T
6.2.3.6 Auxiliary hash-function POLY
The function POLY is a polynomial hash-function used in the second layer hash-function L2-HASH,
see 6.2.7.2.
INPUT: wordbits, the integer 64 or 128
wordbits
maxwordrange, positive integer less than 2
key, integer in the range 0 . prime(wordbits) - 1
Msg, strin
...