首页
论坛
课程
招聘
[原创]首届“安洵杯”国际赛站-WMCTF2022 官方WP之CRYPTO
2022-8-30 11:07 7058

[原创]首届“安洵杯”国际赛站-WMCTF2022 官方WP之CRYPTO

2022-8-30 11:07
7058

首届“安洵杯”国际赛站-WMCTF2022 官方WP

CRYPTO

ecc

由于题目给出了$G$以及$3G$的坐标,还有$n,c,e$,可以稍微想一下是曲线$G$,$3G$,曲线应该是模一个素数n的因子。

 

我们就使用推导$ 2G+G=3G$的方法,$2G$是二倍点,于是我们用二倍点公式和加法公式就能表达出来a和b都是模n的情况下,我们表达出来之后用加法公式中二倍点的东西和加法的东西去表达出来$a+kp$,用$y^2 - x^3 - ax^2 = b \mod p$,我们可以用2条去表达出来$b+k1p$和$b+k2p$然后相减,去和n,GCD分解n。

 

然后$a+k1p$ 和 $b+k2p $ 去模p能拿到a,于是我们就可以拿到a,b。接着就是RSA直接解c,发现a_bit+b_bit+c_bit=flag_bit = 606 bits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.Util.number import *
n = 61262574892917665379101848600282751252633178779864648655116434051615964747592676204833262666589440081296571836666022795166255640192795587508845265816642144669301520989571990670507103278098950563219296310830719975959589061794360407053224254135937766317251283933110936269282950512402428088733821277056712795259
ct = 16002162436420434728223131316901476099110904029045408221515087977802746863468505266500673611412375885221860212238712311981079623398373906773247773552766200431323537510699147642358473715224124662007742017000810447999989426207919068340364725395075614636875116086496704959130761547095168937180751237132642548997
x0,y0 = (3364552845709696244757995625685399274809023621531082895612949981433844727622567352338990765970534554565693355095508508160162961299445890209860508127449468 , 4874111773041360858453223185020051270111929505293131058858547656851279111764112235653823943997681930204977283843433850957234770591933663960666437259499093 )
x3,y3 = (8240596254289477251157504980772167439041663401504657696787046343848644902166655624353107697436635678388969190302189718026343959470011854412337179727187240 , 4413479999185843948404442728411950785256136111461847698098967018173326770728464491960875264034301169184074110521039566669441716138955932362724194843596479 )
fbits = 606
k1 = ((y3+ y0) * inverse(x0 - x3, n)) % n
k0_2 = (k1 ** 2 - (x3 - x0))%n
k0 = (((k0_2 - 3 *x0) * k1 + 2 * y0) * inverse(3 * x0 - k0_2 , n))% n
a_ = (k0 * 2 * y0 - 3 * x0 ** 2 )% n
b1 = y0**2 - x0**3 - x0 * a_
b2 = y3**2 - x3**3 - x3 * a_
e = 0x10001
p = (GCD(b1-b2,n))
a = a_% p
b = b1 % p
q = n//p
d = inverse(e,(p-1)*(q-1))
c = (pow(ct,d,n))
piece_bits = fbits // 3
flag = (a<<(2 * piece_bits)) + (b << piece_bits) + c
print(bin(c))
print(b'wmctf{'+long_to_bytes(flag)+b'}')

nanoDiamond - rev

exp如下:

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
from rich.progress import track
from pwn import *
import string
import hashlib
 
context(log_level='info', os='linux', arch='amd64')
 
r = remote('127.0.0.1', 65100)
 
 
def guess_remote(expr):
    global r
    r.recvuntil(b'Question: ')
    r.sendline(expr)
    r.recvuntil(b'Answer: ')
    ret = r.recvuntil(b'!', drop=True)
    return int(ret == b'True')
 
