writeup for 2021 WMCTF

Posted on Edited on In Word count in article: 15k Reading time ≈ 14 mins.

比赛那天刚好返校, 没怎么打, 复盘一下

checkin

猜谜一样… 直到是背包问题也不知道具体该做什么….

挂着先

baby_OCB

红明古, 下次一定学会咕咕咕咕咕

easylsb

problem

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
#!/usr/bin/python3
# encoding: utf-8
import random
import string
import sys
import os
from hashlib import sha256
import uuid
from Crypto.Util.number import *

password = b'Hidden'
flag = ('flag{' + str(uuid.uuid4()) + '}').encode()

# def proof_of_work():
#     random.seed(os.urandom(8))
#     proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)]).encode()
#     digest = sha256(proof).hexdigest()
#     printf("sha256(XXXX+%s) == %s" % (proof[4:].decode(),digest))
#     printf('Give me XXXX:')
#     x = read_str()
#     if len(x) != 4 or sha256(x.encode()+proof[4:]).hexdigest() != digest: 
#         return False
#     return True

def printf(message):
    sys.stdout.write('{0}\n'.format(message))
    sys.stdout.flush()
    sys.stderr.flush()

def read_str():
    return sys.stdin.readline().strip()

def read_int():
    return int(sys.stdin.readline().strip())

def next_prime(a):
    while not isPrime(a):
        a += 2
    return a

def get_prime(a):
    suffix = getPrime(368)
    return next_prime(a ** 2 + suffix + 1)

def generate_pubkey(key):
    p, q = get_prime(getPrime(512)), get_prime(key)
    n = p * q
    return n

def airdrop(a):
    n = generate_pubkey(a)
    printf('gift: {}'.format(n))
    return

def hint(n, e, c):
    printf('n = {}'.format(n))
    printf('e = {}'.format(e))
    printf('c = {}'.format(c))
    return

def leak():
    p = get_prime(getPrime(512))
    e = 0x1000
    c = pow(bytes_to_long(flag), e, p)
    
    hint(p, e, c)
    return

def backdoor():
    printf('Input your password:')
    user_input = read_str()
    if user_input.encode() == password:
        leak()
    else:
        printf('Wrong')
        exit(0)

if __name__ == '__main__':
    # if not proof_of_work():
    #     exit(0)
    
    a = getPrime(512)
    print(a)
    p = get_prime(a)
    q = get_prime(getPrime(512))
    n = p * q
    e = 0x10001
    max_time = 5
    password_enc = pow(bytes_to_long(password), e, n)
    
    printf('====================================',)
    printf('1. Airdrop                          ',)
    printf('2. Backdoor                         ',)
    printf('3. Hint                             ',)
    printf('4. Exit                             ',)
    printf('====================================',)
    
    try:
        while True:
            printf('Your choice:')
            choice = read_int()
            if choice == 1:
                if max_time > 1:
                    airdrop(a)
                    max_time -= 1
                    printf('Done!')
                else:
                    printf('Greed will destroy you!')
                continue
            elif choice == 2:
                backdoor()
                printf('Done!')
                continue
            elif choice == 3:
                hint(n, e, password_enc)
                printf('Done!')
                continue
            elif choice == 4:
                printf('bye~')
                exit(0)
                continue
            else:
                printf('Invalid!')
                continue
    except:
        exit(-1)

要得到flag 必须通过leak() 而要调用leak()必须知道password

看一下airdrop()函数

choice 1每次调用都会给一个gift 也就是

The Approximate GCD Problem

之前的比赛也有遇到过, 这次认真的再看看

这里是个问题, 所谓的就是近似值

比如现在有

这个就是一般的问题,而呢就是给这里的每个都加上一个

那这样要求出就不能用之前的算法了. 为了解决这个问题可以把这两行合成一下

像这种形式的一看就可以写到一个格子里面去

右边的向量的范数跟是有关的, 而是可以调整的, 所以理论上只要右边的几个参数够小, 我们是有机会找到这个向量从而求出, 求出就能解决问题了.

现在回到题目. 现在有五行式子

