# How does Authentication-Key Recovery for GCM work?

In his Paper "Authentication weaknesses in GCM" Ferguson describes, how some bits of the error polynomial can be set to zero, thereby increasing significantly the chance of a forgery.

Q: What does it mean in detail? That the resulting equations do not solve the problem of obtaining forgery completely, but the solution space is significantly reduced? So we can fix some bits of the error polynomial and the remaining bits must be tested by trial and error?

It is stated, that (for the example) after $$2^{16}$$ trials we expect a successful forgery. What follows I do not right understand: Somehow, by repeating some strategy more and more information about H can be gained.

Q: Repeating with different ciphers? Do I need only one ciphered outcome of an encryption or many different?

Q: This is quite interesting stuff, but beside the original paper I cannot find any literature, which explains the idea a little more in detail. Is there some other source, where I can learn what's behind the idea in a "more didactically prepared way"?

I would be glad if somebody can shed some light on that and possibly give me a link to reading material.

## 1 Answer

They so that by taking an authenticated message, and applying a carefully crafted difference to the message, you can ensure half the bits of the authentication tag will be preserved. You can repeat the attack on different authenticated cipher texts you captured(or perhaps caused) or (more relevant) different solutions for the linear problem as it is under-specified.

This all assumes you are capable of sending modified message to the victim and get feedback if authentication succeeds.

When a forgery is successful, it reveals information about the authentication key, and we can then try forgery again with increased success probability. And repeat until we collect linear constraints and recover the authentication key

• The attacker knows the original tag and his goal is to modify cipherblocks Ci in such a way that this forgery yields the same tag. There is a linear algorithm allowing him to work out a reduced number of candidates for Ci. However, in lack of H he cannot calculate T by himself, so he sends over one by one thereby depending on the information from the victim whether authentication succeeded or not. Is this the idea behind? If yes, then I got the first part on a high level view (mathematics is still another topic...). Anyway this attack is a very tedious challenge and can take a long time. Jul 20 at 6:51
• Yes, An attack which takes $2^16$ attempt is considered very fast. The trouble here is you aren't likely to get a meaningful message which may limit the applicability of such an attack. With the Key recovery, forging more meaningful messages becomes relevant. Jul 20 at 8:43