Klaus' Log

Mo 13 Mai 2019

DEF CON CTF Qualifier 2019 - redacted-puzzle

Posted by Klaus Eisentraut in ctf   

After my first success at DEF CON CTF Qualifier 2019, I was motivated to try another one of the challenges.

The challenge

The challenge was the following completely black picture:

redacted-puzzle.gif

The additional text was: Everything you need is in this file.

Part 1

First thing I did was running identify from ImageMagick against the provided image. The picture is an animated GIF with 34 frames:

# identify redacted-puzzle.gif
/tmp/redacted-puzzle.gif[0] GIF 1280x720 1280x720+0+0 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[1] GIF 592x595 1280x720+341+61 8-bit sRGB 4c 0.000u 0:00.002
/tmp/redacted-puzzle.gif[2] GIF 592x602 1280x720+341+59 8-bit sRGB 4c 0.000u 0:00.002
/tmp/redacted-puzzle.gif[3] GIF 577x608 1280x720+353+56 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[4] GIF 409x610 1280x720+334+56 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[5] GIF 616x592 1280x720+332+76 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[6] GIF 616x619 1280x720+332+49 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[7] GIF 590x584 1280x720+362+49 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[8] GIF 486x586 1280x720+466+47 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[9] GIF 495x630 1280x720+460+45 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[10] GIF 504x630 1280x720+451+45 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[11] GIF 574x581 1280x720+323+96 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[12] GIF 635x635 1280x720+323+42 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[13] GIF 572x637 1280x720+387+42 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[14] GIF 352x287 1280x720+607+392 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[15] GIF 559x559 1280x720+320+121 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[16] GIF 640x640 1280x720+320+40 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[17] GIF 640x640 1280x720+320+40 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[18] GIF 458x640 1280x720+411+40 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[19] GIF 640x549 1280x720+320+131 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[20] GIF 640x559 1280x720+320+121 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[21] GIF 565x559 1280x720+395+121 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[22] GIF 347x528 1280x720+320+152 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[23] GIF 638x450 1280x720+320+107 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[24] GIF 636x634 1280x720+322+43 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[25] GIF 633x634 1280x720+324+43 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[26] GIF 632x630 1280x720+324+45 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[27] GIF 583x630 1280x720+370+45 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[28] GIF 583x625 1280x720+370+47 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[29] GIF 622x474 1280x720+330+198 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[30] GIF 620x618 1280x720+330+52 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[31] GIF 589x614 1280x720+332+52 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[32] GIF 449x612 1280x720+334+54 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[33] GIF 605x608 1280x720+336+56 8-bit sRGB 4c 0.000u 0:00.001
/tmp/redacted-puzzle.gif[34] GIF 600x431 1280x720+341+230 8-bit sRGB 4c 79996B 0.000u 0:00.001

The first picture has a resolution of 1280x720 and the subsequent images update some areas in the middle of it. For instance, the first update frame is 592x595 large and updates the pixels starting at pixel 341x61 up to 933x656 (341+592=933 and 61+595=656).

My first idea was that the pictures might not actually be black, but contain of slightly different colors in it. So I made a histogram with ImageMagick, but it turned out that each of the 34 pictures is completely black:

