0x01 题目描述

111

📎subset.py：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#!/usr/bin/env python3
from random import randint
import sys
import os

flag = str(os.getenv('FLAG')).encode()

def die(*args):
    print_something(*args)
    quit()

def print_something(*args):
    s = " ".join(map(str, args))
    sys.stdout.write(s + "\n")
    sys.stdout.flush()

def scan():
    return sys.stdin.buffer.readline()

def subset_process(n, l, K, A):
    A, K = set(A), set(K)
    return [pow(_, 2, n) + randint(0, 1) for _ in A - K]

def main():
    border_plus = "[+]"
    border_sub = "[-]"
    print_something(border_plus, "You need to complete something before I can give you what you ultimately need! Are you ready? ")
    print_something(border_plus, "eg: 1,2,3,4")
    _flag = False
    n, l = 127, 20
    N = set(list(range(n)))
    K = [randint(0, n-1) for _ in range(l)]
    COUNT, STEP = 0, 2 * n // l - 1

    while True:
        ans = scan().decode().strip()
        try:
            _A = [int(_) for _  in ans.split(',')]
            if len(_A) <= l and set(_A).issubset(N):
                someting = subset_process(n, l, K, _A)
                print_something(border_plus, f'someting = {someting}')
                if set(_A) == set(K):
                    _flag = True
            else:
                die(border_sub, 'Exception! Bye!!')
        except Exception:
            die(border_sub, 'Your input is not valid! Bye!!')
        if _flag:
            die(border_plus, f'Congrats! the flag: {flag}')
        if COUNT > STEP:
            die(border_sub, 'Too many tries, bye!')
        COUNT += 1

if __name__ == '__main__':
	main()

0x02 解题思路

题目主要通过K = [randint(0, n-1) for _ in range(l)]生成一个长度为l，元素范围0到(n-1)的set集合，该语句等效以下代码段：

1
2
3
K = []
for _ in range(l): #循环l次
  K.append(randint(0, n-1))

最终需要输入一个集合_A使得，才能得到flag：

1
2
if set(_A) == set(K):
	_flag = True

而中间可以通过subset_process(n, l, K, A)函数猜测输入的集合_A有哪些元素可能存在于子集K中，一共有11次机会。

1
2
3
def subset_process(n, l, K, A):
    A, K = set(A), set(K)
    return [pow(_, 2, n) + randint(0, 1) for _ in A - K]

每次输入_A之后，输出的内容是_A-K（即不存在于K的元素）的平方随机+1的结果，我们要做的就是还原出_A-K的内容。

设每次输入后得到的结果为result_list，则可以得到_A-K的元素有哪些，并记录到invalid列表中：

1
2
3
4
5
6
invalid = set()
for i in my_set:
  if pow(i,2,n) in result_list:
    invalid.add(i)
  if pow(i,2,n) in [b-1 for b in result_list]:
    invalid.add(i)

然后在输入的集合中将这些剔除掉即可，其中my_set是我们输入的_A集合的元素列表:

1
2
for i in my_set - invalid:
  current_K.add(i)

这样我们重复11次，即可求出最终需要的K，请特别注意需要判断输入的合法性。

使用python3 + pwntools完成交互解题脚本的编写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from pwn import *

r = remote("IP_address", 114514)
context.log_level = 'debug'
n, l = 127, 20
current_K = set()
fullset = set(range(1,128)) 

for _ in range(11):
    my_set = set()
    no_set = set()
    for i in fullset:
        t1 = pow(i,2,n)
        t2 = pow(i,2,n) + 1
        if t1 in no_set or t2 in no_set:
            continue
        no_set.add(t1)
        no_set.add(t2)
        my_set.add(i)
        if len(my_set) == l:
            fullset = fullset - my_set
            break
    r.sendline(",".join(map(str, list(my_set))))
    r.recvuntil(b"[+] someting = ")
    result_list = eval(r.recvline().decode().strip())

    invalid = set()
    for i in my_set:
        if pow(i,2,n) in result_list:
            invalid.add(i)
        if pow(i,2,n) in [b-1 for b in result_list]:
            invalid.add(i)
    for i in my_set - invalid:
        current_K.add(i)
    if len(current_K) == 20:
        r.sendline(",".join(map(str, list(current_K))))
        r.interactive()