Contents

WMCTF 2021

–>

Baby_OCB

想多了,比想象中简单。。。

加密模式为AES.OCB,服务器提供加密和解密功能,

$D(),E()表示aes内部的aes.encrypt,aes.decrypt$

Get flag获取A为

PMAC

是一种处理author的函数,其输出结果只与内部 aes 和 header 参数有关

encrypt

前置:$checksum=\bigoplus^n_{i=1}m_i$

AES.OCB加密函数,对于除去最后一块的前面所有明文块,其满足

$c_i=2_i⋅E(nonce)⨁E(2_i⋅E(nonce)⨁m_i)$

而对与最后一块,其满足

$c_n=m_n⨁E(2_n⋅E(nonce)⨁len(0^n))$

而加密时的 tag 与其他参数,满足

$tag=E(3\cdot 2^n\cdot E(nonce)\bigoplus checksum)$

decrypt

decrypt AES.OCB解密函数,对于除去最后一块的前面所有明文块,其满足

$m_i=D(c_i⨁2^i⋅E(nonce))⨁2^i⋅E(nonce)$

而对与最后一块,其满足

$m_n=c_n⨁E(2^n⋅E(nonce)⨁len(0^n))$

解密时的 checktag 与其他参数,满足

$checksum=\bigoplus^n_{i=1}m_i$

$checktag=E(3⋅2^n⋅E(nonce)⨁checksum)$

同样的,如果 header>0

则新的 $checktag=checktag⨁header$

implement

这里我们这样构造

$m1=len(0n)=15×b′\x00′+b′\x80′ m2=0=16×b′\x00′$

那么 m1 会被当作非最后一块加密

$c1=2⋅E(nonce)⨁E(2⋅E(nonce)⨁m1)$

$c2=m2⨁E(4⋅E(nonce)⨁len(0n)) =E(4⋅E(nonce)⨁len(0n))$

随后调用解密函数时只提交 c1 ,此时会被当作最后一块解密,那么我们会发现

$m1=c1⨁E(2⋅E(nonce)⨁m1) =2⋅E(nonce)⨁E(2⋅E(nonce)⨁len(0n))⨁E(2⋅E(nonce)⨁m1)$

而我们构造的 m1=len(0n) ,那么显然 m1=2⋅E(nonce) ,此时,我们就能够轻松算出 $E(nonce)$ !

但因为AES.OCB的认证特殊性,我们需要使得伪造 tag 来通过认证检测,这里我们选择令 header 为空,那么此时的

$checktag=E(6⋅E(nonce)⨁2⋅E(nonce)) =E(4⋅E(nonce))$

如何能得到这个玩意呢?

当我们再次稍微变化一下 $c1=c1⨁m1$ 后,我们发现此时

$checktag=E(m1⨁6⋅E(nonce)⨁2⋅E(nonce)) =E(m1⨁4⋅E(nonce))=c2$

也就是说,我们给在线 decrypt 函数提供的数据分别为: nonce 为加密时的 nonce , tag 为 c2 , c=c1 , header 为空,这样就能够成功通过客户端的认证检查,并且得到

$2⋅E(nonce) $,对 times2 函数写个逆即可求得$ E(nonce)$

此时,我们即可对于任意的 nonce ,都能得到其对应的 $E(nonce)$ ,但是对于任意的明文 m ,并不能自如的完成任意加密,那么我们现在相当于已经有了 nonce 与其对应的 E(nonce) ,如何来完成任意加密的效果呢?

这里我们为了便于解释,我们记 $L=E(nonce)$ 、

$L′=E(2⋅L⨁m1) $

那么可以轻松算得

$L′=c1⨁2⋅L $

我们再次使用客户端的 encrypt 函数,但这次我们的

$nonce=2⋅L⨁m1 $,

$m=message⨁2⋅L^′ $

那么

$c=2⋅L′⨁E(message⨁2⋅L^′⨁2⋅L^′)$ ,我们就能轻松算出

$E(message)=c⨁2⋅L^′$

我们将前面所有的过程看作一个函数,即使用一个 nonce 名额,来得到我想要的 aes.encrypt(message) ,那么此时所有的加密过程都可以在本地完成,直接在本地计算题目所需要的 cipher 与 tag ,直接打给服务器即可

  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
from pwn import *
from Crypto.Util.number import *
from hashlib import sha256
import string
from pwnlib.util.iters import mbruteforce
import base64
#context.log_level = 'debug'

