这次做出了前两道，后两道主要是复现一位✌的wp（*表示赛中未出的题）

题目

因为两道题的本质都是一样的，所以我就融合成一道题一块来讲了。

点击展开代码

1
from Crypto.Util.number import bytes_to_long
2
from hashlib import md5
3
import os
4
FLAG1 = os.environ.get("FLAG", "flag{**redacted**}")
5
FLAG2 = os.environ.get("FLAG", "flag{**redacted1**}")
6

7
E = EllipticCurve(GF(0x1337_ca7_eae368ff5d702e6067aaaa77ca_ca7_1337), [0, 3])
8
G, n = E(1, 2), E.order()
9

10
def sign(priv, ctx, msg):
11
    k = bytes_to_long(ctx + md5(str(priv).encode() + msg).digest())
12
    z = bytes_to_long(md5(ctx + msg).digest())
13
    r = int((k * G).x()) % n
14
    s = (pow(k, -1, n) * (z + r * priv)) % n
15
    return r, s
16

17
def verify(pub, ctx, msg, sig):
18
    z = bytes_to_long(md5(ctx + msg).digest())
19
    r, s = sig
20
    if 0 < r < n and 0 < s < n:
21
        return r == int((pow(s, -1, n) * (z * G + r * pub)).x()) % n
22

23
def chall(level, flag):
24
    priv = randint(1, n - 1)
25
    pub = priv * G
26
    msg = os.urandom(64)
27

28

29
    print(f"=== level {level} ===")
30
    for _ in range(catalan_number(level)):
31
        ctx = bytes.fromhex(input('context: '))
32
        r, s = sign(priv, ctx, msg)
33
        assert verify(pub, ctx, msg, (r, s))
34
        if level <= 1: print('message:', msg.hex())
35
        if level <= 2: print('sign:', r)
36
        if level <= 3: print('ature:', s)
37

38
    r, s = map(int, input('signature: ').split())
39
    assert verify(pub, b'n1junior_2025', f'cat /flag{level}'.encode(), (r, s))
40
    print(f'flag{level}:', flag)
41

42
if __name__ == "__main__":
43
    chall(0, "💧")
44
    chall(1, "🐱")
45
    chall(2, FLAG1)
46
    chall(3, FLAG2)

解题分析

一，MD5碰撞

这里主要还是先讲这道题的主要考点——MD5哈希碰撞。

对于这道题而言，也就是：存在任意 $n$ 个不同的 $ctx_i$ ，使得对应的哈希值是相同的；这里需要使用的工具是一个能实现“MD5碰撞”的工具（比如fastcoll）；想了解具体原理的话，可以参考Fast Collision Attack on MD5↗，我这里就直接说具体的做法（或者说——怎么通过fastcoll来生成多个符合条件的 $ctx_i$ ）。

我是直接在win上用的fastcoll.exe，因此运行一次，最多只能生成两个符合条件的ctx。

比如说，我这里以 ”test“ 为前缀（放在test.txt里了），运行一次可以得到这样的两个ctx：

点击展开代码

1
# .\fastcoll.exe -p test.txt -o md5_msg1.txt md5_msg2.txt
2
ctx1 = b"test\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00)\xc0{xA\x00\x9f\xaaX\xa7\xee2\x0b\xfb\xad\x12\x9c\xb4%\xd5dVG\xa91bCQM\x90\xa6\x08\x98+\xa9\xc4^'\x1c,\x87ju\x9a\xf3\x8d+WSv\x97?\xdd-\\\xd3\x04\xbd\x1e\x80Y\xb2\x08\xe9\xeb/\xb160\xadE\x03\x7f'\xf1\xec\x01\x06\x08\x08\x9e\xff\x83\x0b%\x06.#\xc9\x1a\xf6\xbb\xecF\xfeg\xd0[\x9eX\x04\x8f\xe4Az\x1fMO\xe20\xd5&GF\x96<\xee/\xcdfVb\x0e$\xba8\x9cg"
3
ctx2 = b"test\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00)\xc0{xA\x00\x9f\xaaX\xa7\xee2\x0b\xfb\xad\x12\x9c\xb4%UdVG\xa91bCQM\x90\xa6\x08\x98+\xa9\xc4^'\x1c,\x87ju\x9a\xf3\r,WSv\x97?\xdd-\\\xd3\x04\xbd\x1e\x00Y\xb2\x08\xe9\xeb/\xb160\xadE\x03\x7f'\xf1\xec\x01\x06\x08\x08\x9e\xff\x83\x8b%\x06.#\xc9\x1a\xf6\xbb\xecF\xfeg\xd0[\x9eX\x04\x8f\xe4Az\x1fMO\xe2\xb0\xd4&GF\x96<\xee/\xcdfVb\x0e\xa4\xba8\x9cg"

我们去查看后缀（除去前缀外的部分）会发现——长度一致但内容不同；而且这两个ctx长度都是64bytes的整数倍（刚好是一个哈希分组块的长度）

1
# len("test") = 4
2
print(len(ctx1[4:])==len(ctx2[4:]), ctx1[4:]==ctx2[4:])
3
# True False

而这就是我们通过fastcoll做这道题的一个关键点了。

假如我们此时以ctx1为我们的前缀，再次使用fastcoll去生成ctx3和ctx4，并检查此时的后缀（与ctx1相比多出的部分）会发现——仍然是长度一致但内容不同；而且这两个ctx长度依然都是64bytes的整数倍。

点击展开代码

1
# .\fastcoll.exe -p test.txt -o md5_msg1.txt md5_msg2.txt
2
ctx3 = b"test\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00)\xc0{xA\x00\x9f\xaaX\xa7\xee2\x0b\xfb\xad\x12\x9c\xb4%\xd5dVG\xa91bCQM\x90\xa6\x08\x98+\xa9\xc4^'\x1c,\x87ju\x9a\xf3\x8d+WSv\x97?\xdd-\\\xd3\x04\xbd\x1e\x80Y\xb2\x08\xe9\xeb/\xb160\xadE\x03\x7f'\xf1\xec\x01\x06\x08\x08\x9e\xff\x83\x0b%\x06.#\xc9\x1a\xf6\xbb\xecF\xfeg\xd0[\x9eX\x04\x8f\xe4Az\x1fMO\xe20\xd5&GF\x96<\xee/\xcdfVb\x0e$\xba8\x9cg\xbe\x98\xa9\xfcW\x1c=\xb6\xbbE\xc0\xdf\xd5\xf7\x82\xea\xc85\xeb\x96\xdb\xc6\xaa\x9a!\xf69a\x15(\x1b'\xc6\xf9\xb5\xb8^\xcd?x\x8b\xe4O\x12\xee\x11!G\x8a\xcf*\xdc={\x0f;\xc9\xef\x9ba\xaf5\xd9B\xfa\xafx\xaf\xd4\x83\xc5\xb9\xc3\r\xbf\x03\xf7\xcfj8G\x11cWpY\x93(+\xb3\x10w\x06`\xa8\xc6\xcbKN\x14\xaf\xc7[^:\t\x0c\\\x8b_\x17\xe2\xa8\x81\x0c\xb3$\x86]IblU\xd4\x86\x04\x15\xcc"
3
ctx4 = b"test\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00)\xc0{xA\x00\x9f\xaaX\xa7\xee2\x0b\xfb\xad\x12\x9c\xb4%\xd5dVG\xa91bCQM\x90\xa6\x08\x98+\xa9\xc4^'\x1c,\x87ju\x9a\xf3\x8d+WSv\x97?\xdd-\\\xd3\x04\xbd\x1e\x80Y\xb2\x08\xe9\xeb/\xb160\xadE\x03\x7f'\xf1\xec\x01\x06\x08\x08\x9e\xff\x83\x0b%\x06.#\xc9\x1a\xf6\xbb\xecF\xfeg\xd0[\x9eX\x04\x8f\xe4Az\x1fMO\xe20\xd5&GF\x96<\xee/\xcdfVb\x0e$\xba8\x9cg\xbe\x98\xa9\xfcW\x1c=\xb6\xbbE\xc0\xdf\xd5\xf7\x82\xea\xc85\xeb\x16\xdb\xc6\xaa\x9a!\xf69a\x15(\x1b'\xc6\xf9\xb5\xb8^\xcd?x\x8b\xe4O\x12\xee\x91!G\x8a\xcf*\xdc={\x0f;\xc9\xef\x9b\xe1\xaf5\xd9B\xfa\xafx\xaf\xd4\x83\xc5\xb9\xc3\r\xbf\x03\xf7\xcfj8G\x11c\xd7pY\x93(+\xb3\x10w\x06`\xa8\xc6\xcbKN\x14\xaf\xc7[^:\t\x0c\\\x8b\xdf\x16\xe2\xa8\x81\x0c\xb3$\x86]IblUT\x86\x04\x15\xcc"
4

