【技術分享】分析Teaser Dragon CTF 2019中Crypto方向題目 - 網安 - 專業的網絡安全產業、社區、知識平臺

前言

在Teaser Dragon CTF 2019中有2道考察Crypto方向的題目，一道Crypto題目，一道Web+Crypto題目，在這里對題目進行一下分析。

rsachained

題目描述如下：

Keys are generated in the standard way with the default setup…

task.py output.txt

題目描述里的這句話其實應該算是一個梗…在今年的DEFCON CTF Quals上有一道名叫chainedrsa的Reverse+Crypto題目，考察根據私鑰低位恢復私鑰高位，題目挺簡單的但是最終只有10個隊做出來，很多隊伍的exp都在本地打通了，但是遠程就是不行，原因在于當時那道題服務器上的密鑰在生成時沒有使用:

φ(n) = (p-1)*(q-1)

而是使用的：

λ(n) = lcm(p-1,q-1)

來生成密鑰，而很多人在本地自己模擬時候都還是用的φ(n)，因此出現了過的了本地過不了遠程這種情況。當時有一些隊伍在比賽期間去問主辦方，主辦方給出了如下回復：

這句話成功的”誤導”了更多的隊伍…因此也導致了很多隊伍賽后對這道題的吐槽，因此有了這么一個梗，這次Teaser Dragon CTF 2019中的這個題目的名字、題目描述和考點都是和當時那道題有關: )。

好我們回到這次的題目上，首先看一下題目的源代碼：

import os
import gmpy2
flag = int(open('flag.txt').read().encode("hex"), 16)
def genPrime(bits):
    data = os.urandom(bits/8)
    number = int(data.encode("hex"), 16)
    return gmpy2.next_prime(number)
e = 1667
# rsa1: p - 700 bits q - 1400 bits
p = genPrime(700)
q = genPrime(1400)
n = p*q
phi = (p-1)*(q-1)
d = gmpy2.powmod(e, -1, phi)
rsa1 = (n, d)
# rsa2: p - 700 bits, q - 700 bits, r = 700 bits
p = genPrime(700)
q = genPrime(700)
r = genPrime(700)
n = p*q*r
phi = (p-1)*(q-1)*(r-1)
d = gmpy2.powmod(e, -1, phi)
rsa2 = (n, d)
# rsa3: p - 700 bits, q - 700 bits, r = 700 bits
p = genPrime(700)
q = genPrime(700)
n = p*q*r
phi = (p-1)*(q-1)*(r-1)
d = gmpy2.powmod(e, -1, phi)
rsa3 = (n, d)
# rsa4: p - 700 bits, q - 700 bits
p = genPrime(700)
q = genPrime(700)
n = p*q*q
phi = (p-1)*(q-1)*q
d = gmpy2.powmod(e, -1, phi)
rsa4 = (n, d)
rsa = sorted([rsa1, rsa2, rsa3, rsa4])
for n, d in rsa:
    print 'pubkey:', n, d % (2**1050)
    flag = pow(flag, e, n)
print 'encrypted flag', flag

其執行結果如下：

