What is the disadvantage of AES-GCM mode for authenticated encryption? Why does the CAESAR competition say that it’s one of the goals to find an AE scheme that offers an advantage over AES-GCM? What advantage they are talking about?

• I've removed my answer as Dimitry's answer is much better (don't forget to accept). But I'll put it here as a comment: the goal of the competition is to find better schemes of authenticated encryption. Even though GCM has many disadvantages, it seems mainly used as a base line within the competition. That does not mean that the previous modes have been broken, or that there is one particular advantage that they focus on. – Maarten Bodewes Sep 11 '14 at 10:12

AES-GCM has the following problems:

• In the case of nonce reuse both integrity and confidentiality properties are violated. If the same nonce is used twice, an adversary can create forged ciphertexts easily.
• When short tags are used, it is rather easy to produce message forgeries. For instance, if the tag is 32 bits, then after $2^{16}$ forgery attempts and $2^{16}$ encryptions of chosen plaintexts (also of length $2^{16}$), a forged ciphertext can be produced. Creation of forgeries can be instantaneous when enough forgeries have been found.
• GCM security proof has a flaw. It has been repaired recently, but the new security bounds are far worse for nonces not 12 bytes long;
• GCM implementations are vulnerable to timing attacks if they do not use special AES instructions. The vulnerability remains even if the AES itself is implemented in constant-time. Constant-time implementations of GCM exist, but they are rather slow.
• GCM restricts the message length to 68 GBytes, which might be undesirable in the future. The total amount of data allowed to encrypt on a single key is limited by $2^{64}$ blocks, but this number decreases if long nonces are allowed.
• Reasonably fast implementations of GCM require specific lookup tables, which do not fit into fast memory (L1 cache or similar) on some architectures.
• GCM is vulnerable against cycling attacks; bad values of the internal $H$ key, which can be pre-calculated for specific AES key values, can negatively impact security.
• In Authentication weaknesses in GCM Niels Fergusson states (about forgeries): "This quickly leads to a situation in which the attacker knows all of H, after which arbitrary forgeries can be created without any chance of detection by the receiver." where H is the data used as authentication key (!). So short tags leads to complete loss of authentication, even for ciphertext with a larger tag used later on. This is clearly a more potent statement than your second statement. – Maarten Bodewes Sep 11 '14 at 10:06
• I did not want to go further in the details about multiple forgeries, but if you want you may edit my answer. – Dmitry Khovratovich Sep 11 '14 at 11:48
• Done, same to you, if you think it is unclear, edit or let me know. I thought disclosure of a key is too serious to ignore, I mean, an authentication function cannot get more broken than that. – Maarten Bodewes Sep 11 '14 at 11:57
• I would say that "authentication key" is a bit confusing. Could be better "Subsequent forgeries can be made almost instantaneously so that authenticity is no longer provided." – Dmitry Khovratovich Sep 11 '14 at 13:15
• One may add a performance issue: the not-too-slow implementations of GCM use tables that exhaust L1 caches on small architectures (like the 32-bit Mips found in cheap home routers). It has been reported that on such systems, EAX mode outperforms GCM. – Thomas Pornin Oct 24 '14 at 18:45

I suppose one of the problems (they mention several after a short reading) with a mode like GCM is nonce misuse (e.g. reuse). When the key is the same and the nonce is reused, by misunderstanding the concept or by a simple programming error, information about the plain texts can be revealed.

Phillip Rogaway has already defined an encryption mode (SIV, Synthetic IV) which tries to be more robust against nonce misuse. But it is quite slow, as it requires to process the data twice. It is also not "online", as the first data processing must be finished before the second can start.

• For full nonce reuse resistance there is no way around processing the message twice. i.e. any mode that only processes a message only once is significantly weaker than SIV when nonces are reused. – CodesInChaos Aug 4 '14 at 13:03