if __name__ == '__main__':
 
    def proof_of_work_2(suffix, hash):  # sha256, suffix, known_hash
        def judge(x): return hashlib.sha256(
            x.encode()+suffix).digest().hex() == hash
        return util.iters.bruteforce(judge, string.digits + string.ascii_letters, length=4)
    r.recvuntil(b'sha256(XXXX+')
    suffix = r.recv(16)
    r.recvuntil(b' == ')
    hash = r.recv(64).decode()
    r.recvuntil(b'Give me XXXX:')
    r.sendline(proof_of_work_2(suffix, hash))
 
    for round in track(range(50)):
        chests = [guess_remote(expr) for expr in ['B0', 'B1', 'B2', 'B3', 'B4', 'B5']]
        pairs = tuple([guess_remote(expr) for expr in [f'B0 == {chests[0]} and B1 == {chests[1]}', f'B2 == {chests[2]} and B3 == {chests[3]}', f'B4 == {chests[4]} and B5 == {chests[5]}']])
        if sum(pairs) == 3:
            print("CASE 0")
            tuple([guess_remote(expr) for expr in ['B0', 'B1', 'B2', 'B3']])
        elif sum(pairs) == 2:
            print("CASE 1")
            if pairs[0] == 0:
                chests[0] = int(chests[0] + guess_remote("B0") + guess_remote("B0") > 1)
                chests[1] = int(chests[1] + guess_remote("B1") + guess_remote("B1") > 1)
            if pairs[1] == 0:
                chests[2] = int(chests[2] + guess_remote("B2") + guess_remote("B2") > 1)
                chests[3] = int(chests[3] + guess_remote("B3") + guess_remote("B3") > 1)
            if pairs[2] == 0:
                chests[4] = int(chests[4] + guess_remote("B4") + guess_remote("B4") > 1)
                chests[5] = int(chests[5] + guess_remote("B5") + guess_remote("B5") > 1)
        elif sum(pairs) == 1:
            print("CASE 2")
            if pairs[0] == 0:
                chests[0], chests[1] = guess_remote("B0"), guess_remote("B1")
            if pairs[1] == 0:
                chests[2], chests[3] = guess_remote("B2"), guess_remote("B3")
            if pairs[2] == 0:
                chests[4], chests[5] = guess_remote("B4"), guess_remote("B5")
        print(chests)
        r.recvuntil('open the chests:')
        r.sendline(' '.join([str(int(x)) for x in chests]))
 
    r.interactive()

homo

题目实现的是gentry的同态加密方案,但是参数是随意选取的,这就导致该方案能够使用公钥直接计算出等价私钥。

 

首先,该方案的流程如下

 

密钥生成:
$$
sk = q\
pk = {p_iq + 2*ri}{i=0}^n
$$
其中,p,q,r均为素数。

 

加密时,要求明文仅有1bit
$$
randomly\ generate\ d \in {0,1}^n\
c =m+ \sum_{i=0}^nd[i]pk[i]
$$
解密时,计算
$$
m = (c\%sk)\%2
$$
由于$pk[i]\%sk = 2r_i$为偶数,因此模sk后,m即为结果的LSB。

 

由于n个pk均为q的倍数加上一个扰动(r相对于q较小),因此可以使用求解agcdp的方法求解出私钥q

 

参考https://martinralbrecht.wordpress.com/2020/03/21/the-approximate-gcd-problem/中的格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from sage.all import *
from Crypto.Util.number import *
c =
pubkey =
rbit = 191
Mlen = 10
M = Matrix(ZZ , Mlen , Mlen)
for i in range(1,Mlen):
    M[0 , i] = pubkey[i]
    M[i , i] = pubkey[0]
M[0,0] = 2**rbit
 
p0 = M.LLL()[0,0] // 2**rbit
q = pubkey[0] // p0
print(q)
print(long_to_bytes(int(''.join(str(int(j)) for j in [(i%q)%2 for i in c]),2)))

INTERCEPT

