WhiteHat Contest 13 Writeup

CTF writeup

この大会は2017/5/27 11:00(JST)～2017/5/28 11:00(JST)に開催されました。
今回もチームで参戦。結果は1800点で108チーム中8位でした。
自分で解けた問題をWriteupとして書いておきます。

Da Nang (Cryptography 200)

makefile.pycファイルとn, c1～c4の値が与えられている。
EasyPythonDecompilerでmakefile.pycをデコンパイルすると、以下のようなコードで暗号化していることがわかる。

# Embedded file name: /root/Desktop/ctf-2017/rade/makefile.py
from FLAG import *
from Crypto.Util.number import *
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e1 = 17
e2 = 23
m1 = pow(flag, e1, n)
m2 = pow(flag, e2, n)
c1 = pow(m1 + 12345, e1, n)
c2 = pow(m1 + 56789, e1, n)
c3 = pow(m2 + 12345, e2, n)
c4 = pow(m2 + 56789, e2, n)

まず、Franklin-Reiter Related Message Attackでm1とm2を求める。

# related_message_attack.sage
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]

n = 23992456508721632904544057999056395984840598682551527471151904763246778638836805311058576074076544471814362118450963752614808101805018226501728749753154687251596663180454809994272928278066817153483685668132338944992849111855590973474678454159123639456555256485147196164078477717189520027988101925788303558976065942012105491523422884349644306896086216721825961334666043695121350988761613913914655313225263251356627080558127266206207253980892813908459449433940028268804981985006285644508736389967109173883994849116220035021283230523958640143355551140077459561176550844398278642511471910168765368624465988996082307992457
c1 = 20373828497176435167633953604896280749084861536083536617122139289929021045377176745113967394233342868062933415554192920963948057887324013008257380015103546511196207444982065505097904316167335975881412955740451727799394577357107415462104942067847048630173382510001061068806873459709567970640047451719077689284250663779574472232440594570502056709748603086893912068708152949459839465110567129133452824619222918019880393381073202052633467737917229789195417254877277542398992729106705037414050409175283815504552780234997208287185820010853470529752628470226853313501197054312938111140137899570545855875031148908922559079288
c2 = 4360293477491071631082413589399984151934700148049881396354060511784164719699104502640364063839372357371432182276578283932647249629707984639755245731994004982047010862474568253438883825981211552726455647610616600152683140602219777227764342827766552684058977170125324805316413550680703753463380261978903747369677517090549750490497714726106808405188795507741435252228742048791254891796083781713724953974101730953449734214103419451007355326070889428042830527374106171411884042865409718813225704924308910578917985370161732700040769553579304781551439507813917217693054553136139858632877393572913681604198562756394542739717
c3 = 4345261358659519189634881349240932351623603440440060460588285817392306152201826610576491755629698765088135761317793967803519010356869269204503397215039512744495117601932620637450095192646479479541571697381615227131485964855439316795397514445542660502760126364064850197352955455820341422106740318181122113707487426652989875585231637716536188004952356846847687782788196021954904944243050038759261831381697585862182084930662578928342538660648403902072793943235882313263403348511364765676275877687747514403142706712995406077875195587485333137738286810493929324782535392363155178660765334428891921464976278013274433592459
c4 = 11163192691864487842504791707572292045010440994593022973064948393324184598662086767886111478358067883324039072186651857397731078118781186686459647088206129240315423019956385054334592265029781917246602461962626683725203283354094411740566113019140776580459728655850754495232498348144806199874330892136766891492831287879346899778473534258469040357585649045269842028785546606058644151580331160754603828262995696611984149905299109630697269974668616156412842759609194334129212734919638779629261074770920807952993453659743525451175541328430753432209789806184520128139906770561431423993324872179142853918272022140840732281811
e1 = 17
e2 = 23

diff = 56789 - 12345
m1 = related_message_attack(c1, c2, diff, e1, n) - 12345
print 'm1 =', m1
m2 = related_message_attack(c3, c4, diff, e2, n) - 12345
print 'm2 =', m2

以下の通り、m1とm2を算出することができた。

m1 = 19940708887759698510138918424450978321561069230659682994645881255326771243148984534641521276833375122703596885707253454427683279897828170878752612038114916127076079372073980486084679133895997151796999085785875836411210710632349923692939803228793799180641695640367708674225359974103741571982122048082035653192117956305119783207139142492158377892592169456609523577779421428356103367766774789680587969032302667151786683889761811812272622064633882550675704607685899902862193827181388950179113885788804816791465827265522578945146174815051717419478773041589332193216487854230882177980058898250512045181287339603392316697829
m2 = 2970132540488149339645289732236094260249062136537890152544022014880742014613667308336012839589875906076626365709335806489861391924524036985675821291443068706330596605582227620510725657401246096937011593605357908632053035718719770934145713092502591072370696481368118792860212738265793148704385419081990887592837829524490105986239282282260211257709359015566779069639346641105169115995195678357307965665965863966691547051261296196880300064216255207531200236387931460445195365540532178913046683294419159294042199243485508880751463979557947263693533936834072139357019316229736030987782295309538167642041408183532003721823

次にCommon Modules Attackでflagを求める。

import gmpy

