Scrambled Pizzeria
6 minutos de lectura
Se nos proporciona el código fuente del servidor en Python:
#!/usr/bin/python3
import numpy as np
import numpy.typing as npt
from PIL import Image
import os
def permutation(
img: npt.NDArray[np.uint8], c: npt.NDArray[np.uint64]
) -> npt.NDArray[np.uint8]:
height, width = img.shape
cm = c[np.arange(max(height, width)) % len(c)]
rows = np.argsort(cm[:height])
cols = np.argsort(cm[:width])
return img[rows, :][:, cols]
def substitution(
con: npt.NDArray[np.uint8], c: npt.NDArray[np.uint64]
) -> npt.NDArray[np.uint8]:
ids = np.arange(np.prod(con.shape)) % len(c)
return con ^ (c % 256).astype(np.uint8)[ids].reshape(con.shape)
def main():
c: npt.NDArray[np.uint64] = np.frombuffer(os.urandom(400 * 8), np.uint64)
print(
"Hi, I'm here to take your order! Can you give me an image of the type of pizza you want me to cook?"
)
height = input("What's the height of the image? ")
width = input("What's the width of the image? ")
img_hex = input("Now send me the image and I'll do the rest!\n")
try:
height = int(height)
width = int(width)
assert height <= 400 and width <= 400
img: npt.NDArray[np.uint8] = np.array(
Image.frombytes("L", (width, height), bytes.fromhex(img_hex))
)
except:
print("Uh oh! You're trying to trick me? Out of my pizzeria!")
exit()
con = permutation(img, c)
enc = substitution(con, c)
print("Oh mamma mia! I've scrambled all of your ingredients, look!")
print(enc.tobytes().hex())
flag_img: npt.NDArray[np.uint8] = np.array(Image.open("flag.jpg").convert("L"))
flag_con = permutation(flag_img, c)
flag_enc = substitution(flag_con, c)
print("What a disaster! To make it up to me, here's a gift...")
print(flag_enc.tobytes().hex())
print("My job here is done!")
if __name__ == "__main__":
main()
La flag se almacena dentro de una imagen JPEG llamada flag.jpg y está cifrada usando un cifrado basado en XOR. Se nos permite ingresar una imagen como matriz que se cifrará con una clave aleatoria. Luego, el servidor nos dará el texto cifrado correspondiente y también el texto cifrado para flag.jpg, cifrado con la misma clave.
Por lo tanto, de alguna manera debemos encontrar cómo se está cifrando nuestra imagen de entrada para adivinar los bytes de texto claro de flag.jpg.
Análisis del código fuente
Primero, el servidor define la clave de cifrado aleatorio como un vector $400 \times 8$ bytes:
c: npt.NDArray[np.uint64] = np.frombuffer(os.urandom(400 * 8), np.uint64)
Luego, el servidor toma nuestra imagen a partir de datos hexadecimales:
print(
"Hi, I'm here to take your order! Can you give me an image of the type of pizza you want me to cook?"
)
height = input("What's the height of the image? ")
width = input("What's the width of the image? ")
img_hex = input("Now send me the image and I'll do the rest!\n")
try:
height = int(height)
width = int(width)
assert height <= 400 and width <= 400
img: npt.NDArray[np.uint8] = np.array(
Image.frombytes("L", (width, height), bytes.fromhex(img_hex))
)
except:
print("Uh oh! You're trying to trick me? Out of my pizzeria!")
exit()
Después de eso, nuestra imagen se cifra y el servidor nos la devuelve:
con = permutation(img, c)
enc = substitution(con, c)
print("Oh mamma mia! I've scrambled all of your ingredients, look!")
print(enc.tobytes().hex())
Luego, el servidor carga flag.jpg y la cifra con la misma clave c:
flag_img: npt.NDArray[np.uint8] = np.array(Image.open("flag.jpg").convert("L"))
flag_con = permutation(flag_img, c)
flag_enc = substitution(flag_con, c)
print("What a disaster! To make it up to me, here's a gift...")
print(flag_enc.tobytes().hex())
Análisis del cifrado
El cifrado está compuesto por dos funciones: permutation y substitution:
def permutation(
img: npt.NDArray[np.uint8], c: npt.NDArray[np.uint64]
) -> npt.NDArray[np.uint8]:
height, width = img.shape
cm = c[np.arange(max(height, width)) % len(c)]
rows = np.argsort(cm[:height])
cols = np.argsort(cm[:width])
return img[rows, :][:, cols]
def substitution(
con: npt.NDArray[np.uint8], c: npt.NDArray[np.uint64]
) -> npt.NDArray[np.uint8]:
ids = np.arange(np.prod(con.shape)) % len(c)
return con ^ (c % 256).astype(np.uint8)[ids].reshape(con.shape)
De ahora en adelante, supongamos que todas las imágenes son matrices de tamaño $400 \times 400$ y con enteros de 8 bits como elementos.
En permutation, El servidor toma la matriz de cifrado c y calcula cm limitando a las filas o columnas máximas de la matriz de la imagen (nada cambia si usamos matrices de $400 \times 400$).
Entonces, la variable rows son los índices de lista de cm si se ordenaran:
>>> help(np.argsort)
Help on _ArrayFunctionDispatcher in module numpy:
argsort(a, axis=-1, kind=None, order=None)
Returns the indices that would sort an array.
Darse cuenta de cols es exactamente lo mismo que rows. Entonces, el resultado es img[rows, :][:, cols].
Para substitution, el servidor solo usa XOR en términos de elementos con los valores de c módulo 256 (8 bits).
Solución
Una cosa clara es que: si enviamos una matriz nula, la salida contendrá los valores de c módulo 256 debido a las propiedades de XOR. Además, la operación XOR se aplica por columnas. Podemos probar esto fácilmente:
>>> c: npt.NDArray[np.uint64] = np.frombuffer(os.urandom(3 * 8), np.uint64)
>>> img: npt.NDArray[np.uint8] = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
>>> permutation(img, c)
array([[5, 4, 6],
[2, 1, 3],
[8, 7, 9]])
>>> substitution(permutation(img, c), c)
array([[214, 252, 82],
[209, 249, 87],
[219, 255, 93]])
>>>
>>> img: npt.NDArray[np.uint8] = np.array([[0, 0, 0], [0, 0, 0], [0, 0, 0]])
>>> permutation(img, c)
array([[0, 0, 0],
[0, 0, 0],
[0, 0, 0]])
>>> substitution(permutation(img, c), c)
array([[211, 248, 84],
[211, 248, 84],
[211, 248, 84]])
Por lo tanto, teniendo en cuenta que el texto claro flag.jpg es siempre el mismo, podemos planificar esta estrategia:
- Enviaremos una matriz que contiene todos los ceros excepto por 200 valores de l
1al200en la mitad superior de la primera columna - El servidor permutará estos valores distintos de cero y luego aplicará XOR por columnas
- Podemos determinar fácilmente la clave de XOR de cada columna, ya que hay exactamente 200 valores de texto claro nulo, por lo que habrá exactamente 200 valores clave en las columnas de texto cifrado. Usando estos, podemos descifrar la matriz completa y descubrir un mapa entre los valores no nulos de texto claro y su posición en el texto cifrado
- Habiendo encontrado este mapa, podemos tomar la imagen cifrada
flag.jpg, descifrar sus columnas con la clave XOR correspondiente y finalmente permutar los píxeles que conocemos por el mapa anterior - Luego, hacemos el mismo proceso con la parte inferior de la primera columna
- Y luego repetimos el proceso hasta que completemos las 400 columnas
Vamos a ilustrarlo con un matriz de $6 \times 6$:
>>> img = np.zeros([6, 6], np.uint8)
>>> img[:3, 0] = np.array([1, 2, 3])
>>> img
array([[1, 0, 0, 0, 0, 0],
[2, 0, 0, 0, 0, 0],
[3, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0]], dtype=uint8)
>>> enc = substitution(permutation(img, c), c)
>>> enc
array([[184, 227, 77, 167, 165, 86],
[184, 227, 77, 167, 166, 86],
[184, 227, 77, 167, 165, 86],
[184, 227, 77, 167, 165, 86],
[184, 227, 77, 167, 164, 86],
[184, 227, 77, 167, 167, 86]], dtype=uint8)
>>> k = np.array([184, 227, 77, 167, 165, 86])
>>> enc ^ k
array([[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 3, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 2, 0]])
Ahora podrríamos ver que 1 (0, 0) -> 1 (4, 4), 2 (1, 0) -> 2 (5, 4) y 3 (2, 0) -> 3 (1, 4) y aplicaríamos el mapa inverso al texto cifrado de flag.jpg y la misma clave XOR. Esta tecla XOR se puede obtener automáticamente usando Counter en Pythonn:
>>> from collections import Counter
>>> k = np.array([Counter(enc[:, i]).most_common(1)[0][0] for i in range(6)])
>>> k
array([184, 227, 77, 167, 165, 86], dtype=uint8)
Entonces, solo falta implementar el procedimiento anterior en Python y comenzar a consultar al servidor.
Flag
Una vez que ejecutemos el script, obtendremos la flag dentro de la imagen JPEG:
$ python3 solve.py
[|] Row/Col: 1/399
El script completo se puede encontrar aquí: solve.py.
