　5月25～26日にSECCON Beginners CTFが開催されてました．チームzer0ptsで参加し、見事1位でした．チームメンバーのスピード感にあたふたしながらも、何とか数問通したのでWriteupを書きます． f:id:y05h1k1ng:20190526150254p:plain

チームメンバーのWriteup

st98: Beginners CTF 2019 の write-up - st98 の日記帳

theoldmoon0602: SECCON Beginners CTF 2019 writeup - ふるつき

ptr-yudai: SECCON Beginners CTF 2019のWriteup - CTFするぞ

[Crypto 363pts] Go RSA

Nだけなくしちゃったんだよなあ……。

　とりあえず、ncしてみます．

$ nc 133.242.17.175 1337
Encrypted flag is: 6344991311564553615862579427487315421208055634102890395723986371495652609153052697621268167305282339617530377087384855394685474792773022115680540686568501138450681688735527617827708821485497498334547179214866381804619441945049231222689303859605328356743173601997078352973035701358512748861024520717173066208645110545270222021655297034426926498311814336661104067007494662082645957734853033496598300417493177589227972753784432427753861158326507152049357862231911441535352804653810629357318640120796228696711675902539564632797542696587638137206651220915784909017728259256279217121403410183718987376151252076850594986072
> 0 
0
> 1
1
> 2
2862334794876318566324057598241408128109425191172133981033760448232814429877972087723511977245286558645814682054000700802565238541629306735791660770705209092054679971683689343593450904080873595244990490120345136595441331711791642822309784005850295255019360549477080451991452042485726954377888628611850312169956235832476482473468997735379482200368532387100203433537314371261639774070163736423425627779689468867325590663448606913878199332557603250135695359944006132143818989945004067114026488158760762115016145779669731641814525334761633123615342046269898802364403424297888529318077961694410182680067006220851010487693
The D was 3108589354283999881366977377816211791659702282566657492492997508648885943813044323050780847180267937096874217339239440259051280553557374969326192368619436355830441614153601856008410159305941711348272515678361389635638005453913489251292139406829869123083572863219302494814837811525563431399822598189396464260524809835126230568531180443134269028794046517626742952434891439389309802663719183434506260830073832328429505252129371886238807490334805430087834068647490477751392145402285002619521810094785728754166749922294644025726513925553921296219135200362480519946364396480504261544279372784914298890836180406341120859329

　数字を与えたら何か返ってきます．また、Encrypted flagとDがもらえます．RSAと言われているので、返ってくる数字は

$c = (input\ number)^e \bmod{n}$

と考えられます．

　残るnさえ見つければ、復号できます．となると、mod演算の力の見せ所です...！ mod演算は大雑把に説明すると、余りのことでした．具体的に小さな値で説明すると、

$10 \bmod{8} = 2$

となります．つまり、0~7の値ですべての数字を表します．ではマイナスの値はどのように表せられるでしょうか．なんと、

$-1 \bmod{8} = 7$

となります！！！詳細な説明はGoogleでmod 数学とかでググってください．（説明めんどう...）

　ここまでで、-1がn-1になることがわかりました．あとは、Encrypted flag, D, nから復号するだけです．

$ nc 133.242.17.175 1337
Encrypted flag is: 8574265495326376630715344864118702269699156118364751300483334371118983366068335837878430692194643907630947760218074636257962213901840959279695171778233952421546225414267130705377041788556040425374281913702704126363017674911378922866975795108524827197944518379304446564136766368478442131132639926373420800112390754225415097241757980287552353646752237359721950559438294762549429323083064086759103892170016208312683627723372030448129192438463592881852579263558462628295396255591387527275622328216850681535962245066287633466061728308482282796879985854086150426339364856915080205049371087944085742585047633265078786916717
> -1
15542669559227225429825537324581227774031891481936836236023168265768560509534175413897898039939875309341780656581069256476153063968087844810314599683067761887287458414581491790878409323665908229753209802327406269329874867875899296307778465317869542704169327492799825878469046825297855569668076456765118516134730535748246251497708000239072261510836367562449392851385927337215223745929318252139726812616575352609129732978704075275309551532205839627157499897379612485885734926354947463132399491683701371211067204644701324764499164101507557096214031191342098432721010724037945643454866504810914319842027997822183833426928
> 
Bye
The D was 11294445810590008451256715894011877130636049863981565968908667859208720657125830750743450207578873334636815264492070773310043387985660245681773997822701971285230906503746417520618785810004504532306435504005987399035139855466710836433795285598947451084782032325512289357709536384149184028104314710422845174670617305707095050004395521134314125412593577026243869778911744982261668051428824513145971177432162816223685859285472240021048696838191250769292549473790421401957500586651833875804831485999431831427601391163986595878453821597916628888747151831289612576792460488564806552328452459557394329005245982294646297165825

