This is pretty much a Cryptopals challenge. Solution for those who understand Vietnamese is available at this link. Understanding how to solve this challenge in the Cryptopals intended way requires a deep understanding into how group theory works. A cheating way to solve this is to search the name of the challenge on Github, and there should be Python/Sage solutions.
Leaving this challenge to the future me who “hopefully” understand in the future. There is, however, a solution that does not require any deep knowledge of group theory. Kudos to jusb3 to this solution.
We want to calculate the tag value for the message m of give me the flag (67697665206d652074686520666c6167). However, we are forbidden from calculating the exact tag (and encryption also) for this string as the string flag (666c6167) is forbidden.
This requires a bit of reading into how the tag of AES-GCM is generated, so check out the Cryptopals challenge. With two encrypted messages of the same nonce, associated data, and message length xor-ed together will reduce to $(c0_1 + c0_2) * h ^ n + (c1_1 + c1_2) * h ^ (n-1) + …$, where cN are the blocks we modified, and equal blocks are xored out. Note that xor is addition in GF(2 ^ 128).
Because of this particular property, if we calculate value for $c0_1$, $c0_2$ and $c0_3$ and xor together will result in the correct tag for c0_4 = c0_1 ^ c0_2 ^ c0_3.
For simplicity, we can pick c0_1 = m xor 1, c0_2 = m xor 2 and c0_3 = m xor 3, and the xored value will be c0_4 = m xor 1 xor m xor 2 xor m xor 3 = m. We can get the corresponding tag value tag1, tag2, tag3, and forge the tag for c0_4 = m by tag4 = tag1 xor tag2 xor tag3
Also, AES-GCM is a stream cipher, hence two messages using the same key will share the same keystream.
In short, there are two relations (note that ^ denote xor here):
|
|