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

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.

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

Nonce truncation. The sorcerer aims to conserve bandwidth by truncating nonces from twelve bytes to four. Use the enemy as a decryption oracle to once again, recover the authentication key and forge arbitrary ciphertext.

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 ciphertexts to the Library that decrypt to confidential information under one key, but innocuous banter under another.


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 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., \((\alpha^5 + \alpha+1)+(\alpha^5 + \alpha+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]\).


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

  1. \( aad' = \operatorname{chunk}_{16}(aad, \operatorname{pad}=\mathtt{0x00}) \)
  2. \( c' = \operatorname{chunk}_{16}(c, \operatorname{pad}=\mathtt{0x00}) \)
  3. \( len = \operatorname{encode_{big}}(128\vert aad' \vert, 8) \mathbin\Vert \operatorname{encode_{big}}(128\vert c'\vert, 8) \)
  4. \( blocks = aad' \mathbin\Vert c' \mathbin\Vert (len) \mathbin\Vert (s) \)
  5. \( \operatorname{return} \sum\limits_{i=1}^{\vert blocks\vert} blocks_{\vert blocks \vert-i} h^{i-1}\)


\(\operatorname{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-ECB}(k, n') \)
  2. \( c = r \oplus m \)
  3. \( h = \operatorname{AES-ECB}(k, 0) \)
  4. \( s = \operatorname{AES-ECB}(k, 2^{32}n + 1) \)
  5. \( \operatorname{return} c, \operatorname{GMAC}(h, s, aad, c) \)

The authentication key \( h \) is independent of the nonce \( n \). The constant term \( s \) acts as a blind to hide the confidential block data in the MAC. Finally, note that the polynomial computation reverses the order of the blocks.