How to implement "online" feature of GCM?

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.

• 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). Feb 23 '17 at 9:30
• Also note my question - and of course the followup answer by poncho - here Feb 23 '17 at 9:33

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$$