saltcandy123

SECCON 2013 CTF Online Quals に参加しました

参加しました

SECCON 2013 CTF オンライン予選にチームで参加しました。

私は結局のところ、『数「毒」ちゃれんじ★』のみの解答でした。 もはや CTF をやっているか怪しいレベルなので、精進したいと思います。 そのうち。

『数「毒」ちゃれんじ★』の Writeup

各ステージで数独の問題が与えられます。 X の部分だけ可変でその値が問題ごとに与えられますが、特にひねりもないので、やるだけです。方針としては、数独のルールに則って確実に埋めていったあと、まだ埋まっていないマスがあればバックトラック法で無理やり埋める方法でいきました。

コード (Python 3)

変に長いので、ご注意ください。

#!/usr/bin/env python3

import copy
import re
import telnetlib
import time


def generate_xy():
    return ((i%9, i//9) for i in range(81))

class Square(object):
    def __init__(self):
        self.boolcube = [[[True for n in range(9)]
                          for y in range(9)]
                         for x in range(9)]
        self.numbers = [[None for y in range(9)] for x in range(9)]

    def copy(self):
        copied = self.__class__()
        copied.boolcube = copy.deepcopy(self.boolcube)
        copied.numbers = copy.deepcopy(self.numbers)
        return copied

    def pickup_candidates(self, x, y):
        return [n for n in range(9) if self.boolcube[x][y][n]]

    def fill(self, x, y, n):
        for i in range(9):
            px = x//3*3+i%3
            py = y//3*3+i//3
            self.boolcube[i][y][n] = False
            self.boolcube[x][i][n] = False
            self.boolcube[x][y][i] = False
            self.boolcube[px][py][n] = False
        self.boolcube[x][y][n] = True
        self.numbers[x][y] = n

    def ban(self, x, y, n):
        self.boolcube[x][y][n] = False

    def is_completed(self):
        for x, y in generate_xy():
            if self.numbers[x][y] is None:
                return False
        return True

    def is_valid(self):
        for x, y in generate_xy():
            if len(self.pickup_candidates(x, y)) == 0:
                return False
        return True

    def compute_impact_score(self, x, y, n):
        count = 0
        for i in range(9):
            px = x//3*3+i%3
            py = y//3*3+i//3
            count += 1 if self.boolcube[i][y][n] else 0
            count += 1 if self.boolcube[x][i][n] else 0
            count += 1 if self.boolcube[x][y][i] else 0
            count += 1 if self.boolcube[px][py][n] else 0
        if self.boolcube[x][y][n]:
            count -= 4
        return count


def count_solution(problem):
    has_changed = True
    while has_changed:
        has_changed = False
        for x, y in generate_xy():
            if problem.numbers[x][y] is not None:
                continue
            candidates = problem.pickup_candidates(x, y)
            if len(candidates) == 1:
                problem.fill(x, y, candidates[0])
                has_changed = True
    if not problem.is_valid():
        return 0
    if problem.is_completed():
        return 1
    solutions = 0
    candidates = list()
    for x, y in generate_xy():
        if problem.numbers[x][y] is not None:
            continue
        for n in range(9):
            score = problem.compute_impact_score(x, y, n)
            candidates.append((score, x, y, n))
    candidates.sort(reverse=True)
    for score, x, y, n in candidates:
        copied = problem.copy()
        copied.fill(x, y, n)
        problem.ban(x, y, n)
        solutions += count_solution(copied)
    return solutions

def decode_numbers(square_string):
    pattern = re.compile('\\w ' + '\\|(.)'*9)
    lines = square_string.replace('\r', '').split('\n')
    index = 0
    numbers = [[None for y in range(9)] for x in range(9)]
    for y in range(9):
        while True:
            matched = pattern.search(lines[index])
            index += 1
            if matched is None:
                continue
            for x in range(9):
                s = matched.group(x+1)
                if s == '.':
                    s = None
                elif s != 'X':
                    s = int(s)-1
                numbers[x][y] = s
            break
    return numbers

def decode_xinfo(xinfo):
    matched = re.search('if \'X\' is (\\d+), how many solutions', xinfo)
    if matched is None:
        raise Exception
    return int(matched.group(1))-1

def generate_answer(numbers, xvalue):
    problem = Square()
    for x, y in generate_xy():
        if numbers[x][y] is None:
            continue
        if numbers[x][y] == 'X':
            problem.fill(x, y, xvalue)
        else:
            problem.fill(x, y, numbers[x][y])
    solutions = count_solution(problem)
    return str(solutions)

def main():
    tn = telnetlib.Telnet('133.242.48.175', 65434)
    while True:
        time.sleep(0.5)
        problem_string = tn.read_very_eager().decode()
        if 'Stage' in problem_string:
            numbers = decode_numbers(problem_string)
        print(problem_string, end='')
        x = decode_xinfo(problem_string)
        answer = generate_answer(numbers, x)
        print(answer)
        tn.write(answer.encode()+b'\n')

if __name__ == '__main__':
    main()

途中経過

'suDOKU(su-poison)' challenge for SECCON 2013.
by KeigoYAMAZAKI, 2013.11.22-

* Stage 1

   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |6|4|2|.|X|5|.|8|9|
B |.|.|.|.|.|7|1|3|.|
C |1|.|.|.|9|.|.|2|.|
  $-+-+-$-+-+-$-+-+-$
D |3|.|.|.|2|6|.|.|.|
E |7|.|.|8|.|9|.|.|2|
F |2|8|.|.|7|4|6|1|.|
  $-+-+-$-+-+-$-+-+-$
G |.|7|1|.|.|3|.|6|.|
H |.|6|3|7|.|.|.|.|1|
I |5|.|8|.|6|.|.|7|.|
  $-+-+-$-+-+-$-+-+-$

if 'X' is 1, how many solutions does this sudoku have?  => 1
if 'X' is 3, how many solutions does this sudoku have?  => 2

*** Good job!

* Stage 2

   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |X|5|.|.|.|.|.|.|.|
B |.|.|6|5|7|3|2|.|.|
C |.|.|2|8|4|.|.|.|5|
  $-+-+-$-+-+-$-+-+-$
D |.|.|8|.|3|7|9|.|1|
E |.|6|1|.|9|.|.|.|.|
F |5|.|7|4|.|.|.|.|.|
  $-+-+-$-+-+-$-+-+-$
G |7|.|.|9|.|.|.|3|2|
H |.|.|.|.|.|.|.|4|.|
I |6|.|.|.|.|.|7|.|8|
  $-+-+-$-+-+-$-+-+-$

if 'X' is 1, how many solutions does this sudoku have?  => 0
if 'X' is 3, how many solutions does this sudoku have?  => 0
if 'X' is 4, how many solutions does this sudoku have?  => 1
if 'X' is 8, how many solutions does this sudoku have?  => 3
if 'X' is 9, how many solutions does this sudoku have?  => 12

*** Good job!

* Stage 3

   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |.|3|5|1|6|4|.|.|9|
B |7|9|.|.|5|3|.|.|4|
C |.|.|1|.|.|.|5|2|3|
  $-+-+-$-+-+-$-+-+-$
D |3|5|4|6|7|.|.|.|.|
E |.|.|6|9|.|.|3|.|.|
F |.|2|7|3|.|5|.|4|1|
  $-+-+-$-+-+-$-+-+-$
G |4|6|.|5|.|7|2|.|8|
H |.|1|.|.|.|.|4|7|6|
I |8|.|X|4|.|.|9|.|.|
  $-+-+-$-+-+-$-+-+-$

if 'X' is 2, how many solutions does this sudoku have?  => 2
if 'X' is 3, how many solutions does this sudoku have?  => 1

*** Good job!

* Stage 4

   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |.|.|2|1|.|.|6|.|.|
B |1|.|5|.|8|.|.|.|.|
C |8|X|.|.|.|9|.|.|.|
  $-+-+-$-+-+-$-+-+-$
D |.|.|7|.|.|.|5|.|.|
E |.|.|.|6|.|.|3|.|8|
F |.|3|.|5|2|4|.|.|1|
  $-+-+-$-+-+-$-+-+-$
G |2|8|.|4|.|.|.|.|6|
H |6|.|.|9|.|3|8|2|.|
I |.|5|9|.|.|.|.|.|3|
  $-+-+-$-+-+-$-+-+-$

if 'X' is 4, how many solutions does this sudoku have?  => 2
if 'X' is 6, how many solutions does this sudoku have?  => 0
if 'X' is 7, how many solutions does this sudoku have?  => 1

*** Good job!

* Stage 5

   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |.|.|.|2|3|5|8|4|9|
B |2|5|.|.|4|.|.|.|.|
C |3|4|.|X|8|.|.|5|.|
  $-+-+-$-+-+-$-+-+-$
D |.|8|2|9|5|.|.|6|.|
E |1|.|.|6|.|8|5|.|4|
F |6|.|.|3|.|.|1|9|8|
  $-+-+-$-+-+-$-+-+-$
G |.|6|.|8|.|2|.|7|.|
H |.|3|1|.|.|.|.|.|.|
I |.|.|.|5|9|.|.|1|.|
  $-+-+-$-+-+-$-+-+-$

if 'X' is 1, how many solutions does this sudoku have?  => 2
if 'X' is 7, how many solutions does this sudoku have?  => 1

*** Good job!

* Stage 6

   1 2 3 4 5 6 7 8 9 
  $-+-+-$-+-+-$-+-+-$
A |8|1|.|2|.|5|4|6|7|
B |.|.|.|.|7|6|1|8|9|
C |.|6|.|.|8|.|3|5|2|
  $-+-+-$-+-+-$-+-+-$
D |1|.|.|9|2|4|.|3|X|
E |.|9|3|8|6|.|.|1|4|
F |7|4|.|3|5|1|.|2|.|
  $-+-+-$-+-+-$-+-+-$
G |.|.|.|6|1|8|2|7|5|
H |.|.|.|7|4|3|.|.|1|
I |6|.|.|5|.|.|8|4|3|
  $-+-+-$-+-+-$-+-+-$

if 'X' is 6, how many solutions does this sudoku have?  => 2
if 'X' is 8, how many solutions does this sudoku have?  => 1

*** Good job!



*************************************************************************
*** Congratulations! Flag is 'iitai-koto mo ienai konna yononaka-ja!' ***
*************************************************************************

フラグが得られました。ぱちぱち。