SUCTF2026

Above#

周六打完系统安全初赛周日看了看题 Crypto质量都很不错成功ak了写本文来就其中的构造来进一步学习一下

话说这比赛有这么多人打吗除了MISC其他方向基本都被打完了 Crypto的题出解量也比上次夸张了好多x)

出题人师傅blog引流 SUCTF 2026 Crypto方向部分赛题Write UP – 三极管域 | Triode Field ↗ 非常感谢师傅的题🥰

SU_AES#

AES.py

#!/usr/bin/env python


"""
    Copyright (C) 2012 Bo Zhu http://about.bozhu.me

    Permission is hereby granted, free of charge, to any person obtaining a
    copy of this software and associated documentation files (the "Software"),
    to deal in the Software without restriction, including without limitation
    the rights to use, copy, modify, merge, publish, distribute, sublicense,
    and/or sell copies of the Software, and to permit persons to whom the
    Software is furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in
    all copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
    THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
    DEALINGS IN THE SOFTWARE.
"""
from random import Random

# learnt from http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)


Rcon = (
    0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
    0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
    0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
    0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
)


def text2matrix(text):
    matrix = [[] for _ in range(4)]
    for i in range(16):
        byte = (text >> (8 * (15 - i))) & 0xFF
        matrix[i % 4].append(byte)
    return matrix


def matrix2text(matrix):
    text = 0
    for i in range(4):
        for j in range(4):
            text |= (matrix[j][i] << (120 - 8 * (4 * i + j)))
    return text


class AES:
    def __init__(self, master_key, seed=None):
        self.Sbox = [0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
        0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
        0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
        0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
        0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
        0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
        0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
        0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
        0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
        0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
        0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
        0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
        0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
        0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
        0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
        0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16]
        
        Random(seed).shuffle(self.Sbox)

        self.change_key(master_key)

    def change_key(self, master_key):
        self.round_keys = text2matrix(master_key)
        for i in range(4, 4 * 11):
            self.round_keys.append([])
            if i % 4 == 0:
                temp = [
                    self.round_keys[i - 4][0] ^ self.Sbox[self.round_keys[i - 1][1]] ^ Rcon[i // 4],
                    self.round_keys[i - 4][1] ^ self.Sbox[self.round_keys[i - 1][2]],
                    self.round_keys[i - 4][2] ^ self.Sbox[self.round_keys[i - 1][3]],
                    self.round_keys[i - 4][3] ^ self.Sbox[self.round_keys[i - 1][0]],
                ]
            else:
                temp = [
                    self.round_keys[i - 4][j] ^ self.round_keys[i - 1][j] for j in range(4)
                ]
            self.round_keys[i] = temp

    def encrypt(self, plaintext):
        state = text2matrix(plaintext)
        self.add_round_key(state, self.round_keys[:4])
        for i in range(1, 10):
            self.sub_bytes(state)
            self.shift_rows(state)
            self.mix_columns(state)
            self.add_round_key(state, self.round_keys[4*i:4*(i+1)])
        self.sub_bytes(state)
        self.shift_rows(state)
        self.add_round_key(state, self.round_keys[40:])
        return matrix2text(state)

    def add_round_key(self, s, k):
        for i in range(4):
            for j in range(4):
                s[i][j] ^= k[i][j]

    def sub_bytes(self, s):
        for i in range(4):
            for j in range(4):
                s[i][j] = self.Sbox[s[i][j]]

    def shift_rows(self, s):
        s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
        s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
        s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]

    def mix_columns(self, s):
        for i in range(4):
            t = s[i][0] ^ s[i][1] ^ s[i][2] ^ s[i][3]
            u = s[i][0]
            s[i][0] ^= t ^ xtime(s[i][0] ^ s[i][1])
            s[i][1] ^= t ^ xtime(s[i][1] ^ s[i][2])
            s[i][2] ^= t ^ xtime(s[i][2] ^ s[i][3])
            s[i][3] ^= t ^ xtime(s[i][3] ^ u)

    def encrypt_ecb(self, data: bytes) -> bytes:
        if not isinstance(data, (bytes, bytearray)):
            raise TypeError("data must be bytes-like")
        if len(data) % 16 != 0:
            raise ValueError("data length must be multiple of 16 when pad=False")
        out = b''
        for i in range(0, len(data), 16):
            out += self.encrypt(int.from_bytes(data[i : i + 16])).to_bytes(16)
        return out
    
    def change(self, s=None, k=None):
        if s:
            self.Sbox = Random(s).choices(self.Sbox, k=len(self.Sbox))
        if k:
            self.change_key(k)

plaintext

chal.py

from os import urandom
from Crypto.Util.Padding import pad
from AES import AES
import signal
from secret import flag

def handler(_signum, _frame):
  raise TimeoutError("⏰")

seed = int.from_bytes(urandom(16))
key = int.from_bytes(urandom(16))
aes = AES(key, seed)
print(f'[+] Here is your flag ciphertext (in hex): {aes.encrypt_ecb(pad(flag, 16)).hex()}')

menu = """
--- Menu ---
[1] change the S-box
[2] encrypt a message
[3] reset aes
[4] exit
"""

signal.alarm(60)

for _ in range(300):
    print(menu)
    match x:= input('[x] > '):
        case '1':
            s = int(input('[x] your seed: ') or 0, 16) or None
            k = int(input('[x] your key: ') or 0, 16) or None
            aes.change(s, k)
            print('[+] changed!')
        case '2':
            msg = bytes.fromhex(input('[x] your message: '))
            print(f'[+] Here is your ciphertext (in hex): {aes.encrypt_ecb(pad(msg, 16)).hex()}')
        case '3':
            aes = AES(key, seed)
            print('[+] reset!')
        case '4':
            print('[+] Goodbye!')
            exit()
        case _:
            print('[-] Invalid option!')

很漂亮的一道对称要求在300rounds内通过与修改后的AES系统进行交互从密文恢复flag

先从代码方面进行分析

AES实现的差异#

AES.py给出了一个已有的S盒并且随机进行洗牌 Random(seed).shuffle(self.Sbox) 保留了S盒的双射完整性 随后调用生成master_key 开始修改密钥，这里的change_key接口问题不大

然后是关键的

    def change(self, s=None, k=None):
        if s:
            self.Sbox = Random(s).choices(self.Sbox, k=len(self.Sbox))
        if k:
            self.change_key(k)

这里使用的是choice意味着S盒重新放回的信息能产生重合比如可能会有两个位置都映射到137这个置换出口那么产生碰撞后原本对应的映射就会缺失从而 会破坏S盒的双射完整性

可以计算一下进行一次有放回的抽样假设某个元素 $x$ 它对应到了 $137$ 这个映射那么对于另一个元素 $y$ 它在重排后不碰撞上 $137$ 的概率是 $\frac{255}{256}$ 而 $137$ 这个映射出口在 256 次抽样中一次都没被抽中的概率 $P_{\text{miss}}$ 为： $P_{\text{miss}} = \left( 1 - \frac{1}{256} \right)^{256}\approx36.8\%$

简而言之抽样放回后的S盒每个元素都有 $36.8\%$ 的概率不被碰撞上计算一下期望有 $256\times0.368\approx94$ 个元素不会出现在抽样后的S盒输出中 😶‍🌫️

而我们的AES中是支持只改变S盒或者只改变key来进行加密Oracle的

最后这里的ECB加密方式彼此块之间都是独立的

然后是交互方面给了300rounds

每一轮有三种选择

发送自己构造的seed和key 修改AES状态

发送明文给AES 加密获取密文

重置AES为初始状态

至此梳理完毕

PFA与差分思路#

注意到这个AES加密实例允许修改S盒的值并且持久性的拿这个代数性质不好的S盒去加密相关搜索后我找到了这篇文章

(PDF) Persistent Fault Analysis on Block Ciphers (researchgate.net) ↗

针对分组加密如果能够持久性的给置换部分注入破坏随机性的因子就可以产生相关的利用

文章中针对的是单块的加密但本题恰好是ECB模式也能够化用

在这个题这借助文章思路描述一下这个过程

在种子 $s$ 下输入 $x$ 通过choice替换到了 $y=\text{idx}_s[x]$ 修改后的S盒可以看成

Q_s(x) = P[\text{idx}_s[x]]=P[y]

如果是shuffle 那么 $y$ 是可以均匀地取到256个值的但是在choice下 $y$ 有94种情况都取不到了但是这有什么用呢？我们看向

    def encrypt(self, plaintext):
        state = text2matrix(plaintext)
        self.add_round_key(state, self.round_keys[:4])
        for i in range(1, 10):
            self.sub_bytes(state)
            self.shift_rows(state)
            self.mix_columns(state)
            self.add_round_key(state, self.round_keys[4*i:4*(i+1)])
        self.sub_bytes(state)
        self.shift_rows(state)
        self.add_round_key(state, self.round_keys[40:])
        return matrix2text(state)

在最后一轮的加密没有进行mix_columns 这意味着如果我们截取了密文的某一个字节加密就是简单的

C_j = Q_s(State_{9, j}) \oplus RK_{10}[j]

而我们知道每次改变一次S盒, $Q_s$ 都有大约94个元素无法被输出我们设 $v\in\{0,\cdots,255\}$ 就是一个无法被输出的元素那么

C_j \neq v \oplus RK_{10}[j]

顺着这个思路我们注意到加密是不限制Block的个数的那么可以发送很多组Block 都随机分布因为 $v$ 的值域是被限制了那么即便被第10轮密钥混淆异或平移后还是明显会有相当于一部分密文没有出现我们提取这个不出现的密文也就是

M(s, j) = \{ P[y] \oplus RK_{10}[j] \mid y \in Y_{missing}(s) \}

这个有什么用呢举个例子

假设底层有一个特定的索引 $y=5$ 消失

在第 1 轮 seed 测试中，密文缺失集合 $M(s_1, j)$ 里必然包含数值 $P[5] \oplus RK_{10}[j]$
在第 2 轮 seed 测试中，如果 $y=5$ 又消失了，密文缺失集合 $M(s_2, j)$ 里也必然包含数值 $P[5] \oplus RK_{10}[j]$

对于某一个索引的情况我们可以计算多个seed 让它在本地都满足这个 $y=5$ 索引缺失那么取了足够多组缺失的情况那个每次都在缺失集合内的值就是

C=P[5]\oplus RK_{10}[j]

对于多个索引多个seed 缺失的常数情况可以建立二维表 $T_j[y]$

它有 256 行：对应未知的原始 S 盒的输入索引 $y \in \{0 \dots 255\}$ 。
它有 16 列：对应 16 个密文字节的位置 $j \in \{0 \dots 15\}$ 。

例如如果有 $T_0[5] = \texttt{0x3F}$ 那么

$P[5] \oplus RK_{10}[0] = \texttt{0x3F}$

我们从此建立了初始S盒和末态密钥的关系也就是PFA的攻击流程

不难看到 $RK_{10}$ 还是一个未知量我们再看回

    def encrypt(self, plaintext):
        state = text2matrix(plaintext)
        self.add_round_key(state, self.round_keys[:4])
        for i in range(1, 10):
            self.sub_bytes(state)
            self.shift_rows(state)
            self.mix_columns(state)
            self.add_round_key(state, self.round_keys[4*i:4*(i+1)])
        self.sub_bytes(state)
        self.shift_rows(state)
        self.add_round_key(state, self.round_keys[40:])
        return matrix2text(state)

它在一开始就进行了 add_round_key 调用了初始密钥进行了异或这意味着什么呢

如果我们能让两个明文在 self.add_round_key(state, self.round_keys[:4])就成功碰撞由分组加密结构终态密文也一定成功碰撞

我们构造两块明文 $M\;\;N$ 由前面的分析对于已知的seed 可以轻松找到

$a \neq b, \quad \text{idx}_s[a] = \text{idx}_s[b]$

此时把这两个一样的索引传入修改S盒会吐出一样的值

如果我们给碰撞后再去进行一个差分偏移

$M_g[t] = a \oplus g$

$N_g[t] = b \oplus g$

那么add_round_key后得到的状态是

$M'_g[t] = M_g[t] \oplus k_t = a \oplus g \oplus k_t$

$N'_g[t] = N_g[t] \oplus k_t = b \oplus g \oplus k_t$