pubkey: 859120656206379031921714646885063910105407651892527052187347867316222596884434658659405822448255608155810241715879240998190431705853390924506125009673776539735775578734295308956647438104082568455604755897347443474837969627723792555180605570061543466558710984713039896691188382997755705425087392982168984185229388761020298907843938651747237132404355197739247655148879984476412365078220648181358131779226613410257975180399575865809381114503102493767755197618305439592514756307937482535824886677028869214462143121897901687818277055753103973809215799348093165770108731899625440232334370794010877047571087634088643565878666814823597 6404011758157972703612261793681759246464215350955339624160911161422611520145549655575457659757671312362520534084082807541566604214336116674150997699501607769566852492157994984170248823333294918447786457066546086171046532955584494739314351490726886444164048184241514125678560723782999029659135170314199032519015517483
pubkey: 1311485515090222718982495198730831073955174624382380405255882886012541076751694096664143914783345786808989030195914045177845164364400711539537456739170589346033729436625658871146633553503774866142568716068953663977222002088477902235884717082069070796901652820969777833174034685816622756524282480580399883160755030115364291412718061758142515305389808681261201028647918631486855998332674824264495109641835596608336454102370944531225289276734441189842117114187272485368222698210402692987316946307402124818683662256285425749745044473836534317911693431019535047343774304237969249813708212575639444584092633692220540287380100087406907 6762547460602241256253304403057840010356965995658332151464306076734886668348338229477220486851971695831025738065540621944954803087639187605826246170852109559079074614119808221929013953607066074389809368603757307759386199129306765569186327590211123849053154881101151177686828760168745679159348065176015209027306930795
pubkey: 1575060449430659140207638391055943675863526369065063706350412723523667837574603957873052861827978497667790320751709825539894814309966419985565518167069012257059970719629265514554227032833047486506557616694792185308331642271153817395624694602567048186971822198162003259057599067679515651509006583655734337286195372119659961892695887527649792831639865587192165588971284597107150903552624259996427357055727777299373593229142742726141314990452184229476917038184267241036918602554417997784006066104066098902608890274713296413328177121301222893743767266080583504425094092518398681307182308611729107396812972850405735757668088697847951 5707521170224254508659672846933818787001135802176783947179706231070761518271823668313158008289673444516064588686080249076540588375157043626677419185625336049313314641249542595200886768114306555416909136568265340888067484302848785272525288608839874074236050840506402897831477010251518458186504962395384666969171250107
pubkey: 4232819155839550922279592842719433946891627776859962079814516253452165389036653289438928378562503361802962808867376036446065199400114343981489770467719433842467863790025157645790790546711434342749173114584205175937908175583479179580810260063208858154629604787679080148158778144242635384249890271882097552355559004259916015878919322278402739861284711967004042252592561170311676956442870143264815298550428890342085615270647716168020441562257255689477157387477157201225997667848750302348483724394538068236632998615714647043723202692215390463632895984121932442861483996529680353143769212467480570412438553808228897441253339977829074399 4649045196470695353390836308229816980123193670378994484653092063162829775325027591589707695443531712311911547784211686738135679083418730545146218582354267299967469877756913949564462524369735344985321925911759639861523989288138280762813588519717108172156784540565137256654620399500030648870656882195855476291698508835
encrypted flag 594744523070645240942929359037746826510854567332177011620057998249212031582656570895820012394249671104987340986625186067934908726882826886403853350036347685535238091672944302281583099599474583019751882763474741100766908948169830205008225271404703602995718048181715640523980687208077859421140848814778358928590611556775259065145896624024470165717487152605409627124554333901173541260152787825789663724638794217683229247154941119470880060888700805864373121475407572771283720944279236600821215173142912640154867341243164010769049585665362567363683571268650798207317025536004271505222437026243088918839778445295683434396247524954340356

可以看到我們的任務還是根據低位私鑰恢復高位私鑰（模2**1050即表示我們知道的是d的低1050位），只不過每次的場景略微有些不同：

n1 = p1 * q1        (p 700 bits, q 1400 bits)
n2 = p2 * q2 * r    (p 700 bits, q 700 bits, r 700 bits)
n3 = p3 * q3 * r    (p 700 bits, q 700 bits, r 700 bits)
n4 = p4 * q4 * q4   (p 700 bits, q 700 bits)

這里有一點需要注意，我們執行結果里的4個n，并不是和我們上面列舉的4個n一一對應的，因為代碼最后的rsa = sorted([rsa1, rsa2, rsa3, rsa4])這一行打亂了我們的排列順序，所以我們暫時還不能直接看出n1-n4各自具體的值，不過我們可以通過分析來進一步確定。

首先很容易看出r在n2和n3里共用了，因此這里存在模不互素攻擊，可以通過gcd(n2,n3)計算出r，因此我們只需要在執行結果里面去找哪兩個數有1以外的公因子，那么這兩個數就是n2和n3。n2和n3確定以后，n1和n4就只剩下2種順序了，因此最多計算兩遍也就可以確定出來了。

那么接下來我們就依次來看這幾種場景應該如何恢復出私鑰：

場景1：n1 = p1 * q1

首先我們可以推導出如下表達式：

這里由于phi(n)就是常規模型中的phi(n)=(p-1)*(q-1)，因此我們有：

即：

同余式兩邊同乘上p，有：

整理一下，即：

該表達式中除了p和k外，其它均為已知常數。而根據RSA的定義我們知道d=invert(e,phi)，d是模phi的一個值，因此d肯定是小于phi的，而我們又知道這里的k是來自e*d-k*phi=1這一表達式，d小于phi但ed大于kphi，顯然e是大于k的，即k的取值范圍為開區間(0,e)，而在本題中e=1667，即k處在一個很小的搜索區間當中，因此我們可以遍歷k，當找到該方程有素數解且能被n整除的話，那么基本上就可以認為我們得到了p。一旦得到p，表明我們成功的分解了n，那么直接就可以計算出來d了，我們將這一過程寫成SageMath腳本如下：

