De1CTF 2019 Writeup

この大会は2019/8/3 10:00(JST)~2019/8/5 10:00(JST)に開催されました。
今回もチームで参戦。結果は740点で724チーム中84位でした。
自分で解けた問題をWriteupとして書いておきます。

We1come (Misc)

Telegramに入ると、フラグが書いてあった。

de1ctf{We1c0me_2_De1CTF}

xorz (Crypto)

以下のような条件になっているXOR暗号の問題。

keyの長さ38未満
saltの長さ14
keyとsaltのxorがXORの鍵となっている。
→全体の鍵の長さは14の倍数
encの長さは600

鍵の先頭4文字を総当たりで復号し、printableなものを出力してみる。
以下は調査のためのコード。最終的にはencの長さからもj=15の時が怪しく、その場合に絞っている。

from itertools import *
from string import *

def is_letters(s, head):
    chars = letters + ' '
    for c in s:
        if c not in chars:
            return False
    if head:
        #if s[0] not in uppercase:
        if s[0] != 'T':
            return False
    return True

def decrypt4(ct, salt, key):
    pt = ''
    for i in range(4):
        code = ord(ct[i]) ^ ord(salt[i]) ^ ord(key[i])
        pt += chr(code)
    return pt

enc = '49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c'.decode('hex')

salt = 'WeAreDe1taTeam'

for c in product(printable, repeat=4):
    key = ''.join(c)
    pt_head = decrypt4(enc[0:4], salt, key)
    if is_letters(pt_head, True):
        #for j in range(1, 76):
        for j in range(15, 16):
            found = True
            pt_parts = []
            for k in range(0, len(enc), 14 * j):
                pt_part = decrypt4(enc[k:k+4], salt, key)
                pt_parts.append(pt_part)
                if is_letters(pt_part, False) == False:
                    found = False
                    break
            if found:
                print key, pt_parts, j

この結果でもまだかなり多くのパターンがあるが、一つ一つ見たときに以下の復号結果が正解の可能性が高いと推測した。

W3lc ['In f', 'ne d', 'ng t'] 15

この結果をもとに、keyは30バイトで、W3lcの次はomeのリート文字が来ると推測し、試しながら復号する。
W3lc0m3まで指定したときの復号結果は以下の通りとなる。

In fait***********************th mine***********************a thous***********************s my he***********************y despi***********************ew is p***********************mine ea***********************ne deli***********************g to ba***********************ste, no***********************nvitedT***********************h thee *********************** nor my***********************e one f***********************ng thee***********************e liken***********************heart`s***********************h to be***********************r I cou***********************t makes***********************

keyの長さは合っていそうなので、このまま継続して、英単語を推測しながら復号する。さらに途中まで復号すると、ここの文章になることがわかるので、参考にする。
www.poetryfoundation.org
最終的なコードは以下の通りとなる。

ct = '49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c'.decode('hex')

salt = 'WeAreDe1taTeam'
#key = 'W3lc0m3***********************'
key = 'W3lc0m3tOjo1nu55un1ojOt3m0cl3W'

pt = ''
for i in range(len(ct)):
    if key[i%len(key)] == '*':
        pt += '*'
    else:
        code = ord(ct[i]) ^ ord(salt[i%len(salt)]) ^ ord(key[i%len(key)])
        pt += chr(code)

print pt

flag = 'de1ctf{%s}' % key
print flag

これで復号でき、keyもわかり、フラグとなる。実行結果は以下の通り。

In faith I do not love thee with mine eyes,For they in thee a thousand errors note;But `tis my heart that loves what they despise,Who in despite of view is pleased to dote.Nor are mine ears with thy tongue`s tune delighted;Nor tender feeling to base touches prone,Nor taste, nor smell, desire to be invitedTo any sensual feast with thee alone.But my five wits, nor my five senses canDissuade one foolish heart from serving thee,Who leaves unswayed the likeness of a man,Thy proud heart`s slave and vassal wretch to be.Only my plague thus far I count my gain,That she that makes me sin awards me pain.
de1ctf{W3lc0m3tOjo1nu55un1ojOt3m0cl3W}
de1ctf{W3lc0m3tOjo1nu55un1ojOt3m0cl3W}

Baby Rsa (Crypto)

以下のような流れで復号できれば、全部の情報を使わなくても、フラグを求められる。

1. Hastad's broadcast Attackでpを求める。
2. Low Public-Exponent Attackでe2を求める。
3. e2がp*q2と互いに素にならないため、Low Public-Exponent Attackを使いながら、段階を経て復号する。