有且仅有 $g==k_t$ 的时候才会得到 $Q_s(M'_g[t]) = Q_s(a)$

$Q_s(N'_g[t]) = Q_s(b)$ 观察输出这两个部分的字节完全相同说明我们构造的 $g$ 恰巧碰上了这一字节位置的初始密钥

而且我们的查询也是不限制大小的如果想恢复第 $t$ 位置的初始密钥完全可以发送类似 $M_0,N_0,M_1,N_1,\dots,M_{255},N_{255}$

总共 512 个块，只需 1 次 encrypt 即可爆破出是哪个字节验证逻辑 $C_{2g} = C_{2g+1} \Longrightarrow g \text{ 是候选}$

好了我们现在恢复了 $K_0$ 那么怎么和 $RK_{10}[j]$ 扯上关系呢

先单独分析特定的 $j=0$ 字节也就是 $T_0[y] = P[y] \oplus RK_{10}[0]$ 我们其实可以爆破 $\Delta = RK_{10}[0]\in\{0,1,\cdots,255\}$ 都可以恢复出一个初始S盒候选 $P_\Delta[y] = T_0[y] \oplus \Delta$ 可以检查它的性质

它应该是一个 $256\rightarrow256$ 的置换
用恢复的S盒 $P_\Delta$ 和初始密钥 $K_0$ 重新进行AES过程得到 $RK_{10}^{(\Delta)}$
检查是否有 $\forall y,j,\quad P_\Delta[y] \oplus RK_{10}^{(\Delta)}[j] = T_j[y]$ 完全成立

这样子我们可以逐字节恢复最终的密钥那么再异或回去就得到了初始 $S$ 盒后续构造逆 $S$ 盒就可以解密了

计算一下交互总数

恢复 $K_0$

1 次 change

32 次 encrypt

恢复映射表

先 1 次 reset

再对于每一个seed

1 次 change

1 次 encrypt

1 次 reset

总共142次给的很富裕了

exp.sage

from os import urandom
from random import Random
import operator
from pwn import *
from Crypto.Util.Padding import unpad
from AES import AES, matrix2text, text2matrix, xtime
STAGE1_SEED = 3313
STAGE1_PAIRS = [(9, 48), (9, 87)]

PFA_BLOCKS = 4000
PFA_SEEDS = [
    57, 1433, 1524, 233, 1636, 689, 634, 914, 1908,
    514, 1572, 1600, 1725, 1694, 81, 1884, 497, 1488,
    1038, 528, 1115, 289, 222, 740, 1937, 67, 1318,
    1010, 1020, 851, 1500, 1200, 1099, 984, 1658, 1920,
]

ALL_BYTES = set(range(256))


def bxor(left, right):
    return operator.xor(int(left), int(right))


def menu_change(io, s=None, k=None):
    io.sendlineafter(b"[x] > ", b"1")
    io.sendlineafter(b"[x] your seed: ", b"0" if s is None else hex(int(s))[2:].encode())
    io.sendlineafter(b"[x] your key: ", b"0" if k is None else hex(int(k))[2:].encode())
    io.recvline_contains(b"changed")

def menu_encrypt(io, msg):
    io.sendlineafter(b"[x] > ", b"2")
    io.sendlineafter(b"[x] your message: ", msg.hex().encode())
    line = io.recvline_contains(b"ciphertext")
    return bytes.fromhex(line.split(b": ", 1)[1].strip().decode())


def menu_reset(io):
    io.sendlineafter(b"[x] > ", b"3")
    io.recvline_contains(b"reset")


def build_stage1_payload(byte_pos, a, b):
    blocks = []
    for guess in range(256):
        left = bytearray(16)
        right = bytearray(16)
        left[byte_pos] = bxor(a, guess)
        right[byte_pos] = bxor(b, guess)
        blocks.append(bytes(left))
        blocks.append(bytes(right))
    return b"".join(blocks)


def equal_guess_set(ciphertext):
    blocks = [ciphertext[16 * i:16 * (i + 1)] for i in range(512)]
    guesses = set()
    for guess in range(256):
        if blocks[2 * guess] == blocks[2 * guess + 1]:
            guesses.add(guess)
    return guesses


def subword_key_schedule(master_key_int, sbox):
    aes = AES.__new__(AES)
    aes.Sbox = sbox[:]
    aes.change_key(master_key_int)
    return aes


def inv_shift_rows(state):
    state[0][1], state[1][1], state[2][1], state[3][1] = state[3][1], state[0][1], state[1][1], state[2][1]
    state[0][2], state[1][2], state[2][2], state[3][2] = state[2][2], state[3][2], state[0][2], state[1][2]
    state[0][3], state[1][3], state[2][3], state[3][3] = state[1][3], state[2][3], state[3][3], state[0][3]


def inv_sub_bytes(state, inv_sbox):
    for i in range(4):
        for j in range(4):
            state[i][j] = inv_sbox[state[i][j]]


def inv_mix_columns(state):
    for i in range(4):
        u = xtime(xtime(bxor(state[i][0], state[i][2])))
        v = xtime(xtime(bxor(state[i][1], state[i][3])))
        state[i][0] = bxor(state[i][0], u)
        state[i][1] = bxor(state[i][1], v)
        state[i][2] = bxor(state[i][2], u)
        state[i][3] = bxor(state[i][3], v)
    helper = AES.__new__(AES)
    helper.mix_columns(state)


def decrypt_block(aes_obj, block, inv_sbox):
    state = text2matrix(int.from_bytes(block))
    aes_obj.add_round_key(state, aes_obj.round_keys[40:])
    inv_shift_rows(state)
    inv_sub_bytes(state, inv_sbox)
    for round_idx in range(9, 0, -1):
        aes_obj.add_round_key(state, aes_obj.round_keys[4 * round_idx:4 * (round_idx + 1)])
        inv_mix_columns(state)
        inv_shift_rows(state)
        inv_sub_bytes(state, inv_sbox)
    aes_obj.add_round_key(state, aes_obj.round_keys[:4])
    return matrix2text(state).to_bytes(16)


# io = process(["python3", "chal.py"])
io = remote("1.95.115.179", 10015)
flag_line = io.recvline_contains(b"flag ciphertext")
flag_ct = bytes.fromhex(flag_line.split(b": ", 1)[1].strip().decode())
print("[*] flag ciphertext bytes =", len(flag_ct))

print("[*] stage1: recover K0")
menu_change(io, s=STAGE1_SEED)
k0_bytes = []
for byte_pos in range(16):
    candidates = set(range(256))
    for a, b in STAGE1_PAIRS:
        payload = build_stage1_payload(byte_pos, a, b)
        ct = menu_encrypt(io, payload)
        candidates &= equal_guess_set(ct)
    if len(candidates) != 1:
        raise ValueError(f"stage1 ambiguous at byte {byte_pos}: {sorted(candidates)}")
    value = next(iter(candidates))
    k0_bytes.append(value)
    print(f"    byte[{byte_pos:02d}] = {value:02x}")

K0 = int.from_bytes(bytes(k0_bytes))
print("[+] recovered K0 =", hex(K0))

print("[*] stage2+3: collect PFA samples and intersect")
menu_reset(io)
recovered_tables = [[set(range(256)) for _ in range(256)] for _ in range(16)]

for fault_index, fault_seed in enumerate(PFA_SEEDS):
    menu_change(io, s=fault_seed)
    msg = urandom(16 * PFA_BLOCKS)
    ct = menu_encrypt(io, msg)
    observed = [set() for _ in range(16)]
    for offset in range(0, len(ct), 16):
        block = ct[offset:offset + 16]
        if len(block) < 16:
            break
        for j, value in enumerate(block):
            observed[j].add(value)
    missing_cipher = [ALL_BYTES - values for values in observed]
    idx = Random(int(fault_seed)).choices(range(256), k=256)
    missing_y = ALL_BYTES - set(idx)
    for y in missing_y:
        for j in range(16):
            recovered_tables[j][y] &= missing_cipher[j]
    print(f"    seed {fault_index + 1:02d}/{len(PFA_SEEDS)} done; missing_y={len(missing_y)}")
    menu_reset(io)

for j in range(16):
    for y in range(256):
        if len(recovered_tables[j][y]) != 1:
            raise ValueError(f"PFA intersection not singleton at byte={j}, y={y}, size={len(recovered_tables[j][y])}")

tables = [[next(iter(recovered_tables[j][y])) for y in range(256)] for j in range(16)]
print("[+] recovered all T_j[y] singletons")

print("[*] stage4: brute Delta and rebuild original P")
best = None
for delta in range(256):
    p_guess = [bxor(tables[0][y], delta) for y in range(256)]
    if len(set(p_guess)) != 256:
        continue
    aes_guess = subword_key_schedule(K0, p_guess)
    rk10 = matrix2text(aes_guess.round_keys[40:]).to_bytes(16)
    if rk10[0] != delta:
        continue
    good = True
    for j in range(16):
        for y in range(256):
            if bxor(p_guess[y], rk10[j]) != tables[j][y]:
                good = False
                break
        if not good:
            break
    if good:
        best = (delta, p_guess, aes_guess, rk10)
        break

if best is None:
    raise ValueError("no Delta satisfied the full consistency checks")

delta, orig_sbox, aes_final, rk10 = best
print("[+] Delta =", hex(delta))
print("[+] RK10 =", rk10.hex())

print("[*] stage5: decrypt flag")
inv_sbox = [0] * 256
for idx, value in enumerate(orig_sbox):
    inv_sbox[value] = idx

pt = b""
for offset in range(0, len(flag_ct), 16):
    pt += decrypt_block(aes_final, flag_ct[offset:offset + 16], inv_sbox)

flag = unpad(pt, 16)
print("[+] flag =", flag.decode())

'''
[*] flag ciphertext bytes = 32
[*] stage1: recover K0
    byte[00] = 65
    byte[01] = 4e
    byte[02] = ed
    byte[03] = ff
    byte[04] = 88
    byte[05] = f4
    byte[06] = b6
    byte[07] = 2a
    byte[08] = 27
    byte[09] = 88
    byte[10] = 3a
    byte[11] = 4e
    byte[12] = 04
    byte[13] = f2
    byte[14] = 37
    byte[15] = 3c
[+] recovered K0 = 0x654eedff88f4b62a27883a4e04f2373c
[*] stage2+3: collect PFA samples and intersect
    seed 01/36 done; missing_y=98
    seed 02/36 done; missing_y=90
    seed 03/36 done; missing_y=89
    seed 04/36 done; missing_y=96
    seed 05/36 done; missing_y=94
    seed 06/36 done; missing_y=92
    seed 07/36 done; missing_y=102
    seed 08/36 done; missing_y=91
    seed 09/36 done; missing_y=96
    seed 10/36 done; missing_y=88
    seed 11/36 done; missing_y=90
    seed 12/36 done; missing_y=103
    seed 13/36 done; missing_y=98
    seed 14/36 done; missing_y=98
    seed 15/36 done; missing_y=94
    seed 16/36 done; missing_y=92
    seed 17/36 done; missing_y=89
    seed 18/36 done; missing_y=88
    seed 19/36 done; missing_y=91
    seed 20/36 done; missing_y=95
    seed 21/36 done; missing_y=91
    seed 22/36 done; missing_y=92
    seed 23/36 done; missing_y=91
    seed 24/36 done; missing_y=89
    seed 25/36 done; missing_y=96
    seed 26/36 done; missing_y=96
    seed 27/36 done; missing_y=95
    seed 28/36 done; missing_y=91
    seed 29/36 done; missing_y=95
    seed 30/36 done; missing_y=90
    seed 31/36 done; missing_y=96
    seed 32/36 done; missing_y=85
    seed 33/36 done; missing_y=94
    seed 34/36 done; missing_y=104
    seed 35/36 done; missing_y=98
    seed 36/36 done; missing_y=88
[+] recovered all T_j[y] singletons
[*] stage4: brute Delta and rebuild original P
[+] Delta = 0xa8
[+] RK10 = a84db17057fccc085dcf9756bd23962c
[*] stage5: decrypt flag
[+] flag = SUCTF{Th3_K3y_15_1n_7h3_S_80x}
'''

SU_PRNG#

chal.py

from hashlib import md5
from random import randint
import signal
from secret import flag


bits = 256
outs = 56

ror = lambda x, k, n: ((x >> (k % n)) | (x << (n - k % n))) & ((1 << n) - 1)

class LCG:
    def __init__(self, seed, a, b):
        self.seed = seed
        self.a = a
        self.b = b
        self.m = 2**bits

    def next(self):
        self.seed = (self.seed * self.a + self.b) % self.m
        return ror((self.seed >> bits // 2) ^ (self.seed % 2**(bits // 2)), self.seed >> bits - 250, bits)

signal.alarm(15)

a = randint(1, 1 << bits)
b = randint(1, 1 << bits)
seed = randint(1, 1 << bits)
lcg = LCG(seed, a, b)
print(f'{a = }')
print(f'out = {[lcg.next() for _ in [0] * outs]}')
print(f'h = {md5(str(seed).encode()).hexdigest()}')

if int(input('> ')) == seed:
    print('Correct!')
    print(flag)

也是非常简洁的一道流密码

思路梳理#

逻辑很简单先定义了一个右移函数 ror 然后对于state长度为256的LCG实例每轮状态转换为 $s_{i+1}\equiv a\times s_{i}+b\mod 2^{128}$ 为了方便分析给相关参数上下对半拆开为 $s_i=H_i\times2^{128}+L_i$ $a = a_0 + 2^{128} \cdot a_1$ $b = b_0 + 2^{128} \cdot b_1$ 关于函数

ror((self.seed >> bits // 2) ^ (self.seed % 2**(bits // 2)), self.seed >> bits - 250, bits)

它右旋的部分是 $Z_i=H_i\oplus L_i$ 右旋的步长为 $r_i\equiv S>>6\mod 256$

不难注意到 $Z_i$ 的高128位都为0 而根据右旋函数的构造右旋后的结果 $out_i$ 一定也有128组0 那么就可以考虑左旋回去直到高128位都是0 这样就还原了可能的步长 $r_i$ 集合也就是 $r \text{ 是合法的步长 } \iff \operatorname{ROL}_{256}(o_t, r) < 2^{128}$

我们再看向 $r_i$ 的定义它实际上也只取决于当前state $s$ 的低 $6\sim14$ 位也就是只和低128位的 $L_i$ 相关即 $r_t = L_t[6:14]$

左旋恢复步长逆向#

做到这一步可以根据这里的State转移方式找到一篇参考的paper

https://tosc.iacr.org/index.php/ToSC/article/view/8700/8292 ↗

这里的PCG-64的右旋步长由高6位决定而我们这里是低6~14位可以参考这里的UnknownIncrement的求解思路在低14位的计算中截断会得到干净的代数结构那么令 $x_i = L_i \bmod 2^{14}$ 有 $x_i = (r_i \ll 6) \;|\; t,\qquad 0\le t<64$

由前面的定义可以推出 $L_{i+1} = a_0 L_i + b_0 \pmod{2^{128}}$ 模低位可以得到 $x_{i+1} = a_0 x_i + u \pmod{2^{14}}$ 也就是说一旦固定了 $u\;\;x_0$ 56组状态都会被直接确定约束非常强可以考虑进行差分消去 $u$ 然后逐步爆破 $t\;r_i$ 对于不同的 $x_i\;x_{i+1}\;x_{i+2}$ 都带入验证可以非常快的收束到唯一序列

我们已经确认了 $u\;x_0\sim x_{55}$ 那么可以精确的恢复 $r_i$ 从而也得到了精确的56组 $Z_i = L_i \oplus H_i$

分析截断构造线性式#

接下来审视手上已有的数据 $x_i$ 都是低14位的考虑围绕低14位和高114位开始分析结构重新令 $L_i = x_i + 2^{14} y_i,$ 同时 $b_0 = u + 2^{14} v.$ 再代入有 $a_0 x_i + u = x_{i+1} + 2^{14} q_i,$ $y_{i+1} = a_0 y_i + v + q_i \pmod{2^{114}}.$ $q_i = \frac{a_0 x_i + u - x_{i+1}}{2^{14}}.$ 这一步最核心的思路就是面对未知的高114位我们把低14位带来的影响全部被吸纳入了微小的整形噪音 $q_i$ 我们审视这个方程 $y_{i+1} = a_0 y_i + v + q_i \pmod{2^{114}}.$ 有个很小的偏移还有个114bits大小的未知常数 $v$ 参考paper中的差分思路先令 $T_i \equiv a_0 y_i + v + q_i \pmod{2^{128}}$ 由 $y_{i+1}\equiv T_i\mod 2^{114}$ 可以得到 $T_i = y_{i+1} + 2^{114} C_i,$

先在128bits的数量级下对 $T$ 进行一次截断方便分析低位到高位之间的进位代数量化等式

再在114bits下把进位显式地拆出来把代数式和已知量扯上关系

我们分析出来了一个14bits的量 $C_i$ 再结合对于 $L_i$ 的低14位信息 $x_i$ 放在异或的信息中去处理对于式子 $h_i = (Z_i \bmod 2^{14}) \oplus x_i$ 可以写出 $h_{i+1} \equiv a_0 h_i + a_1 x_i + b_{1,\text{low}} + \text{CARRY} \pmod{2^{14}}$ 而由于截断实际上也就能写成 $h_{i+1} \equiv a_0 h_i + a_1 x_i + b_{1,\text{low}} + C_i \pmod{2^{14}}$ 做到这一步终于看到了可以处理的线性等式

我们观察这个递推 $a_0\;a_1\;C_i\;x_i$ 都是已知/可计算的由前面的异或关系也可以完整的恢复 $h_i$ 那么考虑用做差消去未知的 $b$ 的低位我们可以计算恢复 $\Delta C_i = C_{i+1} - C_i \pmod{2^{14}}$ 再看向下半图由 $T_i \equiv a_0 y_i + v + q_i \pmod{2^{128}}$ 依旧做差 $D_i = T_{i+1} - T_i$ 得到 $D_{i+1} = a_0 D_i + \delta_i \pmod{2^{128}}$ 详细写一下 $y_{i+1} = T_i \bmod 2^{114} = T_i - 2^{114} O_i$ 那么 $T_{i+2} - T_{i+1} = a_0 (T_{i+1} - T_i) - a_0 2^{114} (O_{i+1} - O_i) + (q_{i+2} - q_{i+1}) \pmod{2^{128}}$ 即 $D_{i+1} = a_0 D_i + \left[ q_{i+2} - q_{i+1} - a_0 2^{114} (O_{i+1} - O_i) \right] \pmod{2^{128}}$ $\delta_i = q_{i+2} - q_{i+1} - a_0 2^{114} (O_{i+1} - O_i) \pmod{2^{128}}$ 而 $2^{114} \cdot (O_{i+1} - O_i) \equiv 2^{114} \cdot \left[ (O_{i+1} - O_i) \bmod 2^{14} \right] \pmod{2^{128}}$ 不论 $O_{i+1}-O_i$ 多大左移114位后高14位以上的取值都被截断丢弃所以在 $2^{114}$ 这个系数下可以用先前计算的 $\Delta C_i = C_{i+1} - C_i = \text{approx}_i\pmod{2^{14}}$ 放进去代替它得到 $\delta_i = q_{i+2} - q_{i+1} - a_0 \cdot 2^{114} \cdot \text{approx}_i \pmod{2^{128}}$ 对于 $\delta$ 它完全可算误差噪声也是非常小的综上分析列个表

变量符号	定义	状态	备注 / 作用
完全已知
$a_0, a_1$	乘数 $a$ 的低 128 位和高 128 位	已知	题目给定的公开全局常数。
$x_i$	内部状态 $L_i$ 的最低 14 位	已知	通过第一步的动态规划（DP）完全枚举并锁定。
$Z_i$	上下半部的异或真实值 $L_i \oplus H_i$	已知	知道步长 $r_t$ 后，对输出左旋解旋得到。
$h_i$	上半部的最低 14 位	已知	由 $h_i = (Z_i \bmod 2^{14}) \oplus x_i$ 直接算出。
$q_i$	底部 14 位算式产生的进位	已知	由 $q_i = (a_0 x_i + u - x_{i+1}) / 2^{14}$ 精确算出。
$\text{approx}_i$	进位 $C_i$ 相邻做差在模 $2^{14}$ 下的近似	已知	利用上半部异或特征提取出来的进位变化差值。
$\boldsymbol{\delta_i}$	阻碍 $D_i$ 成为等比数列的巨大干扰项	已知	由 $q_{i+2} - q_{i+1} - a_0 \cdot 2^{114} \cdot \text{approx}_i$ 算出的精确常数。
$K_i$	用于“平移”的特解序列	已知	人为构造： $K_0=0, K_{i+1} = a_0 K_i + \delta_i \pmod{2^{128}}$ 。
用于格规约
$\mathrm{obs}_i$	给到 Lattice 的目标向量的高 14 位快照	已知	$\mathrm{obs}_i = \text{approx}_i - \operatorname{top}_{14}(K_i) \pmod{2^{14}}$ 。
$\boldsymbol{\eta_i}$	真实的极小物理噪声	未知但极小	仅仅来源于高低位截断相减时的借位误差， $\eta_i \in \{0, 1, 2\}$ 。
期望在格中被恢复
$y_i$	下半部 $L_i$ 的高 114 位商序列	未知	我们的最终目标状态。
$T_i$	包含 $y_i$ 的 128 位核心多项式	未知	$T_i \equiv a_0 y_i + v + q_i \pmod{2^{128}}$ 。
$D_i$	$T_i$ 相邻做差的序列	未知	$D_{i+1} = a_0 D_i + \delta_i \pmod{2^{128}}$ 。
$\boldsymbol{G_i}$	绝对纯净的几何序列（等比数列）	格规约的目标	$G_{i+1} \equiv a_0 G_i \pmod{2^{128}}$ 。

格规约#

现在很明显手动构造偏移序列 $K_{i+1} = a_0 K_i + \delta_i \pmod{2^{128}}$ 做差 $G_i = D_i - K_i \pmod{2^{128}}$ 就只用恢复等比列 $G_{i+1} = a_0 G_i \pmod{2^{128}}$ 同时计算 $\mathrm{obs}_i = \text{approx}_i - \operatorname{top}_{14}(K_i)$ $\text{obs}_i$ 只会由于进位产生很小的整数误差参考paper的格思路

做格 $B = \begin{pmatrix} 1 & a_0 & a_0^2 & \cdots & a_0^{n-1} \\ 0 & 2^{128} & 0 & \cdots & 0 \\ 0 & 0 & 2^{128} & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 2^{128} \end{pmatrix}.$ 预期解CVP找 $t = (\mathrm{obs}_0 2^{114}, \; \mathrm{obs}_1 2^{114}, \; \dots, \; \mathrm{obs}_{n-1} 2^{114})$ 考虑KannanEmbedding $B' = \begin{pmatrix} B & \mathbf{0}^T \\ t & \mu \end{pmatrix} = \begin{pmatrix} 1 & a_0 & a_0^2 & \cdots & a_0^{n-1} & 0 \\ 0 & 2^{128} & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 2^{128} & 0 \\ t_0 & t_1 & t_2 & \cdots & t_{n-1} & 2^{114} \end{pmatrix}$ 预期

$(x_0, \; k_1, \; \dots, \; k_{n-1}, \; -1) = (X, \; -1)$

$S = (X, \; -1) \cdot \begin{pmatrix} B & \mathbf{0}^T \\ t & \mu \end{pmatrix}=\Big( X \cdot B + (-1) \cdot t, \quad X \cdot \mathbf{0}^T + (-1) \cdot \mu \Big) = \Big( e_0, \; e_1, \; \dots, \; e_{n-1}, \; -2^{114} \Big)$ $e_i = G_i - \mathrm{obs}_i 2^{114} = \operatorname{low}_{114}(G_i) - \eta_i 2^{114}$ 在128bits系统中数量级为115bits 用20size的BKZ可以打通并且能直接得到 $G_i$ 可以用 $\|\mathrm{obs}_i - (G_i \gg 114)\|\in\{0,1,2\}$ 验证正确性

利用约束恢复完整状态#

好了费了那么多劲终于恢复了 $G$ 先算 $D_i = G_i + K_i.$ 而 $y_{i+2} - y_{i+1} = D_i \bmod 2^{114}.$ 那么 $y_{i+1} \equiv y_1 + \sum_{k=0}^{i-1} D_k \pmod{2^{114}}$ 也写成 $y_i = s_i + c \pmod{2^{114}},$ 既然 $c$ 是可以手动算的那每轮算一下判断 $s_i$ 超过 $2^{114}$ 多少手动给它减去得到 $y_i = s_i + c - \text{wrap}_i \cdot 2^{114}$ 相当于化简了这个同于方程当然也可以根据对 $c$ 的范围估计进一步拆分化简不过最后都会用约束送入z3/进行剪枝爆搜就偷个懒了)

回代最后我们有的56组方程 $H_{i+1} = a_0 H_i + a_1 (x_i + 2^{14} y_i) + B + \text{carry}_i=L_i\oplus Z_i \pmod{2^{128}}$ 没有乱七八糟的模了就是一个XOR和加法乘法约束足够厉害解个高位问题不大了

ok 还原了 $y$ 就可以还原偏移了然后逆向LCG 用md5校验一下

gpt大人硬扛了这么大的码量…

exp.sage

from hashlib import md5
from operator import xor as bit_xor
from fpylll import BKZ, IntegerMatrix
from z3 import BitVec, BitVecVal, SolverFor, ULT, ZeroExt
from pwn import *
import time

MASK = (1 << 256) - 1
SLICE_MASK = (1 << 14) - 1
QUOT_BITS  = 114
LOW_MASK   = (1 << 128)- 1
QUOT_MOD   = 1 << QUOT_BITS

def rol(x, k, n):
    k %= n
    return ((x << k) | (x >> (n - k))) & ((1 << n) - 1)

def ror(x, k, n):
    k %= n
    return ((x >> k) | (x << (n - k))) & ((1 << n) - 1)

def rotation_candidates(out):
    return [r for r in range(256) if (rol(out, r, 256) >> 128) == 0]

def enumerate_low_trajectories(a0, outs):
    a_low = a0 & SLICE_MASK
    rot_sets = [rotation_candidates(out) for out in outs]
    x_sets = [
        sorted({(rot << 6) | lo for rot in rots for lo in range(64)})
        for rots in rot_sets
    ]
    x_membership = [set(values) for values in x_sets]

    layer = {}
    for x0 in x_sets[0]:
        ax = (a_low * x0) & SLICE_MASK
        for x1 in x_sets[1]:
            u = (x1 - ax) & SLICE_MASK
            bucket = layer.setdefault(u, {})
            bucket.setdefault(x1, x0)

    parents = [layer]
    for i in range(1, len(outs) - 1):
        next_layer = {}
        valid = x_membership[i + 1]
        for u, current in layer.items():
            nxt = {}
            for x_i in current.keys():
                x_next = (a_low * x_i + u) & SLICE_MASK
                if x_next in valid and x_next not in nxt:
                    nxt[x_next] = x_i
            if nxt:
                next_layer[u] = nxt
        if not next_layer:
            return
        parents.append(next_layer)
        layer = next_layer

    seen = set()
    for u, current in layer.items():
        for x_last in current.keys():
            xs = [0] * len(outs)
            xs[-1] = x_last
            for i in range(len(outs) - 2, 0, -1):
                xs[i] = parents[i][u][xs[i + 1]]
            xs[0] = parents[0][u][xs[1]]
            key = (u, tuple(xs))
            if key in seen:
                continue
            seen.add(key)
            yield u, xs

def recover_geometric_sequence(a0, obs):
    scale = 1 << QUOT_BITS
    embed = 1 << QUOT_BITS
    for dim in (10, 11, 12):
        basis = IntegerMatrix(dim, dim)
        power = 1
        for j in range(dim):
            basis[0, j] = power
            power = (power * a0) & LOW_MASK
        for i in range(1, dim):
            basis[i, i] = 1 << 128

        target = [int(value) * scale for value in obs[:dim]]
        embedded = IntegerMatrix(dim + 1, dim + 1)
        for i in range(dim):
            for j in range(dim):
                embedded[i, j] = basis[i, j]
        for j in range(dim):
            embedded[dim, j] = target[j]
        embedded[dim, dim] = embed
        BKZ.reduction(embedded, BKZ.Param(block_size=dim + 1))

        candidates = []
        for i in range(dim + 1):
            row = [embedded[i, j] for j in range(dim + 1)]
            candidates.append(row)
            candidates.append([-x for x in row])

        for row in sorted(candidates, key=lambda values: sum(x * x for x in values)):
            if abs(row[-1]) != embed:
                continue
            if row[-1] == -embed:
                lattice_vec = [(target[j] + row[j]) & LOW_MASK for j in range(dim)]
            else:
                lattice_vec = [(target[j] - row[j]) & LOW_MASK for j in range(dim)]

            g0 = lattice_vec[0] & LOW_MASK
            sequence = []
            cur = g0
            ok = True
            for value in obs:
                noise = (value - (cur >> QUOT_BITS)) & SLICE_MASK
                if noise not in (0, 1, 2):
                    ok = False
                    break
                sequence.append(cur)
                cur = (cur * a0) & LOW_MASK
            if ok:
                return sequence
    return None

def solve_interval_offset(a0, a1, xs, zs, carry_terms, base_y, width):
    width = int(width)
    width_bits = max(1, width.bit_length())
    offset = BitVec("offset", int(width_bits))
    upper_const = BitVec("upper_const", int(128))
    solver = SolverFor("QF_BV")
    solver.set(timeout=int(5000))
    solver.add(ULT(offset, BitVecVal(int(width), int(width_bits))))

    offset128 = ZeroExt(int(128 - width_bits), offset) if width_bits < 128 else offset
    equations = min(len(carry_terms), 8)
    for i in range(equations):
        left = BitVecVal(int((xs[i] + (base_y[i] << 14)) & LOW_MASK), int(128)) + (offset128 << 14)
        right = (
            BitVecVal(int((xs[i + 1] + (base_y[i + 1] << 14)) & LOW_MASK), int(128))
            + (offset128 << 14)
        )
        h_left = bit_xor(BitVecVal(int(zs[i]), int(128)), left)
        h_right = bit_xor(BitVecVal(int(zs[i + 1]), int(128)), right)
        solver.add(
            h_right
            == BitVecVal(int(a0), int(128)) * h_left
            + BitVecVal(int(a1), int(128)) * left
            + upper_const
            + BitVecVal(int(carry_terms[i] & LOW_MASK), int(128))
        )

    if solver.check().r != 1:
        return None
    return solver.model()[offset].as_long()

def iter_congruence_solutions(a, rhs, bits=256):
    mod = 1 << bits
    a %= mod
    rhs %= mod
    if a == 0:
        if rhs == 0:
            raise ValueError("degenerate multiplier: infinitely many solutions")
        return
    nu = (a & -a).bit_length() - 1
    g = 1 << nu
    if rhs & (g - 1):
        return
    if g > (1 << 20):
        raise ValueError("too many congruence solutions")
    a_reduced = a >> nu
    rhs_reduced = rhs >> nu
    mod_reduced = mod >> nu
    inv = pow(a_reduced, -1, mod_reduced)
    base = (rhs_reduced * inv) % mod_reduced
    for k in range(g):
        yield base + k * mod_reduced

def solve_instance(a_raw, outs, seed_hash):
    a = a_raw & MASK
    if a == 0:
        return None
    a0 = a & LOW_MASK
    a1 = (a >> 128) & LOW_MASK

    for u, xs in enumerate_low_trajectories(a0, outs):
        rotations = [x >> 6 for x in xs]
        zs = [rol(out, rot, 256) for out, rot in zip(outs, rotations)]
        if any(z >> 128 for z in zs):
            continue

        h_low = [bit_xor(z & SLICE_MASK, x) for z, x in zip(zs, xs)]
        b_low14 = [
            (h_low[i + 1] - a0 * h_low[i] - a1 * xs[i]) & SLICE_MASK
            for i in range(len(xs) - 1)
        ]
        q = [
            (a0 * xs[i] + u - xs[i + 1]) >> 14
            for i in range(len(xs) - 1)
        ]
        approx = [
            (b_low14[i + 1] - b_low14[i]) & SLICE_MASK
            for i in range(len(b_low14) - 1)
        ]
        delta_known = [
            (q[i + 2] - q[i + 1] - a0 * (approx[i] << QUOT_BITS)) & LOW_MASK
            for i in range(len(q) - 2)
        ]
        k_part = [0]
        for term in delta_known:
            k_part.append((a0 * k_part[-1] + term) & LOW_MASK)
        obs = [
            (approx[i] - (k_part[i] >> QUOT_BITS)) & SLICE_MASK
            for i in range(len(k_part))
        ]
        geom = recover_geometric_sequence(a0, obs)
        if geom is None:
            continue

        d_seq = [(geom[i] + k_part[i]) & LOW_MASK for i in range(len(geom))]
        y_offsets = [0]
        for value in d_seq:
            y_offsets.append((y_offsets[-1] + (value & (QUOT_MOD - 1))) & (QUOT_MOD - 1))

        xs_tail = xs[1:]
        zs_tail = zs[1:]
        q_tail = q[1:]
        b_tail = b_low14[1:]
        d_const = (y_offsets[1] - q_tail[0]) & (QUOT_MOD - 1)

        quotients = []
        carry_thresholds = []
        for i in range(len(q_tail)):
            poly = a0 * y_offsets[i] + d_const + q_tail[i]
            quotients.append(poly >> QUOT_BITS)
            tail = poly & (QUOT_MOD - 1)
            carry_thresholds.append(None if tail == 0 else QUOT_MOD - tail)

        wrap_thresholds = [None if value == 0 else QUOT_MOD - value for value in y_offsets]
        deltas = [(value - b_tail[0]) & SLICE_MASK for value in b_tail]
        points = {0, QUOT_MOD}
        for point in carry_thresholds + wrap_thresholds:
            if point is not None:
                points.add(point)
        points = sorted(points)

        first_threshold = carry_thresholds[0]
        for left, right in zip(points, points[1:]):
            if left >= right:
                continue
            pivot = left
            first_carry = 0 if first_threshold is None else int(pivot >= first_threshold)
            ok = True
            for i in range(1, len(q_tail)):
                extra_carry = 0 if carry_thresholds[i] is None else int(pivot >= carry_thresholds[i])
                wrap = 0 if wrap_thresholds[i] is None else int(pivot >= wrap_thresholds[i])
                value = (quotients[i] - quotients[0] + extra_carry - first_carry - a0 * wrap) & SLICE_MASK
                if value != deltas[i]:
                    ok = False
                    break
            if not ok:
                continue

            carries = [
                0 if carry_thresholds[i] is None else int(left >= carry_thresholds[i])
                for i in range(len(q_tail))
            ]
            wraps = [
                0 if wrap_thresholds[i] is None else int(left >= wrap_thresholds[i])
                for i in range(len(y_offsets))
            ]
            shifted_offsets = [
                y_offsets[i] - wraps[i] * QUOT_MOD
                for i in range(len(y_offsets))
            ]
            carry_terms = [
                quotients[i] + carries[i] - a0 * wraps[i]
                for i in range(len(q_tail))
            ]
            base_y = [shifted_offsets[i] + left for i in range(len(y_offsets))]

            offset = solve_interval_offset(a0, a1, xs_tail, zs_tail, carry_terms, base_y, right - left)
            if offset is None:
                continue

            y_values = [base + offset for base in base_y]
            if any(value < 0 or value >= QUOT_MOD for value in y_values):
                continue
            lower_states = [
                xs_tail[i] + (y_values[i] << 14)
                for i in range(len(xs_tail))
            ]
            upper_states = [bit_xor(zs_tail[i], lower_states[i]) for i in range(len(xs_tail))]

            b0 = (lower_states[1] - a0 * lower_states[0]) & LOW_MASK
            carry = (a0 * lower_states[0] + b0) >> 128
            b1 = (
                upper_states[1]
                - a0 * upper_states[0]
                - a1 * lower_states[0]
                - carry
            ) & LOW_MASK
            b_full = b0 | (b1 << 128)
            state_2 = lower_states[0] | (upper_states[0] << 128)

            try:
                first_states = iter_congruence_solutions(a, (state_2 - b_full) & MASK, 256)
                for state_1 in first_states:
                    low = state_1 & LOW_MASK
                    high = state_1 >> 128
                    if (low & SLICE_MASK) != xs[0]:
                        continue
                    if bit_xor(low, high) != zs[0]:
                        continue
                    seeds = iter_congruence_solutions(a, (state_1 - b_full) & MASK, 256)
                    for seed in seeds:
                        if md5(str(seed).encode()).hexdigest() == seed_hash:
                            return seed
            except ValueError:
                continue

    return None

io = remote("1.95.115.179", 10000)
context.log_level = "info"
a = int(io.recvline().decode().split('=')[1].strip())
outs = list(map(int, io.recvline().decode().split('=')[1].strip()[1:-1].split(', ')))
seed_hash = io.recvline().decode().split('=')[1].strip()
time_start = time.time()
seed = solve_instance(a, outs, seed_hash)
if seed is not None:
    print(f"Found seed: {seed}")
    io.sendline(str(seed).encode())
    time_end = time.time()
    print(f"Solved in {time_end - time_start:.2f} seconds")
    print(io.recvall().decode())
else:
    print("No seed found")


# SUCTF{r0r_4nd_lll_t1ll_s33d_c0nf3ss35}

SU_RSA#

from Crypto.Util.number import *
flag = b'******'
m = bytes_to_long(flag)
bits = 1024
delta = 0.08
gamma = 0.39
delta0 = 0.33

p = getPrime(bits // 2)
q = getPrime(bits // 2)
N = p * q
d = getPrime(int(bits*delta0))
phi = (p-1)*(q-1)
e = inverse(d,phi)
S = p + q - (p + q) % (2**int(bits * gamma))
c = pow(m,e,N)

print("N =",N)
print("e =",e)
print("c =",c)
print("S =",S)

"""
N = 92365041570462372694496496651667282908316053786471083312533551094859358939662811192309357413068144836081960414672809769129814451275108424713386238306177182140825824252259184919841474891970355752207481543452578432953022195722010812705782306205731767157651271014273754883051030386962308159187190936437331002989
e = 11633089755359155730032854124284730740460545725089199775211869030086463048569466235700655506823303064222805939489197357035944885122664953614035988089509444102297006881388753631007277010431324677648173190960390699105090653811124088765949042560547808833065231166764686483281256406724066581962151811900972309623
c = 49076508879433623834318443639845805924702010367241415781597554940403049101497178045621761451552507006243991929325463399667338925714447188113564536460416310188762062899293650186455723696904179965363708611266517356567118662976228548528309585295570466538477670197066337800061504038617109642090869630694149973251
S = 19240297841264250428793286039359194954582584333143975177275208231751442091402057804865382456405620130960721382582620473853285822817245042321797974264381440
"""

找到了几乎原本的paper https://eprint.iacr.org/2025/1281.pdf ↗ 应该是对着 Theorem 6出的但是用Theo5的板子也就是经典Herrmann-May算法也可以出赛后问了别的师傅基本只要二元Copper的思路正确 LLM都能手写HM算法解出了

先贴下exp 再讲讲算法大体的思路链

exp.sage

import os
# clone RSA_CFL/attack.py from https://github.com/MengceZheng/RSA_CFL
from attack import approximate_sum_attack
from Crypto.Util.number import long_to_bytes
N = 92365041570462372694496496651667282908316053786471083312533551094859358939662811192309357413068144836081960414672809769129814451275108424713386238306177182140825824252259184919841474891970355752207481543452578432953022195722010812705782306205731767157651271014273754883051030386962308159187190936437331002989
e = 11633089755359155730032854124284730740460545725089199775211869030086463048569466235700655506823303064222805939489197357035944885122664953614035988089509444102297006881388753631007277010431324677648173190960390699105090653811124088765949042560547808833065231166764686483281256406724066581962151811900972309623
c = 49076508879433623834318443639845805924702010367241415781597554940403049101497178045621761451552507006243991929325463399667338925714447188113564536460416310188762062899293650186455723696904179965363708611266517356567118662976228548528309585295570466538477670197066337800061504038617109642090869630694149973251
S = 19240297841264250428793286039359194954582584333143975177275208231751442091402057804865382456405620130960721382582620473853285822817245042321797974264381440
bits = 1024
delta = 0.08
gamma = 0.39
delta0 = 0.33

solutions = approximate_sum_attack(N, e, S, delta0, gamma, 6, 4, "auto", 10)
assert solutions
w = solutions[1]

p_plus_q = S + w
disc = p_plus_q * p_plus_q - 4 * N
assert disc >= 0 and disc.is_square()
sqrt_disc = disc.sqrt()
p = (p_plus_q + sqrt_disc) // 2
q = (p_plus_q - sqrt_disc) // 2
assert p * q == N
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = pow(c, d, N)
print(f"flag : {long_to_bytes(m)}")

'''
INFO:root:Trying approximate_sum_attack with m = 6, t = 4...
INFO:root:Generating shifts...
INFO:root:Generating the lattice...
INFO:root:Reducing the lattice...
INFO:root:Reducing a 46 x 46 lattice within 2.108 seconds...
INFO:root:Reconstructed 45 non-constant polynomials...
INFO:root:Reduced to 10 bivariate polynomials after substituting u = x*y - 1...
INFO:root:Found one possible solution: x0 = 23046290722813476038718953853202262665577865587504904916206909233597137226666603418973995697517833379, y0 = 683148815721841766742686899713115888494025265940826866001098672064769240843667757982350507024623048793200922731436972626, u0 = 15744046214071294834103021682055868882274013700814065864022523774455730099651030460684829899987392033884802839357978059376159523387941398725360575425933917031997836744748181214612690925779888634778239676368707382452083253
flag : b'SUCTF{congratulation_you_know_small_d_with_hint_factor}'
'''

首先从私钥的生成过程可以得到 $ed - k(p-1)(q-1) = 1$ 然后令 $x = k$ ， $y = p+q-S$ 模 $e$ 下可以得到一个简单的方程 $f(x,y) = x(S - N - 1 + y) - 1 \equiv 0 \pmod e$ 按照paper的定义相关的bound为 $X = N^{\alpha+\delta_0-1}$ $Y = N^\gamma$

但是多元copper面对不齐次多项式效果不好或许是shift多项式次数不相对齐导致造出来的系数格不太均匀这里就体现在 $xy$ 变元那么可以引入一个新的变元 $u=xy-1$ 我们不去那么关注 $x\;y\;u$ 自己本身的线性关系而是利用小根的代数特性让格帮我们在归约中自动用上潜在的代数关系找出来小根此时三元多项式方程长这样 $g(x,y,u)=x(S-N-1)+u$ 虽然还是看起来2元但是在构造shift多项式的时候就会出现 $y \cdot f(x,y) = y(Ax + xy - 1) = Axy + xy^2 - y$ 再替换 $A(u+1) + y(u+1) - y = Au + A + yu + y - y = Au + yu + A$ 实现了降次优化了格的分布

后续看别的师傅的对话记录也发现了另一种构造shift的思路 Jochemsz-May 方法

核心在于对于 $f(x,y) = Ax + xy - 1 \equiv 0 \pmod e$ 线性项 $x$ 正常延展shift即可而非线性的 $y$ 项在延展过程中应该有选取的放入系数对于 $h(x,y) = y^j f(x,y)^k e^{m-k}$ $j$ 从 $1$ 取到 $t$ ； $k$ 不能从 $0$ 开始，而是从 $\lfloor \frac{m}{t} \rfloor j$ 取到 $m$ 从而减少冗余次项

如果预见次数大于1 或者不太齐次的系统都最好不要直接上 copper/Lattice了一般来说shift多项式的要求都会很高🫠

SU_Lattice#

逆向部分见 SUCTF-Lattice ↗

经过简单的测试总结靶机流程如下

动态生成1组64位整数 $m$

动态生成 24组64位整数 $a_i\;x_i$

能够无限获取hint

先计算 $y = \sum_{i=0}^{23} a_i x_i \pmod m$

再返回 $h = y \gg 20$

再更新状态 $(x_0,x_1,\dots,x_{22},x_{23}) \longrightarrow(x_1,x_2,\dots,x_{23},y)$

要求恢复 $\text{ans}\equiv\sum x_i\mod m$

搜到是2323.pdf (iacr.org) ↗

相关的格构造以及结式思路都来自文章下面用比较通俗的思路讲讲如何用上文章的构造

对模数的恢复#

先看hint 能够得到 $x_{i} = 2^{20}h_i + e_i$ 并且知道对于任何一个特别的 $x$ 都能找到递推关系 $x_{t+24} - a_{23}x_{t+23} - \dots - a_0x_t \equiv 0 \pmod m$ 这个关系只取决于 $m$ 与 $a_i$ 但是如果直接把 $x_{i} = 2^{20}h_i + e_i$ 代入会导致 $e_i$ 与 $a_i$ 是大小不齐的未知量而且 $m$ 也未知完全无法建立有效约束

但是我们转换一下思路反正要求的都是 $x_i$ 能否直接找到小系数 $d_i$ 使得 $\sum_{i=0}^{r-1} d_i x_i \equiv 0 \pmod m$ 此时再带入等式有 $2^{20}\sum d_i h_i + \sum d_i e_i \equiv 0 \pmod m$

那么 $\sum d_i h_i \equiv -\frac{\sum d_i e_i}{2^{20}} \pmod m$ 注意到 $e_i$ 和 $2^{20}$ 是一个数量级的而 $\sum d$ 也是比较小的量左边的 $h_i$ 却都已知那就转化为了一个熟悉的SIS问题解 $d_i$ 使得 $\sum d_ih_i\approx0\mod m$ 而在常见的格构造后是可以解出 $d_i$ 的

那么解出 $d_i$ 有什么用呢?

我们知道因为递推是存在的那么满足 $\sum_{i=0}^{r-1} d_i x_i \equiv 0 \pmod m$ 的序列 $d_i$ 是一定存在的而能够满足上述要求的序列就肯定满足 $\sum d_i h_i \equiv -\frac{\sum d_i e_i}{2^{20}} \pmod m$ 也就是 $\sum d_ih_i\approx0\mod m$ 我们可以取很多组的 $h$ 通过递推关系的约束进一步限定 $d$ 只要信息足够那么满足条件的 $d_i$ 序列就是可以被直接确定的不会存在别的可能做到这一步我们终于触及到了第一个名词 化零多项式 $F(x) = d_0 + d_1 x + d_2 x^2 + \dots + d_{r-1} x^{r-1}$

不难理解 $d_i$ 序列不是唯一的那么通过格方法就可以恢复至少两组化零多项式也就是对于任何化零多项式都可以被分解 $F(x) \equiv Q(x) \cdot f(x) \pmod m$

$f$ 就是这里特征多项式

构造结式的手法是给多项式灌入一个巨大的取值然后对输出的结果做GCD 这样子除了基本底层线性保留的性质带来的因子其他的性质都会被剥离也就 $R_{1,2} = \mathrm{Res}(f_1, f_2) = K_1 \cdot m^{24}$

$R_{1,3} = \mathrm{Res}(f_1, f_3) = K_2 \cdot m^{24}$

做GCD 如果结果是 $24\times64=1536$ 大小的数那尝试开 $24$ 方根再简单搜一下可恢复 $m$

恢复 $m$ 后就做多项式GCD就可以恢复特征多项式 $f$ 从而恢复系数 $a_i$

恢复LFSR状态#

由 $x_{24+k} \equiv \sum_{j=0}^{23} P_{k, j} x_{24+j} \pmod m$ 代入 $x_i = 2^{20}h_i + e_i$ 可以得到 $e_{24+k} \equiv \sum_{j=0}^{23} P_{k, j} e_j - C_k \pmod m$ 其中 $C_k \equiv 2^{20} \left( h_{24+k} - \sum_{j=0}^{23} P_{k, j} h_j \right) \pmod m$

其中 $P_{k,j}$ 可以通过对递推系数的伴随矩阵 $Q = \begin{pmatrix} 0 & 0 & \dots & 0 & a_0 \\ 1 & 0 & \dots & 0 & a_1 \\ 0 & 1 & \dots & 0 & a_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & a_{23} \end{pmatrix}$ 的不断幂次算出构造49维预期格 $L = \begin{pmatrix} 2^{19} & 2^{19} \dots 2^{19} & (C_{24} + 2^{19}) \dots (C_{47} + 2^{19}) \\ 0 & 1 \dots 0 & P_{24, 0} \dots P_{47, 0} \\ \vdots & \ddots \vdots & \vdots \ddots \vdots \\ 0 & 0 \dots 1 & P_{24, 23} \dots P_{47, 23} \\ 0 & 0 \dots 0 & m \dots 0 \\ \vdots & \vdots \ddots \vdots & \vdots \ddots \vdots \\ 0 & 0 \dots 0 & 0 \dots m \end{pmatrix}$ 会有 $\mathbf{u} = \begin{pmatrix} 1 & -e_0 & -e_1 & \dots & -e_{23} & -q_0 & -q_1 & \dots & -q_{23} \end{pmatrix}$ 满足 $\begin{pmatrix} 1 & -e_0 & -e_1 & \dots & -e_{23} & -q_0 & -q_1 & \dots & -q_{23} \end{pmatrix} \times\begin{pmatrix} 2^{19} & 2^{19} \dots 2^{19} & (C_{24} + 2^{19}) \dots (C_{47} + 2^{19}) \\ 0 & 1 \dots 0 & P_{24, 0} \dots P_{47, 0} \\ \vdots & \ddots \vdots & \vdots \ddots \vdots \\ 0 & 0 \dots 1 & P_{24, 23} \dots P_{47, 23} \\ 0 & 0 \dots 0 & m \dots 0 \\ \vdots & \vdots \ddots \vdots & \vdots \ddots \vdots \\ 0 & 0 \dots 0 & 0 \dots m \end{pmatrix}=\begin{pmatrix} 2^{19}, & 2^{19}-e_0, & \dots, & 2^{19}-e_{47} \end{pmatrix}$

右侧都是 $2^{19}$ 量级的小量可以被格出恢复了 $e_0,\dots,e_{23}$ 可以恢复 $(x_{24},x_{25},\dots,x_{47})$ 逆推 $x_t \equiv c_0^{-1}\left(x_{t+24}-\sum_{i=1}^{23} c_i x_{t+i}\right)\pmod m$ 即可

exp.sage

from pwn import *
from sage.all import *
import re
import time

context.log_level = "error"


ORDER = 24
ALPHA = 40
BETA = 20
HINT_COUNT = 160
TRUNC_COUNT = 48
R = 81
T = 80

STATE_BKZ_BLOCKS = (20, 24, 28)

FIRST_HINT_TIMEOUT = float("45.0")
HINT_TIMEOUT = float("30.0")
RECV_TIMEOUT = float("1.0")
DELAY = float("0.2")

HINT_RE = re.compile(rb"Here is your hint:\s*([+-]?\d+)")


def recv_some(io, timeout=RECV_TIMEOUT):
    try:
        return io.recvrepeat(timeout)
    except EOFError:
        return b""


def recv_until_hint(io, total_timeout):
    end = time.time() + total_timeout
    chunks = []
    while time.time() < end:
        chunk = recv_some(io, RECV_TIMEOUT)
        if chunk:
            chunks.append(chunk)
            data = b"".join(chunks)
            if HINT_RE.search(data):
                return data
        else:
            time.sleep(DELAY)
    return b"".join(chunks)


def collect_hints(io):
    hints = []
    for idx in range(HINT_COUNT):
        io.sendline(b"2")
        timeout = FIRST_HINT_TIMEOUT if idx == 0 else HINT_TIMEOUT
        data = recv_until_hint(io, timeout)
        match = HINT_RE.search(data)
        if not match:
            raise RuntimeError(f"failed to parse hint #{idx} from: {data!r}")
        hints.append(int(match.group(1)))
        if (idx + 1) % 16 == 0 or idx + 1 == HINT_COUNT:
            print(f"[+] collected {idx + 1}/{HINT_COUNT} hints")
        time.sleep(DELAY)
    return hints


def build_unknown_m_lattice(hints):
    q = Integer(1) << ALPHA
    L = Matrix(ZZ, R + T, R + T)
    for i in range(T):
        L[i, i] = q
    for i in range(R):
        window = hints[i : i + T]
        for j in range(T):
            L[T + i, j] = Integer(window[j])
        L[T + i, T + i] = 1
    return L


def coeffs_to_poly(coeffs):
    ring = ZZ["x"]
    x = ring.gen()
    return sum(ZZ(c) * x**i for i, c in enumerate(coeffs))


def extract_annihilating_rows(B):
    rows = []
    for idx in range(min(R, B.nrows())):
        coeffs = tuple(int(c) for c in list(B.row(idx)[T:]))
        rows.append({"index": idx, "coeffs": coeffs, "poly": coeffs_to_poly(coeffs)})
    return rows


def recover_modulus(rows):
    polys = [row["poly"] for row in rows]
    g = ZZ(0)
    for i in range(1, len(polys)):
        for j in range(i):
            rr = polys[i].resultant(polys[j])
            if rr == 0:
                continue
            g = gcd(g, abs(ZZ(rr)))
        if g != 0 and g.nbits() == (ALPHA + BETA) * ORDER:
            break
    if g == 0:
        raise RuntimeError("failed to recover gcd of resultants")

    approx = Integer((RR(g) ** (RR(1) / ORDER)).round())
    bound = 1 << BETA
    for delta in range(bound + 1):
        for cand in (approx - delta, approx + delta):
            cand = Integer(cand)
            if cand <= 1 or g % cand != 0:
                continue
            tmp = Integer(g)
            exp = 0
            while tmp % cand == 0:
                tmp //= cand
                exp += 1
            if exp >= ORDER:
                print(f"[+] recovered modulus = {cand}")
                return int(cand)
    raise RuntimeError(f"failed to refine exact modulus near {approx}")


def recover_coeffs(rows, modulus):
    field = GF(modulus)
    ring = PolynomialRing(field, "x")
    x = ring.gen()
    polys = []
    for row in rows:
        poly = sum(field(c) * x**i for i, c in enumerate(row["coeffs"]))
        if poly.degree() >= ORDER:
            polys.append((int(row["index"]), poly))
        if len(polys) >= 12:
            break

    best_degree = -1
    best_pair = None
    for i in range(1, len(polys)):
        for j in range(i):
            gg = polys[i][1].gcd(polys[j][1]).monic()
            degree = int(gg.degree())
            if degree > best_degree:
                best_degree = degree
                best_pair = (polys[j][0], polys[i][0])
            if degree == ORDER:
                coeffs = [int((-gg[k]) % modulus) for k in range(ORDER)]
                print(f"[+] recovered recurrence from rows {polys[j][0]} and {polys[i][0]}")
                return coeffs
    raise RuntimeError(
        f"failed to recover degree-{ORDER} polynomial, best degree was {best_degree} from pair {best_pair}"
    )


def build_state_lattice(hints, modulus, coeffs):
    two_beta = 1 << BETA
    half = 1 << (BETA - 1)

    Q = Matrix(ZZ, ORDER, ORDER)
    Q_power = identity_matrix(ZZ, ORDER)
    L = Matrix(ZZ, TRUNC_COUNT + 1, TRUNC_COUNT + 1)

    Q[0, ORDER - 1] = coeffs[0]
    for i in range(1, ORDER):
        Q[i, i - 1] = 1
        Q[i, ORDER - 1] = coeffs[i]

    for _ in range(1, ORDER):
        Q_power = (Q_power * Q).apply_map(lambda z: z % modulus)

    for i in range(ORDER, TRUNC_COUNT):
        Q_power = (Q_power * Q).apply_map(lambda z: z % modulus)
        acc = 0
        for j in range(ORDER):
            L[j + 1, i + 1] = Q_power[j, 0]
            acc += Q_power[j, 0] * hints[j]
        L[0, i + 1] = (two_beta * (hints[i] - acc)) % modulus + half

    L[0, 0] = half
    for i in range(1, ORDER + 1):
        L[0, i] = half
        L[i, i] = 1
    for i in range(ORDER + 1, TRUNC_COUNT + 1):
        L[i, i] = modulus
    return L


def forward_step(state, coeffs, modulus):
    return sum(coeffs[i] * state[i] for i in range(ORDER)) % modulus


def recover_observed_state(hints, modulus, coeffs):
    half = 1 << (BETA - 1)
    two_beta = 1 << BETA
    L = build_state_lattice(hints[:TRUNC_COUNT], modulus, coeffs)
    tried_rows = []

    for block_size in STATE_BKZ_BLOCKS:
        B = L.BKZ(block_size=block_size)
        for row_idx in range(B.nrows()):
            row = list(B.row(row_idx))
            if row[0] == half:
                low = [int((half - row[i + 1]) % two_beta) for i in range(ORDER)]
            elif row[0] == -half:
                low = [int((row[i + 1] + half) % two_beta) for i in range(ORDER)]
            else:
                continue

            tried_rows.append(int(row_idx))
            observed = [hints[i] * two_beta + low[i] for i in range(ORDER)]
            state = list(observed)
            ok = True
            for idx in range(ORDER, TRUNC_COUNT):
                nxt = forward_step(state, coeffs, modulus)
                if nxt >> BETA != hints[idx]:
                    ok = False
                    break
                state = state[1:] + [nxt]
            if ok:
                print(f"[+] recovered observed state from BKZ-{block_size} row {row_idx}")
                return observed

    raise RuntimeError(f"failed to validate any state candidate, tried rows {tried_rows}")


def step_back(state, coeffs, modulus, steps):
    st = list(state)
    inv_c0 = int(inverse_mod(coeffs[0], modulus))
    for _ in range(steps):
        prev = (st[-1] - sum(coeffs[j] * st[j - 1] for j in range(1, ORDER))) * inv_c0 % modulus
        st = [prev] + st[:-1]
    return st


def compute_answer(hints, modulus, coeffs):
    observed = recover_observed_state(hints, modulus, coeffs)
    initial = step_back(observed, coeffs, modulus, ORDER)
    return sum(initial) % modulus


def submit_answer(io, answer):
    io.sendline(b"1")
    io.sendline(str(answer).encode())
    time.sleep(DELAY)
    data = recv_some(io, float("5.0"))
    data += recv_some(io, float("5.0"))
    return data.decode("utf-8", "ignore")


io = remote("1.95.152.117", 10001)
try:
    hints = collect_hints(io)

    print("[+] running unknown-modulus BKZ")
    reduced = build_unknown_m_lattice(hints).BKZ(block_size=20)
    rows = extract_annihilating_rows(reduced)

    modulus = recover_modulus(rows)
    coeffs = recover_coeffs(rows, modulus)
    answer = compute_answer(hints, modulus, coeffs)

    print(f"[+] recovered answer = {answer}")
    print(submit_answer(io, answer))
finally:
    io.close()


# SUCTF{b8faea32-9f91-42b5-9355-33865e06270c}

SU_Isogeny#

from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import *
from hashlib import sha256
from secret import flag
from random import randint
import os

p = 5326738796327623094747867617954605554069371494832722337612446642054009560026576537626892113026381253624626941643949444792662881241621373288942880288065659

F = GF(p)

pl = [x for x in prime_range(3, 374) + [587]]
pvA = [randint(-5, 5) for _ in pl]
pvB = [randint(-5, 5) for _ in pl]

assert len(pl) == len(pvA) == len(pvB)


def cal(A, sk):
    E = EllipticCurve(F, [0, A, 0, 1, 0])
    for sgn in [1, -1]:
        for e, ell in zip(sk, pl):
            for i in range(sgn * e):
                while not (P := (p + 1) // ell * E.random_element()) or ell * P != 0:
                    pass
                E = E.isogeny_codomain(P)
        E = E.quadratic_twist()
    return E.montgomery_model().a2()

menu = """[1] Get public key
[2] Get gift
[3] Get flag
[4] Exit
>>> """

def main():
    while True:
        try:
            op = input(menu)
            if op == "1":
                pkA = cal(0, pvA)
                pkB = cal(0, pvB)
                print(f"pkA: {pkA}")
                print(f"pkB: {pkB}")
            elif op == "2":
                pkA = int(input("pkA >>> "))
                pkB = int(input("pkB >>> "))
                A = cal(pkA, pvB)
                B = cal(pkB, pvA)
                if A != B:
                    print("Illegal public key!")
                print(f"Gift : {int(A) >> 200}")
            elif op == "3":
                key = sha256(str(cal(cal(0, pvB), pvA)).encode()).digest()
                print(f"Here is your flag: {AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16)).hex()}")
            elif op == "4":
                print("Bye~")
                break
            else:
                print("Invalid option.")
        except:
            print("Something wrong...")
            break

if __name__ == "__main__":
    main()

是一道CI-HNP问题可以参考 https://eprint.iacr.org/2023/1409.pdf ↗ 基本上是一样的情景复现了这里简单学习一下相关同源的结构

def cal(A, sk):
    E = EllipticCurve(F, [0, A, 0, 1, 0])
    for sgn in [1, -1]:
        for e, ell in zip(sk, pl):
            for i in range(sgn * e):
                while not (P := (p + 1) // ell * E.random_element()) or ell * P != 0:
                    pass
                E = E.isogeny_codomain(P)
        E = E.quadratic_twist()
    return E.montgomery_model().a2()

相关的代数几何名词看的头痛😵 总结一下

对于一条蒙哥马利曲线 $E_A: y^2 = x^3 + Ax^2 + x$ 可以计算它的同源 $B = \frac{2A - 12}{A + 2}$ $C = \frac{2A + 12}{2 - A}$ 对应的曲线可以得到

AB - 2A + 2B + 12 = 0

BC - 2B + 2C + 12 = 0

AC + 2A - 2C + 12 = 0

落到题目里面使用就是对于题目给我们的公钥 $M_a\;M_b$ 可以计算同源公钥

M_{ac} = \frac{2M_a - 12}{M_a + 2}

M_{ab} = \frac{2M_a + 12}{2 - M_a}

提交给Gift接口可以获得剩下的两组额外信息高位

A = A_{hi} \cdot 2^{200} + x

B = B_{hi} \cdot 2^{200} + y

C = C_{hi} \cdot 2^{200} + z

带回上式可得

f(x,y,z) = (A_0 + x)(B_0 + y) - 2(A_0 + x) + 2(B_0 + y) + 12

g(x,y,z) = (B_0 + y)(C_0 + z) - 2(B_0 + y) + 2(C_0 + z) + 12

h(x,y,z) = (A_0 + x)(C_0 + z) + 2(A_0 + x) - 2(C_0 + z) + 12

此时可以用作者在https://github.com/juliannowakowski/automated-coppersmith ↗ 提供的板子来打出来低位

exp.sage

from copy import deepcopy
import logging
import os
import re
import tempfile
import time
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from fpylll import IntegerMatrix
from pwn import *


context.log_level = "critical"

P = ZZ(5326738796327623094747867617954605554069371494832722337612446642054009560026576537626892113026381253624626941643949444792662881241621373288942880288065659)
F = GF(P)
UNKNOWN_BITS = 200
BOUND = 2 ** 200



def extract_match(pattern, text):
    match = re.search(pattern, text)
    if match is None:
        raise ValueError(f"Could not parse `{pattern}` from output:\n{text}")
    return match.group(1)


def send_choice(io, option):
    io.sendline(str(option).encode())


def read_line_matching(io, marker):
    while True:
        line = io.recvline().decode(errors="ignore")
        if marker in line:
            return line


def get_public_keys(io):
    send_choice(io, 1)
    pk_a = int(extract_match(r"pkA:\s*(\d+)", read_line_matching(io, "pkA:")))
    pk_b = int(extract_match(r"pkB:\s*(\d+)", read_line_matching(io, "pkB:")))
    return pk_a, pk_b


def get_gift(io, pk_a, pk_b):
    send_choice(io, 2)
    io.sendline(str(pk_a).encode())
    io.sendline(str(pk_b).encode())
    return int(extract_match(r"Gift\s*:\s*(\d+)", read_line_matching(io, "Gift :")))


def get_ciphertext(io):
    send_choice(io, 3)
    line = read_line_matching(io, "flag:")
    return bytes.fromhex(extract_match(r"flag:\s*([0-9a-fA-F]+)", line))


def get_four_neighbors(pk_a):
    a = F(pk_a)
    neigh_left = ZZ((2 * a - 12) / (a + 2))
    neigh_right = ZZ((2 * a + 12) / (2 - a))
    return neigh_left, neigh_right


def getBestShiftPoly(mon, polys, monomials, poly=1, label=None, best_label=None, best_poly=None, start=0):
    ring = polys[0].parent()
    count = len(polys)

    if label is None:
        label = [0] * count
        best_label = [0] * count
        best_poly = ring(1)

    shift_poly = poly * mon
    if set(shift_poly.monomials()).issubset(monomials):
        if sum(best_label) <= sum(label):
            best_label = label
            best_poly = shift_poly

        for idx in range(start, count):
            lead = polys[idx].lm()
            if mon % lead == 0:
                next_label = deepcopy(label)
                next_label[idx] += 1
                next_poly = poly * polys[idx]
                next_mon = ring(mon / lead)
                best_label, best_poly = getBestShiftPoly(
                    next_mon,
                    polys,
                    monomials,
                    next_poly,
                    next_label,
                    best_label,
                    best_poly,
                    idx,
                )

    return best_label, best_poly


def constructOptimalShiftPolys(polys, monomials, modulus, m):
    shifts = []
    monomial_set = set(monomials)

    for mon in monomials:
        label, poly = getBestShiftPoly(mon, polys, monomial_set)
        shifts.append(poly * modulus ** (m - sum(label)))

    return shifts


def coppersmithsMethod(polys, modulus, bounds, gb_relations=None, verbose=False):
    if gb_relations is None:
        gb_relations = []

    ring = polys[0].parent()
    for poly in polys:
        if poly.parent() != ring:
            raise ValueError("All polynomials must lie in the same ring.")

    tt = cputime()
    mon_list = []
    mon_dict = {}

    for poly in polys:
        for mon in poly.monomials():
            if mon not in mon_dict:
                mon_dict[mon] = len(mon_list)
                mon_list.append(mon)

    basis = zero_matrix(ZZ, len(polys), len(mon_list))
    for row, poly in enumerate(polys):
        for mon in poly.monomials():
            basis[row, mon_dict[mon]] = ZZ(poly.monomial_coefficient(mon) * mon(*bounds))

    if verbose:
        print("Finished basis generation. Polynomials: %d. Time: %fs." % (len(polys), cputime(tt)))

    fd_in, path_in = tempfile.mkstemp(prefix="basis.", suffix=".tmp")
    os.close(fd_in)
    fd_out, path_out = tempfile.mkstemp(prefix="basis_out.", suffix=".tmp")
    os.close(fd_out)
    os.remove(path_out)

    start = time.time()
    try:
        with open(path_in, "w", encoding="ascii") as handle:
            basis_str = basis.str()
            basis_str = "\n".join(" ".join(line.split()) for line in basis_str.split("\n"))
            handle.write("[\n" + basis_str + "\n]")

        success = os.system(f"flatter -v {path_in} {path_out} >/dev/null 2>&1")
        if success == 0 and os.path.exists(path_out):
            basis_lll = matrix(IntegerMatrix.from_file(path_out))
        else:
            if verbose:
                print("flatter not found. Resorting to FPLLL.")
            basis_lll = basis.LLL()
    finally:
        if os.path.exists(path_in):
            os.remove(path_in)
        if os.path.exists(path_out):
            os.remove(path_out)

    if verbose:
        print("Finished basis reduction. Time: %fs." % (time.time() - start))

    tt = cputime()
    solution_polynomials = list(gb_relations)

    for vector in basis_lll:
        sq_norm = sum(entry ** 2 for entry in vector)
        norm = RR(sqrt(sq_norm))
        if norm < RR(modulus / sqrt(basis_lll.ncols())):
            poly = ring(0)
            for idx, mon in enumerate(mon_list):
                poly += ring(ZZ(vector[idx] / mon(*bounds))) * mon
            solution_polynomials.append(poly)

    if verbose:
        print("Found %d short polynomials. Time: %fs." % (len(solution_polynomials), cputime(tt)))

    tt = cputime()
    var_count = len(ring.gens())
    if len(solution_polynomials) < var_count:
        raise RuntimeError("LLL did not find enough short polynomials.")

    prime_mod = 0
    max_bound = max(bounds)
    crt_modulus = 1
    fail_counter = 0
    crt_results = [[] for _ in range(var_count)]
    moduli = []

    while crt_modulus < max_bound:
        prime_mod = next_prime(prime_mod + 1)
        gb_ring = ring.change_ring(GF(prime_mod))
        ideal_gb = gb_ring * solution_polynomials

        success = True
        try:
            solutions = ideal_gb.variety()
        except ValueError:
            success = False

        if success and len(solutions) == 1:
            solution = solutions[0]
            crt_modulus *= prime_mod
            moduli.append(prime_mod)
            for idx, var in enumerate(gb_ring.gens()):
                crt_results[idx].append(ZZ(solution[var]))
        else:
            fail_counter += 1
            if fail_counter > 100:
                raise RuntimeError("Coppersmith heuristic failed during Groebner basis extraction.")

    roots = [crt(crt_results[idx], moduli) for idx in range(var_count)]
    if verbose:
        print("Finished extracting solutions. Time: %fs." % cputime(tt))
    return roots


def build_polynomials(a_high, b_high, c_high):
    ring = PolynomialRing(QQ, names=("x", "y", "z"), order="lex")
    x, y, z = ring.gens()

    a_known = ZZ(a_high) << UNKNOWN_BITS
    b_known = ZZ(b_high) << UNKNOWN_BITS
    c_known = ZZ(c_high) << UNKNOWN_BITS

    f = (a_known + x) * (b_known + y) - 2 * (a_known + x) + 2 * (b_known + y) + 12
    g = (b_known + y) * (c_known + z) - 2 * (b_known + y) + 2 * (c_known + z) + 12
    h = (a_known + x) * (c_known + z) + 2 * (a_known + x) - 2 * (c_known + z) + 12
    return [f, g, h]


def recover_low_bits(polys, lift_param):
    total_m = lift_param * len(polys)
    monomials = (prod(polys) ** lift_param).monomials()
    tt = cputime()
    shifts = constructOptimalShiftPolys(polys, monomials, P, total_m)
    print("Finished construction of F. Time: %fs." % cputime(tt))
    return coppersmithsMethod(shifts, P ** total_m, [BOUND, BOUND, BOUND], verbose=True)


def decrypt_flag(shared_secret, ciphertext):
    key = sha256(str(shared_secret).encode()).digest()
    plain = AES.new(key, AES.MODE_ECB).decrypt(ciphertext)
    return unpad(plain, 16)


io = remote("1.95.115.179", 10020)
# io = process(["sage", "main.sage"])
try:
    pk_a, pk_b = get_public_keys(io)
    neigh_b, neigh_c = get_four_neighbors(pk_a)

    a_high = get_gift(io, pk_a, pk_b)
    b_high = get_gift(io, neigh_b, pk_b)
    c_high = get_gift(io, neigh_c, pk_b)
    ciphertext = get_ciphertext(io)
    try:
        send_choice(io, 4)
        io.recvall(timeout=1)
    except EOFError:
        pass
finally:
    io.close()

polys = build_polynomials(a_high, b_high, c_high)
roots = None
errors = []
for lift_param in (2, 3):
    try:
        print("Trying Coppersmith with i=%d (m=%d)." % (lift_param, lift_param * len(polys)))
        roots = recover_low_bits(polys, lift_param)
        break
    except Exception as exc:
        errors.append((lift_param, exc))
        print("Attack with i=%d failed: %s" % (lift_param, exc))

if roots is None:
    raise RuntimeError("All attack attempts failed: %s" % errors)

a_low, b_low, c_low = [ZZ(root) for root in roots]
shared_a = (ZZ(a_high) << UNKNOWN_BITS) + a_low
shared_b = (ZZ(b_high) << UNKNOWN_BITS) + b_low
shared_c = (ZZ(c_high) << UNKNOWN_BITS) + c_low

rel1 = (shared_a * shared_b - 2 * shared_a + 2 * shared_b + 12) % P
rel2 = (shared_b * shared_c - 2 * shared_b + 2 * shared_c + 12) % P
rel3 = (shared_a * shared_c + 2 * shared_a - 2 * shared_c + 12) % P
if rel1 != 0 or rel2 != 0 or rel3 != 0:
    raise RuntimeError("Recovered roots do not satisfy the expected 4-isogeny relations.")

flag = decrypt_flag(shared_a, ciphertext)
print("Recovered shared secret:", shared_a)
print("Recovered neighbor secrets:", shared_b, shared_c)
print("Flag:", flag.decode())


'''
Trying Coppersmith with i=2 (m=6).
Finished construction of F. Time: 0.039737s.
Finished basis generation. Polynomials: 125. Time: 0.025680s.
Finished basis reduction. Time: 9.266464s.
Found 124 short polynomials. Time: 0.352170s.
Finished extracting solutions. Time: 4.042748s.
Recovered shared secret: 1672942619534887965573920438280504605792943318764049587502648685145885365965606861377955086783558626765727125032148831292668306286951068563000361240089452
Recovered neighbor secrets: 3872056749387382194069664377584619614798426812381164915955853186810223077545073241108422889264230215208230223028075268471889218579824877567506779591516196 2772347080826602703954667975101629592766793647930358033219048220019502470775459090167354410319534796817838761469244727697472164754215465010304348331595777
Flag: SUCTF{Actu41ly_th1s_iS_4_Pr0blem_7hat_w4s_s0lved_1n_2023_https://eprint.iacr.org/2023/1409}
'''

SU_Restaurant#

from Crypto.Util.number import *
from Crypto.Util.Padding import *
from random import randint, choice, choices
from hashlib import sha3_512
from base64 import b64encode, b64decode
from secret import flag
import numpy as np
import json
import os
# import pty

H = lambda x: [int(y, 16) for y in [sha3_512(x).hexdigest()[i:i+2] for i in range(0, 128, 2)]]
alphabet = "".join([chr(i) for i in range(33, 127)])

class Point:
    def __init__(self, x):
        if isinstance(x, float):
            raise ValueError("...")
        while not isinstance(x, int):
            x = x.x
        self.x = x

    def __add__(self, other):
        if isinstance(other, int):
            return self.x + other
        return Point(min(self.x, other.x))

    def __radd__(self, other):
        if isinstance(other, int):
            return self.x + other
        return Point(min(self.x, other.x))

    def __mul__(self, other):
        return Point(self.x + other.x)

    def __eq__(self, other):
        return self.x == other.x

    def __repr__(self):
        return f"{self.x}"

    def __int__(self):
        return self.x


class Block:
    def __init__(self, n, m, data=None):
        self.n = n
        self.m = m
        if data and (len(data) != n or len(data[0]) != m):
            raise ValueError("...")
        if data:
            if isinstance(data, Point):
                self.data = [[Point(data[i][j].x) for j in range(m)] for i in range(n)]
            else:
                self.data = [[Point(data[i][j]) for j in range(m)] for i in range(n)]
        else:
            self.data = [[Point(randint(0, 255)) for _ in range(m)] for _ in range(n)]

    def __add__(self, other):
        return Block(self.n, self.m, [[self.data[i][j] + other.data[i][j] for j in range(self.m)] for i in range(self.n)])

    def __mul__(self, other):
        assert self.m == other.n, "😭"
        res = [[Point(511) for _ in range(other.m)] for _ in range(self.n)]
        for i in range(self.n):
            for j in range(other.m):
                for k in range(self.m):
                    res[i][j] = res[i][j] + (self.data[i][k] * other.data[k][j])

        return Block(self.n, other.m, res)

    def __eq__(self, other):
        res = True
        for i in range(self.n):
            for j in range(self.m):
                res = res and self.data[i][j] == other.data[i][j]
        return res

    def __getitem__(self, item):
        return self.data[item]

    def __repr__(self):
        return f"{self.data}"

    def legitimacy(self, lb, rb):
        for i in range(self.n):
            for j in range(self.m):
                if not (lb <= int(self.data[i][j].x) <= rb):
                    return False
        return True

class Restaurant:
    def __init__(self, m, n, k):
        self.m, self.n, self.k = m, n, k
        self.chef = Block(m, k)
        self.cooker = Block(k, n)
        self.fork = self.chef * self.cooker

    def cook(self, msg):
        if isinstance(msg, str):
            msg = msg.encode()
        tmp = H(msg)
        M = Block(self.n, self.m, [[tmp[i * self.m + j] for j in range(self.m)] for i in range(self.n)])
        while True:
            U = Block(self.n, self.k)
            V = Block(self.k, self.m)
            P = self.chef * V
            R = U * self.cooker
            S = U * V
            A = (M * self.chef) + U
            B = (self.cooker * M) + V
            if A != U and B != V:
                break
        return A, B, P, R, S

    def eat(self, msg, A, B, P, R, S):
        if isinstance(msg, str):
            msg = msg.encode()
        tmp = H(msg)
        M = Block(self.n, self.m, [[tmp[i * self.m + j] for j in range(self.m)] for i in range(self.n)])
        Z = (M * self.fork * M) + (M * P) + (R * M) + S
        W = A * B
        legal = A.legitimacy(0, 256) and B.legitimacy(0, 256) and P.legitimacy(0, 256) and R.legitimacy(0, 256) and S.legitimacy(0, 256)
        return W == Z and W != S and legal


banner = """=================================================================
 ____  _   _   ____           _                              _   
/ ___|| | | | |  _ \ ___  ___| |_ __ _ _   _ _ __ __ _ _ __ | |_ 
\___ \| | | | | |_) / _ \/ __| __/ _` | | | | '__/ _` | '_ \| __|
 ___) | |_| | |  _ <  __/\__ \ || (_| | |_| | | | (_| | | | | |_ 
|____/ \___/  |_| \_\___||___/\__\__,_|\__,_|_|  \__,_|_| |_|\__|
=================================================================
"""

menu = """Do something...
[1] Say to the waiter: "Please give me some food."
[2] Say to the waiter: "Please give me the FLAG!"
[3] Check out
What do you want to do? 
>>> """

foodlist = ["Spring rolls", "Red Rice Rolls", "Chencun Rice Noodles", "Egg Tart", "Cha siu bao"]
table = []

def main():
    print(banner)
    SU_Restaurant = Restaurant(8, 8, 7)

    havefork = False
    try:
        while True:
            op = int(input(menu))
            if op == 1:
                if len(table) == 2:
                    print("You're full and don't want to order more...")
                    continue
                foodname = choice(foodlist)
                while foodname in table:
                    foodname = choice(foodlist)
                print(f'The waiter says: "Here is your {foodname}!"')
                table.append(foodname)
                A, B, P, R, S = SU_Restaurant.cook(foodname)
                print(f'A = {A}\nB = {B}\nP = {P}\nR = {R}\nS = {S}')

            elif op == 2:
                Fo0dN4mE = "".join(choices(alphabet, k=36))
                print(f'The waiter says: "Please make {Fo0dN4mE} for me!"')
                res = json.loads(input(">>> "))
                r1 = np.linalg.matrix_rank(np.array(res["A"]))
                r2 = np.linalg.matrix_rank(np.array(res["B"]))
                r3 = np.linalg.matrix_rank(np.array(res["P"]))
                r4 = np.linalg.matrix_rank(np.array(res["R"]))
                r5 = np.linalg.matrix_rank(np.array(res["S"]))

                if r1 < 7 or r2 < 7 or r3 < 8 or r4 < 8 or r5 < 8:
                    print('The waiter says: "These are illegal food ingredients"')
                    continue

                A = Block(8, 7, res["A"])
                B = Block(7, 8, res["B"])
                P = Block(8, 8, res["P"])
                R = Block(8, 8, res["R"])
                S = Block(8, 8, res["S"])
                if SU_Restaurant.eat(Fo0dN4mE, A, B, P, R, S):
                    print(f'The waiter says: "Here is the FLAG: {flag}"')
                else:
                    print('The waiter says: "This is not what I wanted!"')
                    exit(0)

            elif op == 3:
                print('The waiter says: "Welcome to our restaurant next time!"')
                break
            else:
                print("Invalid option!")
    except:
        print("Something wrong...")
        exit(0)

if __name__ == "__main__":
    main()

https://eprint.iacr.org/2026/387.pdf ↗

基于热带半环的签名系统可以复用Theo6 使用SMT的方法来解出之前UniCTF也出过一道相关的热带半环的题总之在逻辑结构层面的逻辑电路对于Z3相当友好转化出 $(c = a_1) \lor (c = a_2) \lor \dots \lor (c = a_t)$ 利于求解的式子然后针对可计算的公钥量 $W^{(r)} = A^{(r)} \otimes B^{(r)}$ 从签名层面建立约束即可 Z3可能会找到伪解多重连打几次就行犯懒原谅这次先放exp了后续遇到相关半环题一定详细写分析

exp.py

import ast
import json
import random
import re
import sys

import numpy as np
from pwn import *
from z3 import Int, Or, Solver, sat

from main import H


context.log_level = "info"

MENU_PROMPT = b">>> "
TARGET_RE = re.compile(r'Please make (?P<msg>.+?) for me!')
FOOD_RE = re.compile(r"Here is your (?P<food>.+?)!")
MATRIX_RE = re.compile(r"([ABPRS]) = (\[\[.*?\]\])", re.S)


def hash_matrix(msg):
    if isinstance(msg, str):
        msg = msg.encode()
    tmp = H(msg)
    return [[tmp[i * 8 + j] for j in range(8)] for i in range(8)]


def trop_add(a, b):
    return [[min(a[i][j], b[i][j]) for j in range(len(a[0]))] for i in range(len(a))]


def trop_mul(a, b):
    rows = len(a)
    mid = len(b)
    cols = len(b[0])
    out = [[0] * cols for _ in range(rows)]
    for i in range(rows):
        for j in range(cols):
            out[i][j] = min(a[i][k] + b[k][j] for k in range(mid))
    return out


def add_min_eq(solver, c, terms):
    for term in terms:
        solver.add(c <= term)
    solver.add(Or(*[c == term for term in terms]))


def parse_signature_block(blob):
    text = blob.decode()
    food_match = FOOD_RE.search(text)
    if not food_match:
        raise ValueError(f"failed to parse food name from:\n{text}")
    mats = {}
    for name, matrix_text in MATRIX_RE.findall(text):
        mats[name] = ast.literal_eval(matrix_text)
    if set(mats) != {"A", "B", "P", "R", "S"}:
        raise ValueError(f"failed to parse all matrices from:\n{text}")
    return food_match.group("food"), mats


def collect_two_signatures(io):
    sigs = []
    io.recvuntil(MENU_PROMPT)
    for _ in range(2):
        io.sendline(b"1")
        blob = io.recvuntil(MENU_PROMPT, drop=False)
        food, mats = parse_signature_block(blob)
        entry = {
            "food": food,
            "M": hash_matrix(food),
            "A": mats["A"],
            "B": mats["B"],
            "P": mats["P"],
            "R": mats["R"],
            "S": mats["S"],
        }
        entry["W"] = trop_mul(entry["A"], entry["B"])
        sigs.append(entry)
    return sigs


def recover_equivalent_key(signatures, timeout_ms=120000):
    solver = Solver()
    solver.set(timeout=timeout_ms)

    x = [[Int(f"x_{i}_{j}") for j in range(7)] for i in range(8)]
    y = [[Int(f"y_{i}_{j}") for j in range(8)] for i in range(7)]
    t = [[Int(f"t_{i}_{j}") for j in range(8)] for i in range(8)]
    u_all = []
    v_all = []

    for r in range(len(signatures)):
        u_all.append([[Int(f"u_{r}_{i}_{j}") for j in range(7)] for i in range(8)])
        v_all.append([[Int(f"v_{r}_{i}_{j}") for j in range(8)] for i in range(7)])

    for arr in [x, y] + u_all + v_all:
        for row in arr:
            for var in row:
                solver.add(var >= 0, var <= 255)
    for row in t:
        for var in row:
            solver.add(var >= 0, var <= 510)

    for i in range(8):
        for j in range(8):
            add_min_eq(solver, t[i][j], [x[i][k] + y[k][j] for k in range(7)])

    for r, sig in enumerate(signatures):
        m = sig["M"]
        a = sig["A"]
        b = sig["B"]
        p = sig["P"]
        rr = sig["R"]
        s = sig["S"]
        w = sig["W"]
        u = u_all[r]
        v = v_all[r]

        for i in range(8):
            for j in range(7):
                add_min_eq(solver, a[i][j], [u[i][j]] + [m[i][k] + x[k][j] for k in range(8)])

        for i in range(7):
            for j in range(8):
                add_min_eq(solver, b[i][j], [v[i][j]] + [y[i][k] + m[k][j] for k in range(8)])

        for i in range(8):
            for j in range(8):
                add_min_eq(solver, p[i][j], [x[i][k] + v[k][j] for k in range(7)])
                add_min_eq(solver, rr[i][j], [u[i][k] + y[k][j] for k in range(7)])
                add_min_eq(solver, s[i][j], [u[i][k] + v[k][j] for k in range(7)])

                mtm_terms = [m[i][a0] + t[a0][b0] + m[b0][j] for a0 in range(8) for b0 in range(8)]
                mp_terms = [m[i][k] + p[k][j] for k in range(8)]
                rm_terms = [rr[i][k] + m[k][j] for k in range(8)]
                add_min_eq(solver, w[i][j], mtm_terms + mp_terms + rm_terms + [s[i][j]])

    if solver.check() != sat:
        raise RuntimeError("SMT solver did not find a satisfying equivalent key")

    model = solver.model()
    x_val = [[model[x[i][j]].as_long() for j in range(7)] for i in range(8)]
    y_val = [[model[y[i][j]].as_long() for j in range(8)] for i in range(7)]
    t_val = [[model[t[i][j]].as_long() for j in range(8)] for i in range(8)]
    return x_val, y_val, t_val


def forge_payload(target, x, y, max_attempts=2000):
    m = hash_matrix(target)
    for _ in range(max_attempts):
        u = [[random.randint(0, 255) for _ in range(7)] for _ in range(8)]
        v = [[random.randint(0, 255) for _ in range(8)] for _ in range(7)]
        a = trop_add(trop_mul(m, x), u)
        b = trop_add(trop_mul(y, m), v)
        p = trop_mul(x, v)
        r = trop_mul(u, y)
        s = trop_mul(u, v)

        ranks = [np.linalg.matrix_rank(np.array(mat)) for mat in [a, b, p, r, s]]
        if ranks[0] >= 7 and ranks[1] >= 7 and ranks[2] >= 8 and ranks[3] >= 8 and ranks[4] >= 8:
            return {
                "A": a,
                "B": b,
                "P": p,
                "R": r,
                "S": s,
            }
    raise RuntimeError("failed to sample a payload that passes the rank checks")


def request_target(io):
    io.sendline(b"2")
    blob = io.recvuntil(MENU_PROMPT, drop=False)
    text = blob.decode()
    match = TARGET_RE.search(text)
    if not match:
        raise ValueError(f"failed to parse target message from:\n{text}")
    return match.group("msg"), blob


def run_once(attempt):
    # io = process(["python", "main.py"])
    io = remote("101.245.107.149", 10020)
    try:
        signatures = collect_two_signatures(io)
        foods = ", ".join(sig["food"] for sig in signatures)
        print(f"[*] attempt {attempt}: signatures = {foods}")

        x, y, t = recover_equivalent_key(signatures)
        print(f"[*] attempt {attempt}: recovered model sample x[0][0]={x[0][0]}, y[0][0]={y[0][0]}, t[0][0]={t[0][0]}")

        target, _ = request_target(io)
        print(f"[*] attempt {attempt}: target = {target}")

        payload = forge_payload(target, x, y)
        io.sendline(json.dumps(payload).encode())
        result = io.recvall(timeout=2).decode(errors="replace")
        success = "SUCTF{" in result
        return success, result
    finally:
        io.close()


def main():
    max_attempts = 20
    for attempt in range(1, max_attempts + 1):
        success, result = run_once(attempt)
        print(result)
        if success:
            return
    raise SystemExit(f"failed after {max_attempts} attempts")


if __name__ == "__main__":
    main()

'''
The waiter says: "This is not what I wanted!"
Something wrong...

[x] Opening connection to 101.245.107.149 on port 10020
[x] Opening connection to 101.245.107.149 on port 10020: Trying 101.245.107.149
[+] Opening connection to 101.245.107.149 on port 10020: Done
[*] attempt 2: signatures = Red Rice Rolls, Cha siu bao
[*] attempt 2: recovered model sample x[0][0]=147, y[0][0]=155, t[0][0]=28
[*] attempt 2: target = 1g-$bM:s6fgsDqQ7.+b#F,%+sNOx)*uof{"&
[x] Receiving all data
[x] Receiving all data: 0B
[x] Receiving all data: 246B
[+] Receiving all data: Done (246B)
[*] Closed connection to 101.245.107.149 port 10020
The waiter says: "Here is the FLAG: b'SUCTF{W3lc0m3_t0_SU_R3stAur4nt_n3Xt_t1me!:-)}'"
Do something...
[1] Say to the waiter: "Please give me some food."
[2] Say to the waiter: "Please give me the FLAG!"
[3] Check out
What do you want to do?
'''

Above#

SU_AES#

AES实现的差异#

PFA与差分思路#

SU_PRNG#

思路梳理#

左旋恢复步长 逆向#

分析截断 构造线性式#

格规约#

利用约束恢复完整状态#

SU_RSA#

SU_Lattice#

对模数的恢复#

恢复LFSR状态#

SU_Isogeny#

SU_Restaurant#

左旋恢复步长逆向#

分析截断构造线性式#