CScamp 2012 Quals – Web 300

CScamp CTF 2012 - Web 300 - puzzle image website

Bei dieser Challenge (Web 300) ist das eigentliche Ziel sehr schnell klar. Es existiert ein Bild, deren Teile verwürfelt sind, und die von uns innerhalb von zwei Sekunden in die richtige Reihenfolge gebracht werden müssen. Da es sehr schwer werden wird, das Bild innerhalb von zwei Sekunden per Hand zu sortieren und das Ergebnis einzugeben, bleibt uns nur der Weg, eine automatisierte Lösung per Skript zu entwickeln.

Dabei wird es erforderlich sein, jedes der zwölf Quadrate eindeutig zu identifizieren. Zur Umsetzung habe ich mir daher überlegt, aus jedem Quadrat die Farben (Rot – Grün – Blau) von vier Pixeln aus den Eckbereichen zu entnehmen und darüber eine Art “Fingerabdruck” jedes Quadrates zu erhalten – hier vereinfacht dargestellt ;-).

CScamp CTF 2012 - Web 300 - identifying puzzle pieces by pixel

Bei der Umsetzung hat sich jedoch das Problem ergeben, dass – wohlmöglich durch die jeweils erneute JPEG-Umwandlung – die Farben der Pixel sich immer (minimal) unterscheiden. Als Umweg werden wir daher nur festhalten, ob sich viel oder wenig Rot-/Grün-/Blau-Töne in den Pixeln befinden und so eine eindeute Zuordnung der Quadrate realisieren.

Um den Server nicht unnötig mit Anfragen zu beschäftigen, nutzen wir hier zwei Skripte. Ein Bash-Skript zur Kommunikation mit dem Server sowie ein Python-Skript zur Sortierung des Bildes. Somit kann die Sortierung an ein- und demselben Bild wiederholt durchgeführt werden um die korrekte Funktion des Sortieralgorithmus zu testen.

Das Skript zur Kommunikation mit dem Server sieht folgendermaßen aus:

#!/bin/bash

echo Fetching image...
rm -f cookie
curl -c cookie -b cookie http://176.9.193.13/CxliTo3-ra/
curl -c cookie -b cookie http://176.9.193.13/CxliTo3-ra/image.php -o sortme.jpeg

SORT=$(./sort.py)
echo "SOLUTION: $SORT"

echo "Posting..."
curl -c cookie -b cookie -G --data-urlencode "order=$SORT" http://176.9.193.13/CxliTo3-ra/s.php -o solution.txt
cat solution.txt

Zunächst werden hier die Cookies vom Server geladen und das zu sortierende Bild als “sortme.jpeg” gespeichert (Zeilen 4-6). Dann wird das Sortier-Skript “sort.py” aufgerufen sowie das Ergebnis der Sortierung zu Kontrollzwecken ausgegeben (Zeilen 8-9). Zuletzt wird das Ergebnis an den Server gesendet und die Antwort des Servers ausgegeben (Zeilen 11-13).

Nachdem die Kommunikation realisiert ist, muss nun noch die eigentliche Sortierung folgen. Das entsprechende Python-Skript, welches die Python Image Library verwendet, sieht folgendermaßen aus:

#!/usr/bin/python

import sys
import Image

# load image
im = Image.open("sortme.jpeg")
pix = im.load()

# these are the sorted image fingerprints
sorted = ["101101101101", "101111101001", "000111001001", "000001001010",
          "101101100100", "101001111111", "001001000000", "010010010010",
          "100100100100", "100111100110", "111010110110", "010010110110"]
res = ""

# loop through fingerprints to find 1st, 2nd, ... part
for i in range(0,12):
  pos = 0
  # image is 400x300, take every 100x100 part
  for y in range(0, 300, 100):
    for x in range(0, 400, 100):
      fingerprint = ""

      # create 4x3 array containing 4 pixel with 3 colors (RGB)
      check = pix[x+10,y+10] + pix[x+90,y+10] + pix[x+10,y+90] + pix[x+90,y+90]

      # loop though RGB-colors to create fingerprint
      # we need this because jpeg-converting seems to make colors differ
      for k in check:
        if k < 128:
          fingerprint = fingerprint + "0"
        if k >= 128:
          fingerprint = fingerprint + "1"

      # DEBUG OUTPUT: to create sorted-array manually
      # print(str(x) + ":" + str(y) + " --> " + fingerprint)

      # correct part found?
      if sorted[i] == fingerprint:
        res = res + str(pos) + ":"
        break
      pos += 1

# output in challenge format
sys.stdout.write(res[0:len(res)-1])

Das Bild wird zunächst geladen (Zeilen 7-8) und anschließend das Fingerprint-Array “sorted” definiert (Zeilen 11-13). Diese Array erhalt man, wenn man das Kommentar der DEBUG-Zeile 36 im Skript sowie die äußere For-Schleife entfernt (Skript) und das Ergebnis sortiert:

0:0     --> 101001111111
100:0   --> 101111101001
200:0   --> 100100100100
300:0   --> 111010110110
0:100   --> 100111100110
100:100 --> 001001000000
200:100 --> 000111001001
300:100 --> 000001001010
0:200   --> 101101101101
100:200 --> 101101100100
200:200 --> 010010110110
300:200 --> 010010010010

Wenn man sich nun überlegt, wie das Bild korrekt aussehen würde und diese Fingerabdrücke einmalig sortiert, erhält man das sorted-Array (Zeilen 11-13). Das Skript iteriert anschließend nur noch über alle Quadrate und versucht die richtige Zuordnung über das sorted-Array zu finden (Zeilen 17-42). Abschließend wird das Ergebnis in der von der Challenge geforderten Form ausgegeben.

Führt man das Bash-Skript nun aus, erhalt man diese Ausgabe:

rup0rt@lambda:~/CScamp2012$ ./web300.sh
Fetching image... 
SOLUTION: 8:1:6:7:9:0:5:11:2:4:3:10
Posting...
key : 1e48572e9fb2f0b42c3f59bf8245f034

Die Lösung lautet somit: “1e48572e9fb2f0b42c3f59bf8245f034“.

Leave a Reply

Your email address will not be published. Required fields are marked *