Monday, 1 April 2019

Big Bad Writeup - Sunshine CTF 2019

In this challenge, we are provided a PNG image that displays a Binary Tree as shown below:


After analyzing the tree, it was concluded that the challenge is related to Huffman Encoding.

In Huffman Encoding, we can construct the value for each leaf node by traversing the tree from the root node till the leaf node using the following logic:

1. If a left branch is taken, then we consider the bit 0.
2. If a right branch is taken, then we consider the bit 1.

The left and right branches originating from the root node of the tree are marked as 0 and 1 respectively in the provided image which is also an indication that we have to use Huffman Encoding.

So, based on the above logic, we construct the Huffman Encoding table:

s = 000
u = 0010
_ = 0011
0 = 010
d = 0110
9 = 0111
5 = 1000
n = 10010
h = 10011
l = 10100
a = 10101
e = 10110
b = 10111
1 = 1100
{ = 11010
} = 11011
r = 11100
c = 11101
k = 11110
3 = 11111

In Huffman Encoding, if we have to decode the message, we need a binary stream. However, no binary stream was provided in the challenge description.

After further analysis, it was found using Steganography that the binary stream was encoded in the PNG image as a set of vertical black and white lines as shown below:


Each line has a width of 1 pixel, so we can extract the binary stream using the logic:

1. If the pixel value is 255, then we consider the bit to be 1.
2. If the pixel value is 1, then we consider the bit to be 0.

We can leverage the Python PIL library to accomplish this:

#! /usr/bin/python

from PIL import image
import sys

if len(sys.argv) != 2:
    print "usage: python decode_stream.py <image_file>"
   
im = Image.open(sys.argv[1])

stream = ""

for i in range(152):
    if im.getpixel((i, 0)) == 255:
        stream += str(1)
    else:
        stream += str(0)
   
print stream

We scan 152 pixels from the left side of the image because based on analysis of the image in Gimp, it was found that approximately 152 pixels need to be scanned to extract the complete binary stream.

we get the binary stream as:

00000101001011010000100110100010101000110101010011001010001011001100011101111110011001110111110000001111000100101100110011111010100011000111110111111111

We can apply the Huffman Encodings to above binary stream to get the flag as: sun{sh0ulda_u5ed_br1cks_10011305191101}

c0d3inj3cT

No comments:

Post a Comment