其实这里我一拿到这五行就开始构造格子做了, 但dbt👴提醒了我, 问题右边参数越小越好, 考虑一下开方, 因为问题本身就是一个近似值求解GCD的问题. 所以我们在做的过程中也做点近似一般是不会影响的(?有爷爷研究过近似的一个度吗

让右边的式子更小之后, 用五组数据构造格子

规约之后能找到向量(后面的不重要就先不写了)

但在规约的时候, 因为范数的问题, 需要不断的调整的值才能找我们需要的那个向量, 调整的依据就是这个的大小, 这个大小是知道的,所以最后得到的应该是

事实上, 在我看到的blog里面, 这个R的取值是有一定的方法的, 没有搞懂具体该怎么去判断, 所以只能通过调整的方法来做这题了,

想起来自己的博客之前也有试过去推一个大概的值, 可以翻前面的看看

所以现在只需要不断的调整的大小, 直到找出一个的真正的 ,有了就能求出了,

解出剩下的就是已知高位了

做这题的时候发现如果只用四组数据, 不管怎么的调整, 也没有办法找出想要的那个向量出来, 不知道是不是因为参数的大小, 四组数据给出的约束不够强?

解完AGCD之后就能拿到一个加密的flag, e和phi不互素, 发现e是, 直接开12次平方根就行了

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
import sys

sys.path.append("/home/k1rit0/CTF/")
import myCrypto.AMM as AMM

from sage.all import *

from Crypto.Util.number import inverse, isPrime, long_to_bytes

LAM = 380
l = 5
M = [[0 for _ in range(l)] for _ in range(l)]
N = [21068286322889605292449387381402285403911455560141090214735354974440606624419616964297007580321013791067226167439872996226832500580037706653803152998537359002847432836899418650117306549893607343160006144352760334920785866221130409904894118963374929467323935674617670738402419178327965359202178162667267351040190371168301980935481660326630257816016921697149710082155701629870160350348818834688225753303057415885022226024601907498521621901308603324694768684738802528845831936410741399435491742825201984427922436831471812070309418640813794622730842698875782093607446798284303784522710493344963880678737688403891400189331,     
12308853561607841041934092506744511689155586116240481655471529969953855274038227343811431655989608434591583673694139060863738492861944511267544267389946989849658784130545243679913412818685768313761630659910263680193434985838781131523993553907838129189461461476296694554655782825701774629683350764866069156868009043211117580921049441277102377562595106269789041165210135844474567428536421792003953066707002965308982249630472773112238349557943156998108879517471317999283500584387777397105486037127797366322210846034599129011995028171723686883387966414035624689126402104807914499946793228044511016295452985310557970379011,     
30738697791225132085580847654714047571186902668616746842899304102159584623469816318757206927486219023390491315148910896488732403322767246394501024688827804510369382155878820868892068583525039291929122306306627213766241320525799308714371006850194133645674073652842238370607838910482032953868627367283394607836966578300168303793400060582848922857236410576441317474208136497407564188049755626445760675555940268390636610085726624705570165069943427799504990418468772678900305743541682004982830947893963522764021022122922104982911181491725457610355492465006313490505471915305370861395875195908816803244772843442663436627811,     
8305502698327938163061403448570905343510072391121488812862051390404395134941843998819543534972233651342461635174480345500578515464031763529097882752145582280163441217012244252516496790390759043249994221367357315376275069348967721415258505344163223181510037360702185803627278919587509933485368201596116686196256578251198487468448008040978019816660838136301253757474040665970837583661727365857243232757366302995923446406792674664094421560455977644181219681801233665490911903627509944363786700632306093740157219837713108792604909612708233475959478546962262259340699913418281265092058666045625836471989209312154073075491,      
9249057556737779363640590847304104073427145700484200097209450631890326978899167760679154628208658960714377959140386507599020762987984595928908203986925752986701463694818100098371494812801057184146507393471109418242580315774651644212154315684690259768215107765517606521494940441845123991021958309973443907208341450704221754039776849253367952771456447007511355415631917532484344389697848200615413029231558971975377100287746424454815515972611696776506127916905426006223842544245270081659891304287086426791583147370534686626291189249685625856952980692492700851557019098598454447260906380261199261945010423393013023715209 ]



for i in range(l):
    N[i] = int(sqrt(N[i]))


for i in range(1,l):
    M[i][i] = -N[0]
    M[0][i] = N[i]
M[0][0] = 2 ** LAM
L = Matrix(M).LLL()[0]
assert L[0] % 2 ** LAM == 0

q = abs(L[0] // 2 ** LAM)
n = N[0]
a = (n - (n % q)) // q
# Know high bit of p
n = 9249057556737779363640590847304104073427145700484200097209450631890326978899167760679154628208658960714377959140386507599020762987984595928908203986925752986701463694818100098371494812801057184146507393471109418242580315774651644212154315684690259768215107765517606521494940441845123991021958309973443907208341450704221754039776849253367952771456447007511355415631917532484344389697848200615413029231558971975377100287746424454815515972611696776506127916905426006223842544245270081659891304287086426791583147370534686626291189249685625856952980692492700851557019098598454447260906380261199261945010423393013023715209        
e = 65537
c = 596355871374007258796739088580480254690421307398563449520929804224579804032978250178898982384142847223103176953609592214108362545413436815340326688408982175941755069859344738153840235542651636279657627294019566968304679361239665444560606473133283058393087609946086549065553264454684624204753050326115020520403436076532095607286695957435489522985881581820635688415133423515447960953517405315231071959346343447601273197470177184887138457495799503680274625485150493280857586565387473867813858817367137470006514777542969192548145776362722942018998084778630461770023286812913356191141099060132770816764636107436181833654

_p = a**2 
R = PolynomialRing(Zmod(n),'x')
x = R.gens()[0]
f = _p + x
roots = f.small_roots(X=2 ** 368,beta = 0.4)
if roots:
    p = _p + int(roots[0])
    print(p)
assert n % p == 0
q = n // p
phi = (p-1) * (q-1)
d = inverse_mod(e,phi)
print(long_to_bytes(pow(c,d,n)))


p = 117235409029105051846806067899523247170361728684595002856792997268214583527481018331523314373480172502868245719103537926811678162691190783273715963938227870577908696266175564889962816950193051688136250287087726752359306820791879258724210723175953346754995614733931375012961016374642411090783817788045807125779 
e = 4096
c = 9565562547953889050875342796317230683573917021053842636334550812905648260474828549598393988661413478381057558054348342995403993026447829846151651076469025927491897151314215230367392957203050021568190862146104714972731651005427897872753163387978990574633850084765886249824258759820964357075803586150088309646   

R = PolynomialRing(Zmod(p),'x')
R1 = [c]
R2 = []
for _ in range(12):
    for r in R1:
        x = R.gens()[0]
        f = x ^ 2 - r 
        roots = f.roots()
        if roots:
            for root in roots:
                R2.append(root[0])
    R1 = R2
    R2 = []
    print(R1)
for m in R1:
    print(long_to_bytes(m))

ezl1near

problem

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
from Crypto.Util.number import long_to_bytes , bytes_to_long , getPrime , inverse
from Crypto.Cipher import AES
import socketserver , signal
import random
import string
from hashlib import sha256
import os
flag = 'aaaaaaaaaaaaaaaa'
q = 2**24

def getrandbits(n):
    return bytes_to_long(os.urandom(n // 8+1)) >> (8-n%8)

class server(socketserver.BaseRequestHandler):
    

    def _recv(self):
        data = self.request.recv(1024)
        return data.strip()

    def _send(self, msg, newline=True):
        if isinstance(msg , bytes):
            msg += b'\n'
        else:
            msg += '\n'
            msg = msg.encode()
        self.request.sendall(msg)

    def proof_of_work(self):
        random.seed(os.urandom(8))
        proof = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(20)])
        _hexdigest = sha256(proof.encode()).hexdigest()
        self._send(f"sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
        self._send(b'Give me XXXX: ')
        x = self._recv()
        if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
            self.send('wrong')
            return False
        return True

    def genrsa(self):
        _p = getPrime(1024)
        _q = getPrime(1024)
        self.n = _p * _q
        self.e = 65537
        self.d = inverse(self.e , (_p-1)*(_q-1))

    def to_vec(self,num , length):
        vec = []
        while length > 0:
            vec = [num % q] + vec
            num //= q
            length -= 1
        return vec

    def to_mat(self,numlist):
        M =[]
        for i in numlist:
            M.append(self.to_vec(i , 40))
        return M

    def enc(self, key , m):
        key = self.to_mat(key)  
        res = []
        for i in range(40):
            temp = 0
            for j in range(16):
                temp += m[j]* key[j][i]
                temp %= q
            res.append(temp)
        return res
    def handle(self):
        # signal.alarm(120)
        # self.proof_of_work()
        self.genrsa()
        self._send(str(self.n))
        self._send(str(self.e))
        secret = [1] + [2*getrandbits(23)-1 for _ in range(15)]
        print(secret)
        self._send(b'Please generate key for me and I will give you my secret.But you have only two chances.')
        for i in range(2):
            key = []
            f0 = getrandbits(480)
            print(f0)
            key.append(f0)
            self._send(str(pow(f0 , self.e , self.n)))
            f0 += f0 << 480
            for j in range(15):
                self._send('key'+str(i+1) + ':')
                c = int(self._recv())
                m = pow(c , self.d , self.n)
                f = m - f0
                f %= self.n
                key.append(f)
            c = self.enc(key , secret)
            self._send('Thanks, here is your cipher:' + str(c))
        self._send(b'do you know the secret?')
        guess = [int(i) for i in self._recv().split(b' ')]
        if len(guess) == 16:
            for j in range(16):
                if guess[j] != secret[j]:
                    break
            else:
            
                self._send(b'congratulations. here is your flag:')
                self._send(flag)
                return 0
        else:
            self._send(b'L1near don\'t care.')
        

class ForkedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass

if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10000
    server = ForkedServer((HOST, PORT), server)
    server.allow_reuse_address = True
    server.serve_forever()

流程有点长, 大概就是随机生成一个向量, 我们的目标就是得到这个

一开始他会生成一个, 并通过RSA加密然后给我们密文

中间他会让我们输入15个, 但是这十五个不是直接咱们输入什么就是什么的, 他会经过一个RSA的解密

最后加上我们输入的15个一起生成一个的矩阵(一个key就生成一行)

然后计算密文

这里密文我们是知道的, 我们只需要弄到就能得到了

而这里除了第一行, 都是我们自己构造的, 但是比较难控制,因为实际上的key和我们传过去差一个解密, 但是我们有一个的密文, 我们可以利用RSA的乘法同态就构造, 这个想是多少就是多少.

而且观察的生成, 我们发现只要得到第一行的所有数, 我们就能还原回, 因为的第一个固定是1, 而的第一行只有后面20个才有数字, 前面的20个都是0, 所以我们只要让后面的20列除了第一行都是0就可以得到了. 而且, 我们可以传, 让的后面几行的生成就是第一行的数字往前推i个, 所以我们让就能推到刚好只有第一行的后面列是有数字的.

那么大概的思路有了, 构造, 1. 必须得可逆, 才能求. 2. 后面20列是0
$$
(1,s_0,s_1,\cdots,s_{13},s_{14})
\begin{pmatrix}
0&0&\cdots&0&a_0&a_1&\cdots&a_{19} \
k_{1,0}&k_{1,1}&\cdots&k_{1,19}&0&0&\cdots&0 \
&&&\cdots \
k_{15,0}&k_{15,1}&\cdots&k_{15,19}&0&0&\cdots&0

\end{pmatrix}
\
=(c_0,c_1,\cdots,c_{19},a_0,a_1,\cdots,a_{19})
$$
我们需要这个可逆, 就是要满秩, 就每次传的时候再加一个随机的系数就行了, 也就是传

构造出了上面这个, 就能利用还原, 再用生成整个, 最后求个算回即可

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
from sage.all import *
import re
import pwn
import random
q = 2**24

def shiftf0(enc_f0,i):
    a = 2 ** 480 + 1 +  (i+1) * q**20
    return ((enc_f0 * pow(a,e,n)) % n)

def to_vec(num , length):
    vec = []
    while length > 0:
        vec = [num % q] + vec
        num //= q
        length -= 1
    return vec

def to_mat(numlist):
    M =[]
    for i in numlist:
        M.append(to_vec(i , 40))
    return M


CON = pwn.remote('172.27.176.1',10000)
resp = CON.recvuntil('key1:\n').decode().split('\n')
n = int(resp[0])
e = 65537
enc = int(resp[3])
for _ in range(14):
    CON.sendline(str(shiftf0(enc,_)).encode())
    resp = CON.recvuntil('key1:\n').decode()
    print(_,resp)
CON.sendline(str(shiftf0(enc,_+1)).encode())
resp = CON.recvuntil('key2:\n').decode().split('\n')


_res = resp[0][29:-1].split(',')
res =[]
for i in _res:
    res += [int(i)]
f0 = 0
for i in res[-20:]:
    f0 += i
    f0 = f0 << 24
f0 = f0 >> 24
key = [f0]+ [((i+1)* q**20  * f0 ) % n for i in range(15)]
M = matrix(Zmod(q),to_mat(key))
print(M.solve_left(vector(res)))