fiesta

这题使用了一个自定义的 512 位伪随机数生成器来产生 AES 密钥对应的 seed，但题目只给出了预热很多轮之后的 6 个 256 位输出。关键观察是：题目里的 256 位循环旋转会把 512 位状态拆成两个 256 位半块，因此可以把状态转移写成模 2^256 的方程组。把这些方程解出来后，就能恢复出真正的 seed，进一步还原 AES 密钥。

设 x_i = a_i * 2^256 + b_i，其中题目给出的 hint 正好就是低 256 位，也就是 b_i。

题目的状态更新过程为：

w_{i+1} = w_i + s mod 2^512

t_i = x_i^2 + w_{i+1} mod 2^512

x_{i+1} = rot256(t_i)

这里的旋转会把 t_i 的高低两个 256 位半块直接交换，因此我们可以写出 a_i 与 Weyl 状态低半部分之间的递推关系。继续把进位项单独提出来之后，剩余部分就会变成模 2^256 的线性约束。由于进位空间非常小，直接枚举即可，最终可以恢复出精确的 512 位 seed，再用 sha256(str(seed)) 作为 AES-CBC 密钥解出 flag。

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
from math import gcd
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

hints = [
    5100470261801288066851078741242860040360613431215130905861114040808596900903,
    91288410909898657211943477632073929974703716733541065395190648162031156080965,
    102867096580705835660852583237676193828262285566716237689198873708982205609103,
    87723742834153804183126238332676257917437224690578129842736927821744378844764,
    114792592720274564459571965135967121671431736017877734866432305488544398773322,
    31194548874299031189468237471841564954299474688584267063166306145378678484635,
]

enc = (
    b"x\x9b\x9a\xbd\x92\xe9\xd8\t\xa4\xb56^\xcf\xa5\xf2\xef"
    b"`\x15&\xf7\x9a\xe6\xa7\xf6c\x1f\x0fwo\xf68~"
    b"\xf8M\x88\x95\x96\xae2\xd6\xa5\x12\r4\x02%\xb0\x03"
)

B = 1 << 256
MASK = B - 1
b = [None] + hints

r = [None]
q = [None]
for x in hints:
    sq = x * x
    r.append(sq & MASK)
    q.append(sq >> 256)

S = {2: 0}
for i in range(3, 7):
    S[i] = (S[i - 1] + r[i - 1] - r[i - 2]) % B

A2 = (2 * (b[4] - 2 * b[3] + b[2])) % B
B2 = (4 * (b[4] - b[3])) % B
C2 = (2 * b[4] * S[4] - 4 * b[3] * S[3]) % B
A3 = (2 * (b[5] - 2 * b[4] + b[3])) % B
B3 = (2 * (3 * b[5] - 4 * b[4] + b[3])) % B
C3 = (2 * b[5] * S[5] - 4 * b[4] * S[4] + 2 * b[3] * S[3]) % B
D = (A2 * B3 - A3 * B2) % B


def solve_linear(coeff, rhs, mod):
    g = gcd(coeff, mod)
    if rhs % g:
        return []
    coeff //= g
    rhs //= g
    mod //= g
    base = (rhs * pow(coeff, -1, mod)) % mod
    return [base + t * mod for t in range(g)]


for carry_mask in range(16):
    cs = {
        2: (carry_mask >> 0) & 1,
        3: (carry_mask >> 1) & 1,
        4: (carry_mask >> 2) & 1,
        5: (carry_mask >> 3) & 1,
    }

    for k_mask in range(16):
        k = {
            3: (k_mask >> 0) & 1,
            4: (k_mask >> 1) & 1,
            5: (k_mask >> 2) & 1,
            6: (k_mask >> 3) & 1,
        }

        H2 = (b[3] - q[2] - k[3]) % B
        H3 = (b[4] - q[3] - k[4]) % B
        H4 = (b[5] - q[4] - k[5]) % B
        H5 = (b[6] - q[5] - k[6]) % B

        R2 = (H4 - 2 * H3 + H2 - cs[4] + cs[3] - C2) % B
        R3 = (H5 - 2 * H4 + H3 - cs[5] + cs[4] - C3) % B

        a2_list = solve_linear(D, (R2 * B3 - R3 * B2) % B, B)
        sl_list = solve_linear(D, (A2 * R3 - A3 * R2) % B, B)
        if not a2_list or not sl_list:
            continue

        for a2 in a2_list:
            for sl in sl_list:
                if (A2 * a2 + B2 * sl - R2) % B != 0:
                    continue
                if (A3 * a2 + B3 * sl - R3) % B != 0:
                    continue

                a = {2: a2}
                for i in range(3, 7):
                    a[i] = (a2 + (i - 2) * sl + S[i]) % B

                if any((1 if a[i] < r[i - 1] else 0) != k[i] for i in range(3, 7)):
                    continue

                d = {i: (a[i] - r[i - 1]) % B for i in range(2, 7)}
                if any((1 if d[i + 1] < d[i] else 0) != cs[i] for i in range(2, 6)):
                    continue

                sh = (
                    H3
                    - H2
                    - (2 * b[3] * a[3] - 2 * b[2] * a[2])
                    - cs[3]
                ) % B
                c2 = (H2 - 2 * b[2] * a[2] - sh - cs[2]) % B

                c3 = (c2 + sh + cs[2]) % B
                c4 = (c3 + sh + cs[3]) % B
                c5 = (c4 + sh + cs[4]) % B

                if (2 * b[2] * a[2] + c2 + sh + cs[2]) % B != H2:
                    continue
                if (2 * b[3] * a[3] + c3 + sh + cs[3]) % B != H3:
                    continue
                if (2 * b[4] * a[4] + c4 + sh + cs[4]) % B != H4:
                    continue
                if (2 * b[5] * a[5] + c5 + sh + cs[5]) % B != H5:
                    continue

                seed = (sh << 256) | sl
                key = sha256(str(seed).encode()).digest()

                try:
                    pt = unpad(AES.new(key, AES.MODE_CBC, iv=bytes(16)).decrypt(enc), 16)
                except ValueError:
                    continue

                if pt.startswith(b"flag{"):
                    print(seed)
                    print(pt.decode())
                    raise SystemExit

运行输出：

1
2
12420637146355779074975858206981742709327536607883036234535434310980326197400010919644899625214905460690121326723135205491697751039005432071898086728747649
flag{pr3s3N7_4_Food_OfF3RiN9_7o_7H3_LOrD}