5
print(len(t3[len(t1):])==len(t4[len(t1):]), t1[len(t1):]==t2[len(t1):])
6
# True True
7

8
# 这里假设以"test"为前缀来看
9
print(len(t3[4:])==len(t4[4:]), t1[4:]==t2[4:])
10
# True False

看到这的师傅，应该会有这么个猜想：因为此时是以ctx1为前缀生成的ctx3和ctx4，且ctx3和ctx4的后缀也跟前面ctx1和ctx2的后缀是同一规律；那会不会ctx3和ctx4的后缀给ctx2也能生成同样的MD5值呢？

答案是肯定的：

点击展开代码

1
from hashlib import md5
2
ctx1 = b"test\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00)\xc0{xA\x00\x9f\xaaX\xa7\xee2\x0b\xfb\xad\x12\x9c\xb4%\xd5dVG\xa91bCQM\x90\xa6\x08\x98+\xa9\xc4^'\x1c,\x87ju\x9a\xf3\x8d+WSv\x97?\xdd-\\\xd3\x04\xbd\x1e\x80Y\xb2\x08\xe9\xeb/\xb160\xadE\x03\x7f'\xf1\xec\x01\x06\x08\x08\x9e\xff\x83\x0b%\x06.#\xc9\x1a\xf6\xbb\xecF\xfeg\xd0[\x9eX\x04\x8f\xe4Az\x1fMO\xe20\xd5&GF\x96<\xee/\xcdfVb\x0e$\xba8\x9cg"
3
ctx2 = b"test\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00)\xc0{xA\x00\x9f\xaaX\xa7\xee2\x0b\xfb\xad\x12\x9c\xb4%UdVG\xa91bCQM\x90\xa6\x08\x98+\xa9\xc4^'\x1c,\x87ju\x9a\xf3\r,WSv\x97?\xdd-\\\xd3\x04\xbd\x1e\x00Y\xb2\x08\xe9\xeb/\xb160\xadE\x03\x7f'\xf1\xec\x01\x06\x08\x08\x9e\xff\x83\x8b%\x06.#\xc9\x1a\xf6\xbb\xecF\xfeg\xd0[\x9eX\x04\x8f\xe4Az\x1fMO\xe2\xb0\xd4&GF\x96<\xee/\xcdfVb\x0e\xa4\xba8\x9cg"
4
ctx3 = b"test\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00)\xc0{xA\x00\x9f\xaaX\xa7\xee2\x0b\xfb\xad\x12\x9c\xb4%\xd5dVG\xa91bCQM\x90\xa6\x08\x98+\xa9\xc4^'\x1c,\x87ju\x9a\xf3\x8d+WSv\x97?\xdd-\\\xd3\x04\xbd\x1e\x80Y\xb2\x08\xe9\xeb/\xb160\xadE\x03\x7f'\xf1\xec\x01\x06\x08\x08\x9e\xff\x83\x0b%\x06.#\xc9\x1a\xf6\xbb\xecF\xfeg\xd0[\x9eX\x04\x8f\xe4Az\x1fMO\xe20\xd5&GF\x96<\xee/\xcdfVb\x0e$\xba8\x9cg\xbe\x98\xa9\xfcW\x1c=\xb6\xbbE\xc0\xdf\xd5\xf7\x82\xea\xc85\xeb\x96\xdb\xc6\xaa\x9a!\xf69a\x15(\x1b'\xc6\xf9\xb5\xb8^\xcd?x\x8b\xe4O\x12\xee\x11!G\x8a\xcf*\xdc={\x0f;\xc9\xef\x9ba\xaf5\xd9B\xfa\xafx\xaf\xd4\x83\xc5\xb9\xc3\r\xbf\x03\xf7\xcfj8G\x11cWpY\x93(+\xb3\x10w\x06`\xa8\xc6\xcbKN\x14\xaf\xc7[^:\t\x0c\\\x8b_\x17\xe2\xa8\x81\x0c\xb3$\x86]IblU\xd4\x86\x04\x15\xcc"
5
ctx4 = b"test\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00)\xc0{xA\x00\x9f\xaaX\xa7\xee2\x0b\xfb\xad\x12\x9c\xb4%\xd5dVG\xa91bCQM\x90\xa6\x08\x98+\xa9\xc4^'\x1c,\x87ju\x9a\xf3\x8d+WSv\x97?\xdd-\\\xd3\x04\xbd\x1e\x80Y\xb2\x08\xe9\xeb/\xb160\xadE\x03\x7f'\xf1\xec\x01\x06\x08\x08\x9e\xff\x83\x0b%\x06.#\xc9\x1a\xf6\xbb\xecF\xfeg\xd0[\x9eX\x04\x8f\xe4Az\x1fMO\xe20\xd5&GF\x96<\xee/\xcdfVb\x0e$\xba8\x9cg\xbe\x98\xa9\xfcW\x1c=\xb6\xbbE\xc0\xdf\xd5\xf7\x82\xea\xc85\xeb\x16\xdb\xc6\xaa\x9a!\xf69a\x15(\x1b'\xc6\xf9\xb5\xb8^\xcd?x\x8b\xe4O\x12\xee\x91!G\x8a\xcf*\xdc={\x0f;\xc9\xef\x9b\xe1\xaf5\xd9B\xfa\xafx\xaf\xd4\x83\xc5\xb9\xc3\r\xbf\x03\xf7\xcfj8G\x11c\xd7pY\x93(+\xb3\x10w\x06`\xa8\xc6\xcbKN\x14\xaf\xc7[^:\t\x0c\\\x8b\xdf\x16\xe2\xa8\x81\x0c\xb3$\x86]IblUT\x86\x04\x15\xcc"
6

7
print(md5(ctx3).hexdigest())
8
print(md5(ctx2+ctx3[len(ctx2):]).hexdigest())
9
print(md5(ctx2+ctx4[len(ctx2):]).hexdigest())
10
"""
11
f5624faf5b3f1d67342a20d7bbeb0f81
12
f5624faf5b3f1d67342a20d7bbeb0f81
13
f5624faf5b3f1d67342a20d7bbeb0f81
14
"""

