题目

题目要求 flag 满足正则表达式 “flag{[!-z]{11}}”，也就是 flag 的花括号中包含 11 个 ASCII 字符：

1
flag{xxxxxxxxxxx}

题目代码使用 Sage 语法：将 flag 转换为整数后，与输入值进行按位异或，并重复进行 $7^7$ 次素性判断。由于判断结果组成的列表非空，断言条件可以通过；程序不会直接输出每次素性判断的结果。

1
2
3
4
5
6
7
8
9
10
11
12
assert (
    __import__('re').fullmatch(
        br'flag\{[!-z]{11}\}',
        flag := os.getenvb(b'FLAG')
    )
    and [
        is_prime(
            int(flag.hex(), 16) ^^ int(input('🌌 '))
        )
        for _ in range(7^7)
    ]
)

思路

设 flag 转换成的整数为

$$
m=\operatorname{int}(\text{flag.hex()},16).
$$

程序实际判断的是 $m\oplus x$ 是否为素数，其中 $x$ 是输入值。这里使用的是 Sage 语法：^ 表示幂运算，^^ 表示按位异或。

时间侧信道： 题目不会直接输出素性判断结果，但可以利用素性判断所需的时间差异，逐步求出 $m$ 模各个小素数的值，再使用中国剩余定理（CRT）恢复 flag。

求 $m\bmod 3$

记

$$
y=m\oplus x.
$$

由于 $m<2^{256}$ 且 $m$ 为奇数，构造 $x$ 为 $2^{256}$ 的倍数时，可以将 $m\oplus x$ 看作 $m+x$。分别构造三组输入，使 $y\bmod 3$ 遍历 ${0,1,2}$。当 $y\bmod 3=0$ 时，素性判断会更快返回。

可以构造输入

$$
x_{k,j}=(k+3j)2^{256},
\qquad
k\in{1,2,3},
\quad
j\in{1,2,3,\ldots}.
$$

求 $m\bmod 5$

为了观察 $m\bmod 5$，需要避免 $y$ 被 2 和 3 整除，否则这些较小素数会影响时间侧信道。

不能直接使用

$$
x=(k+5j)2^{256}
\qquad\text{或}\qquad
x=(k+15j)2^{256},
\quad
k\in{1,2,3,4,5}.
$$

这是因为还需要同时控制 $y\bmod 3$。例如，若已知 $m\bmod 3$，可以令 $k=3t+k’$，再让 $t$ 遍历 ${0,1,2,3,4}$，从而在保证不被 3 整除的同时遍历 $m\bmod 5$ 的所有可能值。

一般情形与 CRT

依次处理素数 $p_i$。设已经求出的素数乘积为

$$
P=\prod_{r<i}p_r,
\qquad
m\equiv f_i\pmod P.
$$

取 $a_i$ 使得

$$
a_i\cdot 2^{256}+f_i\equiv 1\pmod P.
$$

然后构造输入

$$
x_{i,k,j}=(a_i+kP+jPp_i)2^{256},
\qquad
k\in{0,1,\ldots,p_i-1}.
$$

此时

$$
m+x_{i,k,j}
\equiv (a_i+kP)2^{256}+f_i
\equiv a_i\cdot 2^{256}+f_i
\equiv 1\pmod P,
$$

同时，随着 $k$ 遍历 $0,1,\ldots,p_i-1$，$m+x_{i,k,j}$ 模 $p_i$ 的值也会遍历所有可能结果。通过时间最短的一组输入即可判断 $m\bmod p_i$，再使用 CRT 合并当前结果。

依次求出足够多的模数后，即可恢复整数 $m$，最后将其转换回字节串得到 flag。实际实现中，每求出一个新的素数模数，就进行一次 CRT。

解答

下面的脚本使用 Sage 运行，server.sage 为题目服务端脚本：

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
56
57
58
59
60
61
62
63
64
65
66
67
68
from Crypto.Util.number import *
from time import time
from pwn import context, process
import os

context.log_level = 'error'

# 本地调试
os.environ["FLAG"] = "flag{_test_flag_}"
path = "server.sage"


# 记录批量输入的总耗时
def get_spend(io, numbers):
    payload = "".join(f"{num}\n" for num in numbers)
    io.send(payload.encode())

    begin = time()
    for _ in range(len(numbers)):
        io.recvuntil("🌌 ".encode())
    end = time()

    return end - begin


# N：已经求出的素数之积
# pn：当前处理的素数
# fn：m mod N
# an：满足 an * 2^256 + fn = 1 mod N 的修正项
N = 1
pn = 1
fn = 0
an = 0

io = process(["sage", path])
io.recvuntil("🌌 ".encode())

for i in range(28):
    if pn == 1:
        pn = 3
    else:
        pn = next_prime(pn)

    spends = []

    # 靶机中的循环次数可能用完，定期重置进程
    if i % 5 == 0:
        io.close()
        io = process(["sage", path])
        io.recvuntil("🌌 ".encode())

    for k in range(pn):
        numbers = [
            (an + k * N + j * N * pn) << 256
            for j in range(300)
        ]
        spends.append(get_spend(io, numbers))

    # 用耗时最短的一组输入确定当前余数
    k = spends.index(min(spends))
    fn_ = -((an + k * N) << 256) % pn
    fn = int(crt([fn, fn_], [N, pn]))
    an = (1 - fn) * pow(1 << 256, -1, N * pn) % (N * pn)
    N *= pn

    print(fn, end=" ")

print(long_to_bytes(fn))