def find_p(d0, e, n, start, stop):
    X = var('X')
    for k in xrange(start, stop):
        print k
        results = solve_mod([e*d0*X - k*(n*X-X*X-n+X) == X], 2^1050)
        for x in results:
            p0 = ZZ(x[0])
            if is_prime(p0) and gcd(n,p0)!=1:
                return p0

最后解出該場景的參數如下：

n1 = 4232819155839550922279592842719433946891627776859962079814516253452165389036653289438928378562503361802962808867376036446065199400114343981489770467719433842467863790025157645790790546711434342749173114584205175937908175583479179580810260063208858154629604787679080148158778144242635384249890271882097552355559004259916015878919322278402739861284711967004042252592561170311676956442870143264815298550428890342085615270647716168020441562257255689477157387477157201225997667848750302348483724394538068236632998615714647043723202692215390463632895984121932442861483996529680353143769212467480570412438553808228897441253339977829074399
d0_1 = 4649045196470695353390836308229816980123193670378994484653092063162829775325027591589707695443531712311911547784211686738135679083418730545146218582354267299967469877756913949564462524369735344985321925911759639861523989288138280762813588519717108172156784540565137256654620399500030648870656882195855476291698508835
#results
k = 785
p = 188689169745401648234984799686937623590015544678958930140026860499157441295507274434268349194461155162481283679350641089523071656015001291946438485044113564467435184782104140072331748380561726605546500856968771

這里需要注意的一點是，如果我們試圖直接執行find_p(e,d0,n1,1,e)來執行的話，時間消耗是非常巨大的，也就是說我們是很難跑出來結果的，這里注意到我們在每次循環中所做的運算都是相互獨立的，因此我們可以將開區間(0,e)切片成若干個小區間，然后并行計算，這樣可以大大減小我們跑腳本所需要的時間，對于后面的幾種場景我們也同樣需要采用并行計算的方法來跑出結果。

場景2：n2 = p2 * q2 * r;n3 = p3 * q3 * r

首先我們根據模不互素的思路找到n2、n3和r：

import itertools
n = [859120656206379031921714646885063910105407651892527052187347867316222596884434658659405822448255608155810241715879240998190431705853390924506125009673776539735775578734295308956647438104082568455604755897347443474837969627723792555180605570061543466558710984713039896691188382997755705425087392982168984185229388761020298907843938651747237132404355197739247655148879984476412365078220648181358131779226613410257975180399575865809381114503102493767755197618305439592514756307937482535824886677028869214462143121897901687818277055753103973809215799348093165770108731899625440232334370794010877047571087634088643565878666814823597,1311485515090222718982495198730831073955174624382380405255882886012541076751694096664143914783345786808989030195914045177845164364400711539537456739170589346033729436625658871146633553503774866142568716068953663977222002088477902235884717082069070796901652820969777833174034685816622756524282480580399883160755030115364291412718061758142515305389808681261201028647918631486855998332674824264495109641835596608336454102370944531225289276734441189842117114187272485368222698210402692987316946307402124818683662256285425749745044473836534317911693431019535047343774304237969249813708212575639444584092633692220540287380100087406907,1575060449430659140207638391055943675863526369065063706350412723523667837574603957873052861827978497667790320751709825539894814309966419985565518167069012257059970719629265514554227032833047486506557616694792185308331642271153817395624694602567048186971822198162003259057599067679515651509006583655734337286195372119659961892695887527649792831639865587192165588971284597107150903552624259996427357055727777299373593229142742726141314990452184229476917038184267241036918602554417997784006066104066098902608890274713296413328177121301222893743767266080583504425094092518398681307182308611729107396812972850405735757668088697847951,4232819155839550922279592842719433946891627776859962079814516253452165389036653289438928378562503361802962808867376036446065199400114343981489770467719433842467863790025157645790790546711434342749173114584205175937908175583479179580810260063208858154629604787679080148158778144242635384249890271882097552355559004259916015878919322278402739861284711967004042252592561170311676956442870143264815298550428890342085615270647716168020441562257255689477157387477157201225997667848750302348483724394538068236632998615714647043723202692215390463632895984121932442861483996529680353143769212467480570412438553808228897441253339977829074399]
for c in itertools.combinations(n, 2):
    r = gcd(c[0], c[1])
    if r != 1:
        print(c[0], c[1])
        print(r)

由于引入了r，本題這里的phi變成了(p-1)(q-1)(r-1)，因此我們還需要調整一下場景一的表達式：

即有：

同余式兩邊同乘上q，有：

整理一下，即：

我們將這一過程寫成SageMath腳本如下，實際上跟場景一相比只是替換了solve_mod的表達式：

