# Is (AES-)GCM parallelizable?

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?)?
• Bouncy Castle even has a trick implemented to handle addition of Additional Authenticated Data after normal data has been processed, although it does require modulo exponentiation in addition to multiplication, which requires additional tables. – Maarten Bodewes Aug 13 '15 at 22:38
• Please ask only one question per question. This site format works best when you ask only one question. If you ask two questions, you can create problems (e.g., if one answer explains the answer to question #1, and another explains the answer to question #2, how are you going to choose which one to accept?). It's usually better to avoid this: if you have two questions, it is often better to post two separate questions -- in 2 separate posts. Thank you. – D.W. Aug 14 '15 at 3:46
• Decryption of individual blocks is not unique to CTR. You can also decrypt individual blocks of a CBC or CFB encryption. But it is not a very interesting feature for an authenticated encryption, since you can't authenticate individual blocks. – kasperd Aug 14 '15 at 16:06

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.

• Note that there is a related question #2. It would be nice if the answer would be fully separate of that of Stephen. – Maarten Bodewes Aug 13 '15 at 22:41
• @MaartenBodewes, well with some fantasy one can imagine that this answer catches #1 and #2 although not as explicit as Stephen does it. We know CTR has random-access and we know also know that tag computations can be heavily speeded-up. Further we know that we have to compute the tag over the whole message and as the tag is computed over the ciphertext we only need to decrypt the part of the message that interests us and can use the "fast verification" to ensure our decrypted block is actually correct. – SEJPM Aug 14 '15 at 14:42
• Thanks for the correction! I've updated my answer to refer to yours. – Stephen Touset Aug 14 '15 at 17:28
• @SEJPM We know that yes :) I just wanted to make the excellent answer by Poncho independent of that of Stephen (he's already corrected his answer by now) and make sure that future readers - not just the top 20 contributors - can understand it without doing all the deductions themselves. – Maarten Bodewes Aug 15 '15 at 15:59
• Can this be used to bitslice the authentication? – Demi Apr 5 '16 at 18:45

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.