Summary
Work over the binary extension field with nbits = 64*3 = 192. The internal state evolves affinely and the output is the top 64 bits of the 192-bit state.
$$S_{t+1}=a,S_t+b \text{ in } \mathbb{F}_{2^{192}}$$ $$y_t=\lfloor S_t / 2^{128}\rfloor \in {0,\ldots,2^{64}-1}$$
The challenge prints 200 outputs values $= [y_0,\ldots,y_{199}]$, then takes two more outputs $v_1=y_{200}$, $v_2=y_{201}$ to form the AES-ECB key (big-endian):
$$\text{key}=(v_2 \ll 64)\ | \ v_1$$
The padded flag is encrypted with this 128-bit key; the ciphertext msg is provided.
Goal: recover $v_1$ and $v_2$ from the 200 observed outputs, derive the key, and decrypt the flag.
Solve
We treat field elements and outputs as bit vectors over $\mathbb{F}_2$.
- There exists a binary matrix $A\in\mathbb{F}_2^{192\times 192}$ and a vector $B\in\mathbb{F}_2^{192}$ such that $$S*{t+1}=A,S_t \oplus B$$
- The “top-64-bits” projection is a fixed binary matrix $P\in\mathbb{F}_2^{64\times 192}$ with $$y_t=P,S_t$$
To remove the constant $B$ within linear algebra, use an augmented state: define $\tilde S_t=\begin{bmatrix}S_t\\ 1\end{bmatrix}\in\mathbb{F}_2^{193}$, the block matrix $\tilde A=\begin{bmatrix}A & B\\ 0\ \cdots\ 0 & 1\end{bmatrix}\in\mathbb{F}_2^{193\times 193}$, and $\tilde P=\begin{bmatrix}P & 0\end{bmatrix}\in\mathbb{F}_2^{64\times 193}$. Then the system is linear and time-invariant over $\mathbb{F}_2$:
$$\tilde S_{t+1}=\tilde A,\tilde S_t \qquad \text{and} \qquad y_t=\tilde P,\tilde S_t$$
Iterating gives $\tilde S_t=\tilde A^t\tilde S_0$ and $y_t=\tilde P,\tilde A^t\tilde S_0$. Since the augmented state has dimension $193$ and each output provides $64$ linear bits, the output sequence satisfies a block linear recurrence of order at most
$$m \le \left\lceil \frac{193}{64} \right\rceil = 4$$
Therefore there exist binary matrices $M_0,M_1,M_2,M_3 \in \mathbb{F}_2^{64\times 64}$ such that
$$y_{t+4}=M_3,y_{t+3} \oplus M_2,y_{t+2} \oplus M_1,y_{t+1} \oplus M_0,y_t$$
Method
Concatenate four consecutive outputs into a 256-bit input vector $X_t=[y_{t+3}\ ||\ y_{t+2}\ ||\ y_{t+1}\ ||\ y_t]$. For each bit index $k\in{0,\ldots,63}$ there exists a mask $w^{(k)}\in\mathbb{F}*2^{256}$ such that $$(y_{t+4})_k\equiv w^{(k)}\cdot X_t \pmod 2$$
For each $k$, stack all times $t=0,\ldots,195$ into a tall linear system over $\mathbb{F}_2$ to solve for $w^{(k)}$ (200 outputs $\Rightarrow$ 196 training pairs).
Solve over $\mathbb{F}_2$. Perform Gaussian elimination to recover each $w^{(k)}$. With clean data, the learned predictor reproduces the training window exactly (zero mismatches).
Apply the predictor twice to obtain $v_1=y_{200} \; \text{and} \; v_2=y_{201}$
Derive key & decrypt. Form the big-endian key and decrypt
msg(AES-ECB, PKCS#7): $$\text{key}=(v_2 \ll 64)\ | \ v_1$$
This entire method is implemented in the code below.
values = [...]
msg = b'..'
def gf2(ms, bs, n):
r = [ (ms[i] & ((1<<n)-1)) | ((bs[i]&1)<<n) for i in range(len(ms)) ]
p, row, m = [-1]*n, 0, len(r)
for c in range(n):
k = next((i for i in range(row, m) if (r[i]>>c)&1), None)
if k is None: continue
r[row], r[k] = r[k], r[row]
p[c] = row
for i in range(m):
if i!=row and ((r[i]>>c)&1): r[i] ^= r[row]
row += 1
if row==m: break
x = 0
for c in range(n-1, -1, -1):
i = p[c]
if i==-1: continue
v = (r[i]>>n)&1
h = r[i] & (((~0)<<(c+1)) & ((1<<n)-1))
v ^= (h & x).bit_count() & 1
if v: x |= 1<<c
return x
def learn(vals):
T, n = len(vals)-5, 256
ms = []
rhs = [[] for _ in range(64)]
for t in range(T):
y3,y2,y1,y0 = vals[t+3],vals[t+2],vals[t+1],vals[t]
m = (y3 & ((1<<64)-1)) | ((y2 & ((1<<64)-1))<<64) | ((y1 & ((1<<64)-1))<<128) | ((y0 & ((1<<64)-1))<<192)
ms.append(m)
y4 = vals[t+4] & ((1<<64)-1)
for k in range(64): rhs[k].append((y4>>k)&1)
cs = [gf2(ms, rhs[k], n) for k in range(64)]
def pred(a,b,c,d):
mask = (d & ((1<<64)-1)) | ((c & ((1<<64)-1))<<64) | ((b & ((1<<64)-1))<<128) | ((a & ((1<<64)-1))<<192)
o = 0
for k in range(64):
if ((cs[k]&mask).bit_count()&1): o |= 1<<k
return o
return cs, pred
cs, pred = learn(values)
v1 = pred(values[196], values[197], values[198], values[199])
v2 = pred(values[197], values[198], values[199], v1)
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
key = ((v2<<64)|v1).to_bytes(16, "big")
pt = AES.new(key, AES.MODE_ECB).decrypt(msg)
print(unpad(pt, 16).decode())
Flag
crew{Its_34513r_1n_GF2_d1a83b1addeb0ed863b46a85aef9a293}