def find_p(d0, e, n, start, stop):
    X = var('X')
    for k in xrange(start, stop):
        print k
        results = solve_mod([e*d0*r*X - k*(n*r*X -n*X - X*X*r*r + X*X*r - n*r + n +X*r*r - X*r) == X*r], 2^1050)
        for x in results:
            p0 = ZZ(x[0])
            if is_prime(p0) and gcd(n,p0)!=1:
                return p0

最后解出該場景的參數如下：

n2 = 859120656206379031921714646885063910105407651892527052187347867316222596884434658659405822448255608155810241715879240998190431705853390924506125009673776539735775578734295308956647438104082568455604755897347443474837969627723792555180605570061543466558710984713039896691188382997755705425087392982168984185229388761020298907843938651747237132404355197739247655148879984476412365078220648181358131779226613410257975180399575865809381114503102493767755197618305439592514756307937482535824886677028869214462143121897901687818277055753103973809215799348093165770108731899625440232334370794010877047571087634088643565878666814823597
d0_2 = 6404011758157972703612261793681759246464215350955339624160911161422611520145549655575457659757671312362520534084082807541566604214336116674150997699501607769566852492157994984170248823333294918447786457066546086171046532955584494739314351490726886444164048184241514125678560723782999029659135170314199032519015517483
#results
k = 1041
p = 90298557884682577669238320760096423994217812898822512514104930945042122418007925771281125855142645396913218673571816112036657123492733042972301983242487835472292994595416656844378721884370309120262139835889657
n3 = 1311485515090222718982495198730831073955174624382380405255882886012541076751694096664143914783345786808989030195914045177845164364400711539537456739170589346033729436625658871146633553503774866142568716068953663977222002088477902235884717082069070796901652820969777833174034685816622756524282480580399883160755030115364291412718061758142515305389808681261201028647918631486855998332674824264495109641835596608336454102370944531225289276734441189842117114187272485368222698210402692987316946307402124818683662256285425749745044473836534317911693431019535047343774304237969249813708212575639444584092633692220540287380100087406907
d0_3 = 6762547460602241256253304403057840010356965995658332151464306076734886668348338229477220486851971695831025738065540621944954803087639187605826246170852109559079074614119808221929013953607066074389809368603757307759386199129306765569186327590211123849053154881101151177686828760168745679159348065176015209027306930795
#results
k = 877
p = 142270506848638924547091203976235495577725242858694711068289574174127601000137457280276860615471044907560710121669055364010408768146949985099404319539891688093875478389341632242096859500255283810703767020918479

場景3：n4 = p4 * q4 * q4

這里的phi變成了(p-1)(q-1)q，因此我們調整一下場景一的表達式即可：

即有：

同余式兩邊同乘上q，有：

整理一下，即：

我們將這一過程寫成SageMath腳本如下，實際上跟場景一相比只是替換了solve_mod的表達式：

def find_p(d0, e, n, start, stop):
    X = var('X')
    for k in xrange(start, stop):
        print k
        results = solve_mod([e*d0*X - k*(n*X-n-X*X*X + X*X) == X], 2^1050)
        for x in results:
            p0 = ZZ(x[0])
            if is_prime(p0) and gcd(n,p0)!=1:
                return p0

最后解出該場景的參數如下：

n4 = 1575060449430659140207638391055943675863526369065063706350412723523667837574603957873052861827978497667790320751709825539894814309966419985565518167069012257059970719629265514554227032833047486506557616694792185308331642271153817395624694602567048186971822198162003259057599067679515651509006583655734337286195372119659961892695887527649792831639865587192165588971284597107150903552624259996427357055727777299373593229142742726141314990452184229476917038184267241036918602554417997784006066104066098902608890274713296413328177121301222893743767266080583504425094092518398681307182308611729107396812972850405735757668088697847951
d0_2 = 5707521170224254508659672846933818787001135802176783947179706231070761518271823668313158008289673444516064588686080249076540588375157043626677419185625336049313314641249542595200886768114306555416909136568265340888067484302848785272525288608839874074236050840506402897831477010251518458186504962395384666969171250107
#results
k = 572
p = 267307309343866797026967908679365544381223264502857628608660439661084648014195234872217075156454448820508389018205344581075300847474799458610853350116251989700007053821013120164193801622760845268409925117073227

所有的n都分解完了，那么我們直接連續解密恢復flag即可，腳本如下：