def commom_modules_attack(c1, c2, e1, e2, n):
    gcd, s1, s2 = gmpy.gcdext(e1, e2)
    if s1 < 0:
        s1 = -s1
        c1 = gmpy.invert(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = gmpy.invert(c2, n)
 
    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    x = (v*w) % n
    return x

n = 23992456508721632904544057999056395984840598682551527471151904763246778638836805311058576074076544471814362118450963752614808101805018226501728749753154687251596663180454809994272928278066817153483685668132338944992849111855590973474678454159123639456555256485147196164078477717189520027988101925788303558976065942012105491523422884349644306896086216721825961334666043695121350988761613913914655313225263251356627080558127266206207253980892813908459449433940028268804981985006285644508736389967109173883994849116220035021283230523958640143355551140077459561176550844398278642511471910168765368624465988996082307992457
e1 = 17
e2 = 23
m1 = 19940708887759698510138918424450978321561069230659682994645881255326771243148984534641521276833375122703596885707253454427683279897828170878752612038114916127076079372073980486084679133895997151796999085785875836411210710632349923692939803228793799180641695640367708674225359974103741571982122048082035653192117956305119783207139142492158377892592169456609523577779421428356103367766774789680587969032302667151786683889761811812272622064633882550675704607685899902862193827181388950179113885788804816791465827265522578945146174815051717419478773041589332193216487854230882177980058898250512045181287339603392316697829
m2 = 2970132540488149339645289732236094260249062136537890152544022014880742014613667308336012839589875906076626365709335806489861391924524036985675821291443068706330596605582227620510725657401246096937011593605357908632053035718719770934145713092502591072370696481368118792860212738265793148704385419081990887592837829524490105986239282282260211257709359015566779069639346641105169115995195678357307965665965863966691547051261296196880300064216255207531200236387931460445195365540532178913046683294419159294042199243485508880751463979557947263693533936834072139357019316229736030987782295309538167642041408183532003721823

flag = commom_modules_attack(m1, m2, e1, e2, n)
flag_str = ('%x' % flag).decode('hex')
print flag_str

この結果は以下の通り。

common_modulus_and_franklin_reiter_related_message

$ echo -n common_modulus_and_franklin_reiter_related_message | sha1sum
4111c011bc640806ef98a32a5caaf9d169a960a0  -

WhiteHat{4111c011bc640806ef98a32a5caaf9d169a960a0}

Ha Long bay (Cryptography 250)

以下のコードと、n, e, C1～C3の値が与えられている。

from Crypto.Util import number

from secret import M, flag

p = number.getPrime(512)
q = number.getPrime(512)
n = p * q
e = 3

assert (len(flag) < 18),"Fail!"

fsplit = len(flag)/3

m1 = M + chr(number.getRandomRange(32, 128)) + flag[:fsplit]
m2 = M + chr(number.getRandomRange(32, 128)) +  flag[fsplit:2*fsplit]
m3 = M + chr(number.getRandomRange(32, 128)) +  flag[2*fsplit:]

m1 = int(m1.encode('hex'),16)
m2 = int(m2.encode('hex'),16)
m3 = int(m3.encode('hex'),16)

C1 = pow(m1, e, n)
C2 = pow(m2, e, n)
C3 = pow(m3, e, n)

Coppersmith's Short Pad Attackで平文の差を求めながら、Franklin-Reiter Related Message Attackでm1～m3を求める。

# coppersmiths_short_pad-and-related_message_attack.sage
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]

n = 103812409689464886276475047044770609297885893720146571798654593885477457188425375786047017735691464865799751262776976174291152757506033948402223696021505470811665108707476725788296289255777914656800454451779117367605227364391483323666809650532860469176398816220707851639905500304208833022438234033264200398959
e = 3

C1 = 9317106922634505445328279149755295612464875825943780841886193649700131610057100771444165757592479299555845021862440454968502065319770337331674061960123779876709748994547507057835826773522733671492329400557540100987018908395372213360970889608191940631081957498661950679566048064234326337242245437800870328713
C2 = 9314352234311777268152500810432217195086739647228997430466360767070638972017377674642639833356580951663634114522574738957708645348438979256455824440476178459296267056062724307782801856615506577790281367843133061096735566462588088807072141910079117362448136849082448630141871675817981866725491776400151339928
C3 = 102298788718908831383454512674839558060033746080468660252243145800572734468521296602058538109452538907204027081338987796558296639830757629468491322438048912956916198524821066676689795698612028521062296901313097979278633376983280108123961097977187251599033620058543603046291262367128490175209233898073639549204

diff = short_pad_attack(C1, C2, e, n)
m1 = related_message_attack(C1, C2, diff, e, n)
msg1 = ('%x' % m1).decode('hex')
m2 = m1 + diff
msg2 = ('%x' % m2).decode('hex')

diff = short_pad_attack(C2, C3, e, n)
m3 = m2 + diff
msg3 = ('%x' % m3).decode('hex')
print msg1
print msg2
print msg3

この結果は以下の通り。

ab688786fce01806bea4f1812740c15703837b12_part of flag is !uozt_
ab688786fce01806bea4f1812740c15703837b12_part of flag is \ficm_
ab688786fce01806bea4f1812740c15703837b12_part of flag is l41t0r

このことから以下のことがわかる。

flag = 'uozt_ficm_41t0r'

$ echo -n uozt_ficm_41t0r | sha1sum
a1ac8b83a8c8495b94007c2745596206d431748f  -

WhiteHat{a1ac8b83a8c8495b94007c2745596206d431748f}