Scrambled Pizzeria
6 minutes to read
We are given the source code of the server in 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()
The flag is stored inside a JPEG image called flag.jpg and it is encrypted using some XOR based cipher. We are allowed to enter an image as a matrix that will be encrypted with a random key. Then, the server will give us the corresponding ciphertext and also the ciphertext for flag.jpg encrypted with the same key.
Therefore, we must somehow find how our input image is being encrypted to guess the plaintext bytes of flag.jpg.
Source code analysis
First, the server defines the random encryption key as a $400 \times 8$ bytes array:
c: npt.NDArray[np.uint64] = np.frombuffer(os.urandom(400 * 8), np.uint64)
Then, the server takes our image from hexadecimal data:
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()
After that, our image is encrypted and given to us:
con = permutation(img, c)
enc = substitution(con, c)
print("Oh mamma mia! I've scrambled all of your ingredients, look!")
print(enc.tobytes().hex())
Then, the server loads flag.jpg and encrypts it with the same key 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())
Cipher analysis
The cipher is composed of two functions: permutation and 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)
From now on, let’s assume all images are $400 \times 400$ matrices with 8-bit integer entries.
In permutation, the server takes the encryption matrix c and computes cm by limiting to the maximum rows or columns of the image matrix (nothing changes if we use $400 \times 400$ matrices).
Then, the rows variable is the list indices of cm if they were sorted:
>>> 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.
Notice that cols is the exact same thing as rows. Then, the result is img[rows, :][:, cols].
For substitution, the server just uses element-wise XOR with the values of c modulo 256 (8 bits).
Solution
One clear thing is that: if we send a null matrix, the output will contain the values of c modulo 256 because of XOR properties. Moreover, the XOR operation is applied by columns. We can easily test this:
>>> 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]])
Therefore, taking into account that the plaintext flag.jpg is always the same, we can plan this strategy:
- We will send a matrix that contains all zeros but for 200 values from
1to200in the upper half part of the first column - The server will permute these non-zero values and then apply XOR by columns
- We can easily determine the XOR key of every column since there are exactly 200 null plaintext values, so there will be exactly 200 key values in the ciphertext columns. Using those, we can decrypt the full matrix and find out a mapping between the plaintext non-zero values and their ciphertext position
- Having found this mapping, we can take the encrypted
flag.jpeg, decrypt its columns with the corresponding XOR key and finally permute the pixels we know from the mapping - Then, we do the same process with the lower half part of the first column
- And then we repeat the process until we complete all 400 columns
Let’s illustrate it with a $6 \times 6$ matrix:
>>> 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]])
Now we could see that 1 (0, 0) -> 1 (4, 4), 2 (1, 0) -> 2 (5, 4) and 3 (2, 0) -> 3 (1, 4) and we would apply the inverse mapping to the encrypted flag.jpg image and the same XOR key. This XOR key can be obtained automatically using Counter in Python:
>>> 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)
Therefore, we onlye need ro implement the above procedure in Python and start querying the server.
Flag
Once we run the script, we will get the flag inside the JPEG image:
$ python3 solve.py
[|] Row/Col: 1/399
The full script can be found in here: solve.py.
