Die “professional programming and coding” – Challenge “Positive” gibt zunächst keine Beschreibung des eigentlichen Ziels. Daher verbinden wir als erstes direkt zum angegebenen System.
MANUAL: Be positive, change all minuses to pluses! Rules: clicking on a cell changed it and it's neighbours. Format: a) "\d\d" - number of cell b) "(?:\d\d)+" numbers of cells ++---+---+ ---------- -+-------- --++------ -+---+-+-- ---+------ ---------- ----++---+ -+---+---- -----+-+--
Mit den ersten Zeilen der Ausgabe sind wir etwas schlauer. Auf dem Spielfeld müssen durch Angabe der Spalte und Zeile alle Minus in Plus getauscht werden. Der Haken dabei ist, dass die benachbarten Felder ebenfalls getauscht werden. Die Eingabe von “11” als Lösung tausch damit neben 11 auch die Positionen 10, 12, 01, 02.
( Bei diesem Spiel handelt es sich um das so genannte “Lights Out” Spiel, das über bestimmte Algorithmen einfach gelöst werden kann. Diesen Hinweis hatte ich beim Lösen der Challenge leider nicht, was sich auch in meinem Lösungsweg widerspiegeln wird ;-). )
Zum Lösen der Challenge habe ich ein Python-Skript geschrieben, das ich im Folgenden schrittweise erläutern möchte:
#!/usr/bin/env python
import socket
import time
import random
s=socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("194.106.195.60",9502))
# fetch manual
data = s.recv(1024)
print "MANUAL: " + data
down = 1
solved = 0
while 1:
# fetch board
board = s.recv(1024).split("\n")
print "BOARD: " + str(board)
Der TCP-Socket wird zunächst deklariert und die Verbindung zum Server hergestellt (Zeilen 6-7). Anschließend wird die Anleitung eingelesen, ausgegeben (Zeilen 10-11) und die Endloschleife zum Lösen des Boards begonnen (Zeile 16). Dann wird das Board eingelesen und am Zeilenumbruch getrennt (Zeile 18). Als Datentyp handelt es sich beim Board damit um ein Array, dass die Zeilen als Elemente enthält.
if "Solved" in board[0]:
print board
solved += 1
print "\nSolved: " + str(solved)
board = s.recv(1024).split("\n")
print "FLAG: " + str(board)
Als Nächstes wird gesprüft um die “solved” Meldung in der ersten Zeile auftritt. Wenn das der Fall ist, wurde das Board mit der letzten Operation erfolgtreich gelöst und die Flagge sollte ausgegeben werden.
Zum Lösen des Boards habe ich mir nun Folgendes überlegt. Die gesamte erste Zeile kann in Plus umgewandelt werden, indem in der zweiten Zeile unterhalb der Minus getauscht wird. Im Beispiel:
++---+---+ *** ***
Diese Zeile wird durch die Lösung “213141617181” daher zu:
++++++++++
Wenn mann dieses Verfahren durchgehend anwendet, kann man die ersten 9 Zeilen in Plus umwandeln, nur um die letzte Zeile muss man sich separat kümmern. Der Quellcode zum tauschen der ersten 9 Zeilen lautet:
if down == 1: solution = "" found = 0 for y in range(0,9): line = board[y] for x in range(10): if line[x] == "-": solution = solution + str(y+1) + str(x) found = 1 if found == 1: break
Die ersten neun Zeilen werden enumeriert (Zeile 4) und für jedes Minus (Zeile 7) wird die darunter liegendene Zeile an der entsprechenden Zeile getauscht (Zeile 8). Die Variable found wird dabei nach einem Fund auf Eins gesetzt (Zeile 9). Da sich die Zeilen nach dem Tausch ändern, wird nach dem Fund in einer Zeile die Schleife beendet um die Lösung abzusenden.
if found == 0:
line = board[9]
pos = line.find("---")
if pos != -1:
solution = "9" + str(pos+1)
else:
pos = line.find("--")
if pos != -1:
solution = "9" + str(pos+1)
if solution == "":
solution = "9" + str(random.randint(0,9))
print "GOING UP..."
down = 0
Sollte in keiner der ersten neun Zeilen ein Tausch vorgenommen worden sein (Zeile 1), dann sind bis auf die letzte Zeile alle anderen Plus und wir kümmern uns jetzt um die letzte Zeile. Dazu wird zunächst auf drei Minus in Folge “—” geprüft und in der Mitte getauscht (Zeilen 3-5). Anschließend wird auf zwei Minus “–” geprüft und entsprechend getauscht (Zeilen 6-9).
Sollte es trotz aller Prüfungen immernoch keinen Tausch geben (Zeile 10), soll per Zufall eine Position getauscht werden (Zeile 11). Zuletzt soll die Richtung gewechselt werden und nun entsprechend von unten nach oben sortiert werden (Zeilen 14ff).
print "SOLUTION: " + solution s.send(solution) s.close()
Nach Abarbeitung aller Operationen und Erhalt mindestens eines Tausches, wird dieser ausgegeben und an den Server gesendet (Zeilen 1-2).
Auch wenn dieser Algorithmus teilweise chaotisch ist und nicht sofort zum Erfolg führt, ist das Spielfeld nach relativ kurzer Zeit (wenigen Sekunden – einige Minuten) gelöst. Die erste Ausführung des Skriptes liefert folgendes Ergebnis:
rup0rt@lambda:~/BaltCTF2013$ ./positiv.py MANUAL: Be positive, change all minuses to pluses! Rules: clicking on a cell changed it and it's neighbours. Format: a) "\d\d" - number of cell b) "(?:\d\d)+" numbers of cells BOARD: ['+--+-++-++', '----+----+', '----+--+-+', '+++-+---+-', '-+---+----', '+++++++++-', '++++--+---', '+-+--+++++', '--+-+---+-', '+-+----+++', ''] SOLUTION: 11121417 BOARD: ['++++++++++', '+----+++++', '-++------+', '+++-+---+-', '-+---+----', '+++++++++-', '++++--+---', '+-+--+++++', '--+-+---+-', '+-+----+++', ''] SOLUTION: 21222324 BOARD: ['++++++++++', '++++++++++', '++-+-+---+', '+--+----+-', '-+---+----', '+++++++++-', '++++--+---', '+-+--+++++', '--+-+---+-', '+-+----+++', ''] SOLUTION: 3234363738 [...] BOARD: ['++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '-+++-+++++', '+++--+-+--', '++++++++++', '++++++++++', '++++++++++', ''] SOLUTION: 6064 BOARD: ['++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '--+++--+--', '-+++-+++++', '++++++++++', '++++++++++', ''] SOLUTION: 707175767879 BOARD: ['++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '-+-+++++++', '--+++--+--', '++++++++++', ''] SOLUTION: 8082 BOARD: ['++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '+---+--+--', '-+-+++++++', ''] SOLUTION: 91929395969899 BOARD: ['Solved!!! Have a fun and finally you will get a flag', ''] ['Solved!!! Have a fun and finally you will get a flag', ''] Solved: 1 FLAG: ['+---+-+---', '-------+--', '---+-++--+', '+++-++---+', '++-+--++-+', '---++-+---', '+++++---+-', '--+----+++', '+---+-+-+-', '-+--------', ''] SOLUTION: 11121315171819 BOARD: ['++++++++++', '+-+--+-++-', '-++---+++-', '+++-++---+', '++-+--++-+', '---++-+---', '+++++---+-', '--+----+++', '+---+-+-+-', '-+--------', ''] SOLUTION: 2123242629 BOARD: ['++++++++++', '++++++++++', '+-+------+', '+-++-++---', '++-+--++-+', '---++-+---', '+++++---+-', '--+----+++', '+---+-+-+-', '-+--------', ''] SOLUTION: 31333435363738 [...]
Das Board wurde tatsächlich gelöst! Jedoch scheint das nicht zu genügen. Der Aussage “have fun and finally you will get a flag” lässt vermuten, dass wir das Spielfeld mehrmals lösen müssen. Also lassen wir das Skript weiter laufen… 10, 20, 50, 75 … 100 Mal müssen wir das Board lösen, bevor wir diese Ausgabe erhalten:
[...]
BOARD: ['++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '-+-+-+-+--', '-+++++-+++', '++++++++++', '++++++++++', '']
SOLUTION: 707274767879
BOARD: ['++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '++-+-+++++', '-+-+-+-+--', '++++++++++', '']
SOLUTION: 8284
BOARD: ['++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '++++++++++', '--+++--+--', '++-+-+++++', '']
SOLUTION: 909195969899
BOARD: ['the flag is: 2e70bd4bbe1ed7c69a088c24c5a6fc95', '']
['the flag is: 2e70bd4bbe1ed7c69a088c24c5a6fc95', '']
Solved: 100
Die Lösung lautet somit “2e70bd4bbe1ed7c69a088c24c5a6fc95“.
UPDATE (17.05.2013): Nach dem Wettkampf wurde der Quellcode veröffentlicht. Wer Interesse hat, kann ihn sich deshalb zusätzlich ansehen:
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import random, socket, signal, sys, re, os, time
FLAG="2e70bd4bbe1ed7c69a088c24c5a6fc95"
PORT=2
Timeout=20
slow="""__________________________________________________________________
__________________________________________________________________
______________________________________†888888‡†___________________
_______________________________8†_†††††††††††††††††8†_____________
___________________________†‡_____††††††††††††††††††††8___________
________________________‡†_______†‡‡‡‡‡‡‡8††††††††††††_†‡†________
____________________‡†____†‡‡†_______________‡††††††††††††8_______
_______________________________________________†‡†††††††††‡‡______
_________________________________________________8†††††††††‡‡†____
___________________________________________________††††††††‡‡†8___
___________________________________________________8†††††††‡‡‡‡___
___________________________________________________8†††††††‡‡‡†___
___________________________________________________8††††††‡‡‡††___
___________________________†‡‡†††††††††††††‡8†_____††††††‡‡‡‡‡†___
_______________________†8††††††††††††††††††††††8†_8‡††††‡‡‡‡‡‡‡___
____________________‡††††††††††††††††††††††††††††††‡†††‡‡‡‡‡‡†8___
________‡‡††‡_†8‡††††††††††88†‡8†††‡8†††††††††††††††‡‡‡‡†‡‡‡‡‡____
______††††††8††††††††††††††††8†††888††8††††††††††††‡‡†8††††††‡____
______8†‡†8††††††††††††††††††‡†8††††††8††††††††††††‡‡‡‡¶††††8_____
_______‡‡__8†††††††††8____‡‡††††‡†††††‡†††††††††††‡‡‡‡††8†††______
________‡¶_8††††††_†8_______†††††‡8888††††††††††‡‡‡‡‡‡††‡8†_______
_______‡†‡†________‡8________‡††††††‡8†††††††‡‡‡‡‡‡‡‡‡‡‡‡‡________
_____8†________________†8‡__‡†††††‡‡‡‡†††‡‡‡‡‡‡‡‡‡‡†‡†‡‡†8________
___‡________________________‡8†††‡‡‡‡††‡‡†‡‡‡‡‡‡‡‡‡‡‡†‡†‡‡†_______
__†____‡_____‡_______________†8†‡‡‡††††‡‡‡‡‡‡‡‡‡†‡‡8††††‡††_______
___†_________________________†8††††††††††‡‡‡‡‡‡‡‡‡††††††‡‡†_______
_____8_‡__‡888‡††____††‡¶‡____‡‡†††††††††††‡‡†‡‡†¶†††††‡†‡________
_______†_¶8¶†††††††‡_†††8___†8‡‡††††††††††‡†8‡‡8_¶‡‡†††††‡________
________‡††¶¶††††††‡†8‡__†‡‡‡‡††8†††††††††‡†8______8‡‡__‡_________
________8‡‡____††††_____88††††††††‡‡‡†††††‡†8_____________________
______†††‡‡__‡‡†___‡‡8______________8‡‡‡888‡†_____________________
______________________________________†¶___‡______________________"""
class Field:
def __init__(self):
self.w = 10
self.h = 10
self.game = [0]*100
random.seed()
t=random.randint(15,85)
for i in range(t):
random.seed()
self.game[random.randint(0,99)]=1
def check(self):
if 0 in self.game:
return False
return True
def change(self, i):
self.game[i]=(self.game[i]+1)%2
def step(self, i):
if i>=self.w:
self.change(i-self.w)
if i<self.w*(self.h-1):
self.change(i+self.w)
if i%self.w!=0:
self.change(i-1)
if i%self.w!=self.w-1:
self.change(i+1)
self.change(i)
def write(self, stream):
screen = ""
for i in range(self.h):
for j in range(self.w):
if self.game[i*self.h+j]:
screen+='+'
else:
screen+='-'
screen+='\n'
stream.send(screen)
sock = socket.socket()
sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
sock.bind(('', PORT))
sock.listen(10)
signal.signal(signal.SIGCHLD, signal.SIG_IGN)
while 1:
client, addr = sock.accept()
if os.fork() == 0:
break
client.close()
sock.close()
f = Field()
client.send(
"""Be positive, change all minuses to pluses!
Rules: clicking on a cell changed it and it's neighbours.
Format:
a) "\d\d" - number of cell
b) "(?:\d\d)+" numbers of cells
""")
def handle(line):
if len(line) < 1:
return (True, None)
if len(line) == 1 and line[0] in "qxQX":
return (False, "Bye")
global f
m = re.match("^[0-9]{2,}$",line)
if m is None or len(line)%2==1:
return (True, "Error input")
m=re.findall("[0-9]{2}",line)
m=map(int,m)
for i in m:
if i>=f.w*f.h:
return (True, "Error number")
for i in m:
f.step(i)
return (True, None)
data = ""
client.settimeout(Timeout)
games=0
try:
while 1:
if f.check():
games+=1
f = Field()
if games==100:
client.send("the flag is: "+FLAG+"\n")
sys.exit(0)
client.send("Solved!!! Have a fun and finally you will get a flag\n")
f.write(client)
data=client.recv(4096)
if len(data)==0:
sys.exit(0)
cont, msg = handle(data.replace('\n',''))
if msg!=None:
client.send(msg + "\n")
if cont==False:
client.close()
sys.exit(0)
except socket.timeout:
client.send("So sloooow\n"+slow+"\n")
sys.exit(0)
sys.exit(0)