本题是个开放题,有多种解题思路和解题方法,出题人提供一种做法供大家参考,如下文所示:

 

最近,在A New Efficient Identity-Based Encryption without Pairing, Salimi 中提出了一种基于 RSA 模 TDDH 假设的新 IBE。 虽然这个方案是不安全的。 特别是,我们表明,给定 IBE 方案中的多个私钥,可以计算出一对等效的主密钥并完全破坏 KGC。

 

参考上面提到的论文,我们可以发现,当遵守他们提出的要求的对手可以访问n个私钥时,Salimi 的 IBE 方案是不安全的。 也就是说,他们的计划可以完全被打破。

 

我们有
$$
di = (y{i_1}s1 + y{i_2}s2)^{-1}\ mod\ zq\
h
{i1}\equiv y{i1}p\ mod\ zq\
h
{i2}\equiv y{i_2}p\ \ mod\ zq\
dj = (y{j_1}s1 + y{j_2}s2)^{-1}\ mod\ zq\
h
{j1}\equiv y{j1}p\ mod\ zq\
h
{j2}\equiv y{j2}p\ mod\ zq\
$$
我们设置了一组变量 $a
{k1},a{k2}$:
$$
\begin{aligned} a
{k_1}&=dih{i_1}-djh{j1}\&= (y{i1}p(y{j_1}s1 + y{j_2}s2)-y{j1}p(y{i_1}s1 + y{i_2}s2))/(y{i_1}s1 + y{i_2}s2)(y{j_1}s1 + y{j_2}s_2)\&=ps2(y{i1}y{j2}-y{j1}y{i2})/(y{i_1}s1 + y{i_2}s2)(y{j_1}s1 + y{j_2}s2)
\end{aligned}
$$
同样,
$$
\begin{aligned}a
{k_2}&=dih{i_2}-djh{j_2}\
&=ps1(y{i2}y{j1}-y{j2}y{i1})/(y{i_1}s1 + y{i_2}s2)(y{j_1}s1 + y{j_2}s2)
\end{aligned}
$$
很容易观察到
$$
\frac{a
{k1} }{a{k_2} } \equiv -\frac{s_2}{s1}\ mod\ zq
$$
所以我们可以知道:
$$
\frac{a
{k1} }{a{k2} }\equiv \frac{a{k'1} }{a{k'2} }\ mod\ zq\
a
{k1}a{k'2}-a{k'1}a{k2}\equiv 0\ mod\ zq
$$
通过计算 $(a
{k1}a{k'2}-a{k'1}a{k_2})$ in $\mathbb{Z}$, 我们收到隐藏阶 $zq$ 的倍数,不等于 0 的概率很高。

 

我们知道 $N/2zq=p+p/2q+1/z+1/2zq\in [p, p+1]$ since $N=(zp+1)(2q+1)=2zqp+zp+2q+1$, 这意味着我们可以求解一个方程来分解 N. 然后使用任何 $(h_{i1},h{i2})$我们能够得到 $(y{i1},y{i_2})$, 通过一些计算我们可以得到 $s'_1\equiv s_1,s'_2\equiv s_2\ mod\ zq$.

 

一旦我们得到这些秘密参数,我们就可以访问任意用户加密的任何消息。

 

flag: WMCTF{cracking_such_a_toy_system_is_so_easy!}

 

EXP:

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
from Crypto.Util.number import *
from gmpy2 import *
from random import randint
import hashlib
from string import digits, ascii_letters
from pwn import *
context.log_level = 'debug'
 
def proof_of_work(suffix,digest):
    table = digits + ascii_letters
    for i in table:
        for j in table:
            for k in table:
                for l in table:
                        guess = i+j+k+l+suffix
                        if hashlib.sha256(guess.encode()).hexdigest() == digest:
                            return (i+j+k+l)
 
 
class user:
    def __init__(self, params):
        self.e, self.d, self.h1, self.h2 = params
 