$ python3
Python 3.5.2 (default, Nov 12 2018, 13:43:14) 
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from binascii import unhexlify
>>> enc_flag = 8574265495326376630715344864118702269699156118364751300483334371118983366068335837878430692194643907630947760218074636257962213901840959279695171778233952421546225414267130705377041788556040425374281913702704126363017674911378922866975795108524827197944518379304446564136766368478442131132639926373420800112390754225415097241757980287552353646752237359721950559438294762549429323083064086759103892170016208312683627723372030448129192438463592881852579263558462628295396255591387527275622328216850681535962245066287633466061728308482282796879985854086150426339364856915080205049371087944085742585047633265078786916717
>>> n_minus_1 = 15542669559227225429825537324581227774031891481936836236023168265768560509534175413897898039939875309341780656581069256476153063968087844810314599683067761887287458414581491790878409323665908229753209802327406269329874867875899296307778465317869542704169327492799825878469046825297855569668076456765118516134730535748246251497708000239072261510836367562449392851385927337215223745929318252139726812616575352609129732978704075275309551532205839627157499897379612485885734926354947463132399491683701371211067204644701324764499164101507557096214031191342098432721010724037945643454866504810914319842027997822183833426928
>>> n = n_minus_1 + 1
>>> d = 11294445810590008451256715894011877130636049863981565968908667859208720657125830750743450207578873334636815264492070773310043387985660245681773997822701971285230906503746417520618785810004504532306435504005987399035139855466710836433795285598947451084782032325512289357709536384149184028104314710422845174670617305707095050004395521134314125412593577026243869778911744982261668051428824513145971177432162816223685859285472240021048696838191250769292549473790421401957500586651833875804831485999431831427601391163986595878453821597916628888747151831289612576792460488564806552328452459557394329005245982294646297165825
>>> flag = pow(enc_flag, d, n)
>>> unhexlify(hex(flag)[2:])
b'ctf4b{f1nd_7he_p4ramet3rs}'

フラグゲット！！！ctf4b{f1nd_7he_p4ramet3rs}

[Crypto 393pts] Bit Flip

平文を1ビットランダムで反転させる能力を手に入れた！

　ソースコードも渡されます．ソースコードを読むと、問題文通りのRSAです． e = 3 は明らかにおかしい（通常はe = 0x10001）ので、low public exponet attack等をやってみますが、条件に合わないのでうまくいきません．

　うーん、これは困りました... いったんe = 3から離れてみましょう．

　ncしたとき、

$ nc 133.242.17.175 31337
11545705109146803081154196731091553481494291928457261149212388528068058378823269333768320005182187108983022445099553663343177812738205610210357260446050457617731702932090378720710803576264258475457572522292489169532629163257089936346472604268088528122978005890263575400712331754280140566518723346561592384959

というふうに、平文をランダムで1ビット反転したものの暗号文がもらえます．再度ncすると、違う場所が反転されたものの暗号文です．となると、1ビット反転後の平文をm'としたとき、m'1とm'2はほとんど同じ平文であることがわかります．

　RSAでbitがわかっている（今回はわかっているとは言えない）ときの攻撃といえば、Coppersmith's Attackです．なんか、今回の条件に合う攻撃なかったかな～と調べていると、

inaz2.hatenablog.com

　ありました！！！！Coppersmith’s Short Pad Attack & Franklin-Reiter Related Message Attack（長い）みたいです！！！攻撃条件は

二つの暗号文について平文の上位bitがnのbit数の (1-1/e²) 程度共通する場合、これらからそれぞれの平文を求めることができる。

