Practical disadvantages of GCM mode encryption

Question

It seems that GCM mode encryption has a clear advantage over CBC + HMAC in the sense that it only requires a single key. But it seems that there are some experts here that do not trust it enough to recommend it. This question is a call to those experts to clearly define those concerns.

Are there any properties of GCM mode encryption that make it less secure in practical operations than CBC + HMAC using two separate keys?

Answers could focus for instance on properties of the algorithm that make it more vulnerable to side channel attacks than other algorithms.

Answer 1

In comparison to CBC mode and HMAC, GCM mode is quite a commonly better alternative. But, I'll go to detail where it necessarily is not. Just like Richie Frame, I also do not agree that CBC + HMAC is always the best comparison target. I've added a few other details. Hope you find them useful.

Against CBC and HMAC

I'll discuss downsides first.

The authentication part of GCM (GHASH) is weaker than HMAC, GHASH provides a maximum 128-bit authentication tag, whereas HMAC allows lot longer tags (HMAC-SHA-256 would allow 256-bit authentication tag). In addition, forgery of GHASH tags in some cases is easier than HMAC:

As with any tag-based authentication mechanism, if the adversary chooses a $t$-bit tag at random, it is expected to be correct for given data with probability $1/2^t$. With GCM, however, an adversary can choose tags that increase this probability, proportional to the total length of the ciphertext and AAD. (Borrowed from NIST SP 800-38D.)

