Overview

In this challenge we are given a custom Feistel cipher network, and we need to perform a known-plaintext key recovery, the attack must be online and take less than 4 minutes. I solved this in a unintended way as I managed to solve it with Gröbner basis, instead of the intended interpolation attack.

Cipher analysis

The cipher we are given implements a 7 round Feistel network with a block size of 16.

The round function it implemented as follows, where key is the $i$-th round subkey

def _f(self, l: int, r: int, key: int) -> int:
	return l ^ sbox(r ^ key, n=self._block_size * 4)

SBOX

The SBOX works over $K = GF(2)[x]/\langle x^{64} + x^4 + x^3 + x + 1 \rangle$ and implements the map $f: x \mapsto x^{2^{64} - 2} + x^{24} + x^{22} + x^{20} + x^{19} + x^{17} + x^{16} + x^{15} + x^{13} + x^{12} + x^{11} + x^7 + x^5 + x^4 + x^2 + x$, which is the same as $f: x \mapsto x^{-1} + x^{24} + x^{22} + x^{20} + x^{19} + x^{17} + x^{16} + x^{15} + x^{13} + x^{12} + x^{11} + x^7 + x^5 + x^4 + x^2 + x$

Notice that this is an invertible function.

An algebraic attack

Since this is all nicely defined over K, we can symbolically walk the cipher forwards and backwards, by working over $F = Frac(K[y_0, ..., y_6])$, where $y_i$ is the $i$-th round key.

So, if we simulate the cipher, we can extract algebraic relations between the plaintext and ciphertext whose roots are the subkeys. For some set of relations $R = {r_0, r_1, ... r_i}$ we can find the intersection (i.e. shared root) of all of the relations by computing the Gröber basis of $R$.

MITM time

If we walk the cipher all the forwards/backwards, we get, for each block, two relations of the form $a/b - c = 0 \Rightarrow a - b \cdot c = 0$, where $a/b \in F$ and $c$ the plaintext/ciphertext. That yields a set of degree ~20 polynomials, and Gröbner does not like that very much (i.e. Does not finish before the heat-death of the universe).

Instead, we take the plaintext and walk it half-way forwards, and the ciphertext and walk it half-way backwards, and try to solve for $a/b - c/d = 0 \Rightarrow a \cdot d - c \cdot b = 0$ for $a/b, c/d \in F$.

This yields degree 8 polynomials, which is significantly better.

Gröbner time

Originally, I had intended to find the solution with sage's $.variety()$ function, however it turned out to be extremely slow, so I instead just extracted it from the Gröbner basis.

Sage, by default uses Singulars singular:groeber algorithm for its Gröbner basis computation. This turns out to be too slow. Thankfully we can just switch to the singular:slimgb algorithm, which is designed to keep polynomials short and their coefficients small.

The solution takes 2m10s on my Hetzner server.

Solution

Note that some variables use different letters in the solution script. Additionally, the solve script is sloppy ctf code. Big sorry.

from binascii import unhexlify
from Crypto.Util.number import long_to_bytes as ltb
from server import *

import random as rnd
import string

from pwn import *
from time import time

proof.all(False)

ROUNDS = 7

forwardsRounds = ROUNDS // 2
backwardsRounds = ROUNDS - forwardsRounds

print(f'{backwardsRounds = }')
print(f'{forwardsRounds = }')

CIPHERROUNDS = 7
blockSize = 16
# key = os.urandom(8)
key = b'\xca\xfe\xba\xbe' * 2
assert len(key) == 8
cipher = Feistel(key, rounds = ROUNDS, block_size = blockSize)

P.<x> = PolynomialRing(GF(2))
poly = x^64 + x^4 + x^3 + x + 1
Q.<y> = GF(2^poly.degree(), 'y', modulus = poly)

R = PolynomialRing(Q, ROUNDS, 'z')
subkeys = R.gens()
z = subkeys[0]
print(f'{subkeys = }')