xor = lambda s1 , s2 : bytes([x1^x2 for x1,x2 in zip(s1,s2)])
table = string.ascii_letters+string.digits

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)
    # print(carry)
    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 pow():
    io.recvuntil(b"XXXX+")
    suffix = io.recv(16).decode("utf8")
    io.recvuntil(b"== ")
    cipher = io.recvline().strip().decode("utf8")
    proof = mbruteforce(lambda x: sha256((x + suffix).encode()).hexdigest() ==
                        cipher, table, length=4, method='fixed')
    io.sendline(proof.encode()) 

def get_FLAG_data():
    io.recv()
    io.sendline(b'3')
    io.recvuntil(b'ciphertext: ')
    ciphertext = base64.b64decode(io.recvline()[:-1])
    io.recvuntil(b'tag: ')
    tag = base64.b64decode(io.recvline()[:-1])
    nonce = b'\x00'*16
    associate_data = b'from admin'
    return ciphertext,tag,nonce,associate_data

def Server_Enc(msg,nonce):
    io.recv()
    io.sendline(b'1')
    io.recv()
    io.sendline(base64.b64encode(nonce))
    io.recv()
    io.sendline(base64.b64encode(msg))

    associate_data = b'from baby'
    io.recvuntil(b'ciphertext: ')
    ciphertext = base64.b64decode(io.recvline()[:-1])
    io.recvuntil(b'tag: ')
    tag = base64.b64decode(io.recvline()[:-1])

    return ciphertext,tag

def Server_Dec(nonce,cip,tag,associate_data):
    io.recv()
    io.sendline(b'2')
    io.recv()
    io.sendline(base64.b64encode(nonce))
    io.recv()
    io.sendline(base64.b64encode(cip))
    io.recv()
    io.sendline(base64.b64encode(tag))
    io.recv()
    io.sendline(base64.b64encode(associate_data))
    io.recvuntil(b'plaintext: ')
    plaintext = base64.b64decode(io.recvline()[:-1])
    return plaintext

def get_my_enc(msg):
    nonce = bytearray(os.urandom(16))
    fake_m = bytearray(b'\x00'*15+b'\x80'+b'\x00'*16)
    cip,tag = Server_Enc(fake_m,nonce)
    m0 = bytearray(b'\x00'*15+b'\x80')
    m1 = bytearray(b'\x00'*16)

    c0 = cip[:16]
    c1 = cip[16:]

    enc = xor_block(Server_Dec(nonce,xor_block(c0,m0),c1,b""),m0)
    A = back_times2(enc)
    B = enc
    C = xor_block(B,c0)

    msg = msg
    new_nonce = xor_block(B,m0)
    new_msg = xor_block(msg,times2(C)) + m1
    new_msg = (bytes(new_msg))
    ENC,TAG = Server_Enc(new_msg,new_nonce)
    
    #io.interactive()
    return xor_block(ENC[:16],times2(C))

def my_pmac(header, blocksize = 16):
    assert len(header)
    m = int(max(1, math.ceil(len(header) / float(blocksize))))
    offset = get_my_enc(bytearray([0] * blocksize))
    offset = times3(offset)
    offset = times3(offset)
    checksum = bytearray(blocksize)
    for i in range(m - 1):
        offset = times2(offset)
        H_i = header[(i * blocksize):(i * blocksize) + blocksize]
        assert len(H_i) == blocksize
        xoffset = xor_block(H_i, offset)
        encrypted = get_my_enc(xoffset)
        checksum = xor_block(checksum, encrypted)
    offset = times2(offset)
    H_m = header[((m - 1) * blocksize):]
    print(H_m)
    assert len(H_m) <= blocksize
    if len(H_m) == blocksize:
        offset = times3(offset)
        checksum = xor_block(checksum, H_m)
    else:
        H_m = H_m + b'\x80'
        while len(H_m) < blocksize:
            H_m += b'\x00'
        assert len(H_m) == blocksize
        checksum = xor_block(checksum, H_m)
        offset = times3(offset)
        offset = times3(offset)
    final_xor = xor_block(offset, checksum)
    auth = get_my_enc(final_xor)
    return auth

