# 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$. python= 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