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.
The python-script reveals the task:

#!/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")
im = flag_img.load()
r = random.randint(1, pow(2, 256))
print flag_img.size

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

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

for x in range(flag_img.size[0]):
    for y in range(flag_img.size[1]):
        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:

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[1])
im = flag_img.load()
enc_img = Image.new(flag_img.mode, flag_img.size)

rd = defaultdict(int)
nope = flag_img.size[0]*flag_img.size[1]

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

for x in range(flag_img.size[0]):
	for y in range(flag_img.size[1]):
		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")

Leave a Reply