Inside The Matrix
7 minutes to read
We are given the source code of the server in Python:
from sage.all_cmdline import *
# from utils import ascii_print
import os
FLAG = b"HTB{????????????????????}"
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(GF(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 = random_prime(2**6, False, 2**4)
def encrypt(self, message: bytes):
self.rotate()
key = self.generate()
message = self.parse(message)
ciphertext = message * key
return ciphertext, key
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)
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}")
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 159.65.81.51 31917
Options:
[L]ook at page
[T]urn page
[C]heat
> L
_________ _________
______/ 1\ / 2 \_______
/| --------------- | --------------- |\
|| Ciphertext:--- - | Key:------------ |||
|| ---------------- | ------ -------- |||
|| ---------- ----- | ---------------- |||
|| [17,35,24,15,25] | [20,5,29,1,24]-- |||
|| [5,12,6,9,35]--- | [19,0,31,18,35]- |||
|| [36,6,20,2,2]--- | [31,35,2,1,24]-- |||
|| [29,11,10,31,16] | [10,24,2,0,13]-- |||
|| [36,6,29,10,20]- | [14,0,17,27,31]- |||
|| ---------------- | ------ ----- --- |||
|| --- - ---------- | ---------------- |||
||______________ _ | ________________|||
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
[(17, 35, 24, 15, 25), (5, 12, 6, 9, 35), (36, 6, 20, 2, 2), (29, 11, 10, 31, 16), (36, 6, 29, 10, 20)]
[(20, 5, 29, 1, 24), (19, 0, 31, 18, 35), (31, 35, 2, 1, 24), (10, 24, 2, 0, 13), (14, 0, 17, 27, 31)]
To encrypt information, the server uses $5 \times 5$ matrices. Let $F$ be the flag in matrix form (there’s a method called 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(GF(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 $p$, which is different on each encryption:
def rotate(self):
self.prime = random_prime(2**6, False, 2**4)
This prime number satisfies $2^4 < p < 2^6$ (see random_number documentation in SageMath for more information). Therefore, there are only a few possible prime numbers:
$ sage -q
sage: { random_prime(2 ** 6, False, 2 ** 4) for _ in range(100) }
{17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61}
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
So, in mathematical terms:
$$ C = F \cdot K \mod{p} $$
Where all matrices are $5 \times 5$.
Decryption
Notice that we are given both $C$ and $K$ as lists. Therefore, we can find $F$ multiplying $C$ by the inverse of $K$:
$$ F = C \cdot K^{-1} \mod{p} $$
Notice that we don’t know the prime number $p$, but it is easy to spot since there are only a few possible primes and all matrix entries will be less than $p$. For instance, in the above lists, the prime number $p$ is likely to be $37$, since the biggest entries are $35$:
[(17, 35, 24, 15, 25), (5, 12, 6, 9, 35), (36, 6, 20, 2, 2), (29, 11, 10, 31, 16), (36, 6, 29, 10, 20)]
[(20, 5, 29, 1, 24), (19, 0, 31, 18, 35), (31, 35, 2, 1, 24), (10, 24, 2, 0, 13), (14, 0, 17, 27, 31)]
Once we have $p$, we can find $F$ as told above. However, that matrix $F$ will be modulo $p$, and the flag characters are ASCII (8 bits, so modulo $256$).
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 ($c_1$), we can build a system of congruences as follows:
$$ \begin{cases} c_1 \equiv f_1 \pmod{p_1} \newline c_1 \equiv f_2 \pmod{p_2} \newline \end{cases} $$
Where $f_1$ and $f_2$ are the residues modulo $p_1$ and $p_2$ respectively of the top-left entry of matrix $F$ (in two different encryptions).
The CRT states that if $p_i$ are coprime (which are, because all $p_i$ are prime numbers), then the system of congruences has a solution $\mod{\prod p_i}$. Two pairs of samples is enough because all $p_i > 2^4$, so $p_i \cdot p_j > 2^4 \cdot 2^4 = 256$. Therefore, the solution $c_1$ of the CRT will be exactly the ASCII value of $c_1$.
SageMath implementation
So, let’s take two pairs of ciphertexts and keys to apply the above theory:
$ nc 159.65.81.51 31917
Options:
[L]ook at page
[T]urn page
[C]heat
> C
[(17, 37, 13, 25, 54), (37, 52, 50, 24, 52), (38, 32, 37, 40, 12), (45, 30, 52, 14, 34), (14, 42, 48, 21, 37)]
[(17, 0, 4, 31, 33), (54, 19, 49, 24, 54), (4, 17, 45, 30, 16), (21, 9, 54, 34, 46), (33, 13, 2, 6, 12)]
Options:
[L]ook at page
[T]urn page
[C]heat
> T
Options:
[L]ook at page
[T]urn page
[C]heat
> C
[(13, 13, 9, 9, 18), (12, 22, 15, 13, 9), (18, 9, 6, 13, 19), (21, 19, 17, 4, 19), (22, 7, 9, 5, 19)]
[(17, 6, 6, 15, 19), (2, 5, 4, 22, 6), (5, 11, 13, 5, 20), (16, 0, 21, 11, 7), (16, 10, 2, 20, 8)]
Alright. Looking at the numbers, it looks like $p_1 = 59$ and $p_2 = 23$. Then, we must find $F_1$ and $F_2$:
$ sage -q
sage: p1 = 59
sage: p2 = 23
sage:
sage: C1 = matrix(GF(p1), [(17, 37, 13, 25, 54), (37, 52, 50, 24, 52), (38, 32, 37, 40, 12), (45, 30, 52, 14, 34), (14, 42, 48, 21, 37)])
sage: K1 = matrix(GF(p1), [(17, 0, 4, 31, 33), (54, 19, 49, 24, 54), (4, 17, 45, 30, 16), (21, 9, 54, 34, 46), (33, 13, 2, 6, 12)])
sage:
sage: C2 = matrix(GF(p2), [(13, 13, 9, 9, 18), (12, 22, 15, 13, 9), (18, 9, 6, 13, 19), (21, 19, 17, 4, 19), (22, 7, 9, 5, 19)])
sage: K2 = matrix(GF(p2), [(17, 6, 6, 15, 19), (2, 5, 4, 22, 6), (5, 11, 13, 5, 20), (16, 0, 21, 11, 7), (16, 10, 2, 20, 8)])
sage:
sage: F1 = C1 * K1.inverse()
sage: F2 = C2 * K2.inverse()
sage:
sage: F1
[13 25 7 5 49]
[48 48 48 36 5]
[57 36 55 45 51]
[36 56 57 52 55]
[56 33 33 33 7]
sage: F2
[ 3 15 20 8 16]
[ 2 2 15 3 18]
[ 1 3 9 12 5]
[ 3 0 1 6 22]
[ 0 10 10 10 10]
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{l00k_@t_7h3_st4rs!!!}'