# TeamItaly CTF 2023
## [crypto] Scrambled Pizzeria (11 solves)
## How does the program workWhen started, the program will prompt the user to send it a greyscale image along with its height and width.The image will then be encrypted with a randomly generated keystream (of length 400) the permutation and substitution layers and sent back to the user, along with the flag encrypted with the same keystream.
Let's look at what those two layers do:```pythondef 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]```Here we take the keystream, we take all its elements up to `max(height, width)`, then we sort it in ascending order. We then permutate the columns and rows of the image using the indices of the sorted truncated keystream.
```pythondef 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)```During the substitution phase we simply create a long enough sequence from the keystream to xor with all the image, so we repeat the original keystream as many times as needed.
## What's the idea of the attackThe idea of the attack is to pass an image built in such a way that the column permutation layer won't have effect on at least one row, such that we can recover the original keystream, and in suh a way that, after having inverted the substitution layer, we can build the permutation map used in the encryption of the image and also of the flag.
Such an image can be constructed in the following way:```pythonshape = (3, 400)I = np.zeros(shape, np.uint8)I[1, :] = np.mod(np.arange(shape[1]), 256) + np.floor(np.arange(shape[1]) / 256)I[2, :] = np.floor(np.arange(shape[1]) / 256) * 255```Here we have a row full of zeroes, such that when it will be XORed with the reduced keystream it will just result in the reduced keystream itself in the ciphertext.The other two rows are needed to recover the permutation map. After recovering the result of the permutation layer of the ciphertext of our image (by inverting the substitution layer), we can just sum the two rows to obtain the full permutation map.
As we don't know which of the three rows is the effective reduced keystream, we need to try all the three rows and find the correct one.
## The solver```python#!/usr/bin/python3
from pwn import *import numpy.typing as nptimport numpy as npfrom PIL import Imageimport os
def inverse_permutation(    img: npt.NDArray[np.uint8], p: npt.NDArray[np.uint]) -> npt.NDArray[np.uint8]:    height, width = img.shape    idxs = np.arange(max(height, width)) % len(p)    rows = np.argsort(p[idxs[:height]])    cols = np.argsort(p[idxs[:width]])    return img[rows, :][:, cols]
def inverse_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)
r = remote("todo.challs.todo.it", 1337)
shape = (3, 400)I = np.zeros(shape, np.uint8)I[1, :] = np.mod(np.arange(shape[1]), 256) + np.floor(np.arange(shape[1]) / 256)I[2, :] = np.floor(np.arange(shape[1]) / 256) * 255
r.sendlineafter(b"What's the height of the image? ", str(shape[0]).encode())r.sendlineafter(b"What's the width of the image? ", str(shape[1]).encode())r.sendlineafter(    b"Now send me the image and I'll do the rest!\n",    I.tobytes().hex().encode(),)
r.recvuntil(b"Oh mamma mia! I've scrambled all of your ingredients, look!\n")enc = bytes.fromhex(r.recvline(False).decode())enc = np.frombuffer(enc, np.uint8).reshape(shape)
r.recvuntil(b"What a disaster! To make it up to me, here's a gift...\n")flag_enc = bytes.fromhex(r.recvline(False).decode())flag_enc = np.frombuffer(flag_enc, np.uint8).reshape((400, 400))
r.close()
if not os.path.exists("results"):    os.mkdir("results")
for i, c in enumerate(enc):    con = inverse_substitution(enc, c).astype(np.uint)    p = con[0] + con[1] + con[2]
    flag_con = inverse_substitution(flag_enc, c)    flag = inverse_permutation(flag_con, p)
    Image.fromarray(flag).save(f"results/{i}.jpg")```