WMCTF 2021

Table of Contents

–>

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 ，直接打给服务器即可

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 #

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 #

WMCTF2021