CSAW CTF Qualification Round 2013 Misc 300 Life

0x00 题目

http://en.wikipedia.org/wiki/Conways_Game_of_Life

nc 128.238.66.216 45678

0x01 解题

连接服务器后，会显示类似的图案:

##### Round 1: 25 Generations ##### 
####################### 
#           *         # 
#*         *          # 
# *                 * # 
# * **        *    ***# 
# **  *      **       # 
#**    *       *      # 
# *             *     # 
#      *        *     # 
#     *    * *   *    # 
#  * *                # 
# *              *    # 
#     *           *   # 
#       *             # 
#           **        # 
#      *              # 
#                     # 
#                *    # 
#         **          # 
#        *     *     *# 
#       *    *  **  * # 
#######################

先介绍一下康威生命游戏（Conway’s Game of Life）

玩过康威生命游戏（Conway’s Game of Life）都知道其中规则和原理，如果不知道可以了解一下：

生命游戏中，对于任意细胞(用方格表示)，规则如下：
每个细胞有两种状态-存活或死亡，每个细胞与以自身为中心的周围八格细胞产生互动。（如图，黑色为存活，白色为死亡）

1.当前细胞为存活状态时，当周围低于2个（不包含2个）存活细胞时， 该细胞变成死亡状态。（模拟生命数量稀少）
2.当前细胞为存活状态时，当周围有2个或3个存活细胞时， 该细胞保持原样。
3.当前细胞为存活状态时，当周围有3个以上的存活细胞时，该细胞变成死亡状态。（模拟生命数量过多）
4.当前细胞为死亡状态时，当周围有3个存活细胞时，该细胞变成存活状态。 （模拟繁殖）

可以把最初的细胞结构定义为种子，当所有在种子中的细胞同时被以上规则处理后, 可以得到第一代细胞图。按规则继续处理当前的细胞图，可以得到下一代的细胞图，周而复始。

我们可以把计算机中的宇宙想象成是一堆方格子构成的封闭空间，尺寸为N的空间就有N x N个格子，这里’#’用来表示边界。而每一个格子都可以看成是一个生命体，每个生命都有生和死两种状态，如果该格子生就用’*’显示，死则显示空白。每一个格子旁边都有邻居格子存在，如果我们把3x3的9个格子构成的正方形看成一个基本单位的话，那么这个正方形中心的格子的邻居就是它旁边的8个格子。

每个格子的生死遵循下面的原则：

1.如果一个细胞周围有3个细胞为生（一个细胞周围共有8个细胞），则该细胞为生（即该细胞若原先为死，则转为生，若原先为生，则保持不变） 。
2.如果一个细胞周围有2个细胞为生，则该细胞的生死状态保持不变；
3.在其它情况下，该细胞为死（即该细胞若原先为生，则转为死，若原先为死，则保持不变）

设定图像中每个像素的初始状态后依据上述的游戏规则演绎生命的变化，由于初始状态和迭代次数不同，将会得到令人叹服的优美图案。

了解完基本规则和原理之后，我们再来尝试做题，题目要求在较短的时间内将给出的当前世界(每个细胞的存活状态情况)的下一代的变化世界(下一代每个细胞的存活状态情况)，实际上就是一道根据规则socket编程题目，这里给出Shellphish中cao的参考示例：

#!/usr/bin/env python3 
# -*- coding: utf-8 -*- 
 
__author__ = "cao" 
__description__ = "csaw2013q: misc300/life; game of life solver" 
__version__ = "1.0-cleanedup" 
 
 
from re import compile 
from socket import socket 
from time import sleep 
 
from numpy import array, int8 
from scipy.ndimage.filters import convolve 
 
 
weights = array([[1, 1, 1], [1, 10, 1], [1, 1, 1]]) 
re_round_generations = compile("##### Round (?P<round>[0-9]+): " 
                               "(?P<generations>[0-9]+) Generations #####") 
 
 
def step(world): 
    # alternative method is: wrap 
    conv = convolve(world, weights, mode="constant") 
    return int8((conv == 3) | (conv == 12) | (conv == 13)) 
 
 
def _decode(i): 
    if i == "*": 
        return 1 
    else: 
        return 0 
 
 
def _encode(i): 
    if i: 
        return "*" 
    else: 
        return " " 
 
# ================================== 
 
s = socket() 
s.connect(("128.238.66.216", 45678)) 
 
f = s.makefile() 
 
for _round in range(1, 101): 
    print("Round: {}\r".format(_round), end="") 
    f.readline()    # Read the one empty line 
    match = re_round_generations.match(f.readline()) 
    generations = int(match.group("generations")) 
 
    border = f.readline().strip() 
    width = len(border) 
 
    # read in world and convert to numbers 
    world = [] 
    while True: 
        ls = f.readline().strip() 
        if ls.startswith("##"): 
            break 
 
        ls = ls[1:-1] 
        world.append([_decode(l) for l in ls]) 
 
    for i in range(generations): 
        world = step(world) 
 
    solution = ["".join(_encode(i) for i in b) for b in world] 
    game = "\n".join("#{}#".format(i) for i in solution) 
    total = "{0}\n{1}\n{0}\n".format(border, game) 
    s.send(bytes(total, "ascii")) 
 
# give them a second to catch up, we got big internet tubes 
sleep(1) 
 
print(str(s.recv(4096)).strip())

最后结果：

Congratulations!You made it!Here's your prize: key{that comp sci assignment was useful after all}

如果你感兴趣，可以去体验一下在线模拟康威生命游戏。