## ASIS CTF 2014: Random Image

May 11, 2014

This crypto-challenge was appointed with 150 points. A very nice task – kudos to the guys from ASIS for organizing the ctf. About the task: when downloading and unziping the file you’ll get two things:

• A picture enc.png
• A python script color-crypto.py

The image only contains random noise or at least does not resemble anything.

```#!/usr/bin/env python

import Image
import random

def get_color(x, y, r):
n = (pow(x, 3) + pow(y, 3)) ^ r
return (n ^ ((n >> 8) << 8 ))
flag_img = Image.open("flag.png")
r = random.randint(1, pow(2, 256))
print flag_img.size

enc_img = Image.new(flag_img.mode, flag_img.size)

for x in range(flag_img.size):
for y in range(flag_img.size):
t = random.randint(1, pow(2, 256)) % 250
enpix[x,y] = t

for x in range(flag_img.size):
for y in range(flag_img.size):
if im[x,y] < 250 :
s = get_color(x, y, r)
enpix[x,y] = s

enc_img.save('enc' + '.png')
```

So it seems that our goal is to restore the original flag.png file.
First we take a look at the two loops: the first one is filling a new image
(having the same dimensions as the flag.png) with random monochrome values.
The second loop is iterating over every pixel in the flag.png. Should the
color-value of a pixel be smaller than 250 (i.e. it is not white),
the result of the get_color method is written at the position of the current
pixel.

We therefore have to analyze the get_color method. It is taking
three arguments: the x and y position of a pixel and a random number r.
r is set at the beginning of the script and contains a random
256-Bit Integer. The method basically then is calculating the sum of
the cubes of x and y, XOR-ed with r. Then it returns the 8 lowest
Bits of this number.

In order to get the original image we  have to do the following:

1. get to know the value of r used to generate the enc.png
2. find out which pixels were part of the original image

So in order to find out the value of r  in the original generation of
the image, we XOR-ed every color-value of each pixel with the lowest 8
Bits of the sum of cubes of the pixel-cordinates. This results in:

(x^3 + y^3) XOR (x^3 + y^3) XOR r

We thus are ending up with only the value of r. As we do not know,
which pixels were calculated that way, we stored the result in a dict with the results as the key and the count as the value.
The value with the most occurrences was then chosen. With ~ 28000
ocurences compared to ~ 300 with the other pixels we determined r to
be 61.

The second part was straight-forward: just use the above calculations
for each pixel again and check if it results in 61. Should this be the
case draw a black pixel at the current position. This resulted in the flag: Here is our code:

```#!/usr/bin/env python

import Image
import random
import sys
from collections import defaultdict
import operator

flag_img = Image.open(sys.argv)
enc_img = Image.new(flag_img.mode, flag_img.size)

rd = defaultdict(int)
nope = flag_img.size*flag_img.size

new_flag = Image.new("RGBA", flag_img.size)

for x in range(flag_img.size):
for y in range(flag_img.size):
pix = im[x,y] % 256
n = (pow(x, 3) + pow(y, 3))
r = pix ^ (n % 256)
if r == 61:
new_flag_im[x,y] = (0, 0, 0, 255)
else:
new_flag_im[x,y] = (0, 0, 0, 0)
rd[r] += 1

sortrd = sorted(rd.iteritems(), key=operator.itemgetter(1))
for k,v in sortrd:
print "%03d %.3f %d" % (k, float(v)/float(nope)*100.0, v)

new_flag.save("new_flag.png")
```