# Understanding the algebra behind GCM's security

I would like to understand the algebra behind GCM's security. Before I ask my questions, let me state my understanding of the math behind GCM. If correct, my questions are at the end; if incorrect, can you please explain my mistake.

For simplicity, assume only one block of ciphertext $$c$$. We want our tag to have two properties:

1. $$tag_k(c)$$ should be a universal uniform hash of $$c$$: that is, for all $$c$$, if $$k$$ is uniformly random, $$P[tag_k(c) = y]$$ is uniform for all $$y$$.

2. $$tag_k(c)$$ should reveal no information about $$k$$, even when $$c$$ is known.

Property 1 is easily satisfied by multiplication by non-zero $$k$$ in $$GF(2^n)$$, since, in $$GF(2^n)$$, $$f(x) = ax$$ is a unique permutation for all $$a \ne 0$$, and $$f$$ is therefore a universal uniform hash.

Property 2, however, would not be satisfied by $$tag_k(c) = kc$$, since we can compute $$c{^-1}$$ and solve $$k = tag_k(c)c^{-1}$$. To meet Property 2, we introduce a "secret ciphertext", $$c_0$$, and define $$tag_k(c) = kc + c_0$$ (addition being bitwise XOR in $$GF(2^n)$$). $$c_0$$ is effectively functioning as a one time pad to encrypt the "root" tag $$kc$$.

What if we want to authenticate two blocks of ciphertext? We could repeat that procedure, making sure to use a new $$c_0$$ each time. In practice, AES-GCM uses c_0 = AES_k(counter++).

However, when authenticating many blocks at once, this is inefficient. Instead, we can use one tag for multiple cipherblocks, using this formula:

$$tag_k(c_1, c_2,...c_n) = kc_0 + \sum k^nc_n.$$ (For simplicity, I am leaving out the length field as well as authenticated plaintext). This preserves both properties.

We might be tempted to simplify that to $$\sum kc_n$$, but this fails, as we can replace $$c_a, c_b$$ with $$fake_a, fake_b$$ as long as $$fake_a + fake_b = c_a + c_b$$. For example, we could flip a bit in any cipherblock as long as we flip the corresponding bit in a different block. (This type of attack was used against WEP, which uses CRC as its "MAC").

1. Is the above correct?
2. How does AES-GCM chose $$k$$?

More importantly, how do we avoid the following apparent failure modes:

1. If $$k = 0$$, $$tag(any\_ciphertext) = 0$$
2. Does $$c_n = 0$$ pose a problem? It doesn't seem to break any of the properties, but it still seems concerning. (Note that we can't simply append zero blocks, since this will change the length field.)
3. It seems to me the multi-block algorithm would be correct if every $$k$$ was a generator of $$GF(2^n)$$ or at least of very high order. But if $$k$$ happens to be of low order, the scheme will fail.

For example: Imagine $$k$$ has order 2. Then we can flip a bit in $$c_1$$ as long as we flip the same bit in $$c_3$$, since \begin{align} k^2c_1 + k^4c_3 &= k^2(c_1 + c_3) \\ &= k^2(c_1 + c_3 + d + d) \\ &= k^2(c_1 + d) + k^4(c_3 + d)\end{align}. How does GCM avoid this failure mode?

I would like to understand the algebra behind GCM's security.

Well, you wrote out the mechanics of how the authentication piece of GCM works; however to understand why those mechanics work, it'd be helpful to approach it in a different way.

GCM uses arithmetic in $$GF(2^{128})$$; this is a field; the important point is that, in a field, any nonzero polynomial of degree at most $$n$$ has at most $$n$$ zeros; that is, for any equation:

$$a_n x^n + a_{n-1} x^{n-1} + ... + a_0 x^0 = 0$$

has at most $$n$$ solutions for $$x$$ (assuming that at least one of the $$a_i$$ values is not zero).

Why this is critical will be clear later.

Now, what GCM does to authenticate is that it takes the encrypted data (and the AAD), and translate that into a polynomial; it then converts the nonce as the constant value of the polynomial, and then evaluates that polynomial at a secret value $$k$$, and the result of that evaluation is the tag; that is:

$$tag := a_n k^n + a_{n-1} k^{k-1} + ... + a_1 k^1 + \text{hash}(nonce)$$

Now, suppose we had a different message/tag pair for the same nonce; that message/tag would pass the GCM integrity check if:

$$tag' := a'_n k^n + a'_{n-1} k^{k-1} + ... + a'_1 k^1 + \text{hash}(nonce)$$