# convert /tmp/redacted-puzzle.gif -define histogram:unique-colors=true -format %c histogram:info:-
    921600: (  0,  0,  0) #000000 black
    352240: (  0,  0,  0,255) #000000FF black
    356384: (  0,  0,  0,255) #000000FF black
    350816: (  0,  0,  0,255) #000000FF black
    249490: (  0,  0,  0,255) #000000FF black
    364672: (  0,  0,  0,255) #000000FF black
    381304: (  0,  0,  0,255) #000000FF black
    344560: (  0,  0,  0,255) #000000FF black
    284796: (  0,  0,  0,255) #000000FF black
    311850: (  0,  0,  0,255) #000000FF black
    317520: (  0,  0,  0,255) #000000FF black
    333494: (  0,  0,  0,255) #000000FF black
    403225: (  0,  0,  0,255) #000000FF black
    364364: (  0,  0,  0,255) #000000FF black
    101024: (  0,  0,  0,255) #000000FF black
    312481: (  0,  0,  0,255) #000000FF black
    409600: (  0,  0,  0,255) #000000FF black
    409600: (  0,  0,  0,255) #000000FF black
    293120: (  0,  0,  0,255) #000000FF black
    351360: (  0,  0,  0,255) #000000FF black
    357760: (  0,  0,  0,255) #000000FF black
    315835: (  0,  0,  0,255) #000000FF black
    183216: (  0,  0,  0,255) #000000FF black
    287100: (  0,  0,  0,255) #000000FF black
    403224: (  0,  0,  0,255) #000000FF black
    401322: (  0,  0,  0,255) #000000FF black
    398160: (  0,  0,  0,255) #000000FF black
    367290: (  0,  0,  0,255) #000000FF black
    364375: (  0,  0,  0,255) #000000FF black
    294828: (  0,  0,  0,255) #000000FF black
    383160: (  0,  0,  0,255) #000000FF black
    361646: (  0,  0,  0,255) #000000FF black
    274788: (  0,  0,  0,255) #000000FF black
    367840: (  0,  0,  0,255) #000000FF black
    258600: (  0,  0,  0,255) #000000FF black

So I gave up on this idea and tried some other ideas, all leadig to nowhere:

  • Search for other, non-image content in the file. binwalk found nothing.
  • identify -verbose redacted-puzzle.gif printed a binary field signature for every picture. For the first one, it looks like signature: 7b382cdea81187d58f65c997c1e2b521010ad38fce5c9be73fdac9618c628489. I tried concatenating all of them, but got only binary gibberish. I'm still not sure what this field actually is. I think it is just a checksum which is not actually stored in the image, but rather calculated by ImageMagick on-the-fly.
  • Assume the information is stored in the size of the frames only. So i drew 34 rectangles into a 1280x720 image where each rectangle was the area of the frame. The idea was that it would give some visual pattern or something like a QR code, but it didn't.
  • I read this useful GIF file format explanation and looked if the GIF file has any Comment Extension blocks in it. Those would start with 0x21 0xFE, but the only occurrence of this hexadecimal pattern in the GIF file is accidentially and there is no actual comment extension block in the file.

After my deep-dive into the GIF file format, I noticed that a GIF file defines a color map. While identify -verbose redacted-puzzle.gif still said that every pixel is black, I noticed that the color black is defined three times in the color map.

  Colors: 1
  Histogram:
    352240: (  0,  0,  0,255) #000000FF black
  Colormap entries: 4
  Colormap:
         0: (  0,  0,  0,255) #000000FF black
         1: (  0,  0,  0,255) #000000FF black
         2: (  0,  0,  0,255) #000000FF black
         3: (255,255,255,  0) #FFFFFF00 srgba(255,255,255,0)

So even while all pixels are black, it still could be stored differently! I used the Pillow image library of Python to update the palette of every frame and saved every frame to a PNG file (the code can be found below).

I had solved the first step and got 34 non-empty, but very similiar pictures. Below you can see the first four of the unredacted pictures:

frame 00 of redacted-puzzle frame 01 of redacted-puzzle

frame 02 of redacted-puzzle frame 03 of redacted-puzzle

Part 2

The second part was quite straight-forward now.

