网鼎杯-2024

Posted by Ma3t1n on 2025-01-17
Estimated Reading Time 12 Minutes
Words 2.8k In Total
Viewed Times

Crypto1

题目基于Shamir门限方案.

他进行了10000轮的Shamir秘密分享，而每一轮的流程是（设flag长度为n）：

设置player数量为n

设置threshold为2n

生成coefs，其由n个模257下的随机数列表组成，每个列表长为2n，记这些长为2n的向量为$\textbf{c}_i$

生成randoms，其长度为2n，前n个为flag，后n个为模257下的随机数，记为$\textbf{r}$

计算：

​ 给出每一轮的$\textbf{c}_i$和$v_i$，要求还原$\textbf{r}$

1
2
3
4
values = [
            sum([r * c for r, c in zip(randoms, coef)]) % self.modulus
            for coef in coefs
        ]

$values=coefs \cdot randoms=coefs\cdot[flags,r] $

​ 我们将coefs也将前n列的向量记作矩阵A，后n列记作矩阵B，所以$values=A\cdot flags+B\cdot r$

​ 对于这个式子我们需要求出$flags$，所以我们需要消掉$r$对于我们的影响然后就可以求出$flags$了，对于一个满秩的矩阵是可以求出一个矩阵与他相乘等于零，所以我们可以求出B的左零向量使得$v\times B=0$，那么上式就可以变成$v\times values=v\times A\cdot flags$，这个式子中$v\times values$与$v\times A$都是可以求出来的，解方程就可以得到$flags$了。而题目中给的数据也是刚刚好，有32组满秩的B可以求出他的左零向量。

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
from sage.all import *


K = 10000
L = 32
modulus=257
class ShamirSS:
    def __init__(self, coefs, value):
        self.coefs = coefs
        self.value = value
V=[]
AA=[]
SS=[]
for k in range(K):
    b = []
    share_file = f"Competition/shares/share_{k}.sobj"
    shares = load(share_file)  # 从文件加载共享对象
    A=[]
    B=[]
    S=[]
    for i in shares:
        A.append(i.coefs[:32])
        B.append(i.coefs[32:])
        S.append(i.value)

    M1=Matrix(Zmod(modulus),32,32,A)
    M2=Matrix(Zmod(modulus),32,32,B)
    
    if(M2.rank()!=32):
        v = vector(M2.left_kernel().basis()[0])
        V.append(v)
        AA.append(v*M1)
        SS.append(v * vector(S))

BB = matrix(Zmod(modulus), AA)
ans = BB.solve_right(vector(SS))

flag = b''
for i in ans:
    flag += bytes.fromhex(hex(i)[2:])

print(flag)

Crypto2

题目基于OT，连接上靶机后靶机会生成：

32字节的aeskey
32字节的xorkey
1024bit的RSA公私钥对
长度为70的secrets列表，其中每个元素都是随机的32个字节

有了这些量之后，靶机接着生成一个长为71的列表message_pairs，其中元素构成为：

第一个值为(aeskey, xorkey)
后70个值为AES和XOR分别对secrets列表中每个元素的加密结果构成的二元组

RSA-OT

之后正式进入限时120s的交互， 交互基于1 out of 2的RSA-OT，共71轮。具体一轮交互过程为：

输入两个值m0，m1，对于题目来讲这都是32字节的量

将两个量分别做PKCS#1 v1.5的encode，得到128字节的m0和m1

PKCS#1 v1.5的encode结果就是：

1
b"\x00\x02" + ps + b"\x00" + m0 (128 bytes)

其中ps是随机填充的每个字节都不等于0的字节串

随机生成128字节的x0，x1并给出，我们需要输入一个v，之后靶机会返回：M0和M1，如下

1
2
M0 = (m0 + pow(v - x0, self.d, self.n)) % self.n
M1 = (m1 + pow(v - x1, self.d, self.n)) % self.n

​ 我们的任务是在71轮交互全部完成后，解出所有的secret，并且拿到完整的aeskey和xorkey从而拿到flag
​ 如果我们输入的$v=x_0$或$x_1$，可以得到一个$M_0$或$M_1$的值，但是对于另一个值的求解问题等价于破解这个系统的RSA问题，毫无可能，所以尝试构造$v=X_0-X1+x_1$，其中$X_0,X_1$为第一次交互得到的$x_0,x_1$，这样构造的$v$可以使得我们每次交互得到的M1后面的

$pow(v - x1, d, n)=pow(X0-X1,d,n)$

​ 这是一个固定不变的值，我们设这个固定不变的值为$k$，变得只有前面的$m1$，而对于PKCS#1填充，前面2个字节是固定的，我们可以通过这两个字节得到$k$的前几个比特，倒数第33个字节也是\x00，我们可以通过这个字节泄露的值对于我们求得的k进行验证。

