IJCTF (2021) Writeup

#1. はじめに
　2021/07/24(土) 16:30 JST ～ 2021/07/25(日) 16:30: JST で、IJCTF 2021 にチーム「N30Z30N」としてソロ参加し、2823 点（得点を得た 132 チーム中 14 位）を獲得しました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/429434/f4d6b65a-2146-1f8e-e467-e2610f7f9ce0.png)
　途中温度管理と体調管理に失敗してヘロヘロになりましたが、すぐに回復して最後には楽しくプレイできたのでヨシ！としましょう。
　以下、解けた問題の Writeup です。
※2021/07/26 19:30 一部修正

#2. Writeup
##2-0. Sanity (Reverse, 100点)
>Just testing your sanity

　ReverseEngineering にカテゴライズされていますが、いわゆる Sanity Check 問題です。
　表層解析（strings）で得られる「IJCTF{simple_sanity_check_for_babies}」はフェイク。
　IDA Free 版で正当ルートと誤答ルートのアドレス（0x127E、0x128c）を把握し、以下のように「angrで殴って」フラグを得ました。

```
import angr
p = angr.Project("./sanity")
state = p.factory.entry_state()
sim = p.factory.simulation_manager(state)
sim.explore(find=(0x400000+0x127E,),avoid=(0x400000+0x128c,))
if len(sim.found) > 0:
  print(sim.found[0].posix.dumps(0))
```

**IJCTF{you_did_not_fall_for_it_right?}**


##2-1. Discrete Log (Crypto, 775点)
>This is unique discrete log answering service.

　指定されたサーバに接続すると、RSA の公開鍵と暗号文（これらは動的に変わる）が与えられた後、離散対数計算をしてくれるサービスに移ります。
　このサービスを使い、公開鍵の Mod として得られた数（$n$）と 適当な $a$ に対し、 $a^{e}$ mod $n$ を base、$a$ を number に指定すれば秘密鍵 $d$ をリークできます。（以下の例では $a=2$）

```
This is service for answering discrete log.
Mod: 5272879985315806480750829848227667078673597426524903989629867291289837202205895105729911030263049767652853040507336730464666448862971166047831422338422763836267673154819009497111448320964677269956421026510801870691884038250252644717112426369042214937218765432467001593126986475212643411723960337823410974583878084993
Here is RSA encrypted flag.(e=65537)
2078051323742198497947676697897248201281731730453580916706850881187365450454406000736694844163879816588323719439348211479031979071841177838207999417896928702373445832007257730209054684989592862856081522430104659043389221295572865603425821572477337892146178569516241993151183556529368415825210776927087538827611890377

base: 2412068478897303550419994071388717578085134969863519524730943382066607030110028947817763899368509231398921628181846186324277555833025734508354445443090803702908835610624160278401860781574732697766646417959891374052983950662501351935914065877522992455234939026057391008959538840762309629376533377691087166357625671731
number: 2
Here is the discrete log: 541190887914106112467315516030691099755831867334784422330062443121612065560491835584360690069188462427589239314777919609847549754745800821226758355728835939062912951366312686162569171537159591324783308378689985888601000205620379990180392507159230270191232229079466226169658085227167865177579928853810207348416772899
```

あとは RSA の復号処理をすれば Ok。

```python:solve.py
from Crypto.Util.number import *

n = 5272879985315806480750829848227667078673597426524903989629867291289837202205895105729911030263049767652853040507336730464666448862971166047831422338422763836267673154819009497111448320964677269956421026510801870691884038250252644717112426369042214937218765432467001593126986475212643411723960337823410974583878084993
e = 65537
c = 2078051323742198497947676697897248201281731730453580916706850881187365450454406000736694844163879816588323719439348211479031979071841177838207999417896928702373445832007257730209054684989592862856081522430104659043389221295572865603425821572477337892146178569516241993151183556529368415825210776927087538827611890377

# discrete_log(base=2**65537, number=2)
d = 541190887914106112467315516030691099755831867334784422330062443121612065560491835584360690069188462427589239314777919609847549754745800821226758355728835939062912951366312686162569171537159591324783308378689985888601000205620379990180392507159230270191232229079466226169658085227167865177579928853810207348416772899

pt = long_to_bytes(pow(c,d,n)).decode()
print(pt[pt.find("IJCTF{"):pt.find("}")+1])
```