此时我们便获得了 $2^2=4$ 个可能的 $ctx_i$ ，那假如以ctx3为前缀继续呢？

那便如下图所示：

此时就有 $2^3=8$ 个可能的 $ctx_i$

组合方式为：

ctx_i=M+(A_1/A_2)+(B_1/B_2)+(C_1/C_2)+(D_1/D_2)

于是就说明：每次生成的两个后缀和前一次的未用前缀拼起来，可以的得到此时的同一md5值的两个串。

所以我们手动 $n$ 次fastcoll，就可以组合出 $2^n$ 个我们需要的 $ctx_i$ （当然，其实maple师傅之前有出过一道题，对应的解题脚本↗里就实现了这一功能）。

二，具体题目

题目中提供数据的部分是这里：

1
# 这里依据当时做题的时候测出来的情况而写的
2
def catalan_number(L):
3
    if L in [0, 1]:
4
        return 1
5
    elif L == 2:
6
        return 2
7
    else:
8
        return 5
9

10
def sign(priv, ctx, msg):
11
    k = bytes_to_long(ctx + md5(str(priv).encode() + msg).digest())
12
    z = bytes_to_long(md5(ctx + msg).digest())
13
    r = int((k * G).x()) % n
14
    s = (pow(k, -1, n) * (z + r * priv)) % n
15
    return r, s
16

17
def verify(pub, ctx, msg, sig):
18
    z = bytes_to_long(md5(ctx + msg).digest())
19
    r, s = sig
20
    if 0 < r < n and 0 < s < n:
21
        return r == int((pow(s, -1, n) * (z * G + r * pub)).x()) % n
22

23
def chall(level, flag):
24
    priv = randint(1, n - 1)
25
    pub = priv * G
26
    msg = os.urandom(64)
27

28
    print(f"=== level {level} ===")
29
    for _ in range(catalan_number(level)):
30
        ctx = bytes.fromhex(input('context: '))
31
        r, s = sign(priv, ctx, msg)
32
        assert verify(pub, ctx, msg, (r, s))
33
        if level <= 1: print('message:', msg.hex())
34
        if level <= 2: print('sign:', r)
35
        if level <= 3: print('ature:', s)
36

37
    r, s = map(int, input('signature: ').split())
38
    assert verify(pub, b'n1junior_2025', f'cat /flag{level}'.encode(), (r, s))
39
    print(f'flag{level}:', flag)

这题的签名算法是ECDSA，题目是让我们根据一定的交互次数与交互后的数据来算出私钥priv，从而伪造签名通过verify的验证。

因此我就按给的level来逐一说明。

Level 0/1

此时题目只给了我们一次输入ctx的机会，并获得一组msg、sign、ature（后两个是r和s）。

而我们知道ECDSA的签名是这样的：

H=md5(ctx + msg),\ k=ctx+md5(priv+msg)\ mod\ n\\ s=k^{-1}(H+r*d)\ mod\ n

于是我们就可以得到：

d=(s*k-H)*r^{-1}\ mod\ n

不过这里会有个问题：因为r = int((k * G).x()) % n，假如使用E.lift_x(r)，我们只是得到一个坐标 $(x,\ y)$ ，但有可能我们需要的正确坐标是 $(x,\ -y)$ 。

好在这里条件充分，且有k = bytes_to_long(ctx + md5(str(priv).encode() + msg).digest())，所以我们可以验证这个式子是否成立来判断取 $(x,\ y)$ 还是 $(x,\ -y)$ ，最后就是去仿造r和s了。

1
# sage 10.6
2

3
# =============Level 0=============
4
io.recvuntil(b"context: ")
5
io.sendline(b"")
6
msg = bytes.fromhex(io.recvline().split()[-1].decode())
7
r = eval(io.recvline().split()[-1].decode())
8
s = eval(io.recvline().split()[-1].decode())
9

10
# s = (pow(k, -1, n) * (z + r * priv)) % n
11
z = bytes_to_long(md5(msg).digest())
12
k1 = (E.lift_x(Integer(r))).log(G)
13
k2 = (-E.lift_x(Integer(r))).log(G)
14
priv = ((s*k1-z)*invert(r, n))%n
15
priv_i = ((s*k1-z)*invert(r, n))%n
16
if k1 != bytes_to_long(md5(str(priv).encode() + msg).digest()):
17
    priv = priv_i
18
r, s = Sign(priv, b'n1junior_2025', f'cat /flag{level}'.encode())
19
io.recvuntil(b"signature: ")
20
io.sendline(b" ".join([str(r).encode(), str(s).encode()]))
21
c1 = io.recvline().decode()
22
print(c1)
23
level += 1
24
# flag0: 💧
25

26
# =============Level 1=============
27
io.recvuntil(b"context: ")
28
io.sendline(b"")
29
msg = bytes.fromhex(io.recvline().split()[-1].decode())
30
r = eval(io.recvline().split()[-1].decode())
31
s = eval(io.recvline().split()[-1].decode())
32

33
# s = (pow(k, -1, n) * (z + r * priv)) % n
34
z = bytes_to_long(md5(msg).digest())
35
k1 = (E.lift_x(Integer(r))).log(G)
36
k2 = (-E.lift_x(Integer(r))).log(G)
37
priv = ((s*k1-z)*invert(r, n))%n
38
priv_i = ((s*k1-z)*invert(r, n))%n
39
if k1 != bytes_to_long(md5(str(priv).encode() + msg).digest()):
40
    priv = priv_i
41
r, s = Sign(priv, b'n1junior_2025', f'cat /flag{level}'.encode())
42
io.recvuntil(b"signature: ")
43
io.sendline(b" ".join([str(r).encode(), str(s).encode()]))
44
c1 = io.recvline().decode()
45
print(c1)
46
level += 1
47
# flag1: 🐱

Level 2

此时题目给了我们两次输入ctx的机会，并获得两组sign、ature（也就是r和s）。

而前面介绍MD5碰撞的时候有说到可以利用n次fastcoll来构造 $2^n$ 个我们需要的 $ctx_i$ 。

于是我们就可以构造出两个ctx，直接传到靶机上去获取数据（毕竟ctx都是64bytes的整数倍，所以不影响最后的哈希值的一致），从而就有下列推导：

\begin{align*} s_1*k_1&=(H+r_1*d)\ mod\ n\\ s_2*k_2&=(H+r_2*d)\ mod\ n\\ s_2*k_2-s_1*k_1&=[(r_2-r_1)*d]\ mod\ n\\ d&=(s_2*k_2-s_1*k_1)*(r_2-r_1)^{-1}\ mod\ n \end{align*}

这里同样会有坐标 $(x,\ y)$ 与坐标 $(x,\ -y)$ 的取舍。

不过，我们如果去写代码去测试正确的 $k$ 与我们计算的 $k$ 的区别，会发现这样一个结论： $ctx_1*256^{16}\ mod\ n$ 与正确的 $k$ 的绝对值一定是最小的！

所以我们可以由此来判断取 $(x,\ y)$ 还是 $(x,\ -y)$ ，最后就是去仿造r和s了。

1
# sage 10.6
2

3
# =============Level 2=============
4
t1 =
5
t2 =
6
tt1 = int(bytes_to_long(t1)*256**16%n)
7
tt2 = int(bytes_to_long(t2)*256**16%n)
8
io.recvuntil(b"context: ")
9
io.sendline(t1.hex().encode())
10
r1 = eval(io.recvline().split()[-1].decode())
11
s1 = eval(io.recvline().split()[-1].decode())
12

