Join Log in
Score:2
MichaelW avatar Crypto

How does Authentication-Key Recovery for GCM work?

in flag
MichaelW

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.

72
1 + 0
gcm
Score:2
Meir Maor avatar Crypto
in flag
Meir Maor

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

0 + 2
MichaelW avatar
in flag
MichaelW
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.
0
Reply
Meir Maor avatar
in flag
Meir Maor
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.
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.