みたいです．今回はe = 3、nのbit数が1023bitなので、平文の上位bitが967bit同じ平文m'1とm'2を用意しなければなりません．これはあまり難しくなくて、1bitしか変わらないので、いくつか暗号文を用意すれば上位bitがほとんど同じペアがあります．ただ、暗号文からどこのbitが反転しているかはわからないです．そのため10個程度暗号文を用意し、数値が近いもの同士で攻撃してみます．

def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1
    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()

    kbits = n.nbits()//(2*e*e)
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]  # find root < 2^kbits with factor >= n^0.5

    return diff

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]


if __name__ == '__main__':
    n = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331
    e = 3

    nbits = n.nbits()
    kbits = nbits//(2*e*e)
    print "upper %d bits (of %d bits) is same" % (nbits-kbits, nbits)

    # ^^ = bit-wise XOR
    # http://doc.sagemath.org/html/en/faq/faq-usage.html#how-do-i-use-the-bitwise-xor-operator-in-sage
    cs = [77806872332913639919230209971392238784617993613323608240759820467908361781292069393342282547351581556259586998986092213607990761433134090374312820694026772204652782705492033343505430039323127158238332166350733150021228707945218465461966055458055161585955918733260995686334094638272681504698713633622376505308, 56989538367235158070306311186976292179966897528478291741508067866076558453602047302097966694208295312681095728980453463065836403911062093169223760418437322965770764311509640241287759696024373113722137027468951246866660964543912817862578633166333098878995510302628735250428938293637106737039139535160299108113, 38904877077171263737628178288521508189937409452080551772429415381447030724554764139002760866443078904692197281533309765344183894882142747076974754239070945859011211448240209079404207383248263468302174482960469183459600520739134108565937096269114702664072319462367117303477702692144066942049118080262294258198, 18583489730966619030615979926193288458958202730544958951381254155250349562324597989826437296289617404778761642054183547194844953317251480423608095521453337512728025268903153005408483464432086619556754592849674435698214322639172504375579000690270700946296005084794493004273617912360198409988034062432904201443, 81779690030003209255009995980102852322918673284543406574532267172257453562542775941820716471921905724303767155906053394193722593095884543297184318525481682039383393411599467185668595266012433381398851647598176014943130868710424785320701066749455904911769968456600407617618999332917394004530335428836578511038, 32723890881319186547872779402620483902697729020200348166442392175021912171894118652683887146846612929006547793375263509134656509739561177352356684588019934405564505733524922144146700314897913117036840607504607821666469911969838394487387376073261438777475081050957502547204126815797206281111078395092049286587, 74515903266795492985898471025229269878024376884435233684330662967167738131179553721410985213658229983853042260704757838616925556197183464709236532593823846170499630895374282114622487171170087091856753282020369482187351762243468042340933214874709271883018014631321412057529269400452647011517326283977015327189, 50884193811664497731364349812345616105175266569747833161903539901598152530392727464246077616701699644190582339965644325919604108036097223534586827791663822181563764715514302285487273629970687924833993670021557569304506460830014722740930334310623881775573664519736313757433300737631028708325665330938763782184, 32723890881319186547872779402620483902697729020200348166442392175021912171894118652683887146846612929006547793375263509134656509739561177352356684588019934405564505733524922144146700314897913117036840607504607821666469911969838394487387376073261438777475081050957502547204126815797206281111078395092049286587, 32723890881319186547872779402620483902697729020200348166442392175021912171894118652683887146846612929006547793375263509134656509739561177352356684588019934405564505733524922144146700314897913117036840607504607821666469911969838394487387376073261438777475081050957502547204126815797206281111078395092049286587, 70349274946614957759744006616813137783981786796010483575643371633588262711107346355531982812397035546281065385276548490062296856185344260769924218825995217554937441693054306002310733683884013698358767818115213188542062367075206824218550649564035135625128570873259781498669780078490598700442802349177736369712, 14980967781796819388041767887889903216468297576583006138007297644760691492596305457996725733919525577152256022483859011858574079640555374613247881143820771398254213825665880164126364722955374272148086280616213121922743671360167002526131898166108921720900263044330025216410582216554968042705705297554547422768, 20084571405797864822888728924121156713191530288959443915037367599696984039639335435370481551716134617000168582476618945013400480262866044903717028607042509827672584798897176555204805945259386570000183369487279952176022447143620009290796257006795499399194469035408992268017445449883256724883866657842304577341, 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331]
    cs.sort()
    for i in range(len(cs)-1):
        c1 = cs[i]
        c2 = cs[i+1]
    try:
            diff = short_pad_attack(c1, c2, e, n)
            print "difference of two messages is %d" % diff

            m1 = related_message_attack(c1, c2, diff, e, n)
            print m1
            print m1 + diff
    except:
        pass