この流れをコードにすると、以下のようになる。

import functools
import gmpy
from Crypto.Util.number import *

def chinese_remainder(n, a):
    sum = 0
    prod = functools.reduce(lambda a, b: a*b, n)
    for n_i, a_i in zip(n, a):
        p = prod // n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod
 
def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a // b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1

def inv_pow(c, e):
    low = -1
    high = c+1
    while low + 1 < high:
        m = (low + high) // 2
        p = pow(m, e)
        if p < c:
            low = m
        else:
            high = m
    m = high
    assert pow(m, e) == c
    return m

#### solve p ####
n =  [20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423L, 31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421L, 29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303L, 25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791L]
c =  [19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569L, 15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031L, 18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446L, 2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797L]
e = 4
a = chinese_remainder(n, c)
for val_n, val_c in zip(n, c):
    assert a % val_n == val_c
p = inv_pow(a, e)

f = lambda m, e, n, c: pow(m, e, n) == c
assert(sum(map(f, [p] * 4, [4] * 4, n ,c)) == 4)

print 'p =', p

#### solve e2 ####
ee2 = 3
ce2 = 13908468332333567158469136439932325992349696889129103935400760239319454409539725389747059213835238373047899198211128689374049729578146875309231962936554403287882999967840346216695208424582739777034261079550395918048421086843927009452479936045850799096750074359160775182238980989229190157551197830879877097703347301072427149474991803868325769967332356950863518504965486565464059770451458557744949735282131727956056279292800694203866167270268988437389945703117070604488999247750139568614939965885211276821987586882908159585863514561191905040244967655444219603287214405014887994238259270716355378069726760953320025828158
tmp = 864078778078609835167779565982540757684070450697854309005171742813414963447462554999012718960925081621571487444725528982424037419052194840720949809891134854871222612682162490991065015935449289960707882463387
n = 15911581555796798614711625288508309704791837516232122410440958830726078821069050404012820896260071751380436992710638364294658173571101596931605797509712839622479368850251206419748090059752427303611760004621378226431226983665746837779056271530181865648115862947527212787824629516204832313026456390047768174765687040950636530480549014401279054346098030395100387004111574278813749630986724706263655166289586230453975953773791945408589484679371854113457758157492241225180907090235116325034822993748409011554673180494306003272836905082473475046277554085737627846557240367696214081276345071055578169299060706794192776825039

c2 = ce2
while True:
    m = gmpy.root(c2, ee2)[0]
    if pow(m, ee2, n) == ce2:
        break
    c2 += n

e2 = m - tmp
assert(pow(e2 + tmp, ee2, n) == ce2)

print 'e2 =', e2

#### solve flag ####
q2 = 114401188227479584680884046151299704656920536168767132916589182357583461053336386996123783294932566567773695426689447410311969456458574731187512974868297092638677515283584994416382872450167046416573472658841627690987228528798356894803559278308702635288537653192098514966089168123710854679638671424978221959513
c2 = 7395591129228876649030819616685821899204832684995757724924450812977470787822266387122334722132760470911599176362617225218345404468270014548817267727669872896838106451520392806497466576907063295603746660003188440170919490157250829308173310715318925771643105064882620746171266499859049038016902162599261409050907140823352990750298239508355767238575709803167676810456559665476121149766947851911064706646506705397091626648713684511780456955453552020460909638016134124590438425738826828694773960514221910109473941451471431637903182205738738109429736425025621308300895473186381826756650667842656050416299166317372707709596

c = c2 % q2
e = e2 / 2
phi = q2 - 1
d = inverse(e, phi)
m1 = pow(c, d, q2)

m0 = m1
c1 = m1
while True:
    m = gmpy.root(c1, 2)[0]
    if pow(m, 2, q2) == m0:
        break
    c1 += q2

flag = m
assert(c2 == pow(flag, e2, p * q2))

flag = long_to_bytes(flag)
print flag

実行結果は以下の通り。

p = 109935857933867829728985398563235455481120300859311421762540858762721955038310117609456763338082237907005937380873151279351831600225270995344096532750271070807051984097524900957809427861441436796934012393707770012556604479065826879107677002380580866325868240270494148512743861326447181476633546419262340100453
e2 = 381791429275130
de1ctf{9b10a98b-71bb-4bdf-a6ff-f319943de21f}
de1ctf{9b10a98b-71bb-4bdf-a6ff-f319943de21f}