def attack():
    '''
    we register `limit_num` users
        (only with their private keys `d_i` and digest values `H1_i`, `h2_i`)
       with using the public params
    to break the KGC
        (factor N = (zp + 1)(2q + 1) and get equivalent master keys `s1`, `s2` in Z_zq)
    '''
 
    sh = remote('0.0.0.0', 12345)
 
    temp = sh.recvline(keepends=False).decode().split(' ')
    suffix, digest = temp[0][-17:-1], temp[-1]
    sh.sendline(proof_of_work(suffix, digest))
 
    sh.sendline('P')
    sh.recvuntil(b'the KGC: ')
    temp = sh.recvline(keepends=False).decode().split(', ')
    N = int(temp[0])
 
    sh.sendline('I')
    sh.recvuntil(b'message ')
    temp = sh.recvline(keepends=False).decode().split(' sent by ')
    username = temp[-1][:-3]
    temp = temp[0].split(', ')
    c1, c2 = int(temp[0][1:]), int(temp[1][:-1])
 
    uu = []
    limit_num = 5
    while len(uu) < limit_num:
        random_username = str(getRandomNBitInteger(20))
        sh.sendline('R')
        sh.recvuntil(b'Input your name: ')
        sh.sendline(random_username)
        temp = sh.recvline()
        if b'Registration Not Allowed!' in temp:
            continue
        sh.recvuntil(b' = ')
        temp = sh.recvline(keepends=False).decode().split(', ')
        e, d, h1, h2 = int(temp[0][1:]), int(temp[1]), int(temp[2]), int(temp[3][:-1])
        uu.append((e, d, h1, h2))
 
    u = [user(uu[i]) for i in range(limit_num)]
    ab = []
 
    def calc(u1, u2):
        a = u1.d * u1.h1 - u2.d * u2.h1
        b = u1.d * u1.h2 - u2.d * u2.h2
        return (a, b)
 
    for i in range(limit_num):
        for j in range(i + 1, limit_num):
            ab.append(calc(u[i], u[j]))
 
    target = ab[0][0] * ab[1][1] - ab[0][1] * ab[1][0]
 
    for i in range(limit_num):
        for j in range(i + 1, limit_num):
            a1, b1 = ab[i]
            a2, b2 = ab[j]
            target = gcd(a1 * b2 - a2 * b1, target)
 
    app = N // target // 2
    qq, zz = 1, 1
    for pp in range(app, app + 2):
        try:
            aa, bb, cc = 2, 1 + 2 * pp * target - N, pp * target
            qq = (-bb + isqrt(bb ** 2 - 4 * aa * cc)) // (2 * aa)
            if target % qq > 0:
                qq = (-bb - isqrt(bb ** 2 - 4 * aa * cc)) // (2 * aa)
            zz = target // qq
            NN = (zz * pp + 1) * (2 * qq + 1)
            if NN == N:
                break
        except:
            continue
 
    s1_, s2_ = 1, 1
    for i in range(limit_num):
        for j in range(i + 1, limit_num):
            try:
                y11, y12 = u[i].h1 * invert(pp, zz * qq) % (zz * qq), u[i].h2 * invert(pp, zz * qq) % (zz * qq)
                y21, y22 = u[j].h1 * invert(pp, zz * qq) % (zz * qq), u[j].h2 * invert(pp, zz * qq) % (zz * qq)
                ys_1 = invert(u[i].d, zz * qq)
                ys_2 = invert(u[j].d, zz * qq)
                s2_ = invert(y21 * y12 - y11 * y22, zz * qq) * (y21 * ys_1 - y11 * ys_2) % (zz * qq)
                s1_ = invert(y11, zz * qq) * (ys_1 - y12 * s2_) % (zz * qq)
                break
            except:
                pass
 
    print("[+]The KGC is broken.")
    print("[+]Parameters are as follows:")
    print("N = {}\np = {}\nq = {}\nz = {}\ns1_ = {}\ns2_ = {}".format(N, pp, qq, zz, s1_, s2_))
    h1 = int(hashlib.sha256(username.encode()).hexdigest(), 16)
    h2 = int(hashlib.sha512(username.encode()).hexdigest(), 16)
    y1 = invert(pp, zz * qq) * h1 % (zz * qq)
    y2 = invert(pp, zz * qq) * h2 % (zz * qq)
    dd = invert(y1 * s1_ + y2 * s2_, zz * qq)
    F = pow(c2, dd, N)
    h3 = int(hashlib.md5(str(F).encode()).hexdigest(), 16)
    m = hex(h3 ^ c1)[2:]
 
    sh.sendline('G')
    sh.sendline(m)
 
    print(sh.recvline())
 
 
