Misay's blog

ACTF2026

发表于 更新于 分类于
本文字数： 17k
ACTF2026-Crypto-全题解

🫡官方repo wp https://github.com/team-s2/ACTF-2026

inverse_pow

I’m tired of watching people insta-gib the proof-of-work with their 128-core machines. So why not inverse it?

赛题提供了一个go写的ELF 逆向后是一个PoW 协议基本如下

生成一个 1 到 99999999 之间的随机数 要求计算一个 满足 在60秒内计算 要求 的高len(m)位恰好是 即

1
str(2**n)[:len(str(m))] == str(m)

题目情景可以理解为找 满足 其中是根据数量级来确定的整数 取对数 我们不难理解

对于一个整数 如果把它写成科学计数法的形式 它的部分的”小数”会决定它的前缀

对于LHS/RHS的 大数 我们全部集中于它的小数部分 设十进制总长度为 那么可以把问题全部限制在 的区间小数 回代取对数 记为 其中 作为每轮的步长

为什么要转化到小数？

就前缀而言 我们其实不是很关注其他无关的后续尾部位数 化为小数的视角理解 可以认为是存在 1后的”截断”

可以认为 作为轮转步数 而 作为无理数 的增加会导致 不重复的分布在 之内 我们简记 就是要找的值 表示多”转”了多少圈

从开始 先讨论是否存在整数 如果存在 直接返回

否则 需要找到满足

求和求没有本质区别 以为主元 注意我们前面的操作手法 都是 只讨论必要的小数 给无关的整数截断

两侧除去 给共同的整数截断 即化归为等价问题 截断掉 只需分析

后续按照一样的思路 定义新的 来递归求解即可

Pandora

These mathematical structures are noisy and chaotic enough, so hiding my numbers here must be safe, right?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
FLAG = b"actf{redacted}"
while (p:=random_prime(2**512))%4 != 3:
    continue
q = random_prime(2**512)
K = QuadraticField(-p, 'w')
R = RealField(2333)
ΔΚ, Δq = -p, -p*q**2
OK = K.maximal_order()
Oq = K.order([1, (Δq+q*K.gen())/2])

token = os.urandom(45)
α = OK.ideal(int(token[:30].hex(),16)+\
             int(token[30:].hex(),16)*K.gen())

a, b, c = list(α.quadratic_form())
A, B = a, b*q%(2*a)
if B >= a: B -= 2*a
h = Oq.ideal([A, (-B + q*K.gen())/2]).quadratic_form()
ζ = list(h.reduced_form())[:2]; ζ[0] >>= 360
λ = f"{R(-Δq).sqrt():.470f}".split('.')[1]

if bytes.fromhex(input(f"{ζ, λ}\n[token]: ")) == token:
    print("^_^ >🚩", FLAG)

先看给了什么

1
ζ = list(h.reduced_form())[:2]; ζ[0] >>= 360

涉及 而 由下列代码定义

1
h = Oq.ideal([A, (-B + q*K.gen())/2]).quadratic_form()

我们需要分析三个变量 A B K

  • A由a决定 而

  • B的定义为

  • K.gen() 由前文对K的定义 严格为

随后在定义的Oq环上由A B 定义一个二次型 并且约化后告诉你系数 的高位 和完整的 

1
λ = f"{R(-Δq).sqrt():.470f}".split('.')[1]

相当于提供 的高精度小数位数

因为它的高位被精准的截断了 我们可以写 等式两边平方

也就是 某个整数

这是个高精度的Integral Diophantine approximation

令 把小数转化为整数方便做格

即

所以说 必须得是的整数倍 也就是一定存在线性关系

做

有

取很大的量来固定目标向量第三位只能取1 提取第一位接近0的向量即可恢复 从而恢复

解出之后拷打LLM 给出了如下性质

在类群密码学中，任何一个二元二次型 必须满足其判别式恒等于系统参数

这里给出的虽然是约化后的二次型 但是仍然满足 把已知的都移到一边 我们有 这里给我们 的高位 可以写 问题转化为经典的已知因子的高位 要进行分解

赛中尝试了朴素的small_roots会直接OOM 于是进行了如下优化

  • 把上界从 压到

然后根据 论文中的Howgrave-Graham 的构造搓了一个格来恢复 再恢复

恢复 后 目标是恢复 高斯约化前的 但是赛中发现