13
io.recvuntil(b"context: ")
14
io.sendline(t2.hex().encode())
15
r2 = eval(io.recvline().split()[-1].decode())
16
s2 = eval(io.recvline().split()[-1].decode())
17

18
# s = (pow(k, -1, n) * (z + r * priv)) % n
19
k1 = (E.lift_x(Integer(r1))).log(G)
20
k2 = (E.lift_x(Integer(r2))).log(G)
21
k11 = (-E.lift_x(Integer(r1))).log(G)
22
k22 = (-E.lift_x(Integer(r2))).log(G)
23
if abs(tt1-k1) > abs(tt1-k11):
24
    k1 = k11
25
if abs(tt2-k2) > abs(tt2-k22):
26
    k2 = k22
27
priv = ((s1*k1-s2*k2)*invert(r1-r2, n))%n
28
r, s = Sign(priv, b'n1junior_2025', f'cat /flag{level}'.encode())
29
io.recvuntil(b"signature: ")
30
io.sendline(b" ".join([str(r).encode(), str(s).encode()]))
31
c2 = io.recvline().decode()
32
print(c2)
33
level += 1
34
# flag2: flag{**redacted**}

Level 3

此时题目给了我们五次输入ctx的机会，并获得五个ature（即s）。

与Level2一样，构造五个 $ctx$ ，直接传到靶机上去获取数据，来得到五个ature（即s）。

此时我们便有这五个式子（我假设叫方程组1）：

\begin{align*} s_1*k_1&=(H+r_1*d)\ mod\ n\\ s_2*k_2&=(H+r_2*d)\ mod\ n\\ s_3*k_3&=(H+r_3*d)\ mod\ n\\ s_4*k_4&=(H+r_4*d)\ mod\ n\\ s_5*k_5&=(H+r_5*d)\ mod\ n \end{align*}

此时，未知数的数量是大于方程数量的（12>5）。但是，我们别忘了这个：

\begin{align*} k_1&={ctx}_1*256^{16} + md5(priv+msg)\\ k_2&={ctx}_2*256^{16} + md5(priv+msg)\\ k_3&={ctx}_3*256^{16} + md5(priv+msg)\\ k_4&={ctx}_4*256^{16} + md5(priv+msg)\\ k_5&={ctx}_5*256^{16} + md5(priv+msg) \end{align*}

如果我们以 $k_0$ 为我们的未知量，那么我们便有（我假设叫方程组2）：

\begin{align*} k_1&=k_0\\ k_2&=k_0+({ctx}_2-{ctx}_1)*256^{16}\\ k_3&=k_0+({ctx}_3-{ctx}_1)*256^{16}\\ k_4&=k_0+({ctx}_4-{ctx}_1)*256^{16}\\ k_5&=k_0+({ctx}_5-{ctx}_1)*256^{16} \end{align*}

此时未知数的数量就减少为8个，仍大于我们的方程数。

于是还需要结合这个：

\begin{align*} r_1&=(k_1G)_x\\ r_2&=(k_2G)_x\\ r_3&=(k_3G)_x\\ r_4&=(k_4G)_x\\ r_5&=(k_5G)_x \end{align*}

此时便有：

\begin{align*} r_1&=(k_0G)_x\\ r_2&=[k_0G+({ctx}_2-{ctx}_1)G]_x=[k_0G+A]_x\\ r_3&=[k_0G+({ctx}_3-{ctx}_1)G]_x=[k_0G+B]_x\\ r_4&=[k_0G+({ctx}_4-{ctx}_1)G]_x=[k_0G+C]_x\\ r_5&=[k_0G+({ctx}_5-{ctx}_1)G]_x=[k_0G+D]_x \end{align*}

此时的未知数数量就减少到3个，小于我们的方程数。

但是，这样实现起来，还需要自己实现一个椭圆运算（因为 $k_0$ 可不是数值），显得过于复杂了，那有没有更简单的方法呢？有的，兄弟有的！

既然是椭圆运算了，那不妨设 $x_0$ 和 $y_0$ 使得：

(k_0G)=(x_0,\ y_0)

于是便有（我假设叫方程组3）：

\begin{align*} r_1&=x_0\\ r_2&=[(\frac{A_y-y_0}{A_x-x_0})^2-(x_0+A_x)]\ mod\ n\\ r_3&=[(\frac{B_y-y_0}{B_x-x_0})^2-(x_0+B_x)]\ mod\ n\\ r_4&=[(\frac{C_y-y_0}{C_x-x_0})^2-(x_0+C_x)]\ mod\ n\\ r_5&=[(\frac{D_y-y_0}{D_x-x_0})^2-(x_0+D_x)]\ mod\ n \end{align*}

结合方程组1、方程组2、方程组3，整理一下就有：

\begin{align*} f_1&=s_1*k_1-H-x_0*d\\ f_2&=s_2*k_2*(A_x-x_0)^2-H*(A_x-x_0)^2-[(A_y-y_0)^2-(x_0+A_x)*(A_x-x_0)^2]*d\\ f_3&=s_3*k_3*(B_x-x_0)^2-H*(B_x-x_0)^2-[(B_y-y_0)^2-(x_0+B_x)*(B_x-x_0)^2]*d\\ f_4&=s_4*k_4*(C_x-x_0)^2-H*(C_x-x_0)^2-[(C_y-y_0)^2-(x_0+C_x)*(C_x-x_0)^2]*d\\ f_5&=s_5*k_5*(D_x-x_0)^2-H*(D_x-x_0)^2-[(D_y-y_0)^2-(x_0+D_x)*(D_x-x_0)^2]*d \end{align*}

此时的未知数数量为5个，刚好就是我们的方程数。

然后我们再用下groebner_basis，计算出 $d$ 然后去伪造r跟s就行了。

1
# sage 10.6
2

3
# =============Level 3=============
4
tt = []
5
t_int = [bytes_to_long(i) for i in tt]
6
io.recvuntil(b"context: ")
7
sh = []
8
R = PolynomialRing(GF(n), "k0, z, x0, y0, d")
9
k0, z, x0, y0, d = R.gens()
10
io.sendline(tt[0].hex().encode())
11
sh.append(eval(io.recvline().split()[-1].decode()))
12
eqs = [y0**2-(x0**3+3), sh[0]*k0-(z+x0*d)]
13
for i in range(1, 5):
14
    io.recvuntil(b"context: ")
15
    ki = k0 + (t_int[i]-t_int[0])*(256**16)
16
    del_k = (t_int[i]-t_int[0])*(256**16)*G
17
    del_kx, del_ky = del_k.xy()
18
    sl = (del_ky-y0)/(del_kx-x0)
19
    xi = sl**2-x0-del_kx
20
    io.sendline(tt[i].hex().encode())
21
    sh.append(eval(io.recvline().split()[-1].decode()))
22
    eqs.append((sh[i]*ki-(z+xi*d)).numerator())
23
# print("over")
24
I = R.ideal(eqs)
25
priv = I.groebner_basis()[-1]
26
# print(priv)
27
priv = int(-priv.coefficients()[-1])
28
r, s = Sign(priv, b'n1junior_2025', f'cat /flag{level}'.encode())
29
io.recvuntil(b"signature: ")
30
io.sendline(b" ".join([str(r).encode(), str(s).encode()]))
31
c3 = io.recvline().decode()
32
print(c3)
33
# flag3: flag{**redacted1**}

exp

点击展开代码

