6
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ The modes of operation you mention are specifically block cipher modes of operation. They do not apply to stream ciphers. $\endgroup$ – puzzlepalace Oct 11 '17 at 18:37
  • 1
    $\begingroup$ That I have mentioned in the question. The question is about those two scenarios i wrote in question and Can GCM be implemented with a stream cipher instead of a block cipher? $\endgroup$ – khan Oct 11 '17 at 18:40
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Academic misgivings"...like how did these clowns get their hands on oscilloscopes! $\endgroup$ – Q-Club Oct 13 '17 at 1:18
  • $\begingroup$ Actually, my answer to question crypto.stackexchange.com/questions/60089/… clearly demonstrates that the problematic part is AES and not GHASH! The GHASH is much faster to calculate than AES without special instructions. $\endgroup$ – juhist Jun 17 '18 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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