if __name__ == "__main__":
    # io = remote("47.104.243.99",10001)
    io = remote("0.0.0.0",10002)
    pow()
    F_ciphertext,F_tag,F_nonce,F_associate_data = get_FLAG_data()

    print(len(F_ciphertext))
    FROMADMIN = my_pmac(b'from admin')
    print(FROMADMIN)
    FROMBABY = my_pmac(b'from baby')
    print(FROMBABY)
    F_associate_data = b'from baby'
    F_tag = xor_block(xor_block(F_tag, FROMADMIN),FROMBABY)

    print(Server_Dec(F_nonce,F_ciphertext,F_tag,F_associate_data))
    io.interactive()

同类型

ezlsb

analysis

核心点是找到passwd访问Backdoor,

再访问Leak给你 p,e,flag_enc 约等于getflag了

Main:

$$ \begin{aligned} a=getPrime(512) \\
p =a^2+sx_1+2k_1+1\\
q = b^2 + sx_2+2k_2+1\\
n=pq\\
e=65537\\
pass_enc = pass^e\mod n\\
\end{aligned} $$

👴推到这里就寄了


lookback

主要任务:4 次 Airdrop 的机会 分解 n,可以将n和gitfs写为一个加强版AGCD问题

$$ \begin{aligned} gift_1 =q_1a^2+q_1r_1\\
gift_2 =q_2a^2+q_2r_2\\
gift_3 =q_3a^2+q_3r_3\\
gift_4 =q_4a^2+q_4r_4 \end{aligned} $$

$n=qa^2+qr$

对n和gifts开方可以得到AGCD的适用的条件范围

用格子规约一下可以得到a的值

然后用copper co一下就拿到pq了

然后解出passwd去拿leak

solve

 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
from Crypto.Util.number import *

n = 47935439323457127833037357083983237496878689261127081988649381912739468031720632155196797632254382181519984640185516509133478757768213513987941266551218952702606511178276633908546681835137035411034761316782876147359960487121213984853077540707588650724919247893999205747065241005931759522778403309142776013266993947909627871209547322186129461944966954255478452004126991923307040855781751576009560486080068518925411003611155913186594087392942825850544717133800805624006483035224985413873703244911627183839595554490748948155205230203576672211733145725061218786720271669259766573150046403742640731305478008090581342450251
c = 3919344937892382453030977567508693676032303846339768189327551099374946365060960690768609451174592443590215485748150561581950399880588830921746078740240411900651523182948715415984890388869890625266181130509341855855926592096861408547012789662424413990132921065901887989126066338526922430576216968899218768929718135909294604392991675565238263427980279809833873727879908414057057251514599614783087363407160259495649433827508201133578753184878878951808963235285802411560617758684149245785926009513999665737813112781227632184408328506347530201548662504337685327938279816153782173263392272482010848912768570644687383402740
e = 0x10001
import gmpy2 
gift = [n,44990368188010733918858560274483758890181415269493297111432503547349003225605998615045785893226033910128870030617267155471810954946701223520640922021975809987807505611903409246795611631098996240773157768116757200113829094343552868816290020352831816362796203792491207823175523672191727528508633850619433949770456610363882692306556232795718586073455551690290817146381615597057233415356702398751201147360489923331479498200944380380485186742204102241268627281885440725091810845139220728878887230186802227055200861696153582625239928130166788950797548542788617056657074111819043054568673588056230147076007178129781162831611, 78683096763326373669536693596249569085095290247102968419967840631586829732977219369969300751984289814402998022338838702200385790818392667580904195251832143834204909181557079203022588554330880322720341355019524178584242950915453525665150758590809948785874945747350388081180350115247240154475291948408741761648481087095447887536869026145459137082976669264740463624475908502268200243221926503732189641142315206390638626198685135408561463549566690400552904111413732721731304453362155831880117750312809828284867777234323889613356325170410656020466019958496069321445323099847122674429896323552643458809760407340317926830901, 155378045723411522600696035951116955917841229585849918356678240504530602921920566960136486129553454017727749961462685165377347755302826839915112915642536853507763599097574159709699129520153090998679336513853206496584404340204651266745291554668873684828162763771988162464321539837322058407795741726134977433737336303715635638805865795180826546489644742166424956313290523391862752963123672824271036686045932898668866001588000885565313392223064341062105415322004215058987783863547389257154167383707353247208122517429835580960973747381235079792989510459208038145580319784674535377716228024727145018179341727746440515438603, 145996826337300053358889785500361366816465399568166384938579711772423913668332754495063912415488340254571832698805395656780786821255846897561093531075917438583833034671829076937376980928330090827535202591154261056743308762095398623323354628401868490174767786058940272278982366625466222310654778128867887749716594188776848527274133080300896292575037380431855075174589507467705421620952488239054607980417485378752030675364661643727200369011640293898438494036260460375174641137939853447480714174584002881316581265441151705735968822426191526020807499157273552559963397713746419094028547071420597530907758157846952075538021]
G = []
for i in gift:
    G.append(gmpy2.iroot(i,2)[0])
