Forbidden Salamanders at cyfraeviolae.org
key commitment · nonce reuse · mac truncation · source code

The FIPS-compliant sorcerer Roseacrucis uses the Advanced Encryption Standard in Galois/Counter Mode to correspond with his retinue. The Library’s cryptanalysts have intercepted the communication channel, but we need your help to exploit their broken protocols.

Choose one of the following missions.

Key commitment. One of our agents has infiltrated Roseacrucis’ inner circle, but all secret keys are required to be surrendered to the counterintelligence authority. Help her send AES-GCM ciphertexts back to the Library that decrypt to confidential information under one key, but innocuous banter under another.

Nonce reuse. Due to rising entropy prices, Roseacrucis has started to reuse AES-GCM nonces. You must perform the Forbidden Attack in order to recover the authentication key and forge arbitrary ciphertext.

MAC truncation. The sorcerer aims to conserve bandwidth by truncating AES-GCM MACs. Use the enemy as a decryption oracle to once again, recover the authentication key and forge arbitrary ciphertext.


Though it is not required to complete your missions, we now review the construction of AES-GCM.

AES-GCM is a block cipher that accepts a key of 16 bytes, a nonce of 12 bytes, plaintext, and additional authenticated data. It returns ciphertext and a message authentication code (MAC). The construction is specified by NIST.

The ciphertext is computed as in counter mode, whereas the MAC is computed using the algorithm GMAC.

Let \[ m = \alpha^{128}+\alpha^7 + \alpha^2 + \alpha + 1 \] \[ \mathbb{K} = \mathbb{F}_{2^{128}}/m. \]

The finite field \(\mathbb{K}\) can be interpreted as the set of polynomials with coefficients in \(\mathbb{F}_2\) of degree less than \(128\). Multiplication is performed modulo \(m\). This field is of characteristic 2; e.g., \(2=0\), \(a=-a\), \((\alpha^5 + 1)+(\alpha^5 + 1) = 0\).

We interpret 16-byte blocks as elements in \(\mathbb{K}\) in little-endian bit order: \[ b_0b_1b_2\ldots{}b_{127} \mapsto b_0 + b_1\alpha + b_2\alpha^2 + \ldots + b_{127}\alpha^{127}, \] where \(b_0\) is the least significant bit of the first byte of the block.

12-byte nonces are interpreted as 96-bit integers in big-endian byte order. Let \(\operatorname{Byte} = [0, 2^8-1]\) and \(x_i\) refer to the \(i\)th 16-byte chunk of the bytestring \(x\).

\(\operatorname{encode_{big}}(x, n)\) encodes an integer \(x\) into \(n\) bytes in big-endian byte order. \(\operatorname{pad_n}(x, p)\) pads the length of the bytestring \(x\) to the nearest multiple of \(n\) with the byte \(p\). \(\operatorname{AES}(k, x)\) refers to the 128-bit AES block cipher.


\(\operatorname{GMAC}(h\in \mathbb{K}, s\in \mathbb{K}, aad\in \operatorname{Byte}^{y}, c\in \operatorname{Byte}^{z})\)

  1. \( len = \operatorname{encode_{big}}(8y, 8) \mathbin\Vert \operatorname{encode_{big}}(8z, 8) \)
  2. \( blocks = \operatorname{pad}_{16}(aad, 0) \mathbin\Vert \operatorname{pad}_{16}(c, 0) \mathbin\Vert len \mathbin\Vert s \)
  3. \( N = \frac{\vert blocks \vert}{16} \)
  4. \( \operatorname{return} \sum\limits_{i=1}^{N} blocks_{N-i} h^{i-1}\)


\(\operatorname{AES-GCM}(k\in \operatorname{Byte}^{16}, n\in \operatorname{Byte}^{12}, aad\in \operatorname{Byte}^{y}, m\in \operatorname{Byte}^{z})\)

  1. \( r = \mathop{\Vert}\limits_{n'=2^{32}n+2}^{2^{32}n+2^{32}-1} \operatorname{AES}(k, n') \)
  2. \( c = r \oplus m \)
  3. \( h = \operatorname{AES}(k, 0) \)
  4. \( s = \operatorname{AES}(k, 2^{32}n + 1) \)
  5. \( \operatorname{return} c, \operatorname{GMAC}(h, s, aad, c) \)