Square CTF 2018 C3: shredded

Analysis

The challenge file contains an image cut in 27 vertical strips. The goal is to use them to reconstruct the original image which contains the flag.

Solution

We wrote a Python script to reconstruct the image as is, named shredded-reconstruct-image.py:

import os

from PIL import Image

images = [Image.open(os.path.join('shredded', '%s.png' % i)) for i in xrange(0, 27)]
widths, heights = zip(*(i.size for i in images))

total_width = sum(widths)
max_height = max(heights)

print ''
print 'total_width is: ', total_width
print ''
print 'max height is: ', max_height
print ''

new_im = Image.new('RGB', (total_width, max_height))

x_offset = 0
for im in images:
    new_im.paste(im, (x_offset, 0))
    x_offset += im.size[0]

new_im.show()

And this is the result image:

The result looks like it might be a QR code. Let’s analyze it. There are 6 white strips and 21 data strips, so this is a QR version 1. This image shows an example of the standard modules for a v1 QR code:

We have to respect certain properties for finder patterns, timing pattern and dark module, as described here.

3 white strips to the left and 3 white strips complete the scheme. We can fix some strip number:

  • 0, 9, 11 – left white strips
  • 5, 6 – left black squares
  • 15, 26, 3 – right side of the left black squares
  • 7 – white band on the left of the upper-right square
  • 1 – left white band inside the upper-right square
  • 18 – right white band inside the upper-right square
  • 12, 13, 17 – right white strips

So we have to compute 27 – 14  =  13 permutations (13! = 6.227.020.800)

We can reduce that number this way:

  • 3! for the strips 2,16, 25
  • 3! for the strips 4, 20, 21
  • 2! for the strips 10, 19
  • 3! for the strips 22, 23, 24
  • 2! for the strips 8, 14

Now we have:

3! * 3! * 3! * 2! * 2! = 
3! * 3! * 3! * 2 * 2 = 
3!3 * 22 = 216 * 4 = 
= 864 permutations

To solve this challenge we wrote this Python script, and called shredded-solver.py:

from __future__ import print_function
import itertools
import os

from PIL import Image, ImageDraw, ImageFont
from pyzbar.pyzbar import decode

images = [Image.open(os.path.join('shredded', '%s.png' % i)) for i in xrange(0, 27)]
widths, heights = zip(*(i.size for i in images))

total_width = sum(widths)
max_height = max(heights)

new_im = Image.new('RGB', (total_width, max_height))
draw = ImageDraw.Draw(new_im)
font = ImageFont.truetype("Roboto-Light.ttf", 7)


white_left = [0,9,11]  # fixed
                          
left = [5,6,2,16,25,15,26,3]

middle = [4,10,20,19,21]

right = [7,14,1,22,23,24,18,8]

white_right = [12,13,17]  #fixed

joined = white_left + left + middle + right + white_right

# 3!^3 * 2!^2 = 216 * 4 = 864 permutations 
permutes = [
    [5, 6, 7],     # 2, 16 and 25 - upper-left central square in finder pattern
    [11, 13, 15],  # 4, 20 and 21 - data (4 and 20 could be dark module!)
    [12, 14],      # 10 and 19 - data
    [17, 23],      # 14 and 8 - upper-right vertical black bands in finder pattern
    [19, 20, 21],  # 22, 23 and 24 - upper-right central square in finder pattern
]

permute_values = []
for i, permute in enumerate(permutes):
    values = [joined[x] for x in permute]
    perms = list(itertools.permutations(values))
    permute_values.append(perms)

for i, product in enumerate(itertools.product(*permute_values)):
    enum_product = []
    for j, group in enumerate(product):
        orig_idx = permutes[j]
        enum_product.append(zip(orig_idx, group))

    flatten = [x for y in enum_product for x in y]
    print (i)
    print (flatten)

    # Create new order
    order = [x for x in joined]
    for idx, value in flatten:
        order[idx] = value

    x_offset = 0
    for j in order:
        new_im.paste(images[j], (x_offset, 0))
        draw.text((x_offset, 5), str(j), (0, 0, 0), font=font)
        x_offset += images[j].size[0]

    data = decode(new_im)

    if data:
        print(data[0].data)
        new_im.save('Qr-Image-With-Flag.png')
        new_im.show()
        break

With only 864 iterations we can solve the puzzle.

And the file ‘Qr-Image-With-Flag.png’ is:

We did it with only 475 iterations (54,97 % of all the 864 possible iterations).

The hidden message was:

GOOD JOB. FLAG-80AD8BCF79

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.