from Crypto.Util.number import *
from gmpy2 import invert
#RSA1
e = 1667
n1 = 4232819155839550922279592842719433946891627776859962079814516253452165389036653289438928378562503361802962808867376036446065199400114343981489770467719433842467863790025157645790790546711434342749173114584205175937908175583479179580810260063208858154629604787679080148158778144242635384249890271882097552355559004259916015878919322278402739861284711967004042252592561170311676956442870143264815298550428890342085615270647716168020441562257255689477157387477157201225997667848750302348483724394538068236632998615714647043723202692215390463632895984121932442861483996529680353143769212467480570412438553808228897441253339977829074399
p1 = 188689169745401648234984799686937623590015544678958930140026860499157441295507274434268349194461155162481283679350641089523071656015001291946438485044113564467435184782104140072331748380561726605546500856968771
q1 = n1 / p1
phi1 = (p1 - 1) * (q1 - 1)
d1 = invert(e, phi1)
#RSA2
r = 32619972550448885952992763634430245734911201344234854263395196070105784406551510361671421185736962007609664176708457560859146461127127352439294740476944600948487063407599124272043110271125538616418873138407229
n2 = 859120656206379031921714646885063910105407651892527052187347867316222596884434658659405822448255608155810241715879240998190431705853390924506125009673776539735775578734295308956647438104082568455604755897347443474837969627723792555180605570061543466558710984713039896691188382997755705425087392982168984185229388761020298907843938651747237132404355197739247655148879984476412365078220648181358131779226613410257975180399575865809381114503102493767755197618305439592514756307937482535824886677028869214462143121897901687818277055753103973809215799348093165770108731899625440232334370794010877047571087634088643565878666814823597
p2 = 90298557884682577669238320760096423994217812898822512514104930945042122418007925771281125855142645396913218673571816112036657123492733042972301983242487835472292994595416656844378721884370309120262139835889657
q2 = (n2 / r) / p2
phi2 = (p2 - 1) * (q2 - 1) * (r - 1)
d2 = invert(e, phi2)
#RSA3
n3 = 1311485515090222718982495198730831073955174624382380405255882886012541076751694096664143914783345786808989030195914045177845164364400711539537456739170589346033729436625658871146633553503774866142568716068953663977222002088477902235884717082069070796901652820969777833174034685816622756524282480580399883160755030115364291412718061758142515305389808681261201028647918631486855998332674824264495109641835596608336454102370944531225289276734441189842117114187272485368222698210402692987316946307402124818683662256285425749745044473836534317911693431019535047343774304237969249813708212575639444584092633692220540287380100087406907
p3 = 142270506848638924547091203976235495577725242858694711068289574174127601000137457280276860615471044907560710121669055364010408768146949985099404319539891688093875478389341632242096859500255283810703767020918479
q3 = (n3 / r) / p3
phi3 = (p3 - 1) * (q3 - 1) * (r - 1)
d3 = invert(e, phi3)
#RSA4
n4 = 1575060449430659140207638391055943675863526369065063706350412723523667837574603957873052861827978497667790320751709825539894814309966419985565518167069012257059970719629265514554227032833047486506557616694792185308331642271153817395624694602567048186971822198162003259057599067679515651509006583655734337286195372119659961892695887527649792831639865587192165588971284597107150903552624259996427357055727777299373593229142742726141314990452184229476917038184267241036918602554417997784006066104066098902608890274713296413328177121301222893743767266080583504425094092518398681307182308611729107396812972850405735757668088697847951
q4 = 267307309343866797026967908679365544381223264502857628608660439661084648014195234872217075156454448820508389018205344581075300847474799458610853350116251989700007053821013120164193801622760845268409925117073227
p4 = n4 / (q4 * q4)
d4 = invert(e, (p4 - 1) * (q4 - 1) * q4)
ct = 594744523070645240942929359037746826510854567332177011620057998249212031582656570895820012394249671104987340986625186067934908726882826886403853350036347685535238091672944302281583099599474583019751882763474741100766908948169830205008225271404703602995718048181715640523980687208077859421140848814778358928590611556775259065145896624024470165717487152605409627124554333901173541260152787825789663724638794217683229247154941119470880060888700805864373121475407572771283720944279236600821215173142912640154867341243164010769049585665362567363683571268650798207317025536004271505222437026243088918839778445295683434396247524954340356
rsa1 = (n1, d1)
rsa2 = (n2, d2)
rsa3 = (n3, d3)
rsa4 = (n4, d4)
rsa = sorted([rsa1, rsa2, rsa3, rsa4], reverse=True)
for n, d in rsa:
    ct = pow(ct, d, n)
print(long_to_bytes(ct))

執行腳本即可得到flag：

DrgnS{w3_fiX3d_that_f0r_y0U}

Looking glass

題目描述如下

We found some shady Looking Glass service. Pretty sure there is a way to get that delicious /flag.

http://lg.hackable.software:8080/

