Inside The Matrix
7 minutos de lectura
Se nos proporciona el código fuente del servidor en 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}")
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 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
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
[(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)]
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(GF(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 = random_prime(2**6, False, 2**4)
Este número primo satisface que $2^4 < p < 2^6$ (véase la documentación de random_number de SageMath para más información). Por lo tanto, solo hay unos pocos números primos posibles:
$ 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}
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
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 $37$, ya que la entrada más grande es $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)]
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 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)]
Está bien. Mirando los números, parece que $p_1 = 59$ y $p_2 = 23$. Entonces, debemos encontrar $f_1$ y $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]
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{l00k_@t_7h3_st4rs!!!}'