idekCTF 2024 - summertime (crypto)
Published on 19 Aug 2024
Writeups
This challenge was about breaking the code-based SURF cryptosystem.
Introduction
In this challenge, we need to solve syndrome decoding for a large binary code with a certain structure:
n, kv, ku = 4800, 916, 1484 # ku + kv = n / 2
Hu = random_matrix(GF(2), kv, n//2, implementation = "m4ri")
Hv = random_matrix(GF(2), ku, n//2, implementation = "m4ri")
Hs = block_matrix(GF(2), [
[Hu, 0],
[Hv, Hv]
])
while (S := random_matrix(GF(2), n//2, n//2, implementation = "m4ri")):
if S.is_invertible():
break
perm = list(range(n))
random.shuffle(perm)
P = Matrix(GF(2), [[1 if i == perm[j] else 0 for j in range(n)] for i in range(n)], implementation = "m4ri")
# Usual obfuscation of the code
Hpub = S * Hs * P
The structured matrix $H_s$ is obfuscated in the usual way $H_{pub}= S \times H_s \times P$: the columns are permuted at random, and we are given a random basis for the row space of the matrix. Both transformations do not change the weights of the solutions.
The goal is to find an error vector $e$ of weight $k_v=916$ satisfying $H_{pub}\times e=h$ where $h$ is a hash of fixed message:
def verify(Hpub, msg, e):
e = vector(GF(2), e)
if e.hamming_weight() != kv:
return False
n = Hpub.ncols()
s = shake_256(msg).digest(n//16)
s = vector(GF(2), list(map(int, bin(int.from_bytes(s, 'big'))[2:].zfill(n//2))))
return Hpub * e == s
msg = b"gimme the flag!"
For simplicity, let's consider a downscaled version of the problem. The applied methods would directly work for the original one as well.
In [1]:
n, kv, ku = 60, 10, 20
Hu = random_matrix(GF(2), kv, n//2, implementation = "m4ri")
Hv = random_matrix(GF(2), ku, n//2, implementation = "m4ri")
Hs = block_matrix(GF(2), [[Hu, 0], [Hv, Hv]])
while (S := random_matrix(GF(2), n//2, n//2, implementation = "m4ri")):
if S.is_invertible():
break
perm = list(range(n))
random.shuffle(perm)
P = Matrix(GF(2), [[1 if i == perm[j] else 0 for j in range(n)] for i in range(n)], implementation = "m4ri")
Hpub = S * Hs * P
In [2]:
def print_mat(name, mat, sep_rows=(), sep_cols=()):
print(name, ":")
for i, row in enumerate(mat):
if i in sep_rows:
print("-" * mat.ncols())
if sep_cols:
prev = 0
for off in sep_cols:
print(*row[prev:off], "|", sep="", end="")
prev = off
print(*row[prev:], sep="")
else:
print(*row, sep="")
print()
In [3]:
print_mat("Hs", Hs, [kv], [n//2])
print_mat("Hpub", Hpub, [kv], [n//2])
Hs : 001010100011100001110000101010|000000000000000000000000000000 111101111110100111011110000110|000000000000000000000000000000 001000010010111101110001000110|000000000000000000000000000000 100101100101011010000011000110|000000000000000000000000000000 111011000110110001110111100100|000000000000000000000000000000 100110001110111011110001000001|000000000000000000000000000000 101010000001010001110000100000|000000000000000000000000000000 110011010100100011111001011111|000000000000000000000000000000 111110011011001011110101010100|000000000000000000000000000000 100100010110110010001010111010|000000000000000000000000000000 ------------------------------------------------------------ 101101010010111100111010101001|101101010010111100111010101001 101110101100111100110101010000|101110101100111100110101010000 010001010010110101100101100011|010001010010110101100101100011 010010000010111111010010110010|010010000010111111010010110010 100001000101011010001100110000|100001000101011010001100110000 010001111100100001100001100101|010001111100100001100001100101 000010011010001011111010001011|000010011010001011111010001011 111011100100001001101010101101|111011100100001001101010101101 101111000110011011000100001100|101111000110011011000100001100 101110101001100101100000001110|101110101001100101100000001110 110010000000000010110011010100|110010000000000010110011010100 100111110110001101100111111001|100111110110001101100111111001 101010111000000000101011101010|101010111000000000101011101010 000001001110001010000111001000|000001001110001010000111001000 011011011100010101110110101100|011011011100010101110110101100 000001001110010011101110101111|000001001110010011101110101111 100011110011110111111101110101|100011110011110111111101110101 101110111100111011011001010110|101110111100111011011001010110 011101011001110010000110010000|011101011001110010000110010000 001010010100011110011110011000|001010010100011110011110011000 Hpub : 001100110000011111110010111101|110101110011011011001000100101 001100011111000010110011011111|010111011010101000111001100001 011001011100001100011001000011|010110011110110100000010110111 010110111101000001100101011101|111110100010111111110000111110 100000101111100101011110010011|011000001000101001101010000001 101110011111011110110001000110|111111100001001001101001101110 011111000001110001001110101001|011110001101110101100111011000 001101000100010100011011110001|011000011010101011011110110101 011110111111110011110100101010|100001011100000101011000010101 000101001101101000000111010101|101101000000010111110010000110 ------------------------------------------------------------ 011100101111000110110100000001|110010010000100110001101011111 101010011111011110100011011011|010100111001010100001110111101 010100010101110010101010011111|110010111110101110001111001010 001111000111011001110100111000|100101110000010010000111000000 100111101010110001001011100111|011010110110010010101010100000 000111000100101100111110110111|111000110111000100110110011110 110100101110001110100101101001|110100101101000010101011010110 101110110100001110100001100000|100101100101011101110110011000 010010010100011110100110001010|000011000011001001011100100101 011010110111110110001111010011|111000111111101000010100001000 001001011100110101101011001010|001100011011010001010001000101 010111011011100100100011001001|100010100010010010110001000101 100011101010011101001010010111|000100111101111100011001001000 010100010100001111101011001101|011110100110101010010000111001 000000100110010011010001010100|101111001100101011111011011010 110110111110010010001001000001|001011001010001101101101101101 000101100111110000101110101100|110101010000101110010000010010 100011000100010101010011011011|001110000110101111101111001101 111100111110010111011001000011|100000100000110010110110111010 110110000000010001101010110010|010100011000110101111111110101
The trapdoor
The parameters are quite large for general decoding, thus we have to use the secret structure: $$H_s = \begin{bmatrix}H_u & 0\\H_v & H_v\end{bmatrix}$$ Where $H_u$ is a $916\times2400$ matrix and $H_v$ is a $1484\times2400$ matrix, which is repeated twice in $H_s$.
Even without the code obfuscation, it is not clear to how use this trapdoor structure to obtain a valid signature: $$\begin{bmatrix}H_u & 0\\H_v & H_v\end{bmatrix} \times \begin{bmatrix}e_1 \\ e_2\end{bmatrix} = \begin{bmatrix}h_u \\ h_v\end{bmatrix},$$ where $h_u$ and $h_v$ are given and $e_1 || e_2$ has weight exactly 916.
The key idea is that the problem reduces to decoding $H_v \times e_2 = h_v$ for $e_2$ of weight 916 and then extending the solution without changing the weight by using the fact that we choose each column of $H_v$ either from the left or from the right half.
Decoding $H_v$
The idea is to first decode using $H_v$. Here, we can use the basic Prange method: compute $Q$ such that $$Q\times H_v = [Id ~\mid~ R]$$ and take columns from the identity part to match the target $Q \times \begin{bmatrix}h_u\\h_v\end{bmatrix}$. The process can be randomized by permuting columns randomly. The solutions will be centered around weight $1484/2=742$.
We can easily increase the weight by adding about $916-742=174$ random columns of $R$ into the solution (which amounts to adding them to the target vector $Q\times h$). Then, by sampling enough random solutions, we can get vector $e_2$ of weight exactly $916$ and satisfying $H_v \times e = h_v$.
Decoding $H_u$
Now, we can extend the solution to the full matrix. Assume first that we take the columns of $H_v$ only from the right half. Then we get $H_s \times \begin{bmatrix}0 \\ e_2\end{bmatrix} = \begin{bmatrix}0 \\ h_v\end{bmatrix}$. If we swap one column from the right side with the paired column from the left (columns $i$ and $i+n/2$), the bottom part of the result does not change, while the top one changes by the corresponding column of $H_u$. Considering all 916 columns from our base solution, we need to find a subset of the corresponding columns of $H_u$ that would add up to $h_u$. This is a simple matrix-vector equation (not decoding), since we are not constrained in weight. We have 916 equations and 916 unknowns, thus with high chance there weill be a solution.
In this challenge, we will recover a matrix of slightly different shape: $$Q' \times H = \begin{bmatrix}B & C\\D & D\end{bmatrix}.$$
The idea remains the same, just the matrix $C$ should be accounted in the correction of the target vector form the base solution.
Recovering the trapdoor
Getting back to the challenge, how can we recover the trapdoor?
Recovering a subspace of the bottom part
The key observation is that inner products between vectors from the bottom part are all zero, since they consist in the sum of two equal sub products. We can thus construct a square matrix $I$ of all pairwise products of rows of a given matrix $M$: $$I_{i,j}(M) = \langle M_{i},M_{j} \rangle.$$
In [4]:
def inner_product_form(mat):
n = mat.nrows()
ipf = matrix(GF(2), n, n)
for i in range(n):
ri = mat[i]
for j in range(i, n):
rj = mat[j]
ipf[i,j] = ipf[j,i] = ri * rj
return ipf
This is how it looks like for the unobfuscated $H_s$:
In [5]:
I = inner_product_form(Hs)
print_mat("I(H_s)", I, [kv], [kv])
I(H_s) : 0111001111|10010111111110101110 1011010000|10110110000101011001 1111101011|10100011010111000000 1111111111|01011101001010110001 0011100111|00010101010110101011 0101010011|11101111110010101010 1011001111|00010100100110100010 1001101011|10100001001101000100 1011111100|01100110011110011110 1011111100|00001010110111011010 ------------------------------ 1110010100|00000000000000000000 0001010010|00000000000000000000 0110010110|00000000000000000000 1101101000|00000000000000000000 0001010001|00000000000000000000 1101111010|00000000000000000000 1110010011|00000000000000000000 1011110100|00000000000000000000 1000011001|00000000000000000000 1010110011|00000000000000000000 1001000110|00000000000000000000 1110101111|00000000000000000000 1011111011|00000000000000000000 0110000101|00000000000000000000 1001111000|00000000000000000000 0101000011|00000000000000000000 1100110011|00000000000000000000 1000000110|00000000000000000000 1000111011|00000000000000000000 0101100000|00000000000000000000
The observation above clearly corresponds to the large square zero submatrix of $I(H_s)$.
For the obfuscated matrix we see no structure of course:
In [6]:
Ipub = inner_product_form(Hpub)
print_mat("I(H_pub)", Ipub, [kv], [kv])
I(H_pub) : 1000011101|11010111100001001010 0010001001|11111010100011101110 0111011000|00010110110001100011 0010001000|11101010010111110101 0000000000|11001010110111001100 1010010001|01010000101101111010 1111000000|01111111001101011100 1000000001|10100110100111100001 0000000000|11101010000010111101 1100010100|11111001010011011001 ------------------------------ 1101100111|10110010101010001001 1101111011|01000101110101000110 0101001111|10001111011110110111 1110011001|10000100101001001111 0101101011|00100011001101101110 1010001100|01110000110011101001 1111101110|10101010111100010000 1000001001|01101001101101110000 1110110100|11010111110001101101 0011100001|01100110110010111011 0000011000|10111011001110011001 0001111100|01101011001011001001 0101100111|10100100011100101011 1111111101|01011101100100110111 0111010110|00101101110011100111 0001011011|00100011011001001110 1100111011|10011100111110011001 0101101010|01111000100001110010 1110010000|01111000010011110111 0011000111|10110100111111101010
However, it is easy to see that $$I(S \times M) = S \times I(M) \times S^T.$$
In [7]:
assert S * I * S.T == Ipub
Thus, at least the rank and row space / kernel are preserved. This is useful, since we can notice that bottom half can not be full-rank since it's spanned my a "high" rectangle. The kernel dimension is at least $k_u - k_v = 568$ for the big instance.
In [8]:
I.rank(), I.nullity(), ku - kv
Out [8]:
(20, 10, 10)
We can match the kernels of $I(H_s)$ and $I(H_{pub})$ and recover some subspace spanned by the part $\begin{bmatrix}H_v & H_v\end{bmatrix}$. For example, multiplying the kernel by $H_s$ gives two augmented copies of the same part of $H_v$:
In [9]:
print_mat("I(Hs)*Hs", I.left_kernel().matrix() * Hs, [], [n//2])
I(Hs)*Hs : 001110100000010011000110001011|001110100000010011000110001011 010011001000101110100011001101|010011001000101110100011001101 111100011010111111110110001111|111100011010111111110110001111 111000101010000000110100010111|111000101010000000110100010111 000110011000010110000000010011|000110011000010110000000010011 011010001100110101111011011111|011010001100110101111011011111 011011010111100100101010001111|011011010111100100101010001111 010010000010111000001000010111|010010000010111000001000010111 110100011011001111011010010000|110100011011001111011010010000 100001001100101101000100010000|100001001100101101000100010000
Groupping column pairs
We can recover these halves from $H_{pub}$ as well, but up to permutation of columns, so nothing is still visible:
In [10]:
print_mat("I(Hpub)*Hpub", Ipub.left_kernel().matrix() * Hpub, [], [n//2])
I(Hpub)*Hpub : 010100101010011010001111110000|101001101111001100011110100010 000000111110110001100101111110|111010101011000001010111001110 111010110011110000011001000100|110000001010100000110100000011 011000101000101000011110100000|010101100011000100001110110010 000110010111101111100101010100|111011101101011000001011101000 110011100011010010001111000010|000100100000001110010100010101 111001011110001011111111110110|101010101011001110000011101111 100100001000101100000010111000|111111001100110101101001110001 100000110100101010000110001110|110011101001001101001111101101 110011010011111011101111011100|111011101000001111011001100001
However, we know that the columns must come in pairs. So we can simply match them:
In [11]:
IH = Ipub.left_kernel().matrix() * Hpub
cols = IH.transpose().rows() # faster
Counter(cols)
Out [11]:
Counter({(0, 0, 1, 0, 0, 1, 1, 1, 1, 1): 2,
(1, 0, 1, 1, 0, 1, 1, 0, 0, 1): 2,
(0, 0, 1, 1, 0, 0, 1, 0, 0, 0): 2,
(1, 0, 0, 0, 1, 0, 0, 1, 0, 0): 2,
(0, 0, 1, 0, 1, 1, 0, 0, 0, 1): 2,
(0, 0, 0, 0, 0, 1, 1, 0, 0, 1): 2,
(1, 1, 1, 1, 0, 1, 0, 0, 1, 0): 2,
(0, 1, 1, 0, 1, 0, 1, 0, 1, 1): 2,
(1, 1, 0, 1, 0, 0, 1, 1, 0, 0): 2,
(0, 1, 0, 0, 1, 0, 1, 0, 1, 0): 2,
(1, 1, 1, 0, 1, 1, 1, 0, 0, 1): 2,
(0, 1, 1, 1, 1, 0, 0, 1, 1, 1): 2,
(1, 1, 1, 0, 0, 1, 0, 0, 0, 1): 2,
(1, 0, 0, 1, 1, 0, 1, 1, 1, 1): 2,
(0, 0, 0, 0, 1, 0, 0, 1, 0, 0): 2,
(1, 0, 0, 0, 1, 1, 1, 0, 1, 1): 2,
(0, 1, 0, 0, 1, 0, 1, 0, 0, 1): 2,
(1, 1, 0, 1, 1, 1, 1, 0, 1, 1): 2,
(1, 0, 0, 1, 0, 1, 1, 1, 1, 1): 2,
(1, 1, 0, 0, 1, 0, 1, 1, 0, 1): 2,
(0, 1, 0, 0, 0, 0, 0, 1, 1, 1): 2,
(0, 1, 0, 0, 0, 1, 1, 0, 1, 0): 2,
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0): 2,
(1, 1, 1, 0, 1, 0, 1, 1, 1, 1): 2,
(0, 0, 0, 1, 0, 1, 0, 1, 0, 0): 2,
(0, 1, 0, 0, 1, 0, 1, 1, 1, 1): 2,
(1, 0, 0, 1, 1, 0, 0, 1, 1, 1): 2,
(1, 1, 1, 1, 0, 0, 1, 0, 0, 0): 2,
(1, 1, 0, 1, 1, 0, 1, 0, 1, 0): 2,
(0, 0, 1, 0, 0, 0, 0, 1, 0, 0): 2})
In [12]:
def row_echelon_transformation(mat):
ker = mat.left_kernel().matrix()
comp = matrix(mat.base_ring(), mat.nrows() - ker.nrows(), mat.nrows())
for i, j in enumerate(mat.pivot_rows()):
comp[i,j] = 1
return comp.stack(ker)
In [13]:
def group_column_pairs(mat):
cols = mat.transpose().rows() # faster
seen = {}
inds = [None] * n
j = 0
for i, vec in enumerate(cols):
vec.set_immutable()
if vec not in seen:
seen[vec] = j
inds[j] = i
j += 1
else:
inds[seen[vec]+n//2] = i
return inds
# PERM arranges equal columns into the (i,n/2+i) positions
PERM = group_column_pairs(IH)
# Q1 is basically echelon form transformation
Q1 = row_echelon_transformation(Ipub)
assert Q1.is_invertible()
Hcols = Hpub.transpose().rows()
H2 = Q1 * matrix(GF(2), [Hcols[i] for i in PERM]).transpose()
print_mat("H_2", H2, [kv, n//2-len(cols[0])], [n//2])
H_2 : 001100110000111110111011101110|101001011001011111001110001000 001100011110000100111110111101|101010010011110110000011011001 011001011100011000000110110101|111100000011011000100111100110 010110111100000011011011110101|000011010111111111111100100101 100000101111001011110110000001|111010000001000100011001001011 101110011110111100000101111010|001010010111010111011100011101 011111000001100011101010110011|010110101101001000111001110011 001101000100101000110010000101|111001101011110100011111101010 011110111111100111001101001000|101110001000100010101111101000 000101001101010001110011101000|000011010010101000111100000111 ------------------------------------------------------------ 011100101110001101000011010001|101011100101000010100110111100 101010011110111100111110100010|100010100111011011100111101010 010100010101100100111111010101|010111110101000111100011011110 100111101011100010100110010100|010101011011011001010010001011 000111000101011001110111000110|011100111101100011110110100111 110100101110011101001011100010|000101001011000011000101111111 101110110100011100000001101010|000100101110101111101000100011 001001011101101010101100100110|110000000010101010011111010000 100011101010111010110110100011|010100010100101101100011011000 000000100110100110010001111001|001101010110100100011001111111 ------------------------------------------------------------ 010100101010110101110001001110|010100101010110101110001001110 000000111111100011011101010110|000000111111100011011101010110 111010110011100000000001000101|111010110011100000000001000101 011000101001010001100000101110|011000101001010001100000101110 000110010111011111010001011010|000110010111011111010001011010 110011100010100101100100100000|110011100010100101100100100000 111001011110010111110101010110|111001011110010111110101010110 100100001001011000111001111001|100100001001011000111001111001 100000110101010101101101011010|100000110101010101101101011010 110011010011110111111001011000|110011010011110111111001011000
Recovering the $H_v$ space
We see that the very bottom part has two equal halves augmented. But the medium part is still not recovered. The top separator above just shows how large it should be.
We can recover this missing part by considering the difference between the two halves. This exploits the fact that we know the correct column positions (up to swaps)! The difference must be zero in the lower part:
In [14]:
H2diff = H2[:,:n//2]+H2[:,n//2:]
print_mat("H2 diff", H2diff, [kv, n//2-len(cols[0])], [])
H2 diff : 100101101001100001110101100110 100110001101110010111101100100 100101011111000000100001010011 010101101011111100100111010000 011010101110001111101111001010 100100001001101011011001100111 001001101100101011010011000000 110100101111011100101101101111 110000110111000101100010100000 000110011111111001001111101111 ------------------------------ 110111001011001111100101101101 001000111001100111011001001000 000011100000100011011100001011 110010110000111011110100011111 011011111000111010000001100001 110001100101011110001110011101 101010011010110011101001001001 111001011111000000110011110110 110111111110010111010101111011 001101110000000010001000000110 ------------------------------ 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000
It is left to find the kernel of the top part and put it in the middle:
In [15]:
# Q2 exhibits the H_v space at the bottom
Q2 = row_echelon_transformation(H2diff)
assert Q2.is_invertible()
H3 = Q2 * H2
print_mat("Q2 * H2diff", Q2 * H2diff, [kv], [n//2])
print_mat("H3 = Q2 * H2", H3, [kv], [n//2])
Q2 * H2diff : 100101101001100001110101100110| 100110001101110010111101100100| 100101011111000000100001010011| 010101101011111100100111010000| 011010101110001111101111001010| 100100001001101011011001100111| 001001101100101011010011000000| 110000110111000101100010100000| 001000111001100111011001001000| 000011100000100011011100001011| ------------------------------ 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| 000000000000000000000000000000| H3 = Q2 * H2 : 001100110000111110111011101110|101001011001011111001110001000 001100011110000100111110111101|101010010011110110000011011001 011001011100011000000110110101|111100000011011000100111100110 010110111100000011011011110101|000011010111111111111100100101 100000101111001011110110000001|111010000001000100011001001011 101110011110111100000101111010|001010010111010111011100011101 011111000001100011101010110011|010110101101001000111001110011 011110111111100111001101001000|101110001000100010101111101000 101010011110111100111110100010|100010100111011011100111101010 010100010101100100111111010101|010111110101000111100011011110 ------------------------------------------------------------ 010001000100010010100100001001|010001000100010010100100001001 111100101011000101111000000101|111100101011000101111000000101 100111110011111110010000110101|100111110011111110010000110101 100001000001001001011001011011|100001000001001001011001011011 000111001001111011100011000101|000111001001111011100011000101 000011110100101001110011011010|000011110100101001110011011010 000010010001111101101111110101|000010010001111101101111110101 110111011001111110001101111000|110111011001111110001101111000 101011011101111111101000100011|101011011101111111101000100011 001011110010110110100101110011|001011110010110110100101110011 010100101010110101110001001110|010100101010110101110001001110 000000111111100011011101010110|000000111111100011011101010110 111010110011100000000001000101|111010110011100000000001000101 011000101001010001100000101110|011000101001010001100000101110 000110010111011111010001011010|000110010111011111010001011010 110011100010100101100100100000|110011100010100101100100100000 111001011110010111110101010110|111001011110010111110101010110 100100001001011000111001111001|100100001001011000111001111001 100000110101010101101101011010|100000110101010101101101011010 110011010011110111111001011000|110011010011110111111001011000
We can now clearly see the two large bottom halves being equal!
Final part
How can we now recover the top part? It seems like an easy linear algebra should do it.. The problem is that we have recovered the positions of columns up to a swap between left/right halves. Thus, the correct mapping that adds bottom rows towards upper rows would clear up a bunch of columns in the top-left submatrix and the complementary bunch of columns in the top-right submatrix. But we don't know which columns...
Luckily, the challenge does not require full trapdoor recovery: the current structure is enough for applying the trapdoor decoding method. In other words, it is not a problem that the top-right part is not zero: the most important part is to have two equal submatrices of the right size at the bottom.
Solution code
In [16]:
from hashlib import shake_256
n, kv, ku = 4800, 916, 1484
msg = b"gimme the flag!"
s = shake_256(msg).digest(n//16)
target = vector(GF(2), list(map(int, bin(int.from_bytes(s, 'big'))[2:].zfill(n//2))))
print(*target, sep="")
100111001000000100111011010101111100010110000001100111010000111100101100000001011011111110011010001010100110100010101001010000001101001101100111101111001000011111110000100011111001100011100011111100100100001110101110001000001111110100111111011000100100000101010001010000001001010111110101110101100010100001001110110011101010111100101000011010110111111101110010110011011101000111100111101011111111111111000111011000101000110010101001100111100011101000100111011010010101101111011001001001001110100100011000011100010010001101101101111000110010011100010101001111101011100011010000010011110101011000001110000111110000010101100001101000000010101000001100101101011100010101101011100000100010111100111110100011001101111001101010111101011110011011111100100001010010000011101001101010001110010101101101110110101000111110101101111001000010110110011011111001100000001011100000110101000010101110111101101011011011101011010000110110000100111000101111011000101000001001111010011101111101111111111101010100000101011100101001101000110001010110010111001110100110011010101110111111000000010100111001110000001011010101100001000000111011011001101101000000011001101100011011001101101010111100000010000010000101000101111001000101010010100011100011110011000101101110111011011111010010101101111000100111101011000000100000110100111100010000011100001111110000011101000000001000010111101011010101000000000000000011001100101100010011001000111011100010011001111010000010101000001011111011111100010111111001010110000100000010101101100111000011110111110001111010010011000111100111000110000100111110100111011110110110111111100011110110010100000111001000111001000011001111000010111011101101101111101000011100011011000001010010011000111111011110010100000000011000110111001001010011100010110001011010000000011010000011110000111010110010100011010110111111000011110100010101101011101011100100111001010010001000101110000001000101001110001010001101011011101010000010010100011011001100001101010011010110100101000010110100111100101010010010010001101110100110010101010101111000101101010001001001110100100111111010110100010001010100001000011101000100111011001001010001100000000110011010010000001101011110111011000000100110100110111101011011101101000101111111101001011111100011000000001111101101000100000001011011100110101000101101010000001000101000111000000100100111111101001111110001010000011100000110000101101111100111010011001101110011110111
In [None]:
if 0:
# local test
Hu = random_matrix(GF(2), n//2 - ku, n//2, implementation = "m4ri")
Hv = random_matrix(GF(2), n//2 - kv, n//2, implementation = "m4ri")
Hs = block_matrix(GF(2), [
[Hu, 0], # 916
[Hv, Hv] # 1484
])
while (S := random_matrix(GF(2), n//2, n//2, implementation = "m4ri")):
if S.is_invertible():
break
perm = list(range(n))
random.shuffle(perm)
P = Matrix(GF(2), [[1 if i == perm[j] else 0 for j in range(n)] for i in range(n)], implementation = "m4ri")
Hpub = S * Hs * P
In [30]:
# remote
from sock import Sock
f = Sock("summertime.chal.idek.team 1337", timeout=10000)
f.read_until("choice: ")
f.send_line("pkey")
Hpub = loads(bytes.fromhex(f.read_line().decode().strip()))
Hpub
Out [30]:
2400 x 4800 dense matrix over Finite Field of size 2
In [31]:
Ipub = inner_product_form(Hpub)
Ipub_ker = Ipub.left_kernel().matrix()
PERM = group_column_pairs(Ipub_ker * Hpub)
Q1 = row_echelon_transformation(Ipub)
Hcols = Hpub.transpose().rows()
H2 = Q1 * matrix(GF(2), [Hcols[i] for i in PERM]).transpose()
In [32]:
H2diff = H2[:,:n//2] + H2[:,n//2:]
Q2 = row_echelon_transformation(H2diff)
H3 = Q2 * H2
In [33]:
assert Q2.is_invertible()
In [34]:
tar = Q2 * (Q1 * target)
target_u = vector(tar[:kv])
target_v = vector(tar[kv:])
print("h_u = ", *target_u, sep="")
print()
print("h_v = ", *target_v, sep="")
h_u = 1001110010000001001110110101011111000101100000011001110100001111001011000000010110111111100110100010101001101000101010010100000011010011011001111011110010000111111100001000111110011000111000111111001001000011101011100010000011111101001111110110001001000001010100010100000010010101111101011101011000101000010011101100111010101111001010000110101101111111011100101100110111010001111001111010111111111111110001110110001010001100101010011001111000111010001001110110100101011011110110010010010011101001000110000111000100100011011011011110001100100111000101010011111010111000110100000100111101010110000011100001111100000101011000011010000000101010000011001011010111000101011010111000001000101111001111101000110011011110011010101111010111100110111111001000010100100000111010011010100011100101011011011101101010001111101011011110010000101101100110111110011000000010111000001101010000101011101111011010110110111010110100001101 h_v = 01000000100110001010101100000111011011100110000100101001100100100000100100101001010101100111010001100000010001111010010101110001101111000111011111110011001001000000011010100110011110010111001111101011110010110010010010101001010111001000101011001101010010101011001110011111010001011010110100101101101100001001001001001000110010111110101100111110111011010011100010101101010011101001100000000011010001111011100111101100111110001001010000011011010111101000010010010011110100110000010011111001011010101000011100011110100111000011010011011101111110000011101100111111111001101111001111010100100001100001001111100000001000010011101111000101110000001100000101101110110011000100001111100110111111101010000100110011001001001000001101100011000100100011101110111010110101011110111101011010111100011111000000111110011011000011000111010101000101101010100100111100011101101101101110000011110111101100000000100101110100000011011000100110110001111110110101001000000111000010111000101000101111000100001000111011010101001100101110011100010010001111101110010101001001011000110110110001000110000101110001100011110001011001111001011110111100111101100001011010001110111010010000010111011111001011001111010100011011100101011011100100000110010000111001101111010101000011000110101000010101011110011100011010100011101001000101100000100111101000100100110111010111011110010001000101000111000111110111100011101010010101110111101010011000010010000101101011110011010000111001000001010111011001101110011010100001010001
Decoding $h_v$
Make the identity part. Choose pivots to ensure its invertible.
In [35]:
A = H3[kv:,:n//2]
pivots = A.pivots()
npivots = [i for i in range(A.ncols()) if i not in pivots]
Q = ~A[:,pivots]
AA = Q * A
Q_target_v = Q*target_v
In [36]:
def decode_A(AA, Q_target_v):
"""Decode Q_target_v as a sum of kv cols from AA.
Adaptively adds/removes extra columns to match the target weight.
"""
cur = Q_target_v
AAcols = AA.transpose().rows()
cur_inds = set()
while True:
assert sum(AAcols[i] for i in cur_inds) == cur + Q_target_v
if cur.hamming_weight() + len(cur_inds) < kv:
while True:
i = choice(npivots)
if i not in cur_inds:
cur_inds.add(i)
cur += AAcols[i]
break
elif cur.hamming_weight() + len(cur_inds) > kv:
i = cur_inds.pop()
cur -= AAcols[i]
else:
break
cur_inds = sorted(list(cur_inds) + [pivots[i] for i in cur.support()])
assert sum(AAcols[i] for i in cur_inds) == Q_target_v
return cur_inds
In [37]:
H3cols = H3.transpose().rows()
Just test:
In [38]:
cur_inds = decode_A(AA, Q_target_v)
Acols = A.transpose().rows()
AAcols = AA.transpose().rows()
assert sum(AAcols[i] for i in cur_inds) == Q_target_v
assert sum(Acols[i] for i in cur_inds) == target_v
assert sum(H3cols[i] for i in cur_inds)[kv:] == target_v
Extending to the full length
Now in a loop we'll sample solutions for the bottom part and try to extend it to the upper part.
In [39]:
while True:
cur_inds = decode_A(AA, Q_target_v)
assert sum(H3cols[i] for i in cur_inds)[kv:] == vector(list(target_v))
B1 = H3[:kv,:n//2]
B2 = H3[:kv,n//2:]
B1cols = B1.transpose().rows()
B2cols = B2.transpose().rows()
cur_inds = sorted(cur_inds)
# the correction term because the submatrix is non-zero
base = sum(B1cols[i] for i in cur_inds)
diffs = [B2cols[i] - B1cols[i] for i in cur_inds]
mat = matrix(diffs)
print(mat.nrows(), mat.ncols(), mat.rank())
try:
sol = mat.solve_left(base + target_u)
except ValueError:
continue
ans = set(cur_inds)
assert len(sol) == len(cur_inds)
for i, flip in enumerate(sol):
if flip:
ans.remove(cur_inds[i])
ans.add(cur_inds[i] + n//2)
ans = sorted(ans)
assert sum(H3cols[i] for i in ans) == vector(list(target_u) + list(target_v))
print("solved!")
break
916 916 915 solved!
It is left to map the solution back to $H_{pub}$ by undoing the column permutation.
In [40]:
ans2 = [PERM[i] for i in ans]
Hcols = Hpub.transpose().rows()
assert sum(Hcols[i] for i in ans2) == target
assert len(set(ans2)) == len(ans2) == kv
In [41]:
e = [0] * n
for i in ans2:
e[i] = 1
e = vector(GF(2), e)
In [42]:
print(f.read_until("choice: "))
f.send_line("verifyverifyverifyverifyverifyverify")
print(f.read_until("msg: "))
f.send_line(msg)
print("my len e", len(e))
print(f.read_until("e: "))
f.send_line(str(e)) #b"[" + b", ".join(b"%d" % i for i in e) + b"]")
print(f.read_one())
b'choice: '
b'msg: '
my len e 4800
b'e: '
b'Valid signature!\nidek{h0p3_y0u_enj0y3d_c0d3s_4nd_th4nks_f0r_pl4y1n6_:-)} \n\n'