HackTM CTF Quals 2020 Writeup

CTF writeup

この大会は2020/2/1 17:00(JST)～2020/2/3 17:00(JST)に開催されました。
今回もチームで参戦。結果は 516点で747チーム中132位でした。
自分で解けた問題をWriteupとして書いておきます。

Romanian Gibberish (misc)

問題はこうなっている。

https://en.wikipedia.org/wiki/Gibberish_(language_game)

HapackTM{Wepelcopomepe_Topo_HAPACKTMCTF_2020!}

"pa", "pe", "po"を外す。

HackTM{Welcome_To_HACKTMCTF_2020!}

Bad keys (crypto)

$ nc 138.68.67.161 60005
Starting key server from snapshot #8055 ...
Enter 'k' to generate the next key
> k
Your RSA keys:
((pub),(priv))
((e,n),(d,n ))
((65537, 137417688467756359797848792921596849649790768073161495314477575372798841766852293300511205481418653561628307984765315188339818877322283218342526622470383894798997710542319525493962602304814897519613411188823956663552829906542264398068578748695548563497144701693503515093113085117299532542465467990654323225983), (16229197380722862273759092683723081866569732286895493747563306733379053592252265897828047216475889628255841796269031837858769826364869800417644323937939960086359433302031065593401066479017927161654460166804930445040262208681486580993781132790515056274461396583334534502636207406119958551030720651252502007073, 137417688467756359797848792921596849649790768073161495314477575372798841766852293300511205481418653561628307984765315188339818877322283218342526622470383894798997710542319525493962602304814897519613411188823956663552829906542264398068578748695548563497144701693503515093113085117299532542465467990654323225983))
Enter 'k' to generate the next key
> k
Your RSA keys:
((pub),(priv))
((e,n),(d,n ))
((65537, 14887703973686489670472465065563898633902979110972415506228258615613225664543477842998048377000542542032179029133500397422244667148732787156029037693958076189341405050840371784217187528266056256197211543797286963428908255286673335510215856673653564142024030658368593520314167678786063673673739842242444328829), (-7375816108787808918787409680238555697456335028368148665207826555843963319988131621592438359290639116792694522131553540807526467455821976382335273584160464202671327941929290415426526848787261144705908855795849835428621110403530484803697924515080494159489498795519005544701091938984012084648432935991618102207, 14887703973686489670472465065563898633902979110972415506228258615613225664543477842998048377000542542032179029133500397422244667148732787156029037693958076189341405050840371784217187528266056256197211543797286963428908255286673335510215856673653564142024030658368593520314167678786063673673739842242444328829))
Enter 'k' to generate the next key
> k
Your RSA keys:
((pub),(priv))
((e,n),(d,n ))
((65537, 85067348166796819134140286846911380997120576879261347799893781779203363678458348245741474525610084074356037840061205888025565555103111583087513156825927006418088480057703183195760258461188350345472158519877466355998574793951858736607817735705990664873676427568078019830876054954931985472530872450143006952101), (-19732270729994434357343189963634997236953583620222637735233307453918390140530140379202006435117940981405320463930458396169562957850946828296937226453266735746753440572757291524173711755730548955628802393863052324436041141602477212519819503171521846464517849064876561966030777272275875601306500501037996633239, 85067348166796819134140286846911380997120576879261347799893781779203363678458348245741474525610084074356037840061205888025565555103111583087513156825927006418088480057703183195760258461188350345472158519877466355998574793951858736607817735705990664873676427568078019830876054954931985472530872450143006952101))
Enter 'k' to generate the next key

それぞれp, qを割り出してみる。

import random
from Crypto.Util.number import *

def factor_modulus(n, d, e):
    t = (e * d - 1)
    s = 0

    while True:
        quotient, remainder = divmod(t, 2)
        if remainder != 0:
            break
        s += 1
        t = quotient

    found = False
    while not found:
        i = 1
        a = random.randint(1, n-1)
        while i <= s and not found:
            c1 = pow(a, pow(2, i-1, n) * t, n)
            c2 = pow(a, pow(2, i, n) * t, n)
            found = c1 != 1 and c1 != (-1 % n) and c2 == 1
            i += 1

    p = GCD(c1 - 1, n)
    q = n // p

    return p, q

