Cryptography Reference
In-Depth Information
Mode
) that follows the Encrypt-then-Mac paradigm. When used for authentication
only, GCM becomes a MAC called GMAC. GCM/GMAC has been specified by
NIST [70] and, if used following this specification, it has a security reduction, given
in [138], to the assumption that the underlying block cipher is a pseudo-random
permutation.
One of the main reasons to construct a MAC based on a universal hash function is
efficiency: universal hash functions are usually very fast. We are going to implement
GCM and GMAC in Maple and we will see that the implementation of GMAC is
much faster than, for example, that of CMAC. We do not include a too-detailed
account of GCM and its security properties; we will be satisfied instead with giving
only a broad description of the scheme as we implement it, and we refer for all the
details to [70] and [138].
As mentioned, GCM is an authenticated encryption mode that provides both con-
fidentiality and authenticity. Moreover, the authentication assurance can be provided
for both the confidential (i.e., encrypted) data and for additional data that is not
encrypted. If the GCM input is restricted to data that is not to be encrypted, then the
resulting specialization is a MAC called GMAC. The two main GCM functions are
called authenticated encryption and authenticated decryption. The first encrypts the
confidential data and computes theMAC tag of both the confidential data and the addi-
tional non-confidential data. The authenticated decryption function decrypts the con-
fidential data contingent on the verification of the tag; if verification fails it outputs
FAIL
and the ciphertext is not decrypted (this corresponds to outputting
⊥
in our
previous description of authenticated encryption).
5.5.1.1 GCM Primitives: GHASH and GCTR
The main ingredients of GCM are a universal hash function called GHASH and a
variant of CTR mode which is used for encryption, thus we will start by defining
these two primitives. GHASH is a so-called “polynomial hash function” because it
acts on the message (regarded as a sequence of blocks) by regarding each 128-bit
block as an element of the field
F
2
128
and evaluating the polynomial of
F
2
128
[
x
]
whose
coefficients are given by these blocks at the value
x
s
, where
s
is a 128-bit “hash
subkey” derived from the GCM key
k
. Specifically, if
s
is the 128-bit hash subkey
and
b
=
=
b
1
||
b
2
||
...
||
b
t
, where the
b
i
are 128-bit blocks viewed as elements of
F
2
128
,
then the output of GHASH is the 128-bit block:
t
s
t
−
i
+
1
b
i
·
,
i
=
1
where we denote by '
·
' the multiplication in
F
2
128
. Thus GHASH is the hash function
)
=
i
=
1
b
i
·
128
t
.
But for a few technical details, it is essentially shown in [138] that, keeping the
notation above, GHASH is
s
t
−
i
+
1
for
b
{
g
s
}
s
∈{
0
,
1
}
128
given by
g
s
(
b
∈{
0
,
1
}
2
128
.TheGMAC
ε
-almost Xor universal for
ε
=
t
/
