# 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

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

data = decode(new_im)

if data:
print(data.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: