Security of GCM if Implemented with Stream Cipher instead of Block Cipher

Question

Can GCM be implemented with a stream cipher instead of a block cipher? If no, then what security flaw does it have?

---

If yes, then which possibility from below two is better in terms of security? In terms of speed, option ONE seems better as Stream cipher will be initialized only once in it (assume the input data consists of n blocks{0,1,2...n-1} where each block is of 128 bits).

1. Generate an output stream of length $n+1$ blocks $\{0,1,2,3....n\}$ from stream cipher using single key and single IV. Then XOR the $n$ blocks $\{1,2,3...n\}$ of this output stream with $n$ blocks of plaintext to create ciphertext. Multiply ciphertext blocks together(as in GCM, shown as $\operatorname{mult}_H$ in figure below) and XOR the result with $1^{st}$ block (0) of output stream to make AUTH_TAG.

2. Generate an output stream of length $n+1$ blocks $\{0,1,2,3....n\}$ from stream cipher, where each block is generated with incremental IV (like Counter) but same key. Then XOR the $n$ blocks $\{1,2,3...n\}$ of this output stream with $n$ blocks of plaintext to create ciphertext. Multiply ciphertext blocks together(as in GCM, shown as $\operatorname{mult}_H$ in figure below) and XOR the result with $1^{st}$ block (0) of output stream to make AUTH_TAG.

Answer 1

In AES/GCM, every use of AES can be expressed in terms of AES-CTR:

• From the initial IV (12 bytes + counter initialized at 1), a sequence of $n+16$ bytes is generated, for a source plaintext of $n$ bytes; the first $16$ bytes are the block XORed with the GHASH output to produce the authentication tag.

• The GHASH key ($h$) is obtained as the encryption of an all-zero block; this is equivalent to AES-CTR encryption of an all-zero value with an IV+counter equal to zero.

In fact, it is highly possible and even sensible to implement GCM out of an exclusively CTR implementation of AES (see my GCM code for an example).

Since AES-CTR is supposed to be a strong stream cipher, indistinguishable from a random source, we can replace it with another stream cipher, and things should still be fine in terms of security (i.e. it won't be made worse). In details, this would mean the following:

• The stream cipher works over a key $K$ and a 16-byte IV.
• The stream cipher would be invoked over an all-zero IV to produce $h$ (16 bytes).
• The stream cipher would also be invoked, with the same key, but an IV made of the nonce (12 bytes) + the value 1 (over 4 bytes) to generate $n+16$ bytes, for the XOR with the authentication tag and the data encryption itself.

With this description, we see that AES-CTR is actually a bit lousy with regards to IV management. The specific details of IV construction are meant to avoid nonce reuse; AES-CTR for a run of $k$ blocks "burns up" $k$ successive nonces. This is the reason why counter starts at $1$ for the block to be XORed with the GHASH output, and $2$ for the data itself: that way, the values cannot collide with the all-zero block for $h$. Use of a secure stream cipher in lieu of AES might possibly relax such constraints, and in fact be more secure than GCM^(*).

Of course, this raises the question of why you would do that. The GHASH part of GCM is usually the problematic one when it comes to implementation, not the AES. GHASH is very fast on hardware platforms that have dedicated opcodes (x86 with AES-NI, POWER8...) but these platform also provide an AES hardware implementation that outperforms software-based stream ciphers. In practice, you would probably be better off with Poly1305, which is commonly used in combination with the stream cipher ChaCha20, as described in RFC 7539.

---

^{(*) With the usual caveat that something can be "more secure" than AES/GCM only insofar as AES/GCM is less than ideally secure, but it is currently unbroken. We still have a few academic misgivings related to the relatively short IV, in that random 96-bit IV have a not completely impossible probability of collision.}