URL: http://asis-ctf.ir/challenges/
Type: XOR + grayscale threshold
Solution: ASIS_af4e8dcbbcdcef44fd3ecdbc6e9695d4
Description
Find the flag
file
Archive contains 2 files:
$ tar xvfJ crypto_150_8f3fd5d2bacd408904b8406c19183c23 x color_crypto.py x enc.png
color_crypto.py
is the Python source code of the algorithm used to encrypt the PNG file:
#!/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')
enc.png
is a 8-bit grayscale PNG image:
Algorithm analysis
The coding scheme rely on grayscale threshold. Basicly, in original image:
- if pixel
gray level ≥ 250
then it is considered as bright pixel - if pixel
gray level < 250
then it is considered as dark pixel
In encoded image:
- bright pixel is substitued with a random value:
random.randint(1, pow(2, 256)) % 250
- dark pixel is computed in
get_color(x, y, r)
function, from its coordinates and a constant big random valuer = random.randint(1, pow(2, 256))
: then it returns the 8 less significant bits (i.e. the less significant byte)n = (pow(x, 3) + pow(y, 3)) ^ r
which somehow is equivalent ton ^ ((n >> 8) << 8 )
n & 0xff
Weakness
The weakness here is that for each pixel the coordinates x
and y
are known, and r
is a constant value. Knowing XOR associative property (a^b=c ⇐⇒ a^c=b ⇐⇒ b^c=a
):
- for each pixel of the encoded image, we XOR its value with
(x3 + y3)
- thus, the less significant byte of
r
is the most frequently occurring value - finally:
- if a pixel of the encoded image XOR
(x3 + y3)
= the less significant byte ofr
, then pixel of the original image was dark (let's say black) - else pixel of the original image was bright (let's say white)
There could be some false positive (i.e. pixels that we considered dark when they were bright) due to randomness, but statistically they will be few.
- if a pixel of the encoded image XOR
Python decoder
import Image enc_img = Image.open('enc.png') enc_pix = enc_img.load() # 1. XOR all pixel values with corresponding (x**3 + y**3) pow_pix = [(enc_pix[x,y] ^ (x**3 + y**3)) & 0xff for x in range(enc_img.size[0]) for y in range(enc_img.size[1])] # 2. r_LSbyte = most frequently occurring byte r_LSbyte = max([b for b in range(0x100)], key = pow_pix.count) flag_img = Image.new(enc_img.mode, enc_img.size) flag_pix = flag_img.load() for x in range(enc_img.size[0]): for y in range(enc_img.size[1]): if ((enc_pix[x, y] ^ (x**3 + y**3)) & 0xff == r_LSbyte): flag_pix[x, y] = 0 # original pixel was dark else: flag_pix[x, y] = 255 # original pixel was bright flag_img.save('flag.png')
Running on enc.png
, we obtain the following decoded PNG flag file (with less significant byte of r = 0x3d
):