而 if B >= a: B -= 2*a 已经保证了 也就是说这里的 reduced_form() 实际上没有对系数进行处理

现在梳理一下 我们已知 需要解

接着拷打LLM得到了在当前整环 下的代数结构

二次型判别式的关系满足 同乘 故而 取

而由于 故而

因为我们是已知 的 关于的系数只差一个来对齐 我们构造

这一步最大的帮助就是帮我们给 之间建立了 从模转化到线性的代数关系

回看二次型 有 而我们一定有 给消掉 即

代回去 而我们又有 平方一下

这个二次型其实是存在这样的构造的 我们先令 看看会怎么样 后两项关注 这个4也不难配平 取

3式让我们可以消去 而 所以说 在我们已知二次多项式关系 后 由于我们还知道 的倍数 在shift中加入 即按照 的shift思路造格 可以成功规约出满足 的系数多项式 它长这样 变形成 解出有理根 展开成分数 解出 可以算 然后gcd解 算

ArrAnge in Asceding

From Bubble Sort to Quick Sort, the pursuit of order has always defined humanity.

chal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import tenseal.sealapi as sealapi
import tenseal as ts, random, base64 as b64
FLAG = "actf{redacted}"

ctx = ts.context_from(open("ctx.secret", "rb").read())
ctxdata = ctx.seal_context().data
Base = random.sample(range(512),128)
Chaos = ts.ckks_vector(ctx, Base)

print(b64.b64encode(Chaos.serialize()).decode())
open("ct.bin", 'wb').write(b64.b64decode(input("😶‍🌫️ :")))
(Crystal:=sealapi.Ciphertext()).load(ctxdata, "ct.bin")

decryptor = sealapi.Decryptor(ctxdata, ctx.secret_key().data)
decryptor.decrypt(Crystal, answer:=sealapi.Plaintext())

encoder = sealapi.CKKSEncoder(ctxdata)
answer = list(encoder.decode_double(answer))[:128]
if all(round(i) == sorted(Base).index(j) for i,j in zip(answer, Base)):
    print("^_^ >🚩", FLAG)

setup

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import tenseal as ts

ctx = ts.context(
    ts.SCHEME_TYPE.CKKS,
    32768,
    coeff_mod_bit_sizes=[50]+[40]*12+[50]
)
ctx.global_scale = 2**40

secret_bytes = ctx.serialize(save_secret_key=True)
public_bytes = ctx.serialize(save_secret_key=False)
open("ctx.secret", "wb").write(secret_bytes)
open("ctx.public", "wb").write(public_bytes)

ctx.generate_galois_keys()
ctx.galois_keys().data.save("galois.key")

https://arxiv.org/pdf/2412.15126

远端生成 并给出CKKS加密后的密文 要求得到这128个项的大小索引 加密后重新发回去得到flag 附件给了CKKS的公钥和Galois旋转密钥

CKKS属于FHE的一种 能够支持不解密的情况下对于密文进行计算 等价于直接计算明文

所以初步策略是直接对于密文进行计算 让明文解密后的结果直截等于需要的rank数组

这里引入一个指示函数

有

但是CKKS只支持加法乘法 关于 sgn这种跃迁函数需要用多项式方法进行拟合 拷打LLM后给出了一个能够使用的思路

参考 https://ieeexplore.ieee.org/document/9517029 先用chebshev进行拟合 再在7~8层加入minimax函数

进行复合多项式的拟合 把符号函数的结果拓展到1与-1

这一步能解决排序精度问题 但是开销非常大 相当于每次比较都需要shift 127次 远端会断连

再参考 https://eprint.iacr.org/2025/198 利用已有的galois密钥 给base向量拓展到 行列矩阵

直观上 我们简写一下这两个矩阵长什么样

做差 复杂度是O(1)

然后调用多项式工具 拟合符号函数 再直接进行计算即可

*OhMyCaptcha

I’ve designed a group verification mechanism, let’s try.

task

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
import random, subprocess, os, signal, re
from secret import FLAG

assert re.fullmatch(rb'ACTF\{.{41}\}', FLAG)
valid_mobile = lambda num: [s:=str(num), len(s) == 11 and s[0] == '1'][1] and isPrime(num)
prod = lambda x: 1 if not x else x[0]*prod(x[1:])

