

题目¶

2016 Google CTF woodman¶

程序的大概意思就是一个猜数游戏，如果连续猜中若干次，就算会拿到 flag，背后的生成相应数的核心代码如下

class SecurePrng(object):
    def __init__(self):
        # generate seed with 64 bits of entropy
        self.p = 4646704883L
        self.x = random.randint(0, self.p)
        self.y = random.randint(0, self.p)

    def next(self):
        self.x = (2 * self.x + 3) % self.p
        self.y = (3 * self.y + 9) % self.p
        return (self.x ^ self.y)

这里我们显然，我们猜出前两轮还是比较容易的，毕竟概率也有 0.25。这里当我们猜出前两轮后，使用 Z3 来求解出初始的 x 和 y，那么我们就可以顺利的猜出剩下的值了。

具体的脚本如下，然而 Z3 在解决这样的问题时似乎是有问题的。。。

这里我们考虑另外一种方法，依次从低比特位枚举到高比特位获取 x 的值，之所以能够这样做，是依赖于这样的观察

a + b = c，c 的第 i 比特位的值只受 a 和 b 该比特位以及更低比特位的影响。因为第 i 比特位进行运算时，只有可能收到低比特位的进位数值。
a - b = c，c 的第 i 比特位的值只受 a 和 b 该比特位以及更低比特位的影响。因为第 i 比特位进行运算时，只有可能向低比特位的借位。
a * b = c，c 的第 i 比特位的值只受 a 和 b 该比特位以及更低比特位的影响。因为这可以视作多次加法。
a % b = c，c 的第 i 比特位的值只受 a 和 b 该比特位以及更低比特位的影响。因为这可视为多次进行减法。
a ^ b = c，c 的第 i 比特位的值只受 a 和 b 该比特位的影响。这一点是显而易见的。

注：个人感觉这个技巧非常有用。

此外，我们不难得知 p 的比特位为 33 比特位。具体利用思路如下

首先获取两次猜到的值，这个概率有 0.25。
依次从低比特位到高比特位依次枚举第一次迭代后的 x 的相应比特位。
根据自己枚举的值分别计算出第二次的值，只有当对应比特位正确，可以将其加入候选正确值。需要注意的是，这里由于取模，所以我们需要枚举到底减了多少次。
此外，在最终判断时，仍然需要确保对应的值满足一定要求，因为之前对减了多少次进行了枚举。

具体利用代码如下

import os
import random
from itertools import product


class SecurePrng(object):
    def __init__(self, x=-1, y=-1):
        # generate seed with 64 bits of entropy
        self.p = 4646704883L  # 33bit
        if x == -1:
            self.x = random.randint(0, self.p)
        else:
            self.x = x
        if y == -1:
            self.y = random.randint(0, self.p)
        else:
            self.y = y

    def next(self):
        self.x = (2 * self.x + 3) % self.p
        self.y = (3 * self.y + 9) % self.p
        return (self.x ^ self.y)


def getbiti(num, idx):
    return bin(num)[-idx - 1:]


def main():
    sp = SecurePrng()
    targetx = sp.x
    targety = sp.y
    print "we would like to get x ", targetx
    print "we would like to get y ", targety

    # suppose we have already guess two number
    guess1 = sp.next()
    guess2 = sp.next()

    p = 4646704883

    # newx = tmpx*2+3-kx*p
    for kx, ky in product(range(3), range(4)):
        candidate = [[0]]
        # only 33 bit
        for i in range(33):
            #print 'idx ', i
            new_candidate = []
            for old, bit in product(candidate, range(2)):
                #print old, bit
                oldx = old[0]
                #oldy = old[1]
                tmpx = oldx | ((bit & 1) << i)
                #tmpy = oldy | ((bit / 2) << i)
                tmpy = tmpx ^ guess1
                newx = tmpx * 2 + 3 - kx * p + (1 << 40)
                newy = tmpy * 3 + 9 - ky * p + (1 << 40)
                tmp1 = newx ^ newy
                #print "tmpx:    ", bin(tmpx)
                #print "targetx: ", bin(targetx)
                #print "calculate:     ", bin(tmp1 + (1 << 40))
                #print "target guess2: ", bin(guess1 + (1 << 40))
                if getbiti(guess2 + (1 << 40), i) == getbiti(
                        tmp1 + (1 << 40), i):
                    if [tmpx] not in new_candidate:
                        #print "got one"
                        #print bin(tmpx)
                        #print bin(targetx)
                        #print bin(tmpy)
                        new_candidate.append([tmpx])
            candidate = new_candidate
            #print len(candidate)
            #print candidate
        print "candidate x for kx: ", kx, " ky ", ky
        for item in candidate:
            tmpx = candidate[0][0]
            tmpy = tmpx ^ guess1
            if tmpx >= p or tmpx >= p:
                continue
            mysp = SecurePrng(tmpx, tmpy)
            tmp1 = mysp.next()
            if tmp1 != guess2:
                continue
            print tmpx, tmpy
            print(targetx * 2 + 3) % p, (targety * 3 + 9) % p


if __name__ == "__main__":
    main()

2017 Tokyo Westerns CTF 3^rd Backpacker's Problem¶

题目中给了一个 cpp 文件，大概意思如下

Given the integers a_1, a_2, ..., a_N, your task is to find a subsequence b of a
where b_1 + b_2 + ... + b_K = 0.

Input Format: N a_1 a_2 ... a_N
Answer Format: K b_1 b_2 ... b_K

Example Input:
4 -8 -2 3 5
Example Answer:
3 -8 3 5

即是一个背包问题。其中，在本题中，我们需要解决 20 个这样的背包问题，背包大小依次是 1 * 10~20 * 10。而子集求和的背包问题是一个 NPC 问题，问题的时间复杂度随着随着背包大小而指数增长。这里背包的大小最大是200，显然不可能使用暴力破解的方式。

待完成

题目¶

2016 Google CTF woodman¶

2017 Tokyo Westerns CTF 3rd Backpacker's Problem¶

参考文献¶

2017 Tokyo Westerns CTF 3^rd Backpacker's Problem¶