e = 65537
n = 137417688467756359797848792921596849649790768073161495314477575372798841766852293300511205481418653561628307984765315188339818877322283218342526622470383894798997710542319525493962602304814897519613411188823956663552829906542264398068578748695548563497144701693503515093113085117299532542465467990654323225983
d = 16229197380722862273759092683723081866569732286895493747563306733379053592252265897828047216475889628255841796269031837858769826364869800417644323937939960086359433302031065593401066479017927161654460166804930445040262208681486580993781132790515056274461396583334534502636207406119958551030720651252502007073

p, q = factor_modulus(n, d, e)
print('p =', p)
print('q =', q)

n = 14887703973686489670472465065563898633902979110972415506228258615613225664543477842998048377000542542032179029133500397422244667148732787156029037693958076189341405050840371784217187528266056256197211543797286963428908255286673335510215856673653564142024030658368593520314167678786063673673739842242444328829
d = -7375816108787808918787409680238555697456335028368148665207826555843963319988131621592438359290639116792694522131553540807526467455821976382335273584160464202671327941929290415426526848787261144705908855795849835428621110403530484803697924515080494159489498795519005544701091938984012084648432935991618102207

p, q = factor_modulus(n, d, e)
print('p =', p)
print('q =', q)

n = 85067348166796819134140286846911380997120576879261347799893781779203363678458348245741474525610084074356037840061205888025565555103111583087513156825927006418088480057703183195760258461188350345472158519877466355998574793951858736607817735705990664873676427568078019830876054954931985472530872450143006952101
d = -19732270729994434357343189963634997236953583620222637735233307453918390140530140379202006435117940981405320463930458396169562957850946828296937226453266735746753440572757291524173711755730548955628802393863052324436041141602477212519819503171521846464517849064876561966030777272275875601306500501037996633239

p, q = factor_modulus(n, d, e)
print('p =', p)
print('q =', q)

実行結果は以下の通り。

p = 12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129863163
q = 11340228631395703153203289700584583183108832246939459901831495144294115443808565971462649827019253999757788793971590022606697010599444452781890121322040141
p = 1228589774290646133402194788648441529244684712777228171063273217674759083989656078178171164001861483812271416585347892764476972223742639396962963935224109
q = 12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129864081
p = 7020080078732870012275762272027419319526223683777354425367603486401476812779364788848593675380044935338783635392741186184668167977412374828391262838582383
q = 12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129864747

以下の数値から次の素数が因数としてnが生成されているようだ。

12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129863163

さらに初めの1回目のnについて最大公約数を求めてみる。

$ nc 138.68.67.161 60005
Starting key server from snapshot #8055 ...
Enter 'k' to generate the next key
> k
Your RSA keys:
((pub),(priv))
((e,n),(d,n ))
((65537, 11411176369801108856291485937444160828271725510169664884401250925793437741426548291360502311480456779021690775940864909353759990756428970128937694336285797651385962726325976753344151400931971710251796227290459532029547338266445813361023485990666411190773505392316245156622890857894973388289433053721425505791), (4944256896056766209671682174644313759854798321357062484664508923033255384066226181873946375891466663062086016656496329798577424928201733917959546033128936925305036702866581504884054996140550393707276182730812428551255638580365434903599521667466330808762027001040433457798056660844122262765432385515492255649, 11411176369801108856291485937444160828271725510169664884401250925793437741426548291360502311480456779021690775940864909353759990756428970128937694336285797651385962726325976753344151400931971710251796227290459532029547338266445813361023485990666411190773505392316245156622890857894973388289433053721425505791))
Enter 'k' to generate the next key