if __name__ == "__main__":
    attack()

ocococb

由于nonce可复用,利用前两次加密获取E(nonce),然后用第三次加密获取到所有我们需要的E(message),接着利用unpad的漏洞对secret进行爆破,最后提交即可获得flag。exp如下:

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
from base64 import *
from Crypto.Util.number import *
from gmpy2 import *
from pwn import *
import math
 
table = '1234567890qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM'
def passpow():
    rev = r.recvuntil("sha256(XXXX+")
    suffix = r.recv(16).decode()
    r.recvuntil(" == ")
    res = r.recv(64).decode()
    def f(x):
        hashresult = hashlib.sha256((x+suffix).encode()).hexdigest()
        if hashresult == res:
            return 1
        else:
            return 0
    prefix = util.iters.mbruteforce(f,table,4,'upto')
    r.recvuntil("XXXX: ")
    r.sendline(str(prefix))
 
def times2(input_data,blocksize = 16):
    assert len(input_data) == blocksize
    output =  bytearray(blocksize)
    carry = input_data[0] >> 7
    for i in range(len(input_data) - 1):
        output[i] = ((input_data[i] << 1) | (input_data[i + 1] >> 7)) % 256
    output[-1] = ((input_data[-1] << 1) ^ (carry * 0x87)) % 256
    assert len(output) == blocksize
    return output
 
def times3(input_data):
    assert len(input_data) == 16
    output = times2(input_data)
    output = xor_block(output, input_data)
    assert len(output) == 16
    return output
 
def back_times2(output_data,blocksize = 16):
    assert len(output_data) == blocksize
    input_data =  bytearray(blocksize)
    carry = output_data[-1] & 1
    for i in range(len(output_data) - 1,0,-1):
        input_data[i] = (output_data[i] >> 1) | ((output_data[i-1] % 2) << 7)
    input_data[0] = (carry << 7) | (output_data[0] >> 1)
    if(carry):
        input_data[-1] = ((output_data[-1] ^ (carry * 0x87)) >> 1) | ((output_data[-2] % 2) << 7)
    assert len(input_data) == blocksize
    return input_data
 
def xor_block(input1, input2):
    assert len(input1) == len(input2)
    output = bytearray()
    for i in range(len(input1)):
        output.append(input1[i] ^ input2[i])
    return output
 
def hex_to_bytes(input):
    return bytearray(long_to_bytes(int(input,16)))
 
def my_pmac(header, offset, blocksize = 16):
    assert len(header)
    header = bytearray(header)
    m = int(max(1, math.ceil(len(header) / float(blocksize))))
    # offset = Arbitrary_encrypt(bytearray([0] * blocksize))
    offset = times3(offset)
    offset = times3(offset)
    checksum = bytearray(blocksize)
    offset = times2(offset)
    H_m = header[((m - 1) * blocksize):]
    assert len(H_m) <= blocksize
    if len(H_m) == blocksize:
        offset = times3(offset)
        checksum = xor_block(checksum, H_m)
    else:
        H_m.append(int('10000000', 2))
        while len(H_m) < blocksize:
            H_m.append(0)
        assert len(H_m) == blocksize
        checksum = xor_block(checksum, H_m)
        offset = times3(offset)
        offset = times3(offset)
    final_xor = xor_block(offset, checksum)
    # auth = Arbitrary_encrypt(final_xor)
    # return auth
    return final_xor
 
