8
$\begingroup$

I've heard that Galois Counter Mode (GCM) is an "online" encryption algorithm—it is not necessary to know the size of the input ahead of time. But does GCM require that all authenticated-but-not-encrypted data ("adata") be provided to the algorithm before processing the data to be encrypted?

If there is no ordering requirement, how can an implementation combine the two independently-calculated sides into a single GHASH result? My guess is that if it is possible, it involves rearranging the GHASH results into a polynomial.

I wasn't able to find anything on this with some searches on here and Google.

Improve this question
$\endgroup$
2
  • $\begingroup$ Implementation note: if you want to perform GCM decryption online then you must be able to separate the tag from the ciphertext, otherwise you need to buffer x bytes up to the tag size before being able to decrypt. This is pretty stupid of course, but if you look at the implementation in Java SE or even the AEAD definition in RFC 5116 you will see that this is not obvious to everybody (I'll gladly leave the mathematical GHASH constructions to Poncho below - that's the meat of the problem). $\endgroup$
    – Maarten Bodewes ♦
    Feb 23, 2017 at 9:30
  • $\begingroup$ Also note my question - and of course the followup answer by poncho - here $\endgroup$
    – Maarten Bodewes ♦
    Feb 23, 2017 at 9:33

1 Answer 1

Reset to default
8
$\begingroup$

As you suspect, it's possible to rearrange the GHASH computation so that can compute both the AAD and the encrypted data online and independently.

As you recall, GHASH is defined as:

$$\mathrm{GHASH}( \{a_{i-1}, a_{i-2}, ..., a_0 \}, \{ p_{j-1}, p_{j-2}, ..., p_0 \} ) = \\ a_{i-1} H^{i+j+1} + a_{i-2} H^{i+j} + ... + a_0 H^{j+2} + \\p_{j-1} H^{j+1} + p_{j-2} H^{j-1} + ... + p_0 H^2 + C H$$

where $\{a_{i-1}, a_{i-2}, ..., a_0 \}$ is the AAD, and $\{ p_{j-1}, p_{j-2}, ..., p_0 \}$ is the plaintext, and $C$ is a block containing the lengths of the AAD and the plaintext.

We can rearrange this into:

$$(a_{i-1} H^{i-1} + a_{i-2} H^{i-2} + ... + a_0 H^{0}) \cdot H^{j+2} + \\(p_{j-1} H^{j-1} + p_{j-2} H^{j-2} + ... + p_0 H^0) \cdot H^2 + CH$$

We can online compute $\Sigma a_i H^i$ and $\Sigma p_i H^i$, and so you are iteratively computing $\Sigma p_i H^i$, you also compute $H^{j+2}$. Once we have those collected, compute:

$$\mathrm{GHASH} = (\Sigma a_i H^i) H^{j+2} + (\Sigma p_i H^i) H^2 + CH$$

Improve this answer
$\endgroup$

Your Answer

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

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