**IJCTF{5257c399904eff4833fc2de85b778b8a}**


##2-2. Square Sum (Crypto, 949点)
>Factoring problem is really hard. So I give a hint: square sum of half primes. Please find the flag.

```python:problem.py
from Crypto.Util.number import getPrime, inverse, bytes_to_long
from Crypto.Random.random import randint
from secret import MSG, FLAG


p = getPrime(1024)
q = getPrime(1024)
n = p * q

n2 = n**2
halfpq_sqr_sum = (p//2)**2 + (q//2)**2

k = randint(1, n-1)
g = 1 + k*n
r = randint(2, n2-1)

cmsg = (pow(g, bytes_to_long(MSG), n2) * pow(r, n2, n2)) % n2
c = (bytes_to_long(FLAG) * pow(r, n, n2)) % n2

print('n2='+str(n2))
print('halfpq_sqr_sum='+str(halfpq_sqr_sum))
print('cmsg='+str(cmsg))
print('c='+str(c))
```

```python:output.txt
n2=303520029249457721712088032629157671188675957478999814001107946377897435098262416944078032743694224547812111876508629629098790706348564683510627437608561667668817082232066690156773182947457415470637661555594387660242481075809061863866878134857767064271020275925358862373499666674028571177472256983693456175513694920187605044808723618380459789773493111510245511524263712883363099195516392023821523383273803607532258960986269523229557484356691226627296549458770890488302153036171491536959410916079515480053813267273641384674290430132960320985260531094724351210760834427441063392448845773608652498658579592730319172250637383076619273369963514086477217760274026803102575002211426718751927101891471494221058041179582203541771830433523526001577817599554252231872769532980390483401226639528096938277398399935682866324784993115812281877591865430215134442904551109441541036428784450911307551504003791948952027070850252232846043561327951083360866399333467139115782229855840846646026182204713128402629095939971393271042355316329494426040959059666926611479882720948473312355005677824274551575679913205670022022017139399175510998237850213737165974646339820009635040028632254754412047567426260382111848392850835481772030875035608845098368736718689
halfpq_sqr_sum=9472622129700199703245586196664170084403806786939405819609832782578112766576428480777927359491256761393588992261088804683630755557509473029147106633909601585974763553680654431838374713192695971152635135654980642968043058123569343691081887394840682085558030205578048546258148505272998984973693174088527063719679039240127298660482089717632821831294015315634267021396765367208053481029040950107066330391869209058343986685994748025768502912822369180563838868099092781901052919510720948179559741776416837917783632982451736331078296715767630096860173482291944176969440690386874499002706015031896162301715990323012706805065
cmsg=103078286643622880447473687471766764943564559811909431666893450054168818307349486985249638958378791065494084728451034371725501517686576282043339068765538253257675113627273797306564684365323509359273378294002601649860804748728163025522075672245295550880060720735463310260935029330499002606032562798724954111417118887527073957993508089754394967659543003785760047941879904675059060008485376318332423664374757995851806458605666638976841133899950278214115072866022244614110580100352950200691110948074551191407363470332793295773273747237585817004577206834980715049990997687288385068292724282066219625651831484886243730221023243574538535723396702634705817852703892641398427064494429830352214499320005058534474284577134432341253340519635081380378045892077000915627548861547061501696012768786270148594424943366660662587186418716670250433370555760184571143569773295737850383542649898270826382659942188410185848934468448568325496582525158048118061659983332451282069426273006110854670823360391164278996722155588697598627131803289512431866077055012911415395954770914537654639608929010542439756174537575923529600976400363945111089267192377586187238410504823191760221711696006651813981609780080767483863025507048248680195946925116086994713836313403
c=240819054139924192908276790404232331564539338066363967597355786532131090443403077278934264677782549578055871874639814497554138070603843470651529113660894021443057595391213699869840820555076709709812961373461750130612453785640822249347659164866017931889613080220570111764428471836538389725220257679376309813972857596742069449014122286177227320041653912468408726067139524231446702068292851152761999746103029142674572600075554585602575858028536948546991047817318676231622316199368535515883188272917775993105890398456057174036933873324756054332572569380343179450564438637126650504362820450286638292251182022086719737414761084603628504362175295748323721068857285078233340896776610403227874250072420794722246884387488198976386566266870301419765724246635936193987658699901284391726429640605754046472825878500017779396277376213443347956951870554421838859114868247676278966446582371758603658584495387466611294920606637857755221756257214625128936810241588259047215874829610442603034882068648615080256023583472836142327431962452607719206361748849195548395481842814703649891102211953579454296662259004591314057576449118621217086325140123543677458167848297604521746504718023238069208215956158087066756140657191702426263476717009016863723080567809
```