class SandboxService:
    def __init__(self, p, q):
        self.n = p * q
        self.e = 5
    
    def encrypt(self, msg):
        return pow(bytes_to_long(msg), self.e, self.n)
    
    def run(self, template):
        output = subprocess.run(
            ['python3', '-c', template],
            stdin=subprocess.DEVNULL, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=1,
        ).stdout
        return long_to_bytes(self.encrypt(output.strip()))

class OhMyCaptcha:
    def __init__(self):
        self.code = ''.join(random.sample("0123456789", 10))
        self.pn = None

    def verify(self, message):
        return 0 <= message < prod(self.pn) and all(str(message % p) in self.code for p in self.pn)

    def start(self):
        print("Are you human? ")
        self.pn = list(set(map(int, input("Enter phone numbers to get a group verification code: ").split())))
        assert all(valid_mobile(p) for p in self.pn) and 0 < len(self.pn) < 66
        print(f"[Azure Assassin Alliance] {self.code} is your group verification code, valid for 1 minute.")
        signal.alarm(60)

    def serve(self):
        sandbox = SandboxService(getPrime(0x137), getPrime(0x137))
        print("n =", sandbox.n)
        key, nonce = [os.urandom(8).hex() for _ in ":)"]
        cipher = AES.new(key.encode(), AES.MODE_CTR, nonce=bytes.fromhex(nonce)).encrypt(FLAG).hex()
        for _ in "AAA🤩":
            message = int(input('> '))
            template = f"key = {key!r}\ncipher_with_key_{key}_{nonce} = {cipher!r}\nprint(eval({long_to_bytes(message)}))"
            if self.verify(message):
                print(sandbox.run(template).hex())
            else:
                print("Verification failed.")

if __name__ == "__main__":
    OHC = OhMyCaptcha()
    OHC.start()
    OHC.serve()

先提一下预期解

SandBoxService提供了一个沙箱来运行template的模板 而其中的 eval运行执行 message 再把沙箱的输出进行RSA加密 这里的指数比较小

sandbox的构造

template中的eval允许读已有的信息 可以构造message分别为 key dir()[-2][-16:] 给AES的key 与nonce 读出来 这里二者大概是128字节 而5次幂下截断大概在124字节 稍微爆破一下模数的倍数就可以给二者成功恢复

此时还剩两次机会

随后传eval(dir()[-2]) 可以得到 cipher RSA加密的结果 不难想到有相关明文攻击的机会 即 Franklin-Riether-Attack 那么接下来只需要构造一个payload 能够让沙箱输出 f(cipher)的值即可 先 dir()[-2] 获取cipher的变量名 再 globals()[dir()[-2]] 得到取值 最后字符串拼接一下 globals()[dir()[-2]] + 'a'

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
=== OhMyCaptcha 极短 Payload 测试沙箱 ===
[环境信息] 模拟 Key: c8c4ea2ecdc7a718
[环境信息] 模拟 Nonce: 21df4e7d0ed43209
[环境信息] 模拟 Cipher: 728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62
输入你的 payload 字符串 (例如: key, dir(), globals())，输入 exit 退出。

Payload > dir()[-2][16:32]
--------------------------------------------------
[*] 正在执行 Payload: dir()[-2][16:32]
[*] Payload 长度: 16 bytes

[+] 原始沙箱输出 (Raw): b'c8c4ea2ecdc7a718'
[+] 字符串解码 (Decoded): c8c4ea2ecdc7a718

[*] 最终输出长度: 16 bytes
[~] 长度适中 (16-18 bytes)：会发生轻微模回绕，可利用 k-Brute Force (爆破 k) 恢复。
--------------------------------------------------
Payload > dir()[-2][-16:]
--------------------------------------------------
[*] 正在执行 Payload: dir()[-2][-16:]
[*] Payload 长度: 15 bytes

[+] 原始沙箱输出 (Raw): b'21df4e7d0ed43209'
[+] 字符串解码 (Decoded): 21df4e7d0ed43209

[*] 最终输出长度: 16 bytes
[~] 长度适中 (16-18 bytes)：会发生轻微模回绕，可利用 k-Brute Force (爆破 k) 恢复。
--------------------------------------------------
Payload > eval(dir()[-2])
--------------------------------------------------
[*] 正在执行 Payload: eval(dir()[-2])
[*] Payload 长度: 15 bytes

[+] 原始沙箱输出 (Raw): b'728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62'
[+] 字符串解码 (Decoded): 728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62

