affine.group home writeups about

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'

Site version #161 from 2024-12-30 10:53:25 (CET)