Inside The Matrix
7 minutes to read
We are given the source code of the server in Python:
from utils import ascii_print
import os
from secret import FLAG
from Crypto.Util.number import getPrime
from matrix import Matrix
from sympy import randprime
assert len(FLAG) == 25
class Book:
def __init__(self):
self.size = 5
self.prime = None
def parse(self, pt: bytes):
pt = [b for b in pt]
return Matrix(self.prime, self.size, self.size, pt)
def generate(self):
key = os.urandom(self.size**2)
return self.parse(key)
def rotate(self):
self.prime = randprime(2**4, 2**6)
def encrypt(self, message: bytes):
self.rotate()
key = self.generate()
message = self.parse(message)
ciphertext = message * key
return ciphertext, key.M
def menu():
print("Options:\n")
print("[L]ook at page")
print("[T]urn page")
print("[C]heat\n")
option = input("> ")
return option
def main():
book = Book()
ciphertext, key = book.encrypt(FLAG)
page_number = 1
while True:
option = menu()
if option == "L":
ascii_print(ciphertext, key, page_number)
elif option == "T":
ciphertext, key = book.encrypt(FLAG)
page_number += 2
print()
elif option == "C":
print(f"\n{list(ciphertext)}\n{list(key)}\n")
else:
print("\nInvalid option!\n")
if __name__ == "__main__":
try:
main()
except Exception as e:
print(f"An error occurred: {e}")
There is another file called matrix.py
:
import numpy as np
class Matrix:
def __init__(self, p, rows, cols, m):
self.p = p
self.nrows = rows
self.ncols = cols
self.M = self.unflatten(m).tolist()
def __mul__(self, mat):
return (np.dot(self.M, mat.M) % self.p).tolist()
def unflatten(self, m):
return np.ndarray(shape=(self.nrows, self.ncols), dtype=int, buffer=np.array([i % self.p for i in m]))
Last, there is a file called utils.py
, but it is not relevant to solve the challenge.
Encryption analysis
The server uses a custom function named ascii_print
that is not available (option L
), but the only thing that does is print numbers like if they were inside a book:
$ nc 138.68.153.165 32679
Options:
[L]ook at page
[T]urn page
[C]heat
> L
_________ _________
______/ 1\ / 2 \_______
/| --------------- | --------------- |\
|| Ciphertext:--- - | Key:------------ |||
|| ---------------- | ------ -------- |||
|| ---------- ----- | ---------------- |||
|| [54,27,58,9,13]- | [48,11,2,8,19]-- |||
|| [58,42,27,38,51] | [20,0,46,52,18]- |||
|| [53,55,59,59,2]- | [33,0,9,18,52]-- |||
|| [28,40,21,0,22]- | [58,56,17,18,55] |||
|| [57,49,21,34,36] | [28,35,13,36,43] |||
|| ---------------- | ------ ----- --- |||
|| --- - ---------- | ---------------- |||
||______________ _ | ________________|||
L/______/---------\\_//W--------\_______\J
Not having this function is not a problem because we have option C
, which prints just the relevant information:
Options:
[L]ook at page
[T]urn page
[C]heat
> C
[[54, 27, 58, 9, 13], [58, 42, 27, 38, 51], [53, 55, 59, 59, 2], [28, 40, 21, 0, 22], [57, 49, 21, 34, 36]]
[[48, 11, 2, 8, 19], [20, 0, 46, 52, 18], [33, 0, 9, 18, 52], [58, 56, 17, 18, 55], [28, 35, 13, 36, 43]]
To encrypt information, the server uses parse
for that. Also, the flag contains exactly 25 bytes due to an assertion at the beginning):
def parse(self, pt: bytes):
pt = [b for b in pt]
return Matrix(self.prime, self.size, self.size, pt)
The key is generated randomly on each encryption:
def generate(self):
key = os.urandom(self.size**2)
return self.parse(key)
And the subsequent operations are performed modulo a prime number
def rotate(self):
self.prime = randprime(2**4, 2**6)
This prime number satisfies randprime
documentation in sympy
for more information). Therefore, there are only a few possible prime numbers:
$ python3 -q
>>> from sympy import randprime
>>> { randprime(2 ** 4, 2 ** 6) for _ in range(100) }
{37, 41, 43, 47, 17, 29, 19, 53, 23, 59, 61, 31}
The way to encrypt is the following:
def encrypt(self, message: bytes):
self.rotate()
key = self.generate()
message = self.parse(message)
ciphertext = message * key
return ciphertext, key.M
So, in mathematical terms:
Where all matrices are
Decryption
Notice that we are given both
Notice that we don’t know the prime number
[[54, 27, 58, 9, 13], [58, 42, 27, 38, 51], [53, 55, 59, 59, 2], [28, 40, 21, 0, 22], [57, 49, 21, 34, 36]]
[[48, 11, 2, 8, 19], [20, 0, 46, 52, 18], [33, 0, 9, 18, 52], [58, 56, 17, 18, 55], [28, 35, 13, 36, 43]]
Once we have
But notice that the server is always encrypting the same flag, although using different keys and prime moduli. This is perfect to apply the Chinese Remainder Theorem (CRT). Considering only one character (
Where
The CRT states that if
SageMath implementation
So, let’s take two pairs of ciphertexts and keys to apply the above theory:
$ nc 138.68.153.165 32679
Options:
[L]ook at page
[T]urn page
[C]heat
> C
[[17, 8, 6, 5, 3], [30, 33, 48, 33, 12], [58, 1, 55, 0, 26], [17, 0, 26, 54, 51], [25, 28, 5, 56, 7]]
[[15, 9, 14, 46, 48], [29, 35, 15, 11, 26], [57, 51, 15, 8, 0], [13, 24, 4, 13, 6], [17, 47, 40, 47, 11]]
Options:
[L]ook at page
[T]urn page
[C]heat
> T
Options:
[L]ook at page
[T]urn page
[C]heat
> C
[[22, 0, 18, 2, 35], [16, 1, 30, 10, 36], [29, 33, 10, 36, 1], [14, 22, 23, 20, 34], [27, 36, 19, 25, 28]]
[[19, 21, 28, 35, 14], [4, 27, 18, 22, 7], [26, 7, 25, 6, 20], [32, 22, 0, 32, 30], [6, 31, 22, 30, 35]]
Alright. Looking at the numbers, it looks like
$ sage -q
sage: p1 = 59
sage: p2 = 37
sage:
sage: C1 = matrix(GF(p1), [[17, 8, 6, 5, 3], [30, 33, 48, 33, 12], [58, 1, 55, 0, 26], [17, 0, 26, 54, 51], [25, 28, 5, 56, 7]])
sage: K1 = matrix(GF(p1), [[15, 9, 14, 46, 48], [29, 35, 15, 11, 26], [57, 51, 15, 8, 0], [13, 24, 4, 13, 6], [17, 47, 40, 47, 11]])
sage:
sage: C2 = matrix(GF(p2), [[22, 0, 18, 2, 35], [16, 1, 30, 10, 36], [29, 33, 10, 36, 1], [14, 22, 23, 20, 34], [27, 36, 19, 25, 28]])
sage: K2 = matrix(GF(p2), [[19, 21, 28, 35, 14], [4, 27, 18, 22, 7], [26, 7, 25, 6, 20], [32, 22, 0, 32, 30], [6, 31, 22, 30, 35]])
sage:
sage: F1 = C1 * K1.inverse()
sage: F2 = C2 * K2.inverse()
sage:
sage: F1
[13 25 7 5 48]
[58 57 36 48 43]
[36 36 36 36 57]
[45 51 36 50 52]
[57 55 46 2 7]
sage: F2
[35 10 29 12 11]
[ 6 5 21 11 28]
[21 21 21 21 5]
[30 14 21 35 15]
[ 5 3 31 9 14]
Now it’s time to apply the CRT to each pair of entries of the matrices:
sage: flag = []
sage:
sage: for r1, r2 in zip(F1.rows(), F2.rows()):
....: for f1, f2 in zip(r1, r2):
....: flag.append(crt([int(f1), int(f2)], [p1, p2]) % 256)
Flag
And here’s the flag:
sage: bytes(flag)
b'HTB{0ut_0f____th3_m4trix}'