r=remote("1.13.189.168","32086")
 
def talk1(nonce, message):
    r.recvuntil("[-] ")
    r.sendline("1")
    r.recvuntil("[-] ")
    r.sendline(b64encode(nonce))
    r.recvuntil("[-] ")
    r.sendline(b64encode(message))
    r.recvuntil("ciphertext: ")
    ciphertext = b64decode(r.recvline(False).strip())
    r.recvuntil("tag: ")
    tag = b64decode(r.recvline(False).strip())
    return ciphertext, tag
 
def talk2(nonce, cipher, tag):
    r.recvuntil("[-] ")
    r.sendline("2")
    r.recvuntil("[-] ")
    r.sendline(b64encode(nonce))
    r.recvuntil("[-] ")
    r.sendline(b64encode(cipher))
    r.recvuntil("[-] ")
    r.sendline(b64encode(tag))
    r.recvuntil("plaintext: ")
    message = b64decode(r.recvline(False).strip())
    return message
 
context(log_level='debug')
passpow()
 
finalnonce = b'\x00'*16
m1 = b"\x00"*15 + b"\x80"
m2 = b"\x10"*16
cipher1, finaltag = talk1(finalnonce,m1)
cipher2, _ = talk1(finalnonce,b'')
cipher2 = xor_block(m2,cipher2)
E1 = back_times2(xor_block(cipher1[:16],cipher2))
assert back_times2(times2(E1))
# E1 = E(finalnonce)
print(E1)
 
def get_enc(message, offest):
    cnt = 0
    finalmessage = b''
    for i in message:
        cnt += 1
        E = offest
        for _ in range(cnt):
            E = times2(E)
        # print(cnt)
        finalmessage += xor_block(i,E)
    # print(finalmessage)
    data, tag = talk1(finalnonce,finalmessage)
    cipher = []
    cnt = 0
    for i in range(0,len(data),16):
        cnt += 1
        E = offest
        for _ in range(cnt):
            E = times2(E)
        # print(cnt)
        cipher.append(xor_block(data[i:i+16],E))
    return cipher[:-1]
 
xor1 = my_pmac(b'from baby',E1)
xor2 = my_pmac(b"from admin",E1)
 
xor_all = xor_block(m1,m2)
message = [xor1,xor2,xor_block(times2(times2(times2(E1))),m1)]
for i in range(16,32):
    print(b'\x10'*15+long_to_bytes(i))
    message.append(xor_block(times2(E1),(xor_block(xor_all,bytearray(b'\x10'*15+long_to_bytes(i))))))
# message = [xor1,xor2]
source_cipher = (get_enc(message,E1))
print(source_cipher)
finaltag = xor_block(finaltag,xor_block(source_cipher[0],source_cipher[1]))
source_cipher = source_cipher[2:]
 
# print(cipher1[32:])
secret = b''
for i in range(1,len(source_cipher)):
    finalcipher = xor_block(source_cipher[i],times2(E1)) + \
                  cipher1[16:32] + \
                  xor_block(source_cipher[0],bytearray(b'\x10'*15+long_to_bytes(15+i)))
    secret += (talk2(finalnonce,finalcipher,finaltag))
secret = secret[::-1]
print(secret)
 
r.recvuntil("[-] ")
r.sendline("3")
r.recvuntil("[-] ")
r.sendline(b64encode(secret))
r.recvuntil("flag: ")
flag = r.recvline(False)
print(flag)
# context(log_level='debug')
# r.interactive()
r.close()

[招生]科锐逆向工程师培训46期预科班将于 2023年02月09日 正式开班

收藏
点赞0
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回