from sage.all import *

M = Matrix(ZZ,4+1,4+1)
for i in range(4):
    M[i+1,i+1] = -G[0]
for i in range(4):
    M[0,i+1] = G[i+1]

M[0,0] = 2** (368)
P=M.LLL()[0]
P0 = (abs(P[0])//M[0,0])
Q = [P0]
#print((bin(P0)))

for i in range(1,5):
    tmp = ((P[i]-P0*G[i])//G[0])
    Q.append(tmp)
import gmpy2
a = abs(G[0]//Q[0])
print(a)
'''
N = 47935439323457127833037357083983237496878689261127081988649381912739468031720632155196797632254382181519984640185516509133478757768213513987941266551218952702606511178276633908546681835137035411034761316782876147359960487121213984853077540707588650724919247893999205747065241005931759522778403309142776013266993947909627871209547322186129461944966954255478452004126991923307040855781751576009560486080068518925411003611155913186594087392942825850544717133800805624006483035224985413873703244911627183839595554490748948155205230203576672211733145725061218786720271669259766573150046403742640731305478008090581342450251
pbar = 15606058170269190953682935674386408585241503399431015536676436247560293934016890029594865561178385431706188686337043777633715364517948170845087640826845217
ZmodN = Zmod(N)
P.<x> = PolynomialRing(ZmodN)
f = pbar**2 + x
x0 = f.small_roots(X=2^368, beta=0.1,epsilon = 0.01)
p =  pbar + x0[0]
print("p: ", p)
243549051613825768264099803511229671296850562269513049496935511304072171908221622373325530141385783545202972578556352456412692718100967837804917914686772005951461971082613057233161910519390099300130916541889963526259281974154202935031489884213351283127857066122909931059096582655197258061167540446985751813009
'''
p = 243549051613825768264099803511229671296850562269513049496935511304072171908221622373325530141385783545202972578556352456412692718100967837804917914686772005951461971082613057233161910519390099300130916541889963526259281974154202935031489884213351283127857066122909931059096582655197258061167540446985751813009
q = 47935439323457127833037357083983237496878689261127081988649381912739468031720632155196797632254382181519984640185516509133478757768213513987941266551218952702606511178276633908546681835137035411034761316782876147359960487121213984853077540707588650724919247893999205747065241005931759522778403309142776013266993947909627871209547322186129461944966954255478452004126991923307040855781751576009560486080068518925411003611155913186594087392942825850544717133800805624006483035224985413873703244911627183839595554490748948155205230203576672211733145725061218786720271669259766573150046403742640731305478008090581342450251//p
phi = (p-1)*(q-1)
d = inverse(0x10001,phi)
print(long_to_bytes(pow(c,d,47935439323457127833037357083983237496878689261127081988649381912739468031720632155196797632254382181519984640185516509133478757768213513987941266551218952702606511178276633908546681835137035411034761316782876147359960487121213984853077540707588650724919247893999205747065241005931759522778403309142776013266993947909627871209547322186129461944966954255478452004126991923307040855781751576009560486080068518925411003611155913186594087392942825850544717133800805624006483035224985413873703244911627183839595554490748948155205230203576672211733145725061218786720271669259766573150046403742640731305478008090581342450251)))

c = 26477776136511814537867182410042935036751631193394882824790793880743251563906439761929648379057880893788211246254847830996292172157860942596330440504204415170090503913269874666809421512135396019520075970999555199447275211351781765139220570319976413703772788491129400862990098026864762589440254742120432827191
n = 462759013310826480654170350879608056333317185952185294792509715751354925534996431275210016348827150025558626490699228055937593844557693779418456113065581193070896452111537933875515496157080452283253231904539734791991415148758529596162008849892665895353050001859515122987866725231231752910748407229540350263791
c1 = pow(c,inverse(4096,n-1),n)
c2 = pow(c1,(n+1)//4,n)
print(long_to_bytes(n-c2))

Attachment