Implementations using GCM mode often use short IV (96-bits), in fact, e.g. NIST SP 800-38D recommends using the 96-bit IVs. (Longer IVs are defined but they'll require the extra invocation of GHASH function.) The 96-bit IVs (GCM) can be too short uses where 128-bit IV (CBC) would be sufficient. Consider e.g. collision probability of random IVs.

Benefits of GCM: Properly implemented GCM is almost always faster, and it is easier to use GCM than operate AES + HMAC combination correctly. CBC mode requires padding input to the block size, thus GCM mode produces smaller output if the input is not multiple of the block size.

Against CTR + HMAC

Because the AES parallelization benefits are available via CTR mode as well, CTR + HMAC is fairly similar to GCM and can perform pretty well. It can be better, in case authentication tag requirements exceed what GCM can provide.

Against CCM

The CCM mode is largely similar to GCM mode. It's the largest benefit is that implementation requires less code (SW) or gates (HW), but CCM implementations generally are slower than GCM.

Overall, some IEEE 802 standards tend to pick CCM over GCM due to the HW implementation gate count.

SIV-AES and AES-KW

It is possible to wrap other keys using AES-GCM (key wrapping).

For authenticated encryption where the target is key wrapping (encryption of key with another key), SIV-AES and AES-KW algorithms are commonly better than AES-GCM. Better in the sense that they can be used without reliance on random number generation (or a deterministic IV generator) and that their output can be smaller because there is no need IV in addition to encrypted output and authentication tag. (These are commonly considered to be benefits of deterministic authenticated encryption.)

Key, IV pair reuse

I've already mentioned IV, key pair reuse.

GCM mode does not resist the reuse of Key IV combination. To prevent this, some parties like NIST put more requirements on the proper use of GCM mode than the other modes. This is a good idea from the security point of view, but it may reduce the allowed uses of the mode.

Generally, GCM is most convenient for uses where new keys are agreed or transported as a part of the protocol (TLS or IPsec). If there is use where a persistently stored key is needed, then it can be cumbersome to ensure IV uniqueness.

NIST is aware of this pitfall. NIST's CMVP (Cryptographic Module Validation Program aka FIPS 140-2 validation program) has a requirement for the careful use of GCM (FIPS 140-2 IG A.5). FIPS-approved implementations of GCM mode need to be very careful in their use of keys because, in GCM mode reuse of key, IV pair is not allowed to happen.

CBC-ESSIV

AES-CBC mode can be used for disk encryption (especially with ESSIV, see Wikipedia disk-encryption theory). The fact that GCM often uses small IV length and is not IV collision-resistant makes it hard to apply for contexts where it is needed to encrypt a large number of blocks and encryption does not happen in-order (deterministic IV increasing would be ok). For this reason, AES-GCM is not that much used for encryption of stored data, but rather data at transit.

Summary

GCM is a very good mode of operation, and it often is more convenient than legacy algorithms combinations like CBC + HMAC. However, it is not a universal solution (none of the modes is), but rather it is most convenient only for a large number of data at transit.

Answer 2

There exists a case where developers implemented a new version of the GHASH algorithm that used the new PCLMULQDQ instruction found in Intel processors, and a bug in the implementation allowed message forgery. The code change appeared to improve the performance of AES-GCM on newer processors as well as processors with additional cores that do not support PCLMULQDQ. The bug was not specific to the new instruction, but rather the new aggregation mode that allows parallel encryption of 8 blocks in order to reduce latency of hardware AES instructions on multicore processors.

Full details of the bug and how it can be exploited are described in a paper called The fragility of AES-GCM authentication algorithm

The code was for OpenSSL, and occurred under the following conditions:

$({len/16})$ $mod$ $4 = 1$
$len > 64$

where $len$ is the size of the GHASHED buffer in bytes. Values of $len$ that satisfy this condition are 80, 144, and any other value that increments from 80 by a multiple of 64. The NIST test values they used only included 64 byte messages and up to 20 bytes of additional data. The final test with no ciphertext authenticated 128 bytes of additional data. None of these meet the criteria for the bug to manifest. The bug almost made it into OpenSSL 1.0.2 but was caught in a month and fixed immediately.

The bug proceeded to send $N+1$ blocks of data to GHASH instead of $N$.. The data for the additional block $J$ was whatever happened to be in that memory location.

OpenSSL was supposed to perform the following computation to generate a new tag $T2$ from the current tag $T$ and additional message $M$ comprised of $N$ blocks (5 blocks or 80 bytes for example):

$T2 = ((T + M_1) * H^N) + (M_2 * H^{N-1})$ $...$ $+$ $(M_N * H^1)$

What it actually did was:

$T2' = ((T + M_1) * H^{N+1}) + (M_2 * H^{N-1})$ $...$ $+$ $(M_N * H^2) + (J * H^1)$

In addition to an invalid authentication tag, it had pulled 16 bytes of data from a memory location that it was not supposed to. If $J$ contained null bytes, the invalid authentication tag was equal to $T2 * H^1$

The types of attacks that can be leveraged against this bug include:

• A message is sent with the incorrect implementation to a receiver with the correct implementation, the message is forged but the authentication tag is valid to the receiver.

• A message is sent with the correct implementation to a receiver with the incorrect implementation, the message is forged but the authentication tag is valid to the receiver.

In the first case, the attacker must know the value of datablock J, and the first block of the additionally authenticated data must be zero. In the second case the attacker must be able to modify the incoming memory buffer.

Since the length of the ciphertext and the authenticated data are the first inputs to the GHASH function, the sizes of those are not modifiable as part of the attack. Additionally, this is more of an application mistake, rather than an issue with the algorithm itself, however the type of mistake seen here is from trying to exploit the performance advantage of GCM over CBC + HMAC. CTR + HMAC is also a very valid mode and can leverage multicore processing better without the complexity of the polynomial MAC.

The difficulty of implementing an attack on this type of bug is also quite high, as it requires attackers to have access to system memory. This is most likely to be exploited by nation states with well funded intelligence agencies. Due to the prevalence of OpenSSL, if this had made it into the wild, it would have been caught very quickly and not had much of an impact over the long term. This type of attack is valid for any polynomial MAC that operates in the same manner as GCM.

Apart from this, the original proofs that GCM bases its security on were found to be invalid in 2012, but new proofs allowed GCM to maintain its expected security.

The other primary attack vector on GCM is when short (32-bits for example) authentication tags are used, and there is enough data to reduce the security level to one which is attackable.

The best example is a VOIP application with 8-bit tags. It takes on average 128 attempts to forge a message and this allows recovery of 7-bits of $H$. Less than 1000 forgery attempts will reveal $H$ in its entirety, allowing forgeries of all packets. With an 8-bit tag, this attack is successful in under 5 minutes (speeding up the process will disrupt the audio to a point where parties may be suspicious). The expected 128:1 or better probability of forging a packet has now reached 1:1.