[*] 最终输出长度: 94 bytes
[!] 长度过长 (> 18 bytes)：需要使用 Coppersmith (small_roots) 截断分析，或考虑继续缩短输出！
--------------------------------------------------
Payload > globals()[dir()[-2]] + 'a'
--------------------------------------------------
[*] 正在执行 Payload: globals()[dir()[-2]] + 'a'
[*] Payload 长度: 26 bytes

[+] 原始沙箱输出 (Raw): b'728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62a'
[+] 字符串解码 (Decoded): 728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62a

[*] 最终输出长度: 95 bytes
[!] 长度过长 (> 18 bytes)：需要使用 Coppersmith (small_roots) 截断分析，或考虑继续缩短输出！
--------------------------------------------------
Payload > eval(dir()[-2])*2
--------------------------------------------------
[*] 正在执行 Payload: eval(dir()[-2])*2
[*] Payload 长度: 17 bytes

[+] 原始沙箱输出 (Raw): b'728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62'
[+] 字符串解码 (Decoded): 728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62728f425d770f597c836f1529739d5e766c073de999c71f683b8a0aa4e1629aeb5090a0fcdebbc8af2f6d55a0595b62

[*] 最终输出长度: 188 bytes
[!] 长度过长 (> 18 bytes)：需要使用 Coppersmith (small_roots) 截断分析，或考虑继续缩短输出！
--------------------------------------------------
Payload >

后续搜索的时候 key实在太短 导致m太小 换成了 dir()[-2][16:32]

最后使用的是

  • key – dir()[-2][16:32]
  • nonce – dir()[-2][-16:]
  • cipher – eval(dir()[-2])
  • f(cipher) – eval(dir()[-2])*2

pn的搜索构造

上述payload在末尾增加 # 后再在末尾增加各种乱码也不会引起问题 同时注意到虽然pn是公共的 但是题目给了我们code 和时间 我们完全可以

  • 搜索找10~16组可用的 pn 这一步非常简单 素数 长度OK即可
  • 得到code后 再针对key nonce cipher f(cihper) 当场搜索suffix即可

这里就可以转化为一个背包格问题 来求解

我们的message可以看成 只需满足 这里应该是存在一个背包格的转化的 毕竟suffix 转化回来只会影响低位 但当前还没发现一个稳定的规约成功suffix的思路 如果想要赛中优化 可以参照

  • 字串从 拓展到2位 比如 这样 空间会更足

后续对着官方wp分析还是发现比较大的思路差距了

这里我们搜索的实际上是后缀的字节 本质还是几十的相对大数字，而赛题的关键是 其中是10以内的小量 这也就意味着

如果我们能先确定 再把这个细微的偏移给求出来 那也一样的可以恢复我们的

所有放在模数上的问题我们都不太喜欢 但是如果先确定 那就转化为了去规约一个的量 我们还可以中心化 令 规约这里的并不难

再说回命令本身 当我们先确定了组后 格的规模和维度基本就被固定在64附近 此时前缀相对而言长度没有那么敏感，规约效率也高了很多，同时当payload的长度上升 反而能给我们的提供更大的宽度容错区间

处理数据与格

构造四次message 前两次拿下 key nonce 后续拿下 cipher f(cipher)

前2者是16字节 稍微爆破即可完全恢复 而cipher是94字节 再知道 RSA加密结果后 相当于

我们很容易计算出来 接下来就需要分析 因为AES加密的结果实际上是全部为hex的字串 考虑继续使用背包格求解 可以针对 a-z0-9 来进行稍微的移位和缩放 规约到待求小量均是 的格中 但是这个格的复杂度还是相当大的 目前没有调出来 如果想参考类似的求法可以看看 AliyunCTF2026-Griffin-Rec师傅的手法 这道题是uuid格 但是对于hex的处理还是值得参照的

个人的相关经验和积累还是太少了… 面对这道题赛中折腾了很长一段时间的eval短命令读取…

