nc 18.179.178.246 3002
(This was all of the description)
Overview
From the organizer’s write-up(Link):
FiniteGeneralLinearGroup
is just a matrix class over a finite field.
We can encrypt and decrypt arbitrary messages.
Encryption is defined as: Y = UXU^{-1}.
Decryption is defined as: X = U^{-1}YU.
The size of matrix (from the server) is 6×6.
How to solve
You cannot decrypt the flag directly, because it only accepts the matrix with values in the range 0~255.
Let’s think about (i, j)-th entry of the UXU^{-1}.
(UXU^{-1})_{i, j} = \sum_{i' = 1}^6 \sum_{j'=1}^6 U_{i, i'} X_{i', j'} U^{-1}_{j', j}
If you send the matrix X which has 1 in the (i, j)-th entry and 0 in the others, you can get U_{k, i} U^{-1}_{j, l} values for every (k, l).
Notice that (UXU^{-1})_{i, j} is a linear combination of X_{i', j'} and U_{i, i'} U^{-1}_{j', j}. Because we now know U_{i, i'} U^{-1}_{j', j} values, we can construct the linear system with 36 variables and 36 equations. We can solve the system with sage.
Here’s the extractor code for getting U_{i, i'} U^{-1}_{j', j} values.
from pwn import * import base64 f = open('data', 'w') r = remote('13.231.224.102', 3002) r.recvuntil('Encrypted Flag:\n') eF = r.recvuntil('p = ')[:-5] p = r.recvuntil('=')[:-1] eF = eF.replace('\n', ',') + '\n' f.write(p + eF) for i in range(36): target = b'\x00' * i + b'\x01' + b'\x00' * (35 - i) target = base64.b64encode(target) r.sendline('1') r.sendline(target) r.recvuntil('Encrypted:\n') v = r.recvuntil('=')[:-2] v = v.replace('\n', ',') + '\n' f.write(v) f.close()
Here’s the sage solver for the linear system.
from itertools import product as iproduct # [i][j][i_][j_] = U[i][j] * U**-1[i_][j_] UUm1_coef = [ [ [ [None for i in range(6)] for j in range(6) ] for k in range(6) ] for l in range(6) ] with open('data', 'r') as f: p = int(f.readline()[:-1]) eF = eval(f.readline()[:-1]) for i, j in iproduct(range(6), repeat=2): mat = eval(f.readline()[:-1]) for i_, j_ in iproduct(range(6), repeat=2): UUm1_coef[i_][i][j][j_] = mat[i_][j_] mat = [ [0 for i in range(36)] for j in range(36) ] vec = [ eF[i // 6][i % 6] for i in range(36) ] for i, j, i_, j_ in iproduct(range(6), repeat=4): mat[i * 6 + j][i_ * 6 + j_] += UUm1_coef[i][i_][j_][j] mat[i * 6 + j][i_ * 6 + j_] %= p R = IntegerModRing(p) M = Matrix(R, mat) b = vector(R, vec) ans = M.solve_right(b) flag = '' for i in range(36): flag += chr(ans[i]) print(flag)
The flag is zer0pts{r1ng_h0m0m0rph1sm_1s_c00l}
.
답글 남기기