Inside The Matrix
7 minutos de lectura
Se nos proporciona el código fuente del servidor en 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}")
Hay otro archivo llamado 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]))
Por último, hay un archivo llamado utils.py, pero no es relevante resolver el reto.
Análisis del cifrado
El servidor utiliza una función personalizada con nombre ascii_print que no está disponible (opción L), pero lo único que hace es imprimir números como si estuvieran dentro de un libro:
$ 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
El hecho de no disponser de esta función no es un problema porque tenemos la opción C, que imprime solo la información relevante:
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]]
Para cifrar información, el servidor usa matrices $5 \times 5$. Sea $F$ la flag en forma de matriz (hay un método llamado parse para eso. Además, la flag contiene exactamente 25 bytes debido a una assert al principio):
def parse(self, pt: bytes):
pt = [b for b in pt]
return Matrix(self.prime, self.size, self.size, pt)
La clave se genera aleatoriamente en cada cifrado:
def generate(self):
key = os.urandom(self.size**2)
return self.parse(key)
Y las operaciones posteriores se realizan módulo un número primo $p$, que es diferente en cada cifrado:
def rotate(self):
self.prime = randprime(2**4, 2**6)
Este número primo satisface que $2^4 < p < 2^6$ (véase la documentación de randprime de sympy para más información). Por lo tanto, solo hay unos pocos números primos posibles:
$ 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}
La forma de cifrar es la siguiente:
def encrypt(self, message: bytes):
self.rotate()
key = self.generate()
message = self.parse(message)
ciphertext = message * key
return ciphertext, key.M
Entonces, en términos matemáticos:
$$ C = F \cdot K \mod{p} $$
Donde están todas las matrices $5 \times 5$.
Descifrado
Observe que se nos proporcionan $C$ y $K$ como listas. Por lo tanto, podemos encontrar $F$ multiplicando $C$ por la inversa de $K$:
$$ F = C \cdot K^{-1} \mod{p} $$
Hay que tener en cuenta que no sabemos el número primo $p$, pero es fácil de detectar ya que solo hay unos pocos primos posibles y todas las entradas de matriz serán menores de $p$. Por ejemplo, en las listas anteriores, es probable que el número primo $p$ sea $61$, ya que la entrada más grande es $59$:
[[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]]
Una vez que tenemos $p$, podemos encontrar $F$ como se dijo anteriormente. Sin embargo, esa matriz $F$ será en módulo $p$, y los caracteres de la flag son ASCII (8 bits, así que módulo $256$).
Pero obsérvese que el servidor siempre está cifrando la misma flag, aunque usa diferentes claves y módulos. Pero esto es perfecto para aplicar el Teorema Chino del Resto (CRT). Teniendo en cuenta solo un carácter ($c_1$), podemos construir un sistema de congruencias de la siguiente manera:
$$ \begin{cases} c_1 \equiv f_1 \pmod{p_1} \newline c_1 \equiv f_2 \pmod{p_2} \newline \end{cases} $$
Donde $f_1$ y $f_2$ son los residuos módulo $p_1$ y $p_2$ respectivamente de la entrada superior izquierda de matriz $F$ (en dos cifrados diferentes).
El CRT establece que si $p_i$ son coprimos (que lo son, porque todos los $p_i$ son números primos), entonces el sistema de congruencias tiene una solución $\mod{\prod p_i}$. Dos pares de muestras son suficientes porque todos los $p_i > 2^4$, por lo que $p_i \cdot p_j > 2^4 \cdot 2^4 = 256$. Por lo tanto, la solución $c_1$ del CRT será exactamente el valor ASCII de $c_1$.
Implementación en SageMath
Entonces, tomaremos dos pares de textos y claves de cifrado para aplicar la teoría anterior:
$ 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]]
Está bien. Mirando los números, parece que $p_1 = 59$ y $p_2 = 37$. Entonces, debemos encontrar $f_1$ y $f_2$:
$ 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]
Ahora es momento de aplicar el CRT a cada par de entradas de las 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
Y aquí esta la flag:
sage: bytes(flag)
b'HTB{0ut_0f____th3_m4trix}'