What we can do is subtract the two polynomials (the one corresponding to the good ciphertext that was generated by the valid encryptor, and the one corresponding to the guess by the attacker); we get then [1]:

$$0 = (a_n-a'_n)k^n + (a_{n-1} - a'_{n-1})k^{n-1} + ... + (a_1 - a'_1)k^1 + (tag - tag')k^0$$

This equation holds only if the second ciphertext/tag pair is valid.

Now, we go back to our original observation: this is a polynomial of degree at most $$n$$ and so there are at most $$n$$ different values of $$k$$ for which this equation is true. We also know that at least one coefficient of the polynomial is nonzero (the all zero polynomial is true if the 'forged' ciphertext is precisely the same as the valid one, which isn't considered a forgery). And, if $$k$$ is selected unpredictably, then there are $$2^{128}$$ possible values, and so the probability that it just happens to be one of those $$n$$ values is at most $$n2^{-128}$$, which is truly tiny.

Now, to turn this argument into an actual proof (which has been done), we need to assume that a) $$k$$ is selected uniformly at random, and b) $$\text{hash}(nonce)$$ also is selected randomly (because, if not, the attacker can deduce some things about the value of the polynomial, which would be bad); it turns out that we can tie both into the cryptographical strength of AES.

1. Is the above correct?

Close; you did get one detail wrong; using your notation, we get the tag computation as $$tag_k(c_1, c_2,...c_n) = c_0 + \sum k^nc_n$$ (note that $$c_0$$ is not multiplied by $$k$$):

1. How does AES-GCM chose $$k$$?

It encrypts the all-zero block using AES using the GCM key.

1. If $$k=0$$, $$tag(\text{any_ciphertext})=0$$

No, $$c_0$$ doesn't get multiplied by $$k$$, so we have in this case:

$$tag(\text{any_ciphertext}) = c_0$$

It still means that, in this specific case, the ciphertext can be modified arbitrarily without modifying the tag, however it isn't obvious.

The obvious question is: "isn't this still bad?". Well, with a 128 bit tag, the attacker always has a probability $$2^{-128}$$ of just blinding guessing a valid ciphertext/tag pair - $$k=0$$ has the same probability of occurring, and hence doesn't increase the forgery probability.

1. Does $$c_n=0$$ pose a problem?

No; if you go through the above logic, $$c_n=0$$ is not a special case.

1. But if $$k$$ happens to be of low order, the scheme will fail.

This specific failure scenario still falls within the probability $$n2^{-128}$$ as shown above; if you (say) test if $$k$$ had a small order and reject those values, you won't actually decrease the forgery probability.

[1]: In an even characteristic field such as $$GF(2^{128})$$, addition and subtraction are the same operation, and so we usually write both as $$+$$; I kept it as $$-$$ to make is somewhat clearer to someone unused to such conventions.

• Brilliant answer! If I understand correctly, you're saying: Yes, there are cases where $tag_{forgery}$ has a very simple relationship to $tag_{real}$: when $k = 0$, they're identical, and when $k$ is order 2, they follow the bit flip scheme I showed. But, so what? That doesn't weaken the security: as long as we leak nothing about $k$, the fact remains that for every forgery, there are at most $n$ tags (out of$2^{128}$) that match it; for some $k$, these altered tags are easily computed from $tag_{real}$ and for some $k$ they're not. Is that correct? Jan 18 at 21:21
• @SRobertJames: actually, with this field, there is no $k$ with order 2; on the other hand, there are precisely two values of $k$ that have order 3, so your point is still valid. Jan 18 at 21:28
• You've shown that, given a $c'$ and $k$, there at most $n$ $tag'$s that authenticate $c'$. How do we know those $tag'$s are random functions of $k$? Perhaps some $tag'$s work for very large number of $k$, and some work for few or no $k$. For a linear function $ax + b$, this is not an issue, because a linear function in a finite field is a permutation; but for a polynomial function, this is not true. E.g. $x^2 + x$ sends half of $GF(2^2)$ to $0$. Jan 18 at 21:29
• @SRobertJames: more in line with what you're really asking; it's actually fairly easy to take a set of $n$ values for $k$ and create a forgery that would match it if any of those $k$ values were correct. The computation is a bit more than 'flipping two bits', but still quite feasible. Jan 18 at 21:30
• @SRobertJames: are for 'is the mapping between messages and tags equidistributed', well, remember the $hash(\text{nonce})$ we include in the tag computation? As long as this is equidistributed and independent of the rest of the tag computation (and as it is based on AES, that seems plausible), then the tags themselves are evenly distributed. Jan 18 at 21:32