The flag alphabet +-=ABCDEFGHIJKLMNOPQRSTUVWXYZ_{} has exactly 32 characters. If we assume base32 encoding and include the fact that the flag will start with OOO{, we need to find something like 10001 10001 10001 11110 or - in 8 bit blocks - 10001100 01100011 1110.....

By iterating through the pictures, it was clear that the polygons are created by connecting some of the eight positions in an octagon. In fact, the four polygons above encode 10001100, 01100011, 11100100 and 01000110 which fits to what I expect.

All what was left to do was to decode the 34 pictures into 34 bytes. A little bit annoying was the fact that the positions of the eight corners of the virtual octagon rotated by a few degrees counter-clockwise in every frame. Between the last one and the first one, there was a total turn of around 45 degrees. If one wouldn't account for the slow counter-clockwise turning, one could get a wrong bit representation of the last few ones.

Putting everything together

At the end, my solution looked like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#!/usr/bin/env python
from PIL import Image
from PIL import GifImagePlugin
import sys

# part 1: iterate through gif pictures, update the palette and save single pictures
imageObject = Image.open("./redacted-puzzle.gif")
for frame in range(0,imageObject.n_frames):
    imageObject.seek(frame)
    imageObject.putpalette([255,0,0,0,255,0,0,0,255])
    rgb_im = imageObject.convert('RGB')
    rgb_im.save("/tmp/output-%02u.png" % frame)

# part 2: the information below is extracted from the pictures from part 1
flag_alphabet = "+-=ABCDEFGHIJKLMNOPQRSTUVWXYZ_{}"
flag_bits=[
"10001100", # output-01.png
"01100011",
"11100100",
"01000110",
"10000101",
"00111101", # output-05.png
"01000010", 
"10011000",
"11100000",
"11110100",
"10000000",
"00101101",
"01110010",
"00011100", # output-13.png
"00001000",
"10100101",
"11010111",
"01101110",
"10100110", # output-18.png
"10010001",
"10111100",
"10000100",
"10000001", # output-22.png
"10111001",
"11010100", # output-24.png
"00111011", 
"11001110",
"11110010",
"00011110", # output-28.png
"10011101",
"11001001",
"11000111",
"01100101",
"00011110", # output-33.png
"10011111",
]

# base32 decoding
flag_bits = "".join(flag_bits)
solution = ""
for i in range(0,len(flag_bits),5):
    tmp = flag_bits[i:i+5]
    index = int(tmp,2)
    solution += flag_alphabet[index]
    print(tmp, " == ", index, " -> ", flag_alphabet[index])

print("solution: ", solution)

If you run this script, the output looks like this:

$ python ~/picture.py 
10001  ==  17  ->  O
10001  ==  17  ->  O
10001  ==  17  ->  O
11110  ==  30  ->  {
01000  ==  8  ->  F
10001  ==  17  ->  O
10100  ==  20  ->  R
00101  ==  5  ->  C
00111  ==  7  ->  E
10101  ==  21  ->  S
00001  ==  1  ->  -
01001  ==  9  ->  G
10001  ==  17  ->  O
11000  ==  24  ->  V
00111  ==  7  ->  E
10100  ==  20  ->  R
10000  ==  16  ->  N
00000  ==  0  ->  +
10110  ==  22  ->  T
10111  ==  23  ->  U
00100  ==  4  ->  B
00111  ==  7  ->  E
00000  ==  0  ->  +
01000  ==  8  ->  F
10100  ==  20  ->  R
10111  ==  23  ->  U
01011  ==  11  ->  I
10110  ==  22  ->  T
11101  ==  29  ->  _
01001  ==  9  ->  G
10100  ==  20  ->  R
10001  ==  17  ->  O
10111  ==  23  ->  U
10010  ==  18  ->  P
00010  ==  2  ->  =
01000  ==  8  ->  F
00011  ==  3  ->  A
01110  ==  14  ->  L
01110  ==  14  ->  L
10100  ==  20  ->  R
00111  ==  7  ->  E
01111  ==  15  ->  M
00111  ==  7  ->  E
01111  ==  15  ->  M
00100  ==  4  ->  B
00111  ==  7  ->  E
10100  ==  20  ->  R
11101  ==  29  ->  _
11001  ==  25  ->  W
00111  ==  7  ->  E
00011  ==  3  ->  A
10110  ==  22  ->  T
01010  ==  10  ->  H
00111  ==  7  ->  E
10100  ==  20  ->  R
11111  ==  31  ->  }
solution:  OOO{FORCES-GOVERN+TUBE+FRUIT_GROUP=FALLREMEMBER_WEATHER}

I submitted the flag OOO{FORCES-GOVERN+TUBE+FRUIT_GROUP=FALLREMEMBER_WEATHER} and solved my second one!