　上のように、問題のスクリプトと出力結果が与えられます。halfpq_sqr_sum から $p+q$ を計算できるので、$p$ と $q$ は容易にリークできます。ここで、$\phi(n) = (p-1)(q-1)$ を計算しておきます。
　次に、m := bytes_to_long(MSG) とおくと、pow(g, m, n2) = 1 + k*m*n (mod n2) であり、さらにそれを x 乗すると 1 + k*m*n*x (mod n2) となることから、cmsg の式の両辺を $\phi(n)$ 乗して pow(r, n2, n2) を打ち消すことで k*m を求めることができます。
　k*m が判明すれば、 pow(r, n2, n2) から pow(r, n, n) を求めることができるので、その逆数を c に掛け算してフラグゲットとなります。

```python:solve.py
from Crypto.Util.number import *
import gmpy2

n2 = 303520029249457721712088032629157671188675957478999814001107946377897435098262416944078032743694224547812111876508629629098790706348564683510627437608561667668817082232066690156773182947457415470637661555594387660242481075809061863866878134857767064271020275925358862373499666674028571177472256983693456175513694920187605044808723618380459789773493111510245511524263712883363099195516392023821523383273803607532258960986269523229557484356691226627296549458770890488302153036171491536959410916079515480053813267273641384674290430132960320985260531094724351210760834427441063392448845773608652498658579592730319172250637383076619273369963514086477217760274026803102575002211426718751927101891471494221058041179582203541771830433523526001577817599554252231872769532980390483401226639528096938277398399935682866324784993115812281877591865430215134442904551109441541036428784450911307551504003791948952027070850252232846043561327951083360866399333467139115782229855840846646026182204713128402629095939971393271042355316329494426040959059666926611479882720948473312355005677824274551575679913205670022022017139399175510998237850213737165974646339820009635040028632254754412047567426260382111848392850835481772030875035608845098368736718689
halfpq_sqr_sum = 9472622129700199703245586196664170084403806786939405819609832782578112766576428480777927359491256761393588992261088804683630755557509473029147106633909601585974763553680654431838374713192695971152635135654980642968043058123569343691081887394840682085558030205578048546258148505272998984973693174088527063719679039240127298660482089717632821831294015315634267021396765367208053481029040950107066330391869209058343986685994748025768502912822369180563838868099092781901052919510720948179559741776416837917783632982451736331078296715767630096860173482291944176969440690386874499002706015031896162301715990323012706805065
cmsg = 103078286643622880447473687471766764943564559811909431666893450054168818307349486985249638958378791065494084728451034371725501517686576282043339068765538253257675113627273797306564684365323509359273378294002601649860804748728163025522075672245295550880060720735463310260935029330499002606032562798724954111417118887527073957993508089754394967659543003785760047941879904675059060008485376318332423664374757995851806458605666638976841133899950278214115072866022244614110580100352950200691110948074551191407363470332793295773273747237585817004577206834980715049990997687288385068292724282066219625651831484886243730221023243574538535723396702634705817852703892641398427064494429830352214499320005058534474284577134432341253340519635081380378045892077000915627548861547061501696012768786270148594424943366660662587186418716670250433370555760184571143569773295737850383542649898270826382659942188410185848934468448568325496582525158048118061659983332451282069426273006110854670823360391164278996722155588697598627131803289512431866077055012911415395954770914537654639608929010542439756174537575923529600976400363945111089267192377586187238410504823191760221711696006651813981609780080767483863025507048248680195946925116086994713836313403
c = 240819054139924192908276790404232331564539338066363967597355786532131090443403077278934264677782549578055871874639814497554138070603843470651529113660894021443057595391213699869840820555076709709812961373461750130612453785640822249347659164866017931889613080220570111764428471836538389725220257679376309813972857596742069449014122286177227320041653912468408726067139524231446702068292851152761999746103029142674572600075554585602575858028536948546991047817318676231622316199368535515883188272917775993105890398456057174036933873324756054332572569380343179450564438637126650504362820450286638292251182022086719737414761084603628504362175295748323721068857285078233340896776610403227874250072420794722246884387488198976386566266870301419765724246635936193987658699901284391726429640605754046472825878500017779396277376213443347956951870554421838859114868247676278966446582371758603658584495387466611294920606637857755221756257214625128936810241588259047215874829610442603034882068648615080256023583472836142327431962452607719206361748849195548395481842814703649891102211953579454296662259004591314057576449118621217086325140123543677458167848297604521746504718023238069208215956158087066756140657191702426263476717009016863723080567809

# leak p and q
n = gmpy2.iroot(n2, 2)[0]
p_plus_q = gmpy2.iroot(4 * halfpq_sqr_sum + 2 * n + 1, 2)[0] + 1
p = (p_plus_q + gmpy2.iroot(p_plus_q**2 - 4*n, 2)[0]) // 2
q = n // p

# totiant of n
phi_n = (p-1)*(q-1)

#get k *m (mod n)
km =  (inverse(phi_n, n) * (pow(cmsg, phi_n, n2) - 1) // n) % n

#get pow(r, n2, n2)
R = (cmsg * inverse((1 + km * n), n2)) % n2

#get inverse of pow(r, n, n)
n_inv = inverse(n, phi_n)
rn = pow(R, n_inv, n)
rn_inv = inverse(rn, n)

#get flag
flag = (c * rn_inv) % n
print(long_to_bytes(flag).decode())
```
**IJCTF{8c105018afda40bba64640e50e1da826}**