嗯感谢wuy4n师傅提供的相关脚本 这里贴一个格的构造

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
def solve(p, c, k=60):
    table = string.hexdigits.lower()
    proj = {"0" : (0, -4), "1" : (0, -3), "2" : (0, -2), "3" : (0, -1),
        "4" : (0, 0), "5" : (0, 1),  "6" : (0, 2),  "7" : (0, 3),
        "8" : (0, 4),  "9" : (0, 5),  "a" : (1, -3),  "b" : (1, -2),
        "c" : (1, -1),  "d" : (1, 0),  "e" : (1, 1),   "f" : (1, 2)}

    a, b = 48, 52
    for key in proj.keys():
        x, y = proj[key]
        assert a * x + y + b == ord(key)

    P = PolynomialRing(Zmod(p), [f"x{i}" for i in range(k * 2)])
    vars = P.gens()
    xs = vars[:k]
    ys = vars[k:]

    f = sum([(a * xs[i] + ys[i] + b) * 256**(k - 1 - i) for i in range(k)]) - c
    coeffs = f.coefficients()

    C1 = 4
    C2 = 2**32
    M = matrix(ZZ, k * 2 + 2, k * 2 + 2)
    for i in range(k):
        M[i, i] = C1
        M[i + k, i + k] = 1

    M[2 * k, 2 * k] = C1

    for i in range(k * 2 + 1):
        M[i, -1] = int(coeffs[i]) * C2

    M[-1, -1] = p * C2

    M = M.LLL()
    t1 = time.time()
    M = blaster(M, block_size=63, bkz_tour=10)
    t2 = time.time()
    print("time: ", t2 - t1)
    for row in M:
        if check(row):
            print("Found row:", row)
            for i in row:
                if i<0:
                    row = -row
                    break
                elif i>0:
                    break
            plain = ""
            for i in range(k):
                plain += chr(a * row[i] // C1 + row[i + k] + b)
            print("Plaintext:", plain)
            return plain
    return None

这里预期使用的是256来进行balance

1
f = sum([(a * xs[i] + ys[i] + b) * 256**(k - 1 - i) for i in range(k)]) - c

结合仿射 对如下式子做背包格

亦可尝试改为 来进行balance 取得相对更加可控的格规模

对于hex的字符 令

  • 若是数字：
  • 若是字母：

可以转化为

其中 对应的 背包格相对应转化为

demo

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
  def solve(p, c, k=60):
      n, dim = p, 2 * k
      w = 2**32
      powers_hi = [2 * k - 1 - 2 * i for i in range(k)]
      powers_lo = [2 * k - 2 - 2 * i for i in range(k)]

      const = sum(12 * 16**powers_hi[i] + 4 * 16**powers_lo[i] for i in range(k))
      c0 = (ZZ(c) - ZZ(const)) % ZZ(n)

      M = matrix(ZZ, dim + 2, dim + 2)

      for i in range(dim):
          M[i, i] = 8 if i % 2 == 0 else 1

      M[dim, :] = matrix(1, dim + 2, [-12, -4] * k + [4] + [-(c0 * inverse_mod(3, n) % n) * w])

      coeff_col = []
      inv3 = inverse_mod(3, n)
      for i in range(k):
          coeff_col.append((16**powers_hi[i]) * w % n)          # u_i 对应 high nibble
          coeff_col.append((16**powers_lo[i] * inv3) * w % n)   # v_i 对应 low nibble
      M[:dim, dim + 1] = matrix(dim, 1, [ZZ(x) for x in coeff_col])

      M[dim + 1, dim + 1] = n * w
      
      t1 = time.time()
      M = M.BKZ(block_size = 30)
#     M = blaster(M, block_size=63, bkz_tour=10)
      t2 = time.time()
      print("time:", t2 - t1)

      def decode_row(row):
          msg = []
          for idx in range(0, 2 * k, 2):
              u = ZZ(row[idx])
              v = ZZ(row[idx + 1])

              if u not in (-4, 4):
                  return None

              H = 3 * ((u + 12) // 8)   # 3 or 6
              L = v + 4

              if H not in (3, 6):
                  return None
              if not (0 <= L <= 15):
                  return None

              ch = (H << 4) + L
              if not (0 <= ch <= 255):
                  return None
              msg.append(chr(int(ch)))

          s = "".join(msg)
          if all(ch in "0123456789abcdef" for ch in s):
              return s
          return None

      cands = []
      for row in M:
          s = decode_row(row)
          if s is not None:
              print("Found candidate:", s)
              cands.append(s)

      return cands

再简要说一下非预期 可以直接通过

1
help('secret')

来读取FLAG 虽然flag的长度相当大 但是可以多次重连 获得多组 结合已有的 合并起来打CRT直接恢复 FLAG 😶‍🌫️