src.tgz

訪問目標網站，發現可以使用ping或traceroute加一些參數來執行命令，我們定位到這一部分的代碼段如下：

switch c := cmd.Command.(type) {
case *Command_PingCommand:
    commandline = fmt.Sprintf("ping -%d -c %d %s", c.PingCommand.GetIpVersion(), c.PingCommand.GetCount(), c.PingCommand.GetAddress())
case *Command_TracerouteCommand:
    commandline = fmt.Sprintf("traceroute -%d %s", c.TracerouteCommand.GetIpVersion(), c.TracerouteCommand.GetAddress())
}
// --snip--
e := exec.CommandContext(ctx, "/bin/sh", "-c", commandline)

通過查看源碼，我們發現用戶使用protobuf來發送消息，發送的消息可以是ping請求也可以是traceroute請求，同時用戶還需要提供請求查詢的地址（當然不提供也可以執行，因為有默認地址）。從這段代碼中我們不難發現，如果我們可以任意設置地址內容，那么很容易實現遠程代碼執行，但是這里我們的地址是被嚴格限制的，即地址的字符不能超出a-z0-9.這一字符集，因此我們需要進一步去分析。

由于我們需要使用protobuf來發送消息，我們首先以執行ping google.com這條命令為例來看一下protobuf的基本格式，payload如下：

0A-10-0A-0A-67-6F-6F-67-6C-65-2E-63-6F-6D-10-01-18-04

該payload的格式為：

0A：field 1, type String（這里解釋一下，0A的二進制為00001010，其中前5位00001表示field，即field 1，后3位010表示type，type 2為字符串類型）
10：長度為0x10，表示的是從該字節往后的所有字節的長度（即0A-0A-67-6F-6F-67-6C-65-2E-63-6F-6D-10-01-18-04）
0A：field 1, type String
0A：長度為0xA，表示的是從該字節往后的所有字節的長度（即67-6F-6F-67-6C-65-2E-63-6F-6D-10-01-18-04）
67-6F-6F-67-6C-65-2E-63-6F-6D：google.com的16進制形式
10：field 2, type Variant
01：1 - ping count
18：field 3, type Variant
04：4 - ipv4

在本題的環境下我們最后的10011804（即field 2和field 3）是默認的，我們可以在這里忽略這一部分。為了便于讀者理解，在這里我們可以把這個payload格式抽象成0A 后面的長度 0A 后面的長度地址這種格式，關于Protobuf的格式我們也可以通過這個在線的Protobuf Decoder來進一步了解。

雖然對地址部分限制很嚴格，但是我們進一步審計可以發現如下代碼：

func (v *validator) Valid(data []byte) *Command {
    if len(data) > 270 {
        return nil
    }
    key := md5bytes(data)
    v.lock.Lock()
    defer v.lock.Unlock()
    var cmd Command
    if err := proto.Unmarshal(data, &cmd); err != nil {
        return nil
    }
    var address string
    switch c := cmd.Command.(type) {
    case *Command_PingCommand:
        address = c.PingCommand.GetAddress()
    case *Command_TracerouteCommand:
        address = c.TracerouteCommand.GetAddress()
    }
    valid, ok := v.cache.Get(key)
    if ok && valid.(bool) {
        return &cmd
    } else if checkAddress(address) {
        v.cache.Add(key, true)
        return &cmd
    }
    return nil
}

分析代碼可知，這里網站引入了LRU 緩存機制，即我們的請求如果已經在緩存中存在，那么就不再進行地址過濾了，緩存中的內容是以MD5哈希的形式存在的，那么這里我們就可以設想一種攻擊思路：如果我們能夠構造兩條payload，第一條是合法的，就是很單純的ping一個合法地址，不會被網站過濾；第二條是非法的，可以實現遠程代碼執行，會被網站過濾，但是這兩條payload具有相同的MD5哈希值，我們可以先發送第一條payload，然后網站接收并將其MD5哈希寫入緩存，然后我們再發送第二條payload，由于兩條的payload的MD5哈希值相同，網站在cache中匹配成功，因此不會進行地址過濾，此時觸發遠程代碼執行，我們就可以藉由這種方式拿到flag。

與此同時，我們還注意到了protobuf的兩個特性，一個是如果我們向payload后面添加新的field，這些新的field可以用來存儲任意數據，而且不會被解析。另一個是如果我們在protobuf中有兩個相同的field，那么只有最后一個field會被解析，這些特性可能會對我們構造MD5哈希碰撞提供非常大的幫助。