$ nc 138.68.67.161 60005
Starting key server from snapshot #8055 ...
Enter 'k' to generate the next key
> k
Your RSA keys:
((pub),(priv))
((e,n),(d,n ))
((65537, 112458056813113429397087919281210953800139390285649148569759734945508789354486012990908137525935988864056845076283221312442664207354570210664525404618272819420257678253809603728032854419284998726621507152320820312557210978267143769531086105589054367061788465645401016011753117823441246552584637858466248181593), (-36681811503332862050773585157612441207036937091052716007381385384288896196512618821530482870621689029814351850034429741918104776853054723185003274097453615565526251267781773280351897631488970742182033823078293138470291513522771589531099564419125142122597356040991694500318746949232321715391266035323026723747, 112458056813113429397087919281210953800139390285649148569759734945508789354486012990908137525935988864056845076283221312442664207354570210664525404618272819420257678253809603728032854419284998726621507152320820312557210978267143769531086105589054367061788465645401016011753117823441246552584637858466248181593))
Enter 'k' to generate the next key

>>> from Crypto.Util.number import *
>>> n1 = 11411176369801108856291485937444160828271725510169664884401250925793437741426548291360502311480456779021690775940864909353759990756428970128937694336285797651385962726325976753344151400931971710251796227290459532029547338266445813361023485990666411190773505392316245156622890857894973388289433053721425505791
>>> n2 = 112458056813113429397087919281210953800139390285649148569759734945508789354486012990908137525935988864056845076283221312442664207354570210664525404618272819420257678253809603728032854419284998726621507152320820312557210978267143769531086105589054367061788465645401016011753117823441246552584637858466248181593
>>> GCD(n1, n2)
12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129863163L

やはり必ず以下の数値が因数に含まれている。

12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129863163

この素数から前の素数をさかのぼっていけば、暗号化したときのnの素因数の1つがわかるはず。

from Crypto.Util.number import *
import gmpy2

with open('RSA_PUB', 'r') as f:
    (e, n) = eval(f.read())

with open('flag.enc', 'r') as f:
    c = int(f.read())

base_p = 12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129863163

start_p = base_p - 100000
tmp_p = gmpy2.next_prime(start_p)
found = False
while True:
    if n % tmp_p == 0:
        found = True
        p = tmp_p
        q = n / p
        break
    tmp_p = gmpy2.next_prime(tmp_p)
    if tmp_p > start_p + 100000:
        start_p -= 100000
        tmp_p = gmpy2.next_prime(start_p)

print 'p =', p
print 'q =', q

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)
print flag

実行結果は以下の通り。

p = 12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580128178823
q = 191335851945837067856377662680848400296318974773300853031596930993909166558084000989878627579396244459141148723017644937657511582545081598962216442940353
HackTM{SanTa_ple@s3_TakE_mE_0ff_yOur_l1st_4f2d20ec18}
HackTM{SanTa_ple@s3_TakE_mE_0ff_yOur_l1st_4f2d20ec18}

RSA is easy #1 (crypto)

フラグを1文字ずつRSA暗号化しているので、ブルートフォースで復号する。

with open('c', 'r') as f:
    lines = f.readlines()

(e, n) = eval(lines[1])
flag_c = eval(lines[4])

flag = ''
for c in flag_c:
    for code in range(32, 127):
        if pow(code, e, n) == c:
            flag += chr(code)
            break

print flag

HackTM{why_ar3_MY_pR1va7es_pu8l1C_??}

RSA is easy #2 (crypto)

1文字ずつRSA暗号化しているが、nがわからない。暗号化した数値の配列は1111個の要素を持っている。こんな長いフラグではないだろうから英語の文章になっているはず。
もしかしたらRSA暗号の問題に見えて、換字式暗号の問題か。。。1文字ずつ暗号化しているので、それをアルファベットに置き換える。31種類あるので、記号も使用されていることを考慮して、スペースから推測する。quipqiupを使って、調整しながら、復号する。

import string

with open('c', 'r') as f:
    lines = f.readlines()

flag_c = eval(lines[4])

