Modular matrices - HarekazeCTF 2019

In this blogpost I will be writing about modular matrices, a topic I came across while doing one of the crypto challenges from HarekazeCTF 2019!

Some background math

A modular matrix is simply a matrix in which each cell is under the modulo operator. For instance, here are two matrices that are congruent:

\begin{align} \begin{pmatrix} 1 & 8 \
15 & 9 \
\end{pmatrix} \equiv \begin{pmatrix} 1 & 0 \
3 & 1 \
\end{pmatrix} \pmod{4} \end{align}

Now, modular matrices hold some properties. Whereas matrices in classic arithmetic can be multiplied with this formula:

\begin{align} C_{ij} = \sum_{k=0}^n A_{ik}B_{kj} \end{align}

In modular arithmetic we need to take the modulo of each term in the summation:

\begin{align} C_{ij} = \sum_{k=0}^n [A_{ik}B_{kj} \pmod{x}] \end{align}

The challenge

We are given two files in the challenge:

• problem.py:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#!/usr/bin/python3
import random
import binascii
import re
from keys import flag

flag = re.findall(r'HarekazeCTF{(.+)}', flag)[0]
flag = flag.encode()
#print(flag)

def pad25(s):
    if len(s) % 25 == 0:
        return b''
    return b'\x25'*(25 - len(s) % 25)

def kinoko(text):
    text = text + pad25(text)
    mat = []
    for i in range(0, len(text), 25):
        mat.append([
            [text[i], text[i+1], text[i+2], text[i+3], text[i+4]],
            [text[i+5], text[i+6], text[i+7], text[i+8], text[i+9]],
            [text[i+10], text[i+11], text[i+12], text[i+13], text[i+14]],
            [text[i+15], text[i+16], text[i+17], text[i+18], text[i+19]],
            [text[i+20], text[i+21], text[i+22], text[i+23], text[i+24]],
            ])
    return mat

def takenoko(X, Y):
    W = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
    for i in range(5):
        for j in range(5):
            for k in range(5):
              W[i][j] = (W[i][j] + X[i][k] * Y[k][j]) % 251

    return W

def encrypt(m1, m2):
    c = b""
    for each in m1:
        g = random.randint(0,1)
        if g == 0:
            mk = takenoko(m2, each)
        else:
            mk = takenoko(each, m2)
        for k in mk:
            c += bytes(k)

    return c


if __name__ == '__main__':
    m1 = kinoko(flag)
    m2 = [[1,3,2,9,4], [0,2,7,8,4], [3,4,1,9,4], [6,5,3,-1,4], [1,4,5,3,5]]


    print("Encrypted Flag:")
    enc_flag = binascii.hexlify(encrypt(m1, m2)).decode()
    print(enc_flag)

• result.txt:

1
2

Encrypted Flag:
ea5929e97ef77806bb43ec303f304673de19f7e68eddc347f3373ee4c0b662bc37764f74cbb8bb9219e7b5dbc59ca4a42018

Analysis of the Python script

In order to solve the challenge I started by inspecting the script, identifying what each function did:

• pad25(s): returns a string comprised of as many \x25’s as characters needs the s argument to have a length that is a multiple of 25.

• kinoko(text): pads a the text argument to a multiple of 25 and then splits it into lists of 25 characters, which returns in a list themselves.

• takenoko(X, Y): here comes the (tricky) part of the challenge, recognising that this function performs a modular multiplication of the argument matrices.

• encrypt(m1, m2): calls the takenoko function to perform the multiplication on each of the one dimensional matrices of m1. Another tricky part is that it randomly chooses whether to do \(A \cdot B\) or \(B \cdot A\). We need to keep in mind that matrix multiplication is not commutative in most of the cases (hint: this is not one), and hence \(A \cdot B \neq B \cdot A\). Finally, it returns the concatenation of the bytes resulting from each of the multiplications.

Objective of the challenge

Given the functions, we only need to take a look at the main part of the script to realise what we need to do:

1
2
3
4
5
6
7
8

if __name__ == '__main__':
    m1 = kinoko(flag)
    m2 = [[1,3,2,9,4], [0,2,7,8,4], [3,4,1,9,4], [6,5,3,-1,4], [1,4,5,3,5]]


    print("Encrypted Flag:")
    enc_flag = binascii.hexlify(encrypt(m1, m2)).decode()
    print(enc_flag)