1
from pwn import *
2
from sage.all import *
3
from gmpy2 import invert
4
from Crypto.Util.number import *
5
from hashlib import md5
6

7

8
def Sign(priv, ctx, msg):
9
    k = bytes_to_long(ctx + md5(str(priv).encode() + msg).digest())
10
    z = bytes_to_long(md5(ctx + msg).digest())
11
    r = int((k * G).x()) % n
12
    s = (pow(k, -1, n) * (z + r * priv)) % n
13
    return r, s
14

15

16
E = EllipticCurve(GF(0x1337_ca7_eae368ff5d702e6067aaaa77ca_ca7_1337), [0, 3])
17
G, n = E(1, 2), E.order()
18
# io = remote("60.205.163.215", int(27074))
19
io = process(['sage', 'test.sage'])
20
level = 0
21

22

23
# =============Level 0=============
24
io.recvuntil(b"context: ")
25
io.sendline(b"")
26
msg = bytes.fromhex(io.recvline().split()[-1].decode())
27
r = eval(io.recvline().split()[-1].decode())
28
s = eval(io.recvline().split()[-1].decode())
29

30
# s = (pow(k, -1, n) * (z + r * priv)) % n
31
z = bytes_to_long(md5(msg).digest())
32
k1 = (E.lift_x(Integer(r))).log(G)
33
k2 = (-E.lift_x(Integer(r))).log(G)
34
priv = ((s*k1-z)*invert(r, n))%n
35
priv_i = ((s*k1-z)*invert(r, n))%n
36
if k1 != bytes_to_long(md5(str(priv).encode() + msg).digest()):
37
    priv = priv_i
38
r, s = Sign(priv, b'n1junior_2025', f'cat /flag{level}'.encode())
39
io.recvuntil(b"signature: ")
40
io.sendline(b" ".join([str(r).encode(), str(s).encode()]))
41
c1 = io.recvline().decode()
42
print(c1)
43
level += 1
44

45

46

47
# =============Level 1=============
48
io.recvuntil(b"context: ")
49
io.sendline(b"")
50
msg = bytes.fromhex(io.recvline().split()[-1].decode())
51
r = eval(io.recvline().split()[-1].decode())
52
s = eval(io.recvline().split()[-1].decode())
53

54
# s = (pow(k, -1, n) * (z + r * priv)) % n
55
z = bytes_to_long(md5(msg).digest())
56
k1 = (E.lift_x(Integer(r))).log(G)
57
k2 = (-E.lift_x(Integer(r))).log(G)
58
priv = ((s*k1-z)*invert(r, n))%n
59
priv_i = ((s*k1-z)*invert(r, n))%n
60
if k1 != bytes_to_long(md5(str(priv).encode() + msg).digest()):
61
    priv = priv_i
62
r, s = Sign(priv, b'n1junior_2025', f'cat /flag{level}'.encode())
63
io.recvuntil(b"signature: ")
64
io.sendline(b" ".join([str(r).encode(), str(s).encode()]))
65
c1 = io.recvline().decode()
66
print(c1)
67
level += 1
68

69

70
# =============Level 2=============
71
t1 =
72
t2 =
73
tt1 = int(bytes_to_long(t1)*256**16%n)
74
tt2 = int(bytes_to_long(t2)*256**16%n)
75
io.recvuntil(b"context: ")
76
io.sendline(t1.hex().encode())
77
r1 = eval(io.recvline().split()[-1].decode())
78
s1 = eval(io.recvline().split()[-1].decode())
79

80
io.recvuntil(b"context: ")
81
io.sendline(t2.hex().encode())
82
r2 = eval(io.recvline().split()[-1].decode())
83
s2 = eval(io.recvline().split()[-1].decode())
84

85
# s = (pow(k, -1, n) * (z + r * priv)) % n
86
k1 = (E.lift_x(Integer(r1))).log(G)
87
k2 = (E.lift_x(Integer(r2))).log(G)
88
k11 = (-E.lift_x(Integer(r1))).log(G)
89
k22 = (-E.lift_x(Integer(r2))).log(G)
90
if abs(tt1-k1) > abs(tt1-k11):
91
    k1 = k11
92
if abs(tt2-k2) > abs(tt2-k22):
93
    k2 = k22
94
priv = ((s1*k1-s2*k2)*invert(r1-r2, n))%n
95
r, s = Sign(priv, b'n1junior_2025', f'cat /flag{level}'.encode())
96
io.recvuntil(b"signature: ")
97
io.sendline(b" ".join([str(r).encode(), str(s).encode()]))
98
c2 = io.recvline().decode()
99
print(c2)
100
level += 1
101

102

103
# =============Level 3=============
104
tt = []
105
t_int = [bytes_to_long(i) for i in tt]
106
io.recvuntil(b"context: ")
107
sh = []
108
R = PolynomialRing(GF(n), "k0, z, x0, y0, d")
109
k0, z, x0, y0, d = R.gens()
110
io.sendline(tt[0].hex().encode())
111
sh.append(eval(io.recvline().split()[-1].decode()))
112
eqs = [y0**2-(x0**3+3), sh[0]*k0-(z+x0*d)]
113
for i in range(1, 5):
114
    io.recvuntil(b"context: ")
115
    ki = k0 + (t_int[i]-t_int[0])*(256**16)
116
    del_k = (t_int[i]-t_int[0])*(256**16)*G
117
    del_kx, del_ky = del_k.xy()
118
    sl = (del_ky-y0)/(del_kx-x0)
119
    xi = sl**2-x0-del_kx
120
    io.sendline(tt[i].hex().encode())
121
    sh.append(eval(io.recvline().split()[-1].decode()))
122
    eqs.append((sh[i]*ki-(z+xi*d)).numerator())
123
# print("over")
124
I = R.ideal(eqs)
125
priv = I.groebner_basis()[-1]
126
# print(priv)
127
priv = int(-priv.coefficients()[-1])
128
r, s = Sign(priv, b'n1junior_2025', f'cat /flag{level}'.encode())
129
io.recvuntil(b"signature: ")
130
io.sendline(b" ".join([str(r).encode(), str(s).encode()]))
131
c3 = io.recvline().decode()
132
print(c3)
133

134
"""
135
flag0: 💧
136

137
flag1: 🐱
138

139
flag2: flag{**redacted**}
140

141
flag3: flag{**redacted1**}
142

143
"""

*sign one m0re

题目

1
from fastecdsa.curve import secp256k1
2
from fastecdsa.point import Point
3
from secrets import randbelow
4
from hashlib import sha512
5
import signal
6
import os
7

8
FLAG = os.environ.get("FLAG", "flag{**redacted**}")
9

10
MAX_SESSIONS = 192
11

