Codegate CTF 2022 Quals - Happy S-box (Crypto)
Setup
from sage.all import *
from binteger import Bin
from tqdm import tqdm
from sock import Sock
# optimized table-based version of the challenge's LFSR
from binteger import Bin
from tqdm import tqdm
import os
import random
PRECOMP = None
OUT_PRECOMP = None
class LFSR:
rand = random.Random("Codegate2022")
Sbox = [ [0] * 64 + [1] * 64 for _ in range(512 - 6) ]
for i in range(len(Sbox)):
rand.shuffle(Sbox[i])
def __init__(self, seed):
if PRECOMP:
res = 0
for tab in PRECOMP:
res ^= tab[seed & MASK]
seed >>= W
self.state = res
return
else:
self.state = seed
for _ in range(1024):
self.next()
def next(self):
v = self.state
# x^512 + x^8 + x^5 + x^2 + 1
n = ((v >> 0) ^ (v >> 504) ^ (v >> 507) ^ (v >> 509)) & 1
self.state = (v >> 1) | (n << 511)
def output(self):
if OUT_PRECOMP:
out = 0
x = self.state
for tab in OUT_PRECOMP:
out ^= tab[x & OUT_MASK]
x >>= OUT_W
return out
else:
out = 0
x = self.state
for s in self.Sbox:
out ^= s[x & 127]
x >>= 1
return out
def get_precomp(W):
ret = []
for i in tqdm(range(0, 512, W)):
cur = []
lim = min(W, 512 - i)
for x in range(2**lim):
x = x << i
cur.append(LFSR(x).state)
ret.append(cur)
return ret
def get_out_precomp(W):
step = W - 7 + 1
mask = 2**W - 1
ret = []
for i in tqdm(range(0, 512, step)):
cur = []
lim = min(W, 512 - i)
if lim < 7:
continue
for x in range(2**lim):
res = 0
for j in range(lim - 7 + 1):
val = (x >> j) & 127
res ^= LFSR.Sbox[i + j][val]
cur.append(res)
ret.append(cur)
return ret, step, mask
#assert "59b50430" == Bin([LFSR(int(pow(1231235345345345345, 14234234+123*i, 2**512))).output() for i in range(32)]).hex
print("precomputing optimization tables...")
PRECOMP = None
PRECOMP2 = get_precomp(2)
W = 2
PRECOMP = PRECOMP2
MASK = 2**W-1
PRECOMP4 = get_precomp(4)
W = 4
PRECOMP = PRECOMP4
MASK = 2**W-1
PRECOMP8 = get_precomp(8)
W = 8
PRECOMP = PRECOMP8
MASK = 2**W-1
#assert "59b50430" == Bin([LFSR(int(pow(1231235345345345345, 14234234+123*i, 2**512))).output() for i in range(32)]).hex
OUT_PRECOMP, OUT_W, OUT_MASK = get_out_precomp(12)
#assert "59b50430" == Bin([LFSR(int(pow(1231235345345345345, 14234234+123*i, 2**512))).output() for i in range(32)]).hex
precomputing optimization tables...
100%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 256/256 [00:00<00:00, 347.72it/s] 100%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 128/128 [00:00<00:00, 1324.92it/s] 100%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 64/64 [00:00<00:00, 185.94it/s] 100%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 86/86 [00:00<00:00, 141.98it/s]
TL;DR
In this challenge, we have a filtered 512-bit LFSR. The filter function is a XOR of a 1-bit sliding window of randomly chosen 7-bit balanced Boolean functions. We receive one output bit after 1024 LFSR steps, per each 12-bit IV such that the LFSR is seeded with (secret || IV).
The solution is the cube attack. Since the 7-bit Boolean functions are balanced (we only use that it has even parity), their algebraic degree is at most and typically equal to 6. The LFSR step is linear, so we can treat the inputs to S-boxes as a constant (linear image of the secret key) xor the linear image of the IV. By choosing a subset of IVs having the shape of 5-dimensional linear vector spaces, the inputs to S-boxes will have the shape of vector spaces of dimensions up to 5 (smaller dimensions mean that the small vector space is repeated several times). When we sum a Boolean function of degree 6 on a vector space of dimension 5, the resulting function is a degree-1 function of the other fixed inputs (which include unused bits of the IV and the secret key bits). Thus, this sum leaks a linear function of the key. Collecting enough of them (>500) allows key recovery by solving a linear system.
Example
Consider 7-bit function $f$ applied to the input $L(\text{key}) \oplus L'(\text{IV})=k\oplus i$. Assume that $f(x)$ has a monomial $x_0x_1x_2x_3x_4x_5$ of degree 6, so that $$ x_0x_1x_2x_3x_4x_5 = (i_0\oplus k_0)(i_1\oplus k_1)(i_2\oplus k_2)(i_3\oplus k_3)(i_4\oplus k_4)(i_5\oplus k_5). $$ Summing this monomial over all possible values of $x_0,x_1,x_2,x_3,x_4$ (a 5-dimensional vector space) would result in the value $$ \bigoplus_{(x_0,x_1,x_2,x_3,x_4) \in \mathbb{F}_2^5} x_0x_1x_2x_3x_4x_5 = x_5 = (i_5 \oplus k_5), $$ which is a linear function of the fixed IV bits (const) plus the linear function of the key.
Since $f$ is a xor-sum of monomials of degree at most 6, the resulting sum of the full $f$ over the given subspace of inputs is still an affine function of the key. (Monomials not divisible by $x_0x_1x_2x_3x_4$ will vanish in this sum, irrespectively of the degree).
Since the stream cipher's output is a xor-sum of many such sums, the resulting sum is still an affine function of the key. It can be recovered in a black-box manner by computing the cube sums on the zero input and on the unit vectors (single-bit keys).
from sage.crypto.boolean_function import BooleanFunction
# note: ANF in sage is indexed lsb-to-msb (x0 is the LSB, etc.)
bf = BooleanFunction(LFSR.Sbox[1])
anf = bf.algebraic_normal_form()
anf
x0*x1*x2*x3*x4*x5 + x0*x1*x2*x3*x4*x6 + x0*x1*x2*x3*x5*x6 + x0*x1*x2*x3*x5 + x0*x1*x2*x4*x5 + x0*x1*x2*x4 + x0*x1*x2*x6 + x0*x1*x2 + x0*x1*x3*x4*x5 + x0*x1*x3*x4*x6 + x0*x1*x3*x5*x6 + x0*x1*x3*x5 + x0*x1*x3 + x0*x1*x4*x5 + x0*x1*x4*x6 + x0*x1*x5*x6 + x0*x1*x5 + x0*x1 + x0*x2*x3*x4*x5 + x0*x2*x3*x4*x6 + x0*x2*x4*x5*x6 + x0*x2*x4*x5 + x0*x2*x5*x6 + x0*x2*x6 + x0*x3*x4*x6 + x0*x3*x4 + x0*x3*x6 + x0*x4*x5 + x0*x4*x6 + x0*x4 + x0 + x1*x2*x3*x4 + x1*x2*x3*x5 + x1*x2*x3*x6 + x1*x2*x3 + x1*x2*x4 + x1*x2*x5*x6 + x1*x2*x5 + x1*x3*x4*x5 + x1*x3*x4*x6 + x1*x3*x4 + x1*x3*x5 + x1*x3*x6 + x1*x4*x5*x6 + x1*x4 + x1*x6 + x1 + x2*x3*x4*x5 + x2*x3*x5*x6 + x2*x4*x5*x6 + x2*x5 + x2*x6 + x2 + x3*x4*x5 + x3*x4*x6 + x3*x4 + x3*x5*x6 + x3*x6 + x3 + x4*x5*x6 + x4 + x5*x6 + x6
from itertools import product
sum(anf(x0=x[0],x1=x[1],x2=x[2],x3=x[3],x4=x[4]) for x in product(range(2), repeat=5))
x5 + x6
This cube sum comes from the monomials $x0*x1*x2*x3*x4*x5$ and $x0*x1*x2*x3*x4*x6$. The other monomials vanish when summed over the chosen subspace.
Note: in this example, the input vector space is spanned by 5 unit vectors, but it can similarly be a general 5-dimensional subspace.
Intro
In the challenge, we have a filtered LFSR, where the filter function is a XOR of a step-1 sliding window of randomly chosen 7-bit Boolean functions.
class LFSR:
rand = random.Random("Codegate2022")
Sbox = [ [0] * 64 + [1] * 64 for _ in range(512 - 6) ]
for i in range(len(Sbox)):
rand.shuffle(Sbox[i])
def __init__(self, seed):
self.state = seed
for _ in range(1024):
self.next()
def next(self):
v = self.state
# x^512 + x^8 + x^5 + x^2 + 1
n = ((v >> 0) ^ (v >> 504) ^ (v >> 507) ^ (v >> 509)) & 1
self.state = (v >> 1) | (n << 511)
def output(self):
out = 0
for i in range(512 - 6):
out ^= self.Sbox[i][(self.state >> i) & 127]
return out
guess_this = os.urandom((512 - 8) // 8)
guess_this = guess_this[:-1] + bytes([guess_this[-1] & 0xf0])
seed = int.from_bytes(guess_this, 'big') << 8
print("Seed generated. It'll take some time to generate a hint.")
v = 0
for i in range(2 ** 12):
lfsr = LFSR(seed | i)
v <<= 1
v |= lfsr.output()
print("Here's the hint. It should be enough.")
print(v.to_bytes(2 ** 12 // 8, 'big').hex())
ans = input("Guess the seed > ")
if guess_this == bytes.fromhex(ans):
with open('flag', 'r') as f:
print(f.read())
else:
print("WRONG")
The stream cipher essentially takes the key (seed) and a 12-bit IV. We get 1 bit of output per each of all 4096 different IVs and the same secret key, which we need to recover.
Preparation
def support(proj):
"""Return subset of IVs for a given vector space defined by rows of a matrix."""
return [Bin(v).int for v in proj.row_space()]
Generating random 5-dimensional subspaces:
projs = set()
while len(projs) < 525: # 500 + eps
proj = random_matrix(GF(2), 5, 12).rref()
if proj.rank() != proj.nrows():
continue
proj.set_immutable()
projs.add(proj)
sups = [support(proj) for proj in projs]
len(sups)
525
Cache unit/zero key outputs for all IVs.
cache = {}
for tail in range(2**12):
cache[None,tail] = LFSR(tail).output()
for i in tqdm(range(500)):
for tail in range(2**12):
cache[i,tail] = LFSR(Bin.unit(i, 512).int | tail).output()
100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 500/500 [01:08<00:00, 7.33it/s]
Compute by black-box cube computations the affine functions of the cubes.
cubemat = []
const = []
for sup in tqdm(sups):
c = 0
for s in sup:
c ^= cache[None, s]
const.append(c)
row = []
for i in range(500):
seed = Bin.unit(i, 512)
y = c
for s in sup:
y ^= cache[i, s]
row.append(y)
cubemat.append(row)
cubemat = matrix(GF(2),cubemat)
const = vector(GF(2), const)
print("rank", cubemat.rank(), "/", cubemat.nrows(), cubemat.ncols())
assert cubemat.rank() == 500
100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 525/525 [00:06<00:00, 81.18it/s]
rank 500 / 525 500
The attack
f = Sock("13.209.23.166 9002")
f.read_until("enough.")
f.read_line()
hint = f.read_line()
#hint = "e8dc99f0e0dea6db04188b80578154b160f5d979371f5582b5f7fac45d79dee0cc3623d5ad754dde75de3d081d61ff0682f05c1f9cdb922ddfaafde4c2faa0f748fcf30dfe487c866261ddff60bfc20f2cb0e2c9cb7bbf9a62676a73c274072c06ef536795e451adba193aa2e89da517f0e1673033f78a26d45d6144f7cd05876a3f6f80b465d402077a8cf1f56f0ab26952343ab7e64283cf8c741e3eacf9ee5504660df615575933ff42b08159380faa52cd7fbc1d2e509298e53488330c69f5e46ff4eb911375f0e22212cff798845bc20fca815eeae87057fd4ba3013387588e1e0b2e2b92a73911e5b22ef43d9d343df12121efe64f6a4af8eb143912d2951badace37f9d353e1cc4f13870d1cc619bd7119885c5848e5fd9398fe9f95e94374c8a1cf408679dcf71c504fa6f0af6f2f97156435ea4470a3fdbcacf073e9a2af3d133e2fa73d628e4f2cd5df34850a0a6de93c491afb4350f2a00a48302a11bef7d04f7662116a2e44c84b37156351aa9dde5d668ed5226621cf8be0b53b7856a3ae37162df987bbcccea1b921ed423e77c9ca4e9184d435d01b32bec495e229bd7264d36b5b71224c218881524b0f7aed8d51ffb6a0eee9534685ae7ad459ff6e240c87c35a839740b68ad5423b8a975c117adb6411d149c1c6983e2537f6ce0306b2ff4e6374910a556b333bd3482fbd9ffd123b10b8030e7d32b29f9"
hint = Bin(int(hint, 16), 2**12).tuple
print("solving for hint", Bin(hint).hex)
# compute sums over the subspaces
target = []
for i, sup in enumerate(sups):
v = int(const[i])
for x in sups[i]:
v ^= hint[x]
target.append(v)
# solve for the secret key
target = vector(GF(2), target)
base = cubemat.solve_right(target)
seed = Bin(base).int << 12
print("recovered seed %x" % seed)
f.send_line(("%x" % (seed))[:-2])
print(f.read_all().decode())
solving for hint 56e8adafe51a179b0e608b26d6356a29482e8a0275b5c4fe06c460a99f107f2ad1be49eab8f65abe4dccef5f4241d24c6d4ded5cfc2cb0e92b0be7fd576abc00eadd745c670e26d23e83d7e88a11e3db9c3f73a26b8eeb2a82abfa9a94fe19a693fd3034d2a9bd88586029315fc0a302f1c025d0fbcd6fc8e2b531820e07806bb9df96b597b91f81f1909bfc17044fa6867382d2dfe0b1c9071d30f3727c1643f2f8159d1db7dd656d38ee9e8d226ee49a46726944d6136448d0887c3637c47219eccf386cbfa4fe08413711c91484bb1e98da4d443c6663ad3700e58ce4f8ece90233e8b7856c8f5879c2f05dd2e1fcf3e4376a4ff6d7871f3bb8c540955670d6bdbeeed479238543c1d869a7ab7d1d141122c07448251aeccf8d4d397fe850d083999fc97ed1aa702fed511bd28e3416ec433005dd60d99ca926134f570c632e3c9fba2a9a5ccfb36031fce2f98f01bda92fd3ad4e5c98758d4a432efa53b0855f9a755b16448ef570790ba4bc1e45f44c089677f7462c127ee56edda4be7c939747de58af63a9f4e65371546267f4aff0626b00f504e0b9a369defa4a07fe78c986e513f40c03a91455b008fe437bfd3ec44b99c9670307015b01c0f60b23800a4821b1bb9dc31b7d09cce030f2f3f9467129108606d7361703ef1c503341a19bc0ca64afe63f6eeab5cc2bf8bc13e20e90d186929db4fdedc214c2683df4
recovered seed 440de85b1fdfb1320dbf6e4da9ca675d6742d26c8ebf6442acbb2e48eb271f649ef1a6acb7757816b84cbe292a565ccfe35989b7c47435a48c76c51a319bb000
Guess the seed > codegate2022{73bc443befd5467a50f0139d1dbeae970cdd7487ecd3092fd294329b1537622b1d6925337f613b288c484f8a188899f52a07aba5}