Is (AES-)GCM parallelizable?

Question

I recentely faced the issue of random access decryption while AES-GCM was being used. I said this person that the underlying CTR should allow parallelization but I have no idea how authentication comes into play.

Now I know that one of the cool features of CTR is that you can decrypt any block without needing to involve any other blocks. I also know that CTR is part of the basis for GCM.

Now my question(s) are:

1. Can one somehow parallelize encryption of data in GCM mode (only CTR part? Parts of the MAC as well?)
2. Is it possible to get random access to decrypted ciphertexts (+ fast verification?) or is at least somehow possible to parallelize decryption and authentication (do either of both in parallel or internally parallelize?)?

Answer 1

Contrary to what Stephen says, you absolutely can compute the tag in parallel.

Here's how it works; the tag computation is essentially "assemble the AAD, data, the length field and $Encr(Nonce)$ into a series of values $x_n, x_{n-1}, x_{n-2}, ..., x_0$", and then "compute the polynomial $x_nh^n + x_{n-1}h^{n-1} + x_{n-2}h^{n-2} + ... + x_0h^0$

This computation is evaluated within the field $GF(2^{128})$; since it is a field, all the standard ways of rearranging the polynomial work.

For example, if we wanted to convert this into a three-way parallelism, we could compute $j = h^3$, and then the three polynomials in parallel:

$$tag_2 = j^0x_2 + j^1x_5 + j^2x_8 + ...$$ $$tag_1 = j^0x_1 + j^1x_4 + j^2x_7 + ...$$ $$tag_0 = j^0x_0 + j^1x_3 + j^2x_6 + ...$$

and then combine them for the final result $tag = h^2tag_2 + h^1tag_1 + h^0tag_0$

Obviously, we can tune this to whatever degree of parallelism that suits us, and we haven't changed the tag result in any way.

Stephen also notes that the entire message needs to be scanned to compute the tag; this is trivally true of any method that has a tag that's a complex function of the entire message.

Answer 2

The GCM flowchart on Wikipedia and my intuition support the notion that some of the GCM work can be done in parallel. At the very least you can do each $E_k(ctr)$ operation in parallel, but it doesn't look like you should be able to parallelize the authentication, as each $mult_H$ requires the output of a previous call as its input. Edit: poncho explains why this is wrong in his answer.

Similarly, you can do random-access decryption, but to achieve authentication still requires an authentication pass over the entire ciphertext. That said, it's still a reduction of work since you only have to compute $E_k(ctr)$ once.