[zer0pts CTF 2020] nibelung

tags: zer0pts CTF crypto

Overview

The server gives us the randomly encrypted flag.

    # Create flag F
    n = math.ceil(math.sqrt(len(flag)))
    F = bytes2gl(flag, n)
    p = F.p
    
    # Generate private key
    U = FiniteGeneralLinearGroup(n, p)
    while U.determinant() == 0:
        U.set_random()

    eF = encrypt(U, F)
    assert decrypt(U, eF) == F

FiniteGeneralLinearGroup is just a matrix class over a finite field.

We can encrypt and decrypt arbitrary messages.
Encryption is defined as below:

$$Y=UX{U}^{-1}$$

Dectyption is defined as below:

$$X=U^{-1}YU$$

You can immediately understand it works because

$$DEC(ENC(X))=U^{-1}(UX{U}^{-1})U=X$$

and vice versa.

Solution

So, you just need to put the encrypted flag to the decrypt function?
No.

We can set an element of the matrix to a value between between 0 and 255.

$$E=UF{U}^{-1}$$

The easy (to come up with) way is making E sum of small matrices.

Let

$N_{i,j}$ denote a matrix whose

$(i,j)$ elements are 0 for

$i\ne j$ and 1 for

$i=j$.
Then,

$E$ can be expressed like this:

$$E=e_{1,1}{N}_{1,1}+e_{1,2}{N}_{1,2}+...+e_{n,n}{N}_{n,n}$$

$DEC(E)$ is

$$\begin{array}{rl}DEC(E)& =U^{-1}(e_{1,1}{N}_{1,1}+e_{1,2}{N}_{1,2}+...+e_{n,n}{N}_{n,n})U\\ & =e_{1,1}DEC(N_{1,1})+e_{1,2}DEC(N_{1,2})+...+e_{n,n}DEC(N_{n,n})\end{array}$$

from ptrlib import *
from fglg import FiniteGeneralLinearGroup as Matrix
import re
import base64
import math
import pickle
import sys

def encrypt(data, p):
    sock.sendlineafter("> ", "1")
    sock.sendlineafter("Data: ", base64.b64encode(data))
    return recv_gl(p)

def decrypt(data, p):
    sock.sendlineafter("> ", "2")
    sock.sendlineafter("Data: ", base64.b64encode(data))
    return recv_gl(p)

def recv_gl(p = None):
    sock.recvline()
    mat = []
    for i in range(n):
        mat.append([])
        r = re.findall(b"\d+", sock.recvline())
        for elm in r:
            mat[-1].append(int(elm))
    if p is None:
        return mat
    X = Matrix(n, p)
    for i in range(n):
        for j in range(n):
            X.set_at((j, i), mat[i][j])
    return X

def split(x, base, result):
    if x < base:
        return x
    # x = base ^ q + r
    q = int(math.log(x) / math.log(base))
    r = x - base ** q
    result.append(q)
    return split(r, base, result)

n = 6

if __name__ == '__main__':
    sock = Socket("13.231.224.102", 3002)
    
    # Get eF and p
    mat = recv_gl()
    sock.recvuntil("p = ")
    p = int(sock.recvline())
    eF = Matrix(n, p)
    for i in range(n):
        for j in range(n):
            eF.set_at((j, i), mat[i][j])

    # Create table
    decN = [[None for j in range(n)] for i in range(n)]
    for i in range(n):
        for j in range(n):
            data = b'\x00' * (n*n)
            data = data[:i*n+j] + b'\x01' + data[i*n+j+1:]
            decN[i][j] = decrypt(data, p)

    F = Matrix(n, p)
    for i in range(n):
        for j in range(n):
            F += decN[i][j] * eF.get_at((j, i))
    print(F)

    flag = ''
    for i in range(n):
        for j in range(n):
            flag += chr(F.get_at((j, i)))

    print(flag)