22
$\begingroup$

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?)?
Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes ♦
    Aug 13, 2015 at 22:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – kasperd
    Aug 14, 2015 at 16:06

2 Answers 2

Reset to default
25
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can this be used to bitslice the authentication? $\endgroup$
    – Demi
    Apr 5, 2016 at 18:45
  • $\begingroup$ @Demetri: a bitslice's implementation of GCM can certainly use the above trick to compute the MAC tag (while processing multiple blocks at once) $\endgroup$
    – poncho
    Apr 5, 2016 at 18:55
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.