​ 比方说$M1$的高位是"\x12\x32"，那么我们在不考虑进位的情况下就可以得到k的高位为"\x12\x30"，如果有进位的话就是“\x12\x29”。 在理想的情况下，每次交互我们都能得到两个字节的值的话，在70次的交互是足够还原k的，如果还原了k我们就可以还原每一次交互中的$m_0,m_1$也就可以通过所有的check拿到flag。所以我们还需要将k每次左移2个字节，所以最终构造的$v=(X_0-X_1)\times 2^{16\times e\times i}+x_1$，i指的是第几次与靶机交互。

但是在实际操作中有很多的问题：

​ 第一个是$k$的数量级与我们的$n$是一样的所以我们得到的是$k\times 2^{16\times i}\mod n$，所以高位会被破坏，所以我们需要先将$k\times 2^{16\times i}$还原。因为是模n后的值，我们可以通过加$n$操作进行还原，对于加$n$的个数我们设为$ad$，对于$ad$我们可以通过我们之前求得的k高位进行估计，设我们现在求得的$k$高位为$k_h$，所以$ad\approx (k_h\times 2^{1024}-M_1)//n$，求得的$ad$值与实际的$ad$值误差很小，这个误差与n的大小有关，n的第一个字节越大误差越小，然后我们加上$ad\times n$后再继续加n，使得高位与我们已经得到的$k_h$相同即可。但问题就来了，当n很小的时候，对于现在还原的$k\times 2^{16\times i}$可能并不是正确的，因为继续加n同样可以满足高位不变而，这样的情况个数与n的大小有关，这里难以判断，只有在后续k的还原中可以通过倒数第33字节泄露的值进行检查。

​ 第二个问题也就是我们每次还原的k是否需要减一无法判断。如果我们每次读取3个16进制位的话，我们可以使用第四个16进制进行检查是否进位，但是当第四个16进制位为2时无法判断，但是这样只有$\frac{1}{32}$的概率误判，如果我们读取4个16进制为的话，对于是否进位只有$\frac{1}{2}$的概率误判，但1.5个字节在理想情况下只能还原105个字节，是远远不够的。

​ 但现在我们就已经陷入了一个无法解决的问题，因为前面只要有一次的k高位计算错误，就会导致后面还原的所有k错误，对于ad我们只需要n足够大就可以使得ad正确，这个可以通过多次交互实现，但是对于后面的还原k，即使我们前面使用24次交互获取1.5个字节，剩下的46次进行2个字节的获取，我们还原正确的k的概率为$(\frac{31}{32})^{24}\times (\frac{1}{2})^{46}\approx 6.6\times 10^{-15}$，加上倒数第33字节暴露的k值可以提高正确的概率，但正确的概率最多也就是$(\frac{31}{32})^{24}\times (\frac{1}{2})^{30}\approx 4.4\times 10^{-10}$。

​ 在这个时候或许你会使用dfs进行剪枝爆破，以确保我们每次得到的k是正确的，但实际上仍然无法在120s内得到。或许你会使用在PKCS#7填充中PS部分是不能出现“\x00”的这个地方进行攻击，所以可以使用这个部分对于k的每个字节进行剪枝。

​ 如果有80次交互我们就有$(\frac{31}{32})^{64}\approx 0.131$的概率恢复k。这个概率是可以接受的，所以在多次交互后可以成功的还原k，而还原k后，对于第一次交互aes_key，xor_key，而后面的2-81次交互我们可以拿到每次的$m_1=M1-k$，然后再与我们得到的xor_key进行异或也可以拿到secrets，也就可以正确的通过所有check拿到flag。

​ 这道题没有找到官方的writeup。下面是我自己写的一个脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
from tqdm import *