那么接下來我們的任務就是要實現一次MD5哈希碰撞，關于MD5哈希碰撞的攻擊主要有兩種形式，即相同前綴攻擊和選擇前綴攻擊，那么我們就來分析一下這兩種攻擊。

我們首先看一下選擇前綴攻擊，選擇前綴可以讓我們使用不同的前綴，然后藉由在前綴后面padding碰撞塊實現整體的哈希相同的效果，那么我們用一個合法payload做一個前綴，另一個惡意payload做另一個前綴，然后使用選擇前綴攻擊生成兩個哈希值相同的序列就可以了，這樣聽起來似乎沒有什么問題，但是我們一分析就會發現，由于我們的payload的開頭是有表示長度的字節的，但是選擇前綴攻擊生成的碰撞塊的長度是我們無法預測的，比如說我把表示payload長度的字節的值寫成0x1a，然后我使用選擇前綴攻擊，發現生成的結果的長度是0x2a，然后我再把表示payload長度的字節的值改成0x2a，然后再次使用選擇前綴攻擊，這會生成的結果的長度就又變了，因此我們沒辦法預測生成之后的序列的長度，也就沒辦法指定長度字節的值，這樣二者不匹配，我們就沒辦法構造一個合法的payload，另外，選擇前綴攻擊的耗時是非常長的，因此這種攻擊方式在這里是行不通的。

那么我們再來看一下相同前綴攻擊，相同前綴即指定前綴相同，然后在保持該前綴的基礎上通過padding上不同的碰撞塊實現哈希碰撞，這種方法生成的結果序列長度是可以預測的，即相同的前綴長度會生成相同的序列長度，而且相同前綴攻擊生成序列的速度很快，但是前綴一相同，就等于我們的payload得一樣，那我們就無法再構造惡意payload了，因此這種攻擊方式在這里也是行不通的。

那么除此之外我們還有其他的攻擊方式嗎，通過查閱資料我們可以發現，還有有一種比較特殊的相同前綴攻擊，它也是需要我們提供相同的前綴，但是在生成的兩個結果序列里面，其中一個序列的第10個字節的最后一個比特會發生翻轉，比如本來我們提供的前綴是x00x00x00x00x00x00x00x00x00x00，那么生成之后的兩個序列一個前綴還是x00x00x00x00x00x00x00x00x00x00，另一個序列的前綴將變成x00x00x00x00x00x00x00x00x00x01，就是它會對前綴做一個微小的修改，那么我們接下來嘗試一下能不能利用這1比特的微小變化來達到我們的目的。

根據題目提示，我們假設flag就這/flag目錄下，我們希望在地址處填入;nl /flag，這樣一旦執行ping;nl /flag，就會返回給我們flag的值，當然你也可以選擇使用|代替;，使用cat代替nl等等都可以，只要能夠返回給我們flag就行，那么我們就試著構造一下如下payload：

n~"x00"x00"x00"x00"nt;nl /flag"h

我們來分析一下：

第一個字節n，其ascii碼為0x0A，即我們payload開頭的格式（field 1, type String）。

第二個字節~，其ascii碼為0x7e，表示的是我們后面整個序列的長度，即"x00"x00"x00"x00"nt;nl /flag"h+后面padding的碰撞塊的長度，因為碰撞塊的長度是可以預測的，因此我們可以直接在這個字節寫入正確的長度。

第一個字節n，同第一個字節，即在這按照我們payload的格式填寫即可（field 1, type String）。

第四個字節"，其ascii碼為0b00100010，后三位表示type，這里010（即十進制2）表示這是一個string type，前五位表示field，這里00100（即十進4）表示這是field 4，而field 4是一個不存在的field編號，根據protobuf的規則，該部分會被忽略。

第五個字節x00表示該field的長度，這里填0表示不存在長度，也即后面不填充內容。在這里我們之所以指定了一個不存在的field，作用就是用來占位用的，從而保證第10個字節正好是我們需要的部分，后面連續的4個字節"x00"x00同理，都是用來占位的。

從第九個字節開始到最后這一段"x00"nt;nl /flag"h，就是比較關鍵的部分了，我們來看一下，這一段當中的這個x00是整個我們構造的payload的第10個字節，如果我們把這段payload當做前綴去做我們前面提到的這種比較特殊的相同前綴攻擊的話，我們看一下生成之后的前綴的這一部分內容會變成什么：

第一個前綴：

"x00"nt;nl /flag"h

第二個前綴：

"x01"nt;nl /flag"h