dic = {
20208833413145256771572368688664189468143545391164156105460199405734708819434076552216759462791005323959520084836115140504630769338040681414876273881508073569978297202819424741264124574247314460725471331318820764161255759739403546471531796892912689444815674366578876801858606344288032682809803593429599353582: ' ',
12932315605361356260109350737202295649066381035837249252185795202913980480440863417983883037159810577739986004162343142150811156736478717833534910573828843843135123757197342268856313199793884733585941943828474996180460900240457279087457908434717560236156491751130556115885434115169341757101655831937772066303: '.',
39071839511948638988080907036852746654085273366404837973213329692814484554408908523546999438831321352816110395822192272922701572846039352688552458816923896373772472819785936751685465282644216513301671688378689515602296293965301386883552780271126801778759956341143215735911106078099952795281272294184101222894: ',',
47570760099332538630074246588266937941307517820515142582135658748192399272005539496578959306267521195254022986091052760574620123103280649808061816984656151624030812710123783651478012545264847339309664114861788542619162083048255751820685971177031319072241032895991001430158963380558156843892347920250300986171: '\'',
32673744615799712487218586784858666657615496658878295924699304141157435241805321678825497057203170526047413088723755930727839423037832480520297361079311603101279858983310265841651031957166707800564192379099456051456890378670008176632913201998572911894331423107676669652519124282681545581828946130363768378027: '&'
}

chars = string.letters

index = 0
enc = ''
for c in flag_c:
    if c not in dic:
        dic[c] = chars[index]
        index += 1
    enc += dic[c]

print enc

調整ながら実行した結果は以下の通り。

abcd e afg ed hijjckc ed lbc cfmjn o&g, e pcqegcp abfl e rcjecqcp afg f rmejjefdl cdhmnsleid ghbctc. f getsjc sgcupimfdpit dutrcm glmcft afg fppcp li lbc sjfedlcvl glmcft li hmcflc hesbcmlcvl. lbeg aiujp gcctedkjn lbafml fdn wmcxucdhn fdfjngeg iw lbc hesbcmlcvl, fdp aiujp rc udhmfhyfrjc cqcd li lbc tigl mcgiumhcwuj kiqcmdtcdl edlcjjekcdhc fkcdhecg. e wcjl gi gtuk friul tn fhbecqctcdl. ncfmg jflcm, e peghiqcmcp lbeg gftc ghbctc ed gcqcmfj edlmipuhlimn hmnslikmfsbn lcvlg fdp lulimefj sfscmg. bia dehc. ilbcm hmnslikmfsbcmg bfp lbiukbl iw lbc gftc ghbctc. udwimludflcjn, lbc ghbctc afg smcgcdlcp fg f getsjc bitcaimy fggekdtcdl id bia li ugc cjctcdlfmn hmnslfdfjnleh lchbdexucg li lmeqefjjn hmfhy el. gi tuhb wim tn rmejjefdl ghbctc. wmit lbeg butrjedk cvscmecdhc e jcfmdcp bia cfgn el eg li wfjj edli f wfjgc gcdgc iw gchumeln abcd pcqegedk fd cdhmnsleid fjkimelbt. tigl scisjc pid'l mcfjezc bia wecdpegbjn pewwehujl el eg li pcqegc fd cdhmnsleid fjkimelbt lbfl hfd aelbglfdp f smijidkcp fdp pclcmtedcp fllfhy rn f mcgiumhcwuj issidcdl. bcmc eg lbc wjfk. abcd el hitcg li hmnsli im hfmscl dcqcm mijj nium iad

復号結果は以下の通り。

when i was in college in the early j&s, i devised what i believed was a brilliant encryption scheme. a simple pseudorandom number stream was added to the plaintext stream to create ciphertext. this would seemingly thwart any frequency analysis of the ciphertext, and would be uncrackable even to the most resourceful government intelligence agencies. i felt so smug about my achievement. years later, i discovered this same scheme in several introductory cryptography texts and tutorial papers. how nice. other cryptographers had thought of the same scheme. unfortunately, the scheme was presented as a simple homework assignment on how to use elementary cryptanalytic techniques to trivially crack it. so much for my brilliant scheme. from this humbling experience i learned how easy it is to fall into a false sense of security when devising an encryption algorithm. most people don't realize how fiendishly difficult it is to devise an encryption algorithm that can withstand a prolonged and determined attack by a resourceful opponent. here is the flag. when it comes to crypto or carpet never roll your own

"&"は正しいかわからないが、フラグには影響ないので、よしとする。

HackTM{when_it_comes_to_crypto_or_carpet_never_roll_your_own}