m1 and m2 are both matrices and encrypt(m1, m2) is the concatenation of the bytes contained in a matrix, let’s call it m3, that is the modular multiplication of m1 and m2. Therefore, what we need to do is, given m2 and m3, obtain m1. i.e: obtain \(A\) from \(A \cdot B = C\) given \(B\) and \(C\).

Back to math

Having \(A \cdot B = C\) and given \(B\), \(C\), it is possible to recover \(A\) if \(B\) is invertible: \(C \cdot B^{-1} = A\), where \(B^{-1}\) is the inverse matrix of \(B\).

In classic arithmetic, the inverse matrix \(B^{-1}\) of \(B\) can be obtained the following way:

\begin{align} B^{-1} = \frac{1}{det(B)} \cdot \left(B^{*}\right)^{t} \end{align}

where

        \(det(B)\) is the determinant of \(B\)
        \(B^{*}\) is the adjoint matrix of \(B\)
        \(\left(B^{*}\right)^{t}\) is the traspose of the adjoint matrix

However, in modular arithmetic things are a bit different. Let’s say we want to find the inverse matrix of \(B \pmod{x}\). We need to follow a series of steps:

• First we need to find \(det(B)\). If \(det(B)\) is coprime to \(x\), then \(B\) is invertible modulo \(x\). This is necessary, since only coprime numbers to \(x\) will have a modular inverse modulo \(x\).

• Next, we need to find the modular inverse of \(det(B)\pmod{x}\), which we will denote as \((det(B))^{-1}\). Recall that this number satisfies that \(det(B)\cdot(det(B))^{-1} \equiv 1 \pmod{x}\).

• Then, we calculate the traspose of the adjoint matrix, which is calculated normally. We will name it as before, \(\left(B^{*}\right)^{t}\).

• Finally, the matrix obtained from \((det(B))^{-1}\cdot\left(B^{*}\right)^{t}\) is the inverse of \(B \pmod{x}\). Lastly, we take the modulo of each cell in order to ensure that the integers range from \(0\) to \(x\).

Solution of the challenge

Now we just need to put this into code to solve the challenge and retrieve the challenge, easy right? (It wasn’t)

First thing I did was put back the result of the multiplications, which was encoded as hex, into the original format:

1
2
3
4
5
6
7
8
9
10
11

encrypted = "ea5929e97ef77806bb43ec303f304673de19f7e68eddc347f3373ee4c0b662bc37764f74cbb8bb9219e7b5dbc59ca4a42018"

text = binascii.unhexlify(encrypted)

m3 = []

for i in range(0, len(text), 25):
    submat = []
    for x in range(0, 25, 5):
        submat.append([ord(text[i+x]), ord(text[i+x+1]), ord(text[i+x+2]), ord(text[i+x+3]), ord(text[i+x+4])])
    m3.append(submat)

Then, using numpy to make things easier I calculated the inverse of m2. I needed to use int() to get rid of floating point residues when getting the determinant and also multiply by the determinant, given that np.linalg.inv(m2) divides the traspose by it:

1
2

det = int(np.linalg.det(m2))
Bprime = (np.linalg.inv(m2) * det * modinv(det, 251)) % 251

After that, we need to guess the order of the multiplication. This wasn’t difficult and could be done manually, since m3 only had two matrices and so there were 4 possibilities. It turned out to be this one:

1
2

m1_1 = np.dot(m3[0], Bprime)
m1_2 = np.dot(m3[1], Bprime)

Finally, we extract the numbers from the matrices taking modulo 251 and join them in a string to get the flag. It was necessary to use the round function, as int() rounds down the numbers (1.9 should be 2 and not 1).

1
2
3
4
5
6
7
8
9
10

s = ""

for i in m1_1:
    print i
    for x in i:
        s += chr(int(round(x)) % 251)

for i in m1_2:
    for x in i:
        s += chr(int(round(x)) % 251)

Flag: Op3n_y0ur_3y3s_1ook_up_t0_th3_ski3s_4nd_s33.

Here is the whole script in case you are interested: full solution.

I hope this article was useful, see you next time!