第一個前綴沒有進行修改，保持原樣，我們來分析一下，首先"x00這兩個字節還是跟我們前面一樣，直接被忽略了，然后又是"n（field 4, type String），后面跟上表示長度n的字節，n的ascii碼是10，正好即后面跟著的t;nl /flag這10個字節，再后面又是一個"（field 4,type string），后面跟上h，其ascii碼為104，由于field 4 是不存在的，因此后面的104個字節都會被忽略（這里的104也是提前算出來的，因為padding的碰撞塊是可以預測的）。那么整體看下來我們就會發現，雖然我們寫了一大堆，但是所有東西全被忽略了，等于沒有提供地址，此時網站就會去ping默認地址，因此整個這一段內容是合法的，并且是可以成功執行的。

第二個前綴翻轉了第10個字節的最后一比特，導致x00變成了x01，這樣我們再來分析一下，首先"還是跟前面一樣是field 4,type string，表示一個不存在的field，然后后面跟上的長度由原本的x00變成了x01，這樣一來，緊跟在后面的"也就被當做了field 4中的一部分被忽略了，然后后面的n在這的含義就發生了變化，由原來的表示field 4的長度，變成了表示field 1，type string的開頭，即變成了一個合法的field（這里的變化非常之微妙以及巧妙，沒有理解的同學可以再多幾遍這句話，體會一下其中的變化），這樣后面的t（ascii碼為9）就變成了表示后面跟著的;nl /flag這9個字節，而這9個字節被歸在了一個合法的field 1里面，這樣一來，由于我們這條序列的哈希和前面的合法序列的哈希一致，因此在緩存中匹配成功，地址不會被過濾，而這里的;nl /flag這條命令又被包裹在了一個合法的field當中，整個payload可以被成功執行，因此成功觸發遠程代碼執行，服務器將會返回flag。

那么接下來我們只要按照上述推理生成兩個這種序列即可，這里我們可以使用UniColl來完成這種比較特殊的MD5相同前綴攻擊，使用方法如下：

首先克隆項目，安裝依賴、更新：

git clone https://github.com/cr-marcstevens/hashclash.git
cd hashclash/
sudo apt-get install autoconf automake libtool
sudo apt-get install zlib1g-dev libbz2-dev
./install_boost.sh

然后Build：

autoreconf --install
./configure --with-boost=$(pwd)/boost-1.57.0
make

然后建立自己的工作目錄：

mkdir cpc_workdir
cd cpc_workdir

然后在我們的工作目錄下生成前綴文件：

>>> prefix = '''n~"x00"x00"x00"x00"nt;nl /flag"h'''
>>> f = open('prefix.txt','w')
>>> f.write(prefix)
>>> f.close()

然后在我們的工作目錄下執行：

../scripts/poc_no.sh prefix.txt

執行腳本后等待一段時間，我們得到collision1.bin和collision2.bin，查看一下：

>>> f1 = open('collision1.bin','r').read()
>>> f2 = open('collision2.bin','r').read()
>>> f1
'n~"x00"x00"x00"x00"nt;nl /flag"hx04xe6x9b[xe5x1cxbfxe3wgvx9ex03Wxecx81xdexde0wxf4[Wxdcw,:B_xb9xb5xaexf1xd4xed9%xb4xf8xaaxb5 x927xb8dxf7x0bxc0Ux97xb5xaexf9B4x*S2xeaxd2x1fxf7xebx8bsx02x84xa6ex03xcdx0fXdxe0x01xa8Zx15x1bxebxfexedxa7x1dx8fxd8xdcxaexbfx1fx94sxb5xf4pxfcxbfa!gxa0'
>>> f2
'n~"x00"x00"x00"x01"nt;nl /flag"hx04xe6x9b[xe5x1cxbfxe3wgvx9ex03Wxecx81xdexde0wxf4[Wxdcw,:B_xb9xb5xaexf1xd4xed9%xb4xf8xaaxb5 x927xb8dxf7x0bxc0Tx97xb5xaexf9B4x*S2xeaxd2x1fxf7xebx8bsx02x84xa6ex03xcdx0fXdxe0x01xa8Zx15x1bxebxfexedxa7x1dx8fxd8xdcxaexbfx1fx94sxb5xf4pxfcxbfa!gxa0'
>>> f1==f2
False
>>> md5(f1).hexdigest()==md5(f2).hexdigest()
True

符合條件，那么我們將這兩條序列發送至服務器，即可得到flag：

DrgnS{w00T_Md5_1N_2OI9?}

參考

https://github.com/p4-team/ctf/tree/master/2019-09-21-dragonctf

https://nytr0gen.github.io/writeups/ctf/2019/09/22/teaser-dragon-ctf-2019.html

https://github.com/corkami/collisions#unicoll-md5

https://github.com/corkami/collisions/blob/master/unicoll.md