firstAdd = Q.from_integer(0x01d_5b)
secondAdd = Q.from_integer(0x_15_ba5ed)
knownConstantTerms = firstAdd + secondAdd

def f(l, r, key):
	return l + 1/(r + key) + knownConstantTerms

def encryptBlockAlgebraically(l, r, rounds = ROUNDS):
	for i in range(rounds):
		l, r = r, f(l, r, subkeys[i])
	return l, r

def decryptBlockAlgebraically(l, r, rounds = ROUNDS):
	revsubkeys = subkeys[::-1]
	for i in range(rounds):
		l, r = f(r, l, revsubkeys[i]), l
	return l, r

if args.REMOTE:
	conn = remote('basedsbox.challs.srdnlen.it', 46173)
else:
	conn = process(['sage', '-python', 'server.py'])

pt = (  # ChatGPT cooked a story for us
   "Once upon a time, after linear and differential cryptanalysis had revolutionized the cryptographic landscape, "
   "and before Rijndael was selected as the Advanced Encryption Standard (AES), the field of cryptography was in a unique state of flux. "
   "New cryptanalytic methods exposed vulnerabilities in many established ciphers, casting doubt on the long-term security of systems "
   "once thought to be invulnerable. In response, the U.S. National Institute of Standards and Technology (NIST) "
   "launched a competition to find a successor to the aging DES. In 2000, Rijndael was chosen, setting a new standard for secure encryption. "
   "But even as AES became widely adopted, new challenges, like quantum computing, loomed on the horizon."
).encode()
paddedPt = cipher._pad(pt, blockSize)
# encCt = cipher.encrypt(pt)
encCt = unhexlify(conn.recvline().strip())
blocks = [cipher.xor(encCt[i:i + blockSize], paddedPt[i: i + blockSize]) for i in range(0, len(paddedPt), blockSize)]
cts = [encCt[i: i + blockSize] for i in range(blockSize, len(encCt), blockSize)]
print(f'{len(pt) = }')
print(f'{len(encCt) = }')

assert len(blocks) == len(cts), (len(blocks), len(cts))

relations = []

for enum, pt in enumerate(blocks):
	ct = cts[enum]

	ptl, ptr = splitLR(pt)
	forwards = encryptBlockAlgebraically(ptl, ptr, forwardsRounds)

	ctl, ctr = splitLR(ct)
	backwards = decryptBlockAlgebraically(ctl, ctr, backwardsRounds)

	for left, right in zip(forwards, backwards):
		zeroAtRootsPoly = plsNoFractionField(left, right)
		tmp = zeroAtRootsPoly.factor()
		relations.append(zeroAtRootsPoly)

I = Ideal(relations)

variety = [0] * len(subkeys)
start = time()
if AUTISM:
	G = I.groebner_basis(algorithm = 'singular:slimgb')
	for elem in G:
		print('=' * 40)
		print(elem)
		# pray that we get a z_x - blah
		variable = elem.variables()[0]
		idx = subkeys.index(variable)
		root = elem.univariate_polynomial().roots()[0][0]
		variety[idx] = root
groebnerTime = time() - start
print(f'{groebnerTime = }')

key = 0
for idx in range(len(subkeys)):
	guess = variety[idx].to_integer()
	key ^^= guess

key = ltb(key).hex()
conn.sendline(key)
conn.interactive()

exit()
"""
variety = I.variety(proof = False)
reducedRound = ROUNDS != CIPHERROUNDS
print(f'CONFIGURATION: {ROUNDS}/{CIPHERROUNDS} ({"Reduced round" if reducedRound else "Full round"} spec)')
print(f'ORACLE: {cipher._round_keys = }')
print(f'{len(variety) = }')
for possibleSolution in variety:
	print('=' * 40)
	# print(possibleSolution)
	for key, value in possibleSolution.items():
		print(f'{key}: {value.to_integer()}')
"""