$ ./sage attack.sage
upper 967 bits (of 1023 bits) is same
difference of two messages is 0
32723890881319186547872779402620483902697729020200348166442392175021912171894118652683887146846612929006547793375263509134656509739561177352356684588019934405564505733524922144146700314897913117036840607504607821666469911969838394487387376073261438777475081050957502547204126815797206281111078395092049286587
32723890881319186547872779402620483902697729020200348166442392175021912171894118652683887146846612929006547793375263509134656509739561177352356684588019934405564505733524922144146700314897913117036840607504607821666469911969838394487387376073261438777475081050957502547204126815797206281111078395092049286587
difference of two messages is 0
32723890881319186547872779402620483902697729020200348166442392175021912171894118652683887146846612929006547793375263509134656509739561177352356684588019934405564505733524922144146700314897913117036840607504607821666469911969838394487387376073261438777475081050957502547204126815797206281111078395092049286587
32723890881319186547872779402620483902697729020200348166442392175021912171894118652683887146846612929006547793375263509134656509739561177352356684588019934405564505733524922144146700314897913117036840607504607821666469911969838394487387376073261438777475081050957502547204126815797206281111078395092049286587
difference of two messages is 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831589264307
16260765149986038884145173876068642724013617302097779293079362876653494069932815072038851668676222848467504538570853507159925860036819304291732134150397319327193122637750054910716746167965635612837962028769149915298230040116567157454495798898178036434538204980608594381468821524975316356796051708170
16260765149986038884145173876068642724013617302097779293079362876653494069932815072038851668676222848467504538570853507159925860036819304291732134150397319327193122637750054910716746167965635612837962028769149915298230040116567157454495798898178036434538204980608594381468821524975316356795816827146

　m'1とm'2が同じになってしまうペアがあったようですが、1つうまくいってます．ただ、これはどこかのbitが反転されたものなので、雑プログラムで復号します．

from binascii import unhexlify

m = 16260765149986038884145173876068642724013617302097779293079362876653494069932815072038851668676222848467504538570853507159925860036819304291732134150397319327193122637750054910716746167965635612837962028769149915298230040116567157454495798898178036434538204980608594381468821524975316356796051708170

for i in range(0, 30):
    r = 1 << i
    flag = m ^ r
    try:
        print("[+] {} : {}".format(i, unhexlify(hex(flag)[2:])))
    except:
        pass

　0~30（適当）で雑に調べてますが、特にエラーなく出力されたのでその中で1番うまくいっているのが、

[+] 28 : b'ctf4b{b1tfl1pp1ng_1s_r3lated_m3ss4ge} DUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMY\n'

でした．後ろにDUMMYが入っていたんですね．これでフラグがとれました！ctf4b{b1tfl1pp1ng_1s_r3lated_m3ss4ge}

終わりに

　初めにCryptoのWarmupからやったのですが、全然解けなくて死んでました... theoldmoonにヘルプをだして解いてもらいました... そのときは、Warmupすら解けないの終わりでは...？と思いましたが、結果、きちんと仕事を果たせてよかったです（ほんまか）．

　去年はCTFの存在を知っている程度のbabyで、linuxわからない！って感じで何も解けなかった記憶があります（笑）．そう考えるとCTFを初めて約1年でよくここまで成長したな～と思います．

　まだまだ、わからないことがたくさんあるので、今後も精進していきたいです．

　最後になりましたが、チームメンバー、運営・参加者の皆様お疲れさまでした．ここまで、読んでくださってありがとうございます．

yoshikingのがんばる日記

あたまよくないけどがんばります

SECCON Beginners CTF 2019 Writeup

チームメンバーのWriteup

[Crypto 363pts] Go RSA

[Crypto 393pts] Bit Flip

終わりに