# 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.

• 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