Saarinen in his work GCM, GHASH and Weak Keys says that;
This paper is not very clear and has led many people into regrettable confusion about universal hashing authenticators.
The paper—both the manuscript you cited and the conference paper at FSE 2012—contains misleading claims and misattribution of ideas; describes attacks that apply only beyond the bounds of safe usage in standard security advertisements; and proposes a remedy that neither raises the forgery probability nor addresses any practical concerns, in security or performance, of GCM.
The paper doesn't identify the three main realistic shortcomings of GCM: the danger of truncating tags because of the $O(\ell/2^n)$ term in the forgery probability instead of $O(1/2^n)$ for $n$-bit tags on messages of length up to $\ell$; the quadratic term in forgery probability arising from the use of a block cipher (it is misattributed to universal hashing); and the prohibitive cost to constant-time GHASH evaluation (as well as AES evaluation) in software, which invites leaking secrets through timing.
The GHASH algorithm belongs to a widely studied class of Wegman-Carter
polynomial universal hashes. The security bounds known (this and this) for these algorithms indicate that a $n$-bit tag will give $2^{−n/2}$ security against forgery.
It can be argued that universal hashes sacrifice some communication bandwidth for convenience as traditional hash-based MACs are designed to reach the information theoretic $2^{−n}$ bound against message forgery.
These statements are both misleading at best, and simply false if taken literally on their faces.
Neither universal hashes[1] (paywall-free: (a), (b)) nor the Carter–Wegman method of authenticating multiple messages[2] (paywall-free) gives a quadratic term in forgery probabilities, or ‘$2^{-n/2}$ security’, phrasing which is too glib to distinguish offline computation afforded by an attacker from online forgeries limited by your application's bandwidth[3], and which obscures the intermediate block size vs. the possibly truncated tag size. It is the use of a permutation like AES—or DES, as originally suggested by Shoup[4]—that causes quadratic terms to appear: use functions instead of permutations, and the quadratic terms vanish.
Universal hashes can actually attain the optimal bound $2^{-n}$ on forgery probability for an $n$-bit tag. Indeed, the very first authenticator in history of Gilbert, MacWilliams, and Sloane in 1974[5] (paywall-free), published before the concept of universal hashing was named by Carter and Wegman in 1979, attains this forgery bound—by using a key as long as the message.
Carter and Wegman's innovations[2] were to compress the key to a constant size at a linear cost in forgery probability, and to extend the authenticator to multiple messages by encrypting each authenticator with one-time pad to conceal the structure of the universal hash. Shoup's contribution in 1996[4] was to use DES on a per-message nonce to generate the pad, and proved that if the sender sends no more than $\sqrt{2^n\!/\ell\,}$ messages of length $\ell$ then the forger's success probability after $f$ attempts is bounded by $2 f \ell/2^n$ (Theorem 2).
Details.
GHASH is a family of functions $H_r\colon \{0,1\}^* \to \operatorname{GF}(2^{128})$ for $r \in \operatorname{GF}(2^{128})$ defined on a bit string $m$ by interpreting it, suitably padded, as a sequence $(m_1, m_2, \ldots, m_\ell)$ of elements of $\operatorname{GF}(2^{128})$, and giving $$H_r(m) = m_1 r^\ell + m_2 r^{\ell - 1} + \dots + m_\ell r.$$ In other words, we interpret a message $m$ as a polynomial of degree $\ell$ with zero constant term, and evaluate it at the point $r$. (GHASH is one of several polynomial evaluation hashes in cryptography; Poly1305 is another popular one, over the prime field $\mathbb Z/(2^{130} - 5)\mathbb Z$.)
GHASH is a universal hash family, or, more precisely, GHASH has difference probability $\Pr[H_r(x) - H_r(y) = \delta]$ bounded by $\ell/2^{128}$ for any $\delta$ and any messages $x$ and $y$ of up to $\ell$ blocks. Proof: The solutions in $r$ to $H_r(x) - H_r(y) = \delta$ are the roots of the polynomial $x(r) - y(r) - \delta$ in $r$. This polynomial has degree at most $\ell$, so it has at most $\ell$ roots among $2^{128}$ possible values in $\operatorname{GF}(2^{128})$.
The one-time authenticator $m \mapsto H_r(m) + s$ for independent uniform random $r, s \in \operatorname{GF}(2^{128})$ on messages of up to $\ell$ blocks has forgery probability bounded by $\ell/2^{128}$. Proof: For any $m \ne m'$, $a$, and $a'$, and for independent uniform random $r, s$,
\begin{align}
\Pr&[H_r(m') + s = a' \mid H_r(m) + s = a] \\
&= \Pr[H_r(m') + a - H_r(m) = a'] \\
&= \Pr[H_r(m') - H_r(m) = a' - a] \\
&\leq \ell/2^{128}.
\end{align}
A forger who attempts up to $f$ forgeries can't have better probability of success at a single forgery among all the attempts than $f \ell/2^{128}$. Notice that there's no quadratic term here. Only the bound on difference probabilities, and independence of $r$ and $s$, figured into this analysis—you could use any other hash family with bounded difference probabilities to prove a similar forgery probability bound. For example, the one-time authenticator $m \mapsto m_1 r_1 + m_2 r_2 + \dots + m_\ell r_\ell + s$ with the message-length key $r = (r_1, r_2, \ldots, r_\ell)$ would give a bound of $f/2^{128}$, with no factor of $\ell$.
To authenticate many messages, Carter and Wegman suggested[2] using a uniform random key $r$ with independent uniform random $s_1, s_2, \dots, s_q$ to authenticate each of up to $q$ messages $m_i$ with $m_i \mapsto H_r(m_i) + s_i$. They proved the forgery probability is still $f \ell/2^{128}$. Notice that there is still no quadratic term in the forgery probability $f \ell/2^{128}$ of Carter and Wegman's method, and it is even independent of the number $q$ of messages sent.
The quadratic term arose when Shoup opted[4] to generate $s_i$ by the permutation $\operatorname{DES}_k(i)$. The standard lemma about substituting a permutation for a function adds $q'(q' - 1)/2^{n - 1}$ to the forgery probability bound, where $q'$ is the number of calls to the permutation, which in AES-GCM is $1 + (1 + \ell) (q + f)$. There are somewhat better bounds[6][7], but the point is that there is a quadratic cost to using a permutation like DES or AES.
More recent schemes like NaCl crypto_secretbox_xsalsa20poly1305 do away with the permutation and the Carter–Wegman method and instead simply generate $r$ and $s$ independently by a PRF for each message, as suggested by Lange[8]. But let's come back to GHASH and GCM.
- What is the convenience of universal hashes provides?
Universal hashes can be extremely cheap to evaluate—much cheaper than block ciphers, pseudorandom functions, and especially collision-resistant hashes. There is no inherent limit to the parallelism attainable in evaluating polynomials by precomputing $(r, r^2, \dots, r^t)$ if you can perform $t$ simultaneous multiplications in your vector unit. GHASH in particular is difficult in software because it is defined in terms of a binary field, with a kind of weird bit ordering[9], but there are other universal hashes friendlier to software, like Poly1305, which can run in under one cycle per byte in software.
- How much GHASH increase on the communication?.
GCM/GMAC adds a 128-bit tag. Because the forgery probability is $O(\ell/2^n)$ rather than $O(1/2^n)$, you should avoid truncating the tag much[10]. For example, if you accept messages of up to 16 MB or $2^{20}$ blocks, then the forgery probability for a single 32-bit tag is $2^{-12}$ rather than $2^{-32}$ as you might hope. Note that truncating the tag does not affect the quadratic term $O(q^2\!/2^b)$ arising from the use of a $b$-bit permutation instead of a $b$-bit function: the block size and tag size costs scale separately.
- Why one should not use an information theoretic bound HMAC instead should use a lesser one?
Mu.
The bound above is information-theoretic. There is a corresponding information-theoretic bound for the HMAC model $$m \mapsto f\bigl((k \oplus \mathrm{opad}) \mathbin\| f((k \oplus \mathrm{ipad}) \mathbin\| m)\bigr)$$ with a uniform random function $f$, or for a Merkle–Damgård hash $f$ with a uniform random compression function, and it involves the collision probability of $m \mapsto f((k \oplus \mathrm{ipad}) \mathbin\| m)$.
But you need to choose an actual $f$ to make a practical system. Universal hashing gives us strong guarantees with extremely cheap options; with HMAC we typically use conjecturally collision-resistant functions like SHA-256, which are orders of magnitude more expensive to compute for conjectured security that we don't even care about in this application (collision resistance).
But let's suppose you chose a comparable function to use with a 256-bit key giving a 128-bit tag, maybe one without collision resistance: MD5. As it happens, HMAC-MD5 doesn't provide much security after $2^{64}$ messages either[11]. Oops.
(The fact that MD5's collision resistance is broken is irrelevant here; what's relevant is the 128-bit hash size. The same generic attack on HMAC works when $f$ is a random oracle, which by definition is collision-resistant.)
There is an advantage to HMAC-MD5 over, e.g., AES-GMAC (which is AES-GCM with an empty ciphertext) or Poly1305-AES (another Carter–Wegman–Shoup MAC with AES): HMAC-MD5 doesn't need a nonce, whereas AES-GMAC and Poly1305-AES do; and HMAC-MD5 works not just as a MAC but as a long-input short-output PRF, whereas GMAC and Poly1305-AES don't. But you can also fashion a good, fast, nonceless long-input short-output PRF out of a universal hash and a short-input short-output PRF[12]. For example, AES-GCM-SIV does just that (and fixes the bit ordering in GHASH too).
- Since GHASH provides at most $2^{64}$ security against forgery in TLS 1.3, and that is standard that cannot be changed, are there any other suites that provide information theoretical security against forgery.
You can use ChaCha20-Poly1305. This avoids the quadratic cost in forgery probability of using a block cipher, and it doesn't present a conflict between speed and security in software implementations.
The CCM cipher suites all have the same disadvantage as GCM of $O(q^2\!/2^b)$ in the forgery probability from using a permutation instead of a function of $b$ bits, and they require $\ell$ AES calls rather than 1 AES call per message just for authentication. The advantage they have over GCM is $O(1/2^n)$ instead of $O(\ell/2^n)$ in the forgery probability, and some hardware has dedicated AES circuits that might run faster than software to evaluate ChaCha20 or Poly1305.
