Forbidden Salamanders

+ Forbidden Salamanders + at cyfraeviolae.org +

+ source code + · + nonce reuse + · + nonce truncation + · + key commitment +

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

+
+

+ Attack outline. +

+ Recall that the AES-GCM ciphertext is computed as the XOR of the + keystream and the message. One can modify the bits of the + ciphertext arbitrarily to effect the same change in the decrypted + plaintext. +

+ Where certain bits of the plaintext are already known, the attacker + can fully determine the same bits of the forged plaintext. If + nonces are reused, the keystream will be identical, allowing us to + recover plaintext via + + crib dragging, which makes this attack particularly effective. +

+ However, we still need to compute a new MAC over the forged ciphertext. + Simplifying for a ciphertext \(c\) of two blocks, the GMAC MAC is computed as + \[ + mac = s + (len)h + c_1h^2 + c_0h^3, + \] + where \(s\) is a constant depending on the AES-GCM key and the nonce, and \(h\) + is the authentication key depending only on the AES-GCM key. +

+ If we intercept a second ciphertext \(c'\) encrypted under the same key and nonce, + we can compute + \[ + mac + mac' = (s + s') + (len + len')h + (c_1 + c'_1)h^2 + (c_0+c'_0)h^3, + \] + Since \(s = s'\) and \(x+x=0 \in \mathbb{F}_{2^{128}}\), we are + left with the polynomial equation + \[ + 0 = (mac + mac') + (len + len')h + (c_1 + c'_1)h^2 + (c_0+c'_0)h^3 + \] + where all variables are known other than \(h\). Thus, recovering \(h\) + is a simple matter of finding the roots by factoring the + polynomial using a computer algebra system such as SageMath. +

+ We plug \(h\) back into the first equation to recover \(s\), + and finally, we can forge the MAC for arbitary ciphertext under the + same nonce. +

+
+ +

+ Authentication key + +

+ Forged MAC + +

+
+

+from aesgcmanalysis import xor, gcm_encrypt, nonce_reuse_recover_secrets, forge_gmac
+k = b"YELLOW_SUBMARINE"
+nonce = b"JORGELBORGES"
+m1 = b"""The universe (which others call the Library) is composed of an indefinite and
+perhaps infinite number of hexagonal galleries, with vast air shafts between,
+surrounded by very low railings."""
+aad1 = b"The Anatomy of Melancholy"
+m2 = b"From any of the hexagons one can see, interminably, the upper and lower floors."
+aad2 = b"Letizia Alvarez de Toledo"
+c1, mac1 = gcm_encrypt(k, nonce, m1, aad1)
+c2, mac2 = gcm_encrypt(k, nonce, m2, aad2)
+
+# Recover the authentication key and blind from public information
+h, s = nonce_reuse_recover_secrets(nonce, aad1, aad2, c1, c2, mac1, mac2)
+
+# Forge the ciphertext
+m_forged = b"As was natural, this inordinate hope was followed by an excessive depression."
+c_forged = xor(c2, xor(m2, m_forged))
+aad_forged = b"You who read me, are You sure of understanding my language?"
+mac_forged = forge_gmac(nonce, h, s, c_forged, aad_forged)
+assert gcm_decrypt(k, nonce, c_forged, aad_forged, mac_forged) == m_forged
+

+ Show me the code. +

+ Show me the math. +

+ see homepage + The forged ciphertext can be computed as a xor from original ciphertext, + which should be particularly easy as nonce reuse reveals the XOR and then + crib dragging. +

+ + + + -- cgit v1.2.3