# SEETF 2022

Thanks for Social Engineering Xperts for preparing those interesting problems!

## Neutrality

### Intro

An extremely interesting crypto! The author generates $200$ one-time pads with same numbers of $0$,$1$, and we are given the XORs of flag and those OTPs.

### Beginner-Friendly Math

As XOR is a bitwise operation, it's natural to convert the ciphertexts to bit vectors. Now, it's the key point to the problem.

**Trick.** Change $0$ and $1$ to $-1$ and $1$, respectively. Then the dot product of bit vectors of flag and ciphertext is $0$. For instance, suppose the original flag is $$flag = (0, 0, 1, 0, 1, 1)$$ an one-time pad is $$ otp = (1, 0, 1, 0, 1, 0) $$ The corresponding ciphertext is $$ ct = flag \oplus otp = (1, 0, 0, 0, 0, 1) $$ After our transformation, the vectors become $$ flag = (-1, -1, 1, -1, 1, 1), \quad ct = (1, -1, -1, -1, -1, 1) $$ It's clear that their dot product is $$ flag \cdot ct = -1 + 1 - 1 + 1 - 1 + 1 = 0 $$

We may easily prove this fact. Assume that $$ flag = (p_{1}, p_{2}, \dots, p_{n}), \quad ct = (c_{1}, c_{2}, \dots, c_{n}) $$ According to the construction, there are exactly $\frac{n}{2}$ indices $i$ so that $p_{i} = c_{i}$ while other indices $j$ satisfying $p_{j} = -c_{j}$. Therefore, $$flag \oplus ct = \sum\limits_{i}{p_{i}c_{i}} + \sum\limits_{j}{-p_{j}c_{j}} = \sum\limits_{i}{1} + \sum\limits_{j}{-1} = 0$$

### Problem Re-Formulation

Given $200$ vectors $ct_{i}$ in $\{-1, 1\}^{320}$. Find a vector $flag$ in $\{-1, 1\}^{320}$ which is perpendicular to those $200$ vectors $ct_{i}$.

### Idea from Nguyen-Stern Algorithm: Ortho-Lattice Attack

Ortho-Lattice Attack is well-explained in the section 3.1 of [this paper](https://eprint.iacr.org/2020/461.pdf)

There are many vectors in the orthogonal complement, but we require $flag$ in $\{-1, 1\}^{320}$, consisting of *short vectors*! For convenience, let $$ct_{i} = (c_{i,1}, c_{i,2}, \dots, c_{i,320})$$ and the target solution is $$ flag = (p_{1}, p_{2}, \dots, p_{320}) $$ Then we have $$ flag * ct_{i}^{T} = 0 \longrightarrow flag * \begin{bmatrix} ct_{1}^{T}, ct_{2}^{T}, \cdots, ct_{200}^{T} \end{bmatrix} = [0, 0, \cdots, 0] $$ By definition of matrix multiplication, this means a linear combination of row vectors of $$ \begin{bmatrix} ct_{1}^{T}, ct_{2}^{T}, \cdots, ct_{200}^{T} \end{bmatrix} $$ is zero. Or equivalently, consider the vectors $v_{j} = (c_{1,j}, c_{2, j}, \dots, c_{200, j})$, we get $$ p_{1}v_{1} + p_{2}v_{2} + \cdots + p_{320}v_{320} = (0, 0, \dots, 0) $$ To find the coefficients, we extend $v_{j}$ with $319$ zeros and $1$, like $$\bar{v_{j}} = (c_{1, j}, c_{2, j}, \dots, c_{200, j}, 0, 0, 1, 0, 0, \dots, 0)$$ where $1$ appears in the $200+j$-th position. Then $$ p_{1}\bar{v_{1}} + p_{2}\bar{v_{2}} + \cdots + p_{320}\bar{v_{320}} = (0, 0, \dots, 0, p_{1}, p_{2}, \dots, p_{320}) $$ However, $\bar{v_{j}}$ is alreay short, so we modify those vectors to be $$ w_{j} = (ac_{1, j}, ac_{2, j}, \dots, ac_{200, j}, 0, 0, 1, 0, 0, \dots, 0) $$ Here, $a$ is a large enough (>> $\sqrt{320}$ in our case) integer.

### Almost Happy Ending

Now, we may run LLL (a popular method to find small things, see [wiki](https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm)) and get a short vector. But it's not short enough ...

### Happy Ending

Why not using BKZ as we don't have time limitation :P Here is my script for finding a short vector. Note that if $v$ is a one short vector, then so is $-v$.

with open("neural_output.txt") as f:
	_ = f.readlines()

def toVec(n):
	v = []
	for i in range(40 * 8):
		if n & (1 << i):
			v += [1]
		else:
			v += [-1]
	return v

M = Matrix(ZZ, 320, 200 + 320)
a = 2^50

for i in range(200):
	n = int(_[i][:-1])
	v = toVec(n)
	for j in range(320):
		M[j, i] = a * v[j]
		M[j, j + 200] = 1

L = M.LLL()
L = L.BKZ(block_size = 10)
for i in range(320):
	v = list(L[i])
	if v[:200].count(0) == 200 and v[200:].count(1) + v[200:].count(-1) == 320:
		print(v[200:])
		break