class RSA_OT:

    def __init__(self, key: RSA):
        self.key = key
        self.n = key.n
        self.e = key.e
        self.d = key.d
        self.nbyte = key.size_in_bytes()

    def new(nbits: int) -> "RSA_OT":
        key = RSA.generate(nbits)
        return RSA_OT(key)

    def encrypt(self, message: bytes) -> bytes:
        padded = encode(message, self.nbyte)
        ct = self.key._encrypt(padded)
        return int(ct).to_bytes(self.nbyte, "big")

    def show_public_key(self):
        print("[+] n =", hex(self.n))
        print("[+] e =", self.e)

    def run1(self, m0, m1):
        m0 = int.from_bytes(encode(m0, self.nbyte), "big")
        m1 = int.from_bytes(encode(m1, self.nbyte), "big")
        x0 = int.from_bytes(os.urandom(self.nbyte), "big") % self.n
        x1 = int.from_bytes(os.urandom(self.nbyte), "big") % self.n
        M0 = (m0 + pow(0, self.d, self.n)) % self.n
        M1 = (m1 + pow(x0 - x1, self.d, self.n)) % self.n
        k = pow(x0 - x1, self.d, self.n)
        return x0, x1, M0, M1, k

    def run2(self, m0, m1, x, i):
        m0 = int.from_bytes(encode(m0, self.nbyte), "big")
        m1 = int.from_bytes(encode(m1, self.nbyte), "big")
        x0 = int.from_bytes(os.urandom(self.nbyte), "big") % self.n
        x1 = int.from_bytes(os.urandom(self.nbyte), "big") % self.n
        if i < 64:
            M0 = (
                m0 + pow(x * pow(2, 12 * self.e * i, self.n) + x1 - x0, self.d, self.n)
            ) % self.n
            M1 = (
                m1 + pow(x * pow(2, 12 * self.e * i, self.n), self.d, self.n)
            ) % self.n
        else:
            M0 = (
                m0 + pow(x * pow(2, 16 * self.e * i, self.n) + x1 - x0, self.d, self.n)
            ) % self.n
            M1 = (
                m1 + pow(x * pow(2, 16 * self.e * i, self.n), self.d, self.n)
            ) % self.n
        return M0, M1


def xor(a: bytes, b: bytes) -> bytes:
    return bytes(x ^ y for x, y in zip(a, b))


aes_key = os.urandom(32)
xor_key = os.urandom(32)
aes = AES.new(aes_key, AES.MODE_ECB)
while 1:
    rsa_ot = RSA_OT.new(1024)
    if hex(rsa_ot.n)[2] == "f":
        break
secrets = [os.urandom(32) for i in range(80)]
message_pairs = [(aes_key, xor_key)]
message_pairs += [(aes.encrypt(secret), xor(xor_key, secret)) for secret in secrets]
rsa_ot.show_public_key()
x0, x1, M0, M1, k = rsa_ot.run1(message_pairs[0][0], message_pairs[0][1])
x = x0 - x1
K0 = [M0]
K1 = [M1]
for i in trange(1, len(message_pairs)):
    M0, M1 = rsa_ot.run2(message_pairs[i][0], message_pairs[i][1], x, i)
    K0.append(M0)
    K1.append(M1)
ik = ""
print(hex(k)[2:])


def genad3(c2, i, ik):
    t = "0" * 256
    kk = int(ik + t, 16)
    ad = 0
    if kk > c2:
        ad = (kk - c2) // rsa_ot.n
        sk = int(ik, 16)
        while int(hex(ad * rsa_ot.n + c2)[2:-256], 16) != sk:
            ad += 1
    if i > 21:
        for j in range(10):
            if hex((ad + j) * rsa_ot.n + c2)[-66:-64] == "00":
                return ad + j, ik
        ik = hex(int(ik, 16) - 1)[2:]
        kk = int(ik + t, 16)
        ad = 0
        ad = (kk - c2) // rsa_ot.n
        while (
            hex(ad * rsa_ot.n + c2)[2:-256] != ik
            and hex(ad * rsa_ot.n + c2)[-66:-64] != "00"
        ):
            ad += 1
    return ad, ik


def genad4(c2, ik):
    t = "0" * 256
    kk = int(ik + t, 16)
    ad = (kk - c2) // rsa_ot.n
    sk = int(ik, 16)
    while int(hex(ad * rsa_ot.n + c2)[2:-256], 16) != sk:
        ad += 1
    for j in range(10):
        if hex((ad + j) * rsa_ot.n + c2)[-66:-64] == "00":
            return ad + j, ik
    ik = hex(int(ik, 16) - 1)[2:]
    kk = int(ik + t, 16)
    ad = 0
    ad = (kk - c2) // rsa_ot.n
    while (
        hex(ad * rsa_ot.n + c2)[2:-256] != ik
        and hex(ad * rsa_ot.n + c2)[-66:-64] != "00"
    ):
        ad += 1
    return ad, ik


for i in range(64):
    c2 = K1[i]
    ad, ik = genad3(c2, i, ik)
    ik = hex(ad * rsa_ot.n + c2)[2:-253]
    if int(hex(ad * rsa_ot.n + c2)[-253], 16) < 2:
        ik = hex(int(ik, 16) - 1)[2:]
for i in range(64, 80):
    c2 = K1[i]
    ad, ik = genad4(c2, ik)
    ik = hex(ad * rsa_ot.n + c2)[2:-252]
for i in range(len(ik)):
    if ik[i] != hex(k)[2 + i]:
        print(ik[: i + 1])
        print(hex(k)[2 : i + 3])
        print(i)
        break

如果您喜欢此博客或发现它对您有用，则欢迎对此发表评论。 也欢迎您共享此博客，以便更多人可以参与。 如果博客中使用的图像侵犯了您的版权，请与作者联系以将其删除。 谢谢 ！

特色标签
链友
ESC