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=flagotp=(1,0,0,0,0,1)
After our transformation, the vectors become
flag=(1,1,1,1,1,1),ct=(1,1,1,1,1,1)
It's clear that their dot product is
flagct=1+11+11+1=0

We may easily prove this fact. Assume that

flag=(p1,p2,,pn),ct=(c1,c2,,cn) According to the construction, there are exactly
n2
indices
i
so that
pi=ci
while other indices
j
satisfying
pj=cj
. Therefore,
flagct=ipici+jpjcj=i1+j1=0

Problem Re-Formulation

Given

200 vectors
cti
in
{1,1}320
. Find a vector
flag
in
{1,1}320
which is perpendicular to those
200
vectors
cti
.

Idea from Nguyen-Stern Algorithm: Ortho-Lattice Attack

Ortho-Lattice Attack is well-explained in the section 3.1 of this paper

There are many vectors in the orthogonal complement, but we require

flag in
{1,1}320
, consisting of short vectors! For convenience, let
cti=(ci,1,ci,2,,ci,320)
and the target solution is
flag=(p1,p2,,p320)
Then we have
flagctiT=0flag[ct1T,ct2T,,ct200T]=[0,0,,0]
By definition of matrix multiplication, this means a linear combination of row vectors of
[ct1T,ct2T,,ct200T]
is zero. Or equivalently, consider the vectors
vj=(c1,j,c2,j,,c200,j)
, we get
p1v1+p2v2++p320v320=(0,0,,0)
To find the coefficients, we extend
vj
with
319
zeros and
1
, like
vj¯=(c1,j,c2,j,,c200,j,0,0,1,0,0,,0)
where
1
appears in the
200+j
-th position. Then
p1v1¯+p2v2¯++p320v320¯=(0,0,,0,p1,p2,,p320)
However,
vj¯
is alreay short, so we modify those vectors to be
wj=(ac1,j,ac2,j,,ac200,j,0,0,1,0,0,,0)
Here,
a
is a large enough (>>
320
in our case) integer.

Almost Happy Ending

Now, we may run LLL (a popular method to find small things, see wiki) 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