Category: Crypto
Points: 482 (10 solves)
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.