Auch in bei dieser Challenge (Sudoku) werden wenig Informationen vorab gegeben. Nur chinesische Schriftzeichen stechen hervor, die nach kurzer Anwendung des Google-Translators als “Sudoku” übersetzt werden.
Für einen ersten Überblick verbinden wir uns zu dem angegebenen Server und bekommen folgende Ausgabe:
MANUAL: Have a nice time with sudoku
Format:
a) "[1-9] [1-9] [1-9]" - coords and input digit
b) "solution [1-9]{81}" - full solution
Other:
"restart" to start current game again
"[QqXx]" to exit
-------------
|97_|164|__2|
|__1|5_2|_9_|
|325|_9_|16_|
-------------
|__9|_2_|37_|
|_16|3_5|_4_|
|753|__8|___|
-------------
|5__|78_|419|
|837|_19|2__|
|_94|256|78_|
-------------
Wie erwartet – und bei diesem Capture the Flag auch nicht das erste Mal – muss ein Spiel automatisiert gelöst werden. Wir haben die Möglichkeit, entweder (a) die Felder einzeln anzugeben und so schrittweise eine Lösung zu erzeugen oder (b) die Lösung des gesamten Feldes direkt vorzugeben.
Ich habe mich für den zweiten Weg entschieden, nämlich das Feld lokal automatisiert zu lösen und nur das endgültige Feld abzusenden. Dafür habe ich ein Python-Skript entwickelt, das ich im Folgenden schrittweise erläutern möchte:
#!/usr/bin/env python
import socket
import time
import random
import copy
s=socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("194.106.195.60",9503))
# fetch manual
data = s.recv(1024)
print "MANUAL: " + data
# fetch board
board = s.recv(1024).translate(None, "|-").split("\n")
board.remove('')
board.remove('')
board.remove('')
board.remove('')
board.remove('')
for y in range(9):
board[y] = list(board[y])
print "BOARD: " + str(board)
backup = []
guess = -1
solved = 0
Zuerst wird eine Verbindung zum Server hergestellt (Zeile 8) und die Anleitung eingelesen sowie ausgegeben (Zeilen 11-12). Anschließend wird das Spielfeld (board) eingelesen (Zeile 15), unnötige Anteile entfernt (Zeilen 16-20) und in eine Liste von Listen (damit sie später on-the-fly editiert werden können) umgewandelt (Zeilen 21-22). Zuletzt werden noch einige Variablen vorbelegt.
Beim Datenmodell für das Sudoku-Board handelt es sich daher um ein zweidimensionales Array (eine Liste von Listen), deren Inhalt über “board[y][x]” ausgelesen und verändert werden kann.
while 1:
found = 0
for y in range(9):
for x in range(9):
if board[y][x] == "_":
possible = [ "1", "2", "3", "4", "5", "6", "7", "8", "9" ]
# CHECK LINE
for i in range(9):
if board[y][i] in possible:
possible.remove(board[y][i])
# CHECK ROW
for i in range(9):
if board[i][x] in possible:
possible.remove(board[i][x])
# CHECK SQUARE
sy = (y/3) * 3
sx = (x/3) * 3
for i in range(sy,sy+3):
for j in range(sx,sx+3):
if board[i][j] in possible:
possible.remove(board[i][j])
Nun beginnt das eigentliche Lösen des Spielfeldes. Über alle Zeilen und Spalten wird enumiert und alle Felder, die nicht belegt sind (“_”) werden betrachtet (Zeilen 3-5). Es wird eine Liste erzeugt, die alle möglichen Belegungen für das entsprechende Feld enthält – also von 0 bis 9 (Zeile 6).
Anschließend wird die gesamte Zeile (Zeilen 8-11), die gesamte Spalte (Zeilen 13-16) und der gesamte Block (Zeilen 18-24) überprüft. Alle Zahlen, die sich in einem dieser Elemente befinden, werden aus der Liste möglicher Belegungen (possible) entfernt. So bleiben nur die wirklich möglichen Belegungen für die betrachtete Position übrig.
if len(possible) == 0:
## GUESSING FAILED!!
board = copy.deepcopy(backup)
found = 0
else:
if len(possible) == 1:
board[y][x] = possible[0]
found = 1
else:
if (guess != -1) and (guess == y):
r = random.randint(0,len(possible)-1)
# print "GUESSED " + str(y) + "," + str(x) + " to " + str(possible[r])
board[y][x] = possible[r]
found = 1
guess = -1
guess = -1
Sollte nach der Überprüfung aller Elemente nichts mehr für die betrachtete Position möglich sein, dann ist das gesamte Spielfeld ungültig, da irgendwann falsch geraten wurde. In diesem Fall wird zu einer früheren Backup-Kopie des Spielfeldes zurück gekehrt (Zeilen 1-4).
Wenn nur eine einzige Belegung möglich ist, dann muss es sich dabei um die korrekte Lösung für die Position handeln und sie wird dem Board zugewiesen (Zeilen 5-8). Wenn jedoch noch mehrere Belegungen möglich sind, und die aktuelle Zeile zum Raten bestimmt wurde (folgt später), dann soll eine zufällige, noch mögliche Belegung geraten werden (Zeilen 9-15).
if found == 0:
solution = ""
for y in range(9):
solution = solution + "".join(board[y])
if "_" in solution:
guess = random.randint(0,9)
if backup == []:
backup = copy.deepcopy(board)
# print "CANNOT SOLVE! GUESSING LINE: " + str(guess)
continue
else:
print "SOLUTION: " + solution
s.send("solution " + solution)
solved += 1
print "Solved: " + str(solved) + "x"
if (solved == 100):
while 1:
print s.recv(1024)
Sollte bis zu diesem Zeitpunkt noch keine einzige Position im Spielfeld geändert worden sein (Zeile 1), dann generiere einen Lösungsstring (Zeilen 2-4). Wenn sich in dieser Lösung noch eine unbelegte Position (“_”) befinden sollte (Zeile 5), dann wird soll eine zufällige Zeile geraten und vorher eine Kopie des Spielfeldes angelegt werden (Zeilen 6-10), zu der bei Misserfolg später zurück gekehrt werden kann.
Sollte sich jedoch keine unbelegte Position mehr in der Lösung befinden (Zeile 11), haben wir eine gültige Lösung des gesamten Spielfeldes gefunden (Zeile 12). Diese wird anschließend zum Server gesendet und der Zähler erhöht (Zeilen 14-15). Da wie im vorherigen Spiel auch hier 100 Mal eine Lösung gefunden werden muss, wird nach 100 Erfolgen die Flagge ausgelesen (Zeilen 18-20).
Wenn wir das Skript nun ausführen, erhalten wir diese Ausgabe:
rup0rt@lambda:~/BaltCTF2013$ ./sudoku.py
BOARD: [['7', '5', '_', '_', '9', '_', '3', '_', '_'], ['_', '1', '4', '_', '_', '_', '2', '7', '5'], ['_', '_', '_', '2', '7', '5', '4', '$
SOLUTION: 752491386914386275863275491148763952637952814529814763486537129375129648291648537
Solved: 1x
GOT: Wow!!!
Solved!!! Have a fun and finally you will get a flag
[...]
BOARD: [['_', '_', '_', '3', '_', '_', '_', '_', '_'], ['_', '4', '5', '_', '_', '_', '_', '_', '_'], ['_', '_', '2', '_', '9', '6', '_', '_
', '_'], ['9', '6', '_', '_', '_', '_', '1', '2', '7'], ['_', '_', '_', '_', '_', '7', '_', '_', '_'], ['1', '_', '_', '9', '6', '_', '_', '
_', '_'], ['_', '_', '1', '_', '7', '_', '_', '_', '_'], ['_', '_', '_', '6', '3', '_', '_', '8', '_'], ['_', '_', '_', '5', '_', '1', '2',
'7', '9']]
SOLUTION: 698352714345718962712496835963845127854127396127963458581279643279634581436581279
Solved: 100x
Wow!!!
the flag is: 328df3b4525e060de963a20d3cc86579
Die Lösung lautet daher “328df3b4525e060de963a20d3cc86579“.
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
from copy import copy, deepcopy
FLAG="328df3b4525e060de963a20d3cc86579"
PORT=3
Timeout=10
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 Sudoku:
def __init__(self):
a=[[''for j in range(9)]for i in range(9)]
t=range(1,10)
random.seed()
random.shuffle(t)
k=0
for i in range(9):
if i==3 or i==6: k+=1
for j in range(9):
a[i][j]=str(t[(j+k)%9])
k+=3
for t in range(20):
i=random.choice([0,3,6])
j=random.choice(filter(lambda x: x!=i,[0,3,6]))
for k in range(9):
for l in range(3):
a[k][i+l],a[k][j+l]=a[k][j+l],a[k][i+l]
i=random.choice([0,3,6])
j=random.choice(filter(lambda x: x!=i,[0,3,6]))
for k in range(9):
for l in range(3):
a[i+l][k],a[j+l][k]=a[j+l][k],a[i+l][k]
for s in [[0,1,2],[3,4,5],[6,7,8]]:
i=random.choice(s)
j=random.choice(filter(lambda x: x!=i,s))
for k in range(9):
a[i][k],a[j][k]=a[j][k],a[i][k]
i=random.choice(s)
j=random.choice(filter(lambda x: x!=i,s))
for k in range(9):
a[k][i],a[k][j]=a[k][j],a[k][i]
self.a=deepcopy(a)
#print self.prov(a)
#print "solution "+''.join([''.join(i) for i in a])
t=0
k=random.randint(30,60)
while t!=k:
i=random.randint(0,8)
j=random.randint(0,8)
if a[i][j]!='_':
a[i][j]='_'
t+=1
self.field=deepcopy(a)
self.game=deepcopy(a)
def prov(self, a):
b=[0]*27
for i in range(9):
for j in range(9):
b[i]+=int(a[i][j])
b[9+j]+=int(a[i][j])
b[18+(i/3)*3+j/3]+=int(a[i][j])
return b.count(45)==27
def restart(self):
self.game=deepcopy(self.field)
def check(self,x,y,t):
a=self.game
gor=a[x-1]
ver=[a[k][y-1] for k in range(9)]
i,j=((x-1)/3)*3,((y-1)/3)*3
sq=[a[i][j],a[i][j+1],a[i][j+2],a[i+1][j],a[i+1][j+1],a[i+1][j+2],a[i+2][j],a[i+2][j+1],a[i+2][j+2]]
return not(t in gor or t in ver or t in sq)
def final_check(self):
return ''.join([''.join(i) for i in self.game]).find('_')==-1
def full(self, m):
a=[[''for j in range(9)]for i in range(9)]
for i in range(9):
for j in range(9):
if self.field[i][j]==m[i*9+j] or self.field[i][j]=='_': a[i][j]=m[i*9+j]
else: return "Error"
if self.prov(a):
self.game=deepcopy(a)
return "Wow!!!"
else: return "Error"
def step(self,x,y,t):
if self.field[x-1][y-1]=='_' and self.check(x,y,t):
self.game[x-1][y-1]=t
return "Nice step"
return 'Impossible step'
def write(self, client):
a=self.game[:][:]
s=''
for i in range(9):
if i%3==0: s+='-------------\n'
s+='|'+''.join(a[i][0:3])+'|'+''.join(a[i][3:6])+'|'+''.join(a[i][6:9])+'|\n'
s+='-------------\n'
client.send(s)
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 = Sudoku()
client.send(
"""Have a nice time with sudoku
Format:
a) "[1-9] [1-9] [1-9]" - coords and input digit
b) "solution [1-9]{81}" - full solution
Other:
"restart" to start current game again
"[QqXx]" to exit
""")
def handle(line):
if len(line) < 1:
return (True, None)
if len(line) == 1 and line[0] in "qxQX":
return (False, "Bye")
global f
if line=='restart':
f.restart()
return (True,'Start again')
m = re.match("^solution [1-9]{81}$",line)
if m != None:
m=re.findall("[1-9]{81}",line)[0]
return(True, f.full(m))
m = re.match("^[1-9] [1-9] [1-9]$",line)
if m != None:
m=re.findall("[1-9]",line)
return (True, f.step(int(m[0]),int(m[1]),m[2]))
return (True, "Error input")
data = ""
client.settimeout(Timeout)
games=0
try:
while 1:
if f.final_check():
games+=1
f = Sudoku()
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)