#2-3. Riddle Joker (Forensic, 999点) 
>Joker has returned from his imprisonment. Rumour says that he's scheming a new evil operation by implanting several bombs at a local bank. Each of bomb has a tag information that might be a clue for finding Joker's secret

　このほか、「secret.pdf」という 86,426 バイトの PDF ファイルが提供されます。
　この PDF ファイルを「PDFStreamDumper」というツール（ https://github.com/dzzie/pdfstreamdumper ） を使って解析すると、「flag.txt」が入っているパスワード付 zip が末尾近くに隠されていることと、そのパスワードを記した QR コードを示す画像が 49 分割して保持されていることが分かります。
　この画像を特定し、そのデータ部と思われるバイナリと.pgm 形式ファイルのヘッダを合成し、画像ファイルとして出力します。扱いづらいのでビットマップファイルに変換後、手作業で組み立てていくと以下のような QR コードを得ることができました。
　なお、画像データと思しきバイナリデータは過剰に存在しておりましたが、後半部に書かれている座標情報にある stream の番号と照合し目視で特定していきました（おそらく、強い人ならプログラムを書くところなのでしょう）。
　また、座標が一部誤っているようでしたので、目視で適宜（テキトーに）修正しています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/429434/9a3062bf-d286-b537-cd8b-ffc442a88730.png)
　これを読み取ると
「The passcode is sup3r__cred3nti4l_p4sscode_3da748」
と出てきましたので、このパスワードで zip を解凍してフラグをゲットできました。

**IJCTF{4bbffb87ecc31ba242772ab1f14f569c}**
※この QR は組み立てが若干間違っていて、誤り訂正が効いて救われている可能性大です。

#3. おわりに
　Forensic問 の「Black Letter」ができなかったのが悔しいっす！PNG の修復まではうまくいっていたのに。。。orz