October 23, 2016

HITCON 2016 - Sharingan

It is no fair play. Can you win?


38 Teams solved.

nc 31337



I started by playing around with the program locally. It turns out to be a Go AI with very interesting rule: As soon as the white stone (me) tries to capture black stone (AI), so called “Isanagi” is activated. As a result of “Isanagi”, that last capturing white stone turns black! Other than this unfair rule, it is a very basic AI that plays pure Mirror Go. If there’s no way to mirror the last move, it randomly pick a valid move.

At first I tried to apply some well known mirror go refutations but because of the Isanagi rule, they don’t seem to work. It looks like there’s no easy way to beat this simple AI unless there’s fundamental flaw in the program.

And there is.

def main
  brd = Array.new(N){Array.new(N){EMPTY}}
  who = 0
  loop do
    color = color_of who
    case who
    when 0 then x, y = ai(brd, color)
    when 1 then x, y = player(brd, color)
    next if x.nil?
    brd[x][y] = color
    if who == 1 and will_capture(brd, x, y, color)
      puts "Isanagi activated!"
      brd[x][y] = exchg(brd[x][y])
    N.times do |a|
      N.times do |b|
        next if brd[a][b] == EMPTY || brd[a][b] == color
        capture!(brd, a, b) if not alive?(brd, a, b, Set.new)
    @last_x, @last_y = x, y
    who ^= 1
    show(brd) and flag if win(brd) # <<< checks at every iteration

It turns out the program checks the winning condition at every iteration. It checks if there’re more white stones than black stones right after the white stone’s move, before the mirror happens. This means if I can capture and remove two (because black takes first move) black stones in one move, it will show me the flag!

That’s easy enough. Since AI simply mirror my move, I can pre-capture an area with three holes, put two black stones into them, and fill the last hole with white stone. The Isanagi rule will turn the last white stone into black. Because it is pre-captured, all three black stones will be removed. In the last move, one white stone and two black stones were removed, temporarily leaving more white stones than black stones, and prints the flag.

So the final solution:

$ print "0 1\n1 1\n2 1\n3 1\n3 0\n18 18\n17 18\n2 0" | nc 31337

© jiulongw 2016