12
p, q, G = secp256k1.p, secp256k1.q, secp256k1.G
13
info = int.from_bytes(b"[N1CTF Junior 2025]", "big")
14
z = Point(info, pow(info ** 3 + 7, (p + 1) // 4, p), secp256k1)
15

16
class Signer:
17
    def __init__(self):
18
        self.x = randbelow(q)
19
        self.y = self.x * G
20
        self.sessions = {sid: (0, ) for sid in range(MAX_SESSIONS)}
21

22
    def get_public_key(self):
23
        return self.y
24

25
    def commit(self, sid):
26
        assert sid in range(MAX_SESSIONS), "Invalid session"
27
        assert self.sessions[sid][0] == 0, "Invalid state"
28
        u, s, d = [randbelow(q) for _ in range(3)]
29
        a, b = u * G, s * G + d * z
30
        self.sessions[sid] = (1, u, s, d)
31
        return a, b
32

33
    def sign(self, sid, e):
34
        assert sid in range(MAX_SESSIONS), "Invalid session"
35
        assert self.sessions[sid][0] == 1, "Invalid state"
36
        assert 1 < e < q, "Invalid query"
37
        _, u, s, d = self.sessions[sid]
38
        c = (e - d) % q
39
        r = (u - c * self.x) % q
40
        self.sessions[sid] = (2, )
41
        return r, c, s, d
42

43
class Verifier:
44
    def __init__(self):
45
        self.messages = set()
46

47
    def oracle(self, α, β, z, msg):
48
        to_hash = "||".join(map(str, [α.x, α.y, β.x, β.y, z.x, z.y, msg]))
49
        return int.from_bytes(sha512(to_hash.encode()).digest(), "big") % q
50

51
    def verify(self, pub, sig, msg):
52
        assert all(1 < x < q for x in sig), "Invalid signature"
53
        ρ, ω, σ, δ = sig
54
        if (ω + δ) % q == self.oracle(ρ * G + ω * pub, σ * G + δ * z, z, msg):
55
            self.messages.add(msg)
56
            if len(self.messages) == MAX_SESSIONS + 1:
57
                return FLAG
58
            return "Good signature"
59
        return "Bad signature"
60

61
signal.alarm(300)
62
signer = Signer()
63
verifier = Verifier()
64

65
while True:
66
    cmd, *args = input("> ").split()
67
    if cmd == "get_key":
68
        y = signer.get_public_key()
69
        print(f"y = ({y.x}, {y.y})")
70
    elif cmd == "commit":
71
        sid = int(args[0])
72
        a, b = signer.commit(sid)
73
        print(f"a = ({a.x}, {a.y})")
74
        print(f"b = ({b.x}, {b.y})")
75
    elif cmd == "sign":
76
        sid, e = int(args[0]), int(args[1])
77
        r, c, s, d = signer.sign(sid, e)
78
        print(f"{r = }")
79
        print(f"{c = }")
80
        print(f"{s = }")
81
        print(f"{d = }")
82
    elif cmd == "verify":
83
        sig, msg = tuple(map(int, args[:4])), args[4]
84
        print(verifier.verify(signer.get_public_key(), sig, msg))

解题分析

先分析一下题目：

题目允许我们输入三种指令并输出对应的结果：
1，输入 “get_key”，会返回签名密钥y。
2，输入 “commit sid”（ $sid\in Z_{192}$ ），会返回sid对应的承诺值 $(a,\ b)$ ，其中 $a=u*G$ 、 $b=s*G+d*z$ ；可以发192次。
3，输入 “sign sid e”，会用sid的session来签名e（其中 $e=H(\alpha,\beta,z,\text{msg})$ ， $z$ 为椭圆secp256k1上横坐标为info的点），得到签名值 $(r,\ c,\ s,\ d)$ ，其中 $c=(e-d)\ mod\ q$ 、 $r=(u-c*x)\ mod\ q$ ；可以发192次
4，输入 “verify r c s d msg”，会验证 $(r,\ c,\ s,\ d)$ 是否是msg的签名值；如果是，则返回 “Good signature”并储存到集合messages里，否则为 “Bad signature”；倘若messages里有193个值，则返回flag。

由此可见，我们的目标就是：在能获取192个签名的情况下，伪造出message值不同的第193个签名

而这道题当时有给了提示（不过我没来得及保存），最后是指向一篇叫做Dimensional eROSion: Improving the ROS Attack with Decomposition in Higher Bases↗的论文，相关攻击在5.2节（当然，论文里也有对应的攻击代码，但就是需要改改才能用）。

但在讲攻击方法之前，我们先回看一下刚刚分析的第三步与第四步，因为每次签名与验签都是围绕着这个：

\begin{align*} (c+d)\ mod\ n=e&=H(\alpha,\beta,z,\text{msg})\\ &=H(ρ*G+ω*pub,σ*G+δ*z,z,msg)\\ &=H(r*G+c*pub,s*G+d*z,z,msg) \end{align*}

而如果我们关注一下 $H(r*G+c*pub,s*G+d*z,z,msg)$ 会发现：

\begin{align*} \alpha&=r*G+c*pub=(u-c*x)G+(c*x)g=u*G=a\\ \beta&=s*G+d*z=b \end{align*}

也就是说： $e=(c+d)\ mod\ n=H(a,b,z,msg)$ 。

attacking m-BZ

（因为我自己目前也没完全看懂整篇论文，所以就稍微写了下攻击流程，有空就再写详细点）

流程如下：

已知： $z$
收集 commit
对每个会话 $i=0\dots191$ 做commit，拿到 $(a_i,b_i)$ 。
预计算挑战值
根据Theorem 2，计算 $A=\{A_i|i\in[0,6]\}$ 和 $B=\{B_i|i\in[0,6]\}$ ：
遍历集合 $B$ ，每次遍历里：
选 $B_i$ 条消息 $m_{i,b}$ ，计算 $e_{i,b}=H(a_i,b_i,z,m_{i,b})\bmod n$ ，然后以 $e_{i,0}$ 为基准，构造差值向量 $q_i=[e_{i,1}-e_{i,0},\ e_{i,2}-e_{i,0},\ \dots]$
Lattice + Babai
建矩阵 $M_i=\begin{bmatrix}q_i\\ nI\end{bmatrix}$ ，解“最近向量”（SVP）得 $\mu_i$ ， $\mu_i$ 满足 $\mu_i\cdot q_i\approx[1,2,\dots]$
分解常数
目标： $\sum_{i=0}^{191} \text{pows}[i]\cdot\mu_i\cdot e_{i,\text{digits}[i]}\equiv 1\bmod n$
用 multibase(1,pows) 逐位分解，输出 digits[i]——第 $i$ 维应选的挑战值索引。
一次重放签名
按 digits[i] 重发挑战值 $e_{i,\text{digits}[i]}$ ，拿到 $(r_i,c_i,s_i,d_i)$ 后立即发送验证，累计 192 次。
线性组合伪造
伪造以下参数：
$\begin{aligned} K_i&=\text{extra\_alpha}\cdot\text{pows}[i]\cdot\mu_i\bmod n\\ r_f&=\sum K_i r_i\bmod n\\[2pt] c_f&=\sum K_i c_i\bmod n\\[2pt] s_f&=\sum K_i s_i\bmod n\\[2pt] d_f&=\sum K_i d_i\bmod n \end{aligned}$
这些参数满足：
$c_f+d_f=\sum K_i e_{i,\text{digits}[i]}=H(r_f*G+c_f*pub,s_f*G+d_f*z,z,\text{msg}_{\text{forge}})$
也因此，我们便有了193个不同msg的签名。
触发 flag
把 $(r_f,c_f,s_f,d_f,\text{msg}_{\text{forge}})$ 发给靶机进行 verify，verify通过时消息计数变为 193，于是直接返回了 flag。

exp

这里贴一下某个✌的exp：

1
#!/usr/bin/env python3
2
"""
3
One-shot ROS attack for 'sign one m0re' challenge
4
- Collect 192 commits (a_i, b_i)
5
- For each i, precompute multiple candidate e_{i,j} = H(a_i, b_i, z, m_{i,j}) by varying messages
6
- Build per-dimension lattices and solve via Babai to get mu_i
7
- Decompose target to choose j_i per dimension so that sum K_i * e_{i,j_i} == e_forge
8
- Query sign once per session with e_{i,j_i}, collect (r_i, c_i, s_i, d_i)
9
- Forge (rho, omega, sigma, delta) = sum K_i * (r_i, c_i, s_i, d_i)
10
- Verify forged signature on forged message to get flag
11

12
Notes:
13
- All modular arithmetic is done mod n (curve order)
14
- EC point ops use Sage on secp256k1 over GF(p)
15
- Requires running with `sage -python one_shot_ros.py`
16
"""
17

18
from pwn import *
19
import hashlib
20
import os
21
from sage.all import *
22
from sage.modules.free_module_integer import IntegerLattice
23

24
# secp256k1 params
25
FIELD_P = Integer(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f)  # field prime
26
ORDER_N = Integer(0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141)  # group order
27
Fp = GF(FIELD_P)
28
Zn = GF(ORDER_N)
29
E = EllipticCurve(Fp, [0, 7])
30
G = E(Integer(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798),
31
      Integer(0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8))
32

33
MAX_SESSIONS = 192
34

35
# Fixed z from challenge
36
INFO = int.from_bytes(b"[N1CTF Junior 2025]", "big")
37
z_point = E(Integer(INFO), Integer(pow(INFO ** 3 + 7, (FIELD_P + 1) // 4, FIELD_P)))
38

39
# Oracle identical to challenge (mod n)
40
def oracle(alpha_pt, beta_pt, z_pt, msg_str):
41
    to_hash = "||".join(map(str, [int(alpha_pt[0]), int(alpha_pt[1]), int(beta_pt[0]), int(beta_pt[1]), int(z_pt[0]), int(z_pt[1]), msg_str]))
42
    return Integer(int.from_bytes(hashlib.sha512(to_hash.encode()).digest(), "big")) % ORDER_N
43

44
# Utilities
45

46
def inner_product(coeffs, vals):
47
    return sum(c * v for c, v in zip(coeffs, vals))
48

49

50
def scale_to_Zn(vec):
51
    # Convert a vector of rationals in Zn to a single Zn element (first entry) after solving
52
    assert all(gcd(ORDER_N, el.denominator()) == 1 for el in vec)
53
    return vector(Zn, [Zn(el.numerator()) / Zn(el.denominator()) for el in vec])
54

55

56
def pows_gen(n=7, group_bit_len=256, extra_digits=0):
57
    # Same as provided Sage, but using ORDER_N
58
    max_number = Integer(2) ** group_bit_len
59
    assert n >= 2
60
    factored = []
61
    k = n - 1
62
    while k >= 1:
63
        B = QQ(1) / QQ(500)  # practical tweak
64
        max_k = ceil(log(max_number, k + 1))
65
        if k == 1:
66
            e_k = 0
67
        else:
68
            e_k = ceil(log(B * log(ORDER_N, k + 1) * ORDER_N ** ((k - 1) / k), k + 1)) + extra_digits
69
        factored = [(k + 1, i) for i in range(e_k, max_k)] + factored
70
        max_number = (k + 1) ** e_k
71
        k -= 1
72
    return factored  # list of (base, exponent)
73

74

75
def multibase(num_int, pows):
76
    # pows is list of integers (bases already exponentiated)
77
    temp = Integer(num_int)
78
    digits = []
79
    for base in pows[::-1]:
80
        digits = [temp // base] + digits
81
        temp = temp % base
82
    assert inner_product(digits, pows) == num_int
83
    return digits
84

85

86
def choose_pows_up_to(max_sessions=192, start_basis=7, max_basis_cap=12):
87
    # Try to get len(pows) as close to max_sessions without exceeding
88
    best = None
89
    for mb in range(start_basis, max_basis_cap + 1):
90
        factored = pows_gen(n=mb + 1, group_bit_len=ceil(log(ORDER_N, 2)), extra_digits=0)
91
        pows = [Integer(b) ** Integer(e) for (b, e) in factored]
92
        if best is None or (len(pows) <= max_sessions and len(pows) > len(best[0])):
93
            best = (pows, [b for (b, e) in factored])
94
        if len(pows) == max_sessions:
95
            break
96
    # If still shorter, pad with base=2 powers of 1 to reach max_sessions (benign extra dims)
97
    pows, bases = best
98
    if len(pows) < max_sessions:
99
        pad = [Integer(2)] * (max_sessions - len(pows))
100
        pows = pows + pad
101
        bases = bases + [2] * len(pad)
102
    if len(pows) > max_sessions:
103
        pows = pows[:max_sessions]
104
        bases = bases[:max_sessions]
105
    return pows, bases
106

107

108
def main():
109
    context = contextlib = None  # avoid lint
110
    print("[*] One-shot ROS attack starting...")
111

112
    # Connect to challenge
113
    io = process(['python3', 'sign one m0re.py'])
114

115
    # Get public key
116
    io.sendline(b"get_key")
117
    line = io.recvline().decode().strip()
118
    y_coords = line.split("y = (")[1].rstrip(")")
119
    yx, yy = map(int, y_coords.split(", "))
120
    Y = E(Integer(yx), Integer(yy))
121
    print(f"[*] Public key Y.x={yx}")
122

123
    # Choose bases and pows
124
    pows, pows_bases = choose_pows_up_to(MAX_SESSIONS, start_basis=7, max_basis_cap=12)
125
    ell = len(pows)
126
    assert ell == MAX_SESSIONS, f"ell={ell} != {MAX_SESSIONS}, adjust choose_pows_up_to"
127
    print(f"[*] ell = {ell} dimensions")
128

129
    # Collect commits (a_i, b_i)
130
    A_pts = []
131
    B_pts = []
132
    a_coords_list = []
133
    b_coords_list = []
134

135
    for sid in range(ell):
136
        io.sendline(f"commit {sid}".encode())
137
        la = io.recvline().decode().strip()
138
        lb = io.recvline().decode().strip()
139
        ax_s = la.split("a = (")[1].rstrip(")")
140
        bx_s = lb.split("b = (")[1].rstrip(")")
141
        ax, ay = map(int, ax_s.split(", "))
142
        bx, by = map(int, bx_s.split(", "))
143
        a_pt = E(Integer(ax), Integer(ay))
144
        b_pt = E(Integer(bx), Integer(by))
145
        A_pts.append(a_pt)
146
        B_pts.append(b_pt)
147
        a_coords_list.append((ax, ay))
148
        b_coords_list.append((bx, by))
149
        if sid % 32 == 0:
150
            print(f"[*] commit {sid}/{ell}")
151

152
    # Generate candidate messages and e-values per dimension
153
    # For each i: generate pows_bases[i] candidates indexed 0..B_i-1
154
    msgs = []
155
    e_values = []  # list of lists of integers mod n
156

157
    for i in range(ell):
158
        Bi = int(pows_bases[i])
159
        mi_list = []
160
        ei_list = []
161
        for b in range(Bi):
162
            m = f"m{i}_{b}_{os.urandom(8).hex()}"
163
            eib = oracle(A_pts[i], B_pts[i], z_point, m)
164
            mi_list.append(m)
165
            ei_list.append(int(eib))
166
        msgs.append(mi_list)
167
        e_values.append(ei_list)
168
        if i % 32 == 0:
169
            print(f"[*] candidates {i}/{ell}")
170

171
    # Build qi and lattices M_i
172
    qi = []  # differences list for each i: [e_i_b - e_i_0] for b>=1
173
    M = []
174

175
    for i in range(ell):
176
        base_e0 = Integer(e_values[i][0])
177
        diffs = [Integer((Integer(e_values[i][b]) - base_e0) % ORDER_N) for b in range(1, int(pows_bases[i]))]
178
        qi.append(diffs)
179
        if len(diffs) > 0:
180
            top = Matrix(ZZ, [diffs])  # 1 x (Bi-1)
181
            bottom = ORDER_N * matrix.identity(ZZ, len(diffs))  # (Bi-1) x (Bi-1)
182
            Mi = block_matrix([[top], [bottom]])
183
        else:
184
            Mi = matrix(ZZ, [[int(ORDER_N)]])
185
        M.append(Mi)
186

187
    # Solve CVP with Babai per dimension to obtain mu_i in Zn
188
    mu = []
189
    for i in range(ell):
190
        Bi = int(pows_bases[i])
191
        if Bi > 1:
192
            tgt = vector(ZZ, [int(j * Integer(pows[i])) for j in range(1, Bi)])
193
            lattice = IntegerLattice(M[i])
194
            closest = vector(ZZ, lattice.babai(tgt))
195
            sol = M[i].solve_left(closest)  # rational vector (length 1)
196
            mu_i = (Zn(1) / Zn(int(pows[i]))) * scale_to_Zn(sol)[0]
197
            mu.append(mu_i)
198
        else:
199
            mu.append(Zn.random_element())
200
    print("[*] mu computed")
201

202
    # Forge target alpha,beta points (base sums)
203
    # alpha_base = sum pows[i]*mu[i] * A_pts[i]
204
    # beta_base  = sum pows[i]*mu[i] * B_pts[i]
205
    alpha_base = None
206
    beta_base = None
207
    for i in range(ell):
208
        coeff = int((Zn(int(pows[i])) * mu[i]).lift())  # 0..n-1
209
        if coeff % int(ORDER_N) == 0:
210
            continue
211
        term_a = Integer(coeff) * A_pts[i]
212
        term_b = Integer(coeff) * B_pts[i]
213
        alpha_base = term_a if alpha_base is None else alpha_base + term_a
214
        beta_base = term_b if beta_base is None else beta_base + term_b
215
    if alpha_base is None:
216
        print("[!] alpha_base is None, abort")
217
        io.close(); return
218

219
    # Try decomposition attempts
220
    attempts = 0
221
    success = False
222

223
    while attempts < 80 and not success:
224
        attempts += 1
225
        extra_alpha = Zn.random_element()
226
        if int(extra_alpha) == 0:
227
            continue
228
        inv_extra = Zn(int(pow(int(extra_alpha), -1, int(ORDER_N))))
229

230
        alpha_forge = int(extra_alpha) * alpha_base
231
        beta_forge = int(extra_alpha) * beta_base
232
        msg_forge = f"forge_msg_{os.urandom(6).hex()}"
233
        c_forge = Integer(oracle(alpha_forge, beta_forge, z_point, msg_forge))  # in [0,n)
234

235
        # NUM = extra_alpha^{-1} * c_forge + sum pows*mu*(-e_i0) mod n
236
        NUM = (inv_extra * Zn(int(c_forge)))
237
        for i in range(ell):
238
            NUM += (Zn(0) - (Zn(int(pows[i])) * mu[i] * Zn(int(e_values[i][0]))))
239
        NUM_int = Integer(int(NUM.lift()))  # 0..n-1
240

241
        # greedy digit by digit
242
        digits = [0] * ell
243
        NUM_cur = NUM_int
244
        ok = True
245
        for i in range(ell - 1, -1, -1):
246
            try:
247
                cur_digits = multibase(NUM_cur, [Integer(x) for x in pows])
248
            except AssertionError:
249
                ok = False
250
                break
251
            new_digit = int(cur_digits[i])
252
            digits[i] = new_digit
253
            if new_digit >= int(pows_bases[i]):
254
                ok = False
255
                break
256
            if new_digit != 0:
257
                # NUM_cur -= pows[i] * mu[i] * qi[i][new_digit-1] (mod n) as integer representative
258
                delta = (Zn(int(pows[i])) * mu[i] * Zn(int(qi[i][new_digit - 1])))
259
                NUM_cur = Integer((NUM_cur - int(delta.lift())) % int(ORDER_N))
260
            if NUM_cur < 0:
261
                ok = False
262
                break
263
            if NUM_cur == 0:
264
                # can break early only if remaining higher digits are 0
265
                pass
266
        if ok and NUM_cur == 0:
267
            success = True
268
            print(f"[+] Decomposition success in {attempts} attempts")
269
            break
270
        if attempts % 10 == 0:
271
            print(f"[*] attempt {attempts} failed")
272

273
    if not success:
274
        print("[!] Decomposition failed. Consider rerunning.")
275
        io.close(); return
276

277
    # With digits selected, we now sign once per session using e_i = e_values[i][digits[i]]
278
    # and immediately verify to accumulate 192 messages in the verifier
279
    signed = []  # tuples (r,c,s,d,msg)
280
    for i in range(ell):
281
        e_sel = int(e_values[i][digits[i]])
282
        msg_i = msgs[i][digits[i]]
283
        io.sendline(f"sign {i} {e_sel}".encode())
284
        r_line = io.recvline().decode().strip(); r = int(r_line.split("r = ")[1])
285
        c_line = io.recvline().decode().strip(); c = int(c_line.split("c = ")[1])
286
        s_line = io.recvline().decode().strip(); s = int(s_line.split("s = ")[1])
287
        d_line = io.recvline().decode().strip(); d = int(d_line.split("d = ")[1])
288
        signed.append((r, c, s, d, msg_i))
289
        # verify this legit signature to populate set
290
        io.sendline(f"verify {r} {c} {s} {d} {msg_i}".encode())
291
        vr = io.recvline().decode().strip()
292
        if "Good signature" not in vr and "flag{" not in vr:
293
            print(f"[!] Legit signature verify failed for session {i}: {vr}")
294
            io.close(); return
295
        if i % 32 == 0:
296
            print(f"[*] verified legit {i}/{ell}")
297

298
    # Compute forged signature as linear combination with K_i = extra_alpha * pows[i] * mu[i]
299
    rho_f = 0; omega_f = 0; sigma_f = 0; delta_f = 0
300
    for i in range(ell):
301
        Ki = int((extra_alpha * Zn(int(pows[i])) * mu[i]).lift()) % int(ORDER_N)
302
        r, c, s, d, _ = signed[i]
303
        rho_f = (rho_f + Ki * r) % int(ORDER_N)
304
        omega_f = (omega_f + Ki * c) % int(ORDER_N)
305
        sigma_f = (sigma_f + Ki * s) % int(ORDER_N)
306
        delta_f = (delta_f + Ki * d) % int(ORDER_N)
307

308
    # Final verify forged signature to trigger the flag
309
    io.sendline(f"verify {rho_f} {omega_f} {sigma_f} {delta_f} {msg_forge}".encode())
310
    res = io.recvline().decode().strip()
311
    print(res)
312

313
    io.close()
314

315
if __name__ == "__main__":
316
    main()

后续

还差一题，这周就一定更新！（确信！）

Thanks for reading!

N1junior2025-Crypto

Mon Sep 15 2025

5165 words · 40 minutes

CTF Crypto

N1junior2025-Crypto

sign (in) the ca7s

题目

解题分析

一，MD5碰撞

二，具体题目

Level 0/1

Level 2

Level 3

exp

*sign one m0re

题目

解题分析

attacking m-BZ

exp

后续

N1junior2025-Crypto