CSAW CTF 2024に今回参加しましたので、復習としてWriteupを書きます。
251ポイントで順位は527/1183でした。
Trapdoor (Crypto)
2つの平文の暗号文のファイルmsg1.enc、msg2.encとそれぞれを暗号化するために使用した公開鍵のファイルpublic.key1、public.key2が渡されます。
まず、公開鍵の変数名からRSA暗号で暗号化していることが分かります。
RSA暗号が対象の場合は秘密鍵$d$を求めて暗号文を復号することによってフラグが取得できる場合が多いため、今回はその方針で解法を考えてみます。
今回渡された情報でRSAにどのような脆弱性があるか調べました。
すると、公開鍵と秘密鍵を求めるためのパラメータ$p,q$のうち、異なるパラメータによる暗号化で$p$を使い回してしまっていると公開鍵$n_1$と$n_2$の最大公約数を求めることによって$p$が求まってしまうことを知りました。
つまり、平文$m_1$を暗号化するときのパラメータを$p,q$、平文$m_2$を暗号化するときのパラメータを$p,r$（$p \neq r$)とすると、公開鍵$n_1,n_2$はそれぞれ
$$n_1 = p*q$$
$$n_2 = p*r$$
となります。すると、最大公約数$\text{GCD}(n_1,n_2)$は$q$と$r$は互いに素であるため$p$となり、秘密であるはずのパラメータが分かります。それから$q$と$r$、$e$と$(p-1)(q-1)$（または$(p-1)(r-1)$）からそれぞれの秘密鍵$d_1,d_2$が求まり、$m_1,m_2$に復号できます。
実際に、今回の公開鍵$n_1,n_2$の最大公約数を求めると、
$$\text{GCD}(n_1,n_2)=21390\ldots$$
となります。
$p$を使いまわしてないと$n_1,n_2$の最大公約数は$1$になるので合っていそうです。
次に、$p$と$n_1,n_2$から$q$と$r$を求めます。
$$q = n_1/p = 25117\ldots$$ $$r = n_2/p = 31561\ldots$$
これで秘密鍵を求めるための値が揃ったので、次の式で求めました。
$$d_1 = e^{-1}\quad\text{mod}\quad(p-1)(q-1) = 16076\ldots$$ $$d_2 = e^{-1}\quad\text{mod}\quad(p-1)(r-1) = 29845\ldots$$
後は、それぞれの平文を復号すればよいです。
$$m_1 = c_1^{d_1}\quad\text{mod}\quad n_1 = 16176\ldots$$ $$m_2 = c_2^{d_2}\quad\text{mod}\quad n_2 = 87386\ldots$$
最後に、フラグを得るために数値で得た平文をバイナリ列に変換しようとしましたが、$m_1$の方はバイナリ列に変換できなかったため$m_2$の方をバイナリ列に変換してみると
b'csawctf{n0_p0lyn0m1al_t1m3_f4ct0r1ng_n33d3d_t0_0p3n_th1s_tr4pd00r!}'
となり、フラグを得ることができました。
プログラム
import math
import binascii
# 晴耕雨読さんのmodinv,xgcd関数を利用
# Pythonでモジュラ逆数を求める (modinv)
# https://tex2e.github.io/blog/crypto/modular-mul-inverse
def xgcd(a, b):
x0, y0, x1, y1 = 1, 0, 0, 1
while b != 0:
q, a, b = a // b, b, a % b
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
return a, x0, y0
def modinv(a, m):
g, x, y = xgcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
n1 = 537269810177819460077689661554997290782982019008162377330038831815573146869875494409546502741769078888560119836988893807659619131795600022996155542011901767164659622251852771410530047820953404275439162903782253582402317577272023052873061733154947413969140900242586288282386516940748102303139488999388815366805771566027048823971232923901589854972341140497344922557809346957285480088567527430942352224246175865278666886538920772608403444601667114300055814252644535406924681931233694920723837668899531758291081568304763353729111948368345349994099868469305792181073122419940610781784779666456780500932337154438538720823939250386789917476722260336949625831449027815346423132208841389383282133423240342633209093536658578807788187537292687621305485734565276685038174693348234827761258142100019798785254244633108887403538365377022084266245064851786520352683721896084403163679116876924559581709943841877168418550922700610256010165841228197765129411475811684669156709601802234298096100301516880419138890353002776631827361005170877640327516465104169299292924318171783865084478980121378972145656688829725118773293892358855082049175572479466474304782889913529927629420886850515337785270820884245044809646784251398955378537462225157041205713008379
n2 = 675112413040615754855341368347991520700645749707972662375138119848808538466484973026629442817490775679486087477873647170707728077849174294413106449041183548981099164777126469098349759962366886352375485394430924686294932854410357033579891793697466117311282071223849125728247324019661552591602816412461639181036083039951358738639409104870090776274099206184327026885209301129700589120263558741373320717866973004474880824451611558352986814186406024139122101780061421498582804842387331594088633719788918481809465044314609904522824483927173924396330723272200351268059583559155873089840203176526189465332287149408627146863937339106591410131104971158916770664709755851365697530033135116269758729627681863469646687585133174854282299126206393656205822175860114547244407037919126445577158000448033562711159480289599400271620922791664179514807098083591794558148460941940996477066832640360820650342057071277962750427121243576612067919616033880922920641430414655749007393524344586517489346008845986135281381956392366857764758769758991862758292829265731964283719870708510272500471228442964550074672417445262035130720875562744233719280755235051883245392409892775011413342074824090752055820699150296553380118608786447588243723987854862785887828651597
p = math.gcd(n1, n2)
print(p)
q = n1//p
r = n2//p
print('n1/gcd_n=', q)
print('n2/gcd_n=', r)
e = 65537
d1 = modinv(e, (p-1)*(q-1))
d2 = modinv(e, (p-1)*(r-1))
print('d1=', d1)
print('d2=', d2)
c1 = 161657267735196834912863135763588255051084768060167522685145600975477606522389267911595494255951389308603585891670155516473228040572472139266242046480464411011926872432857745283026840801445383620653451687523682849171134262795620963422201106957732644189004161198543408780876818402717692426183521358742475772803427948145681912577138151854201287217310388360035006450255979612146528569192238510701666997268424852524879191797074298541592238357746219444160311336448978081899531731524195638715227224903445226248602579764214997719090230906191407229446647313099400956970509035654967405630240939959592998616003498236942092817559461000588623573048030445521863492730870242644395352424593752773001495951737895664115609421618170689951704330184048125307163740226054228480085636314748554185748105182003072934516641741388554856693783207538862673881733984454590126630762754413784860309730736733101522402317095930278893263812433036953457501549714213711757368647750210251899325644773678135753158374375837529620580830355398764871600754340989211159192515899566042173210432362519000596760898915443009768635625263875643978408948502726014770826616858752941269838500371205265923373317700072776319154266968103160778573051363936325056002056286215658714259892131
c2 = 494623168173341363340467373358957745383595056417571755948370162317759417390186160270770025384341351293889439841723113891870589515038055355274713359875028285461281491108349357922761267441245606066321766119545935676079271349094728585175909045924367012097484771776396598141703907624715907730873180080611197080012999970125893693838478647963157490065546947042621326070901482489910203413759703603136944502613002083194569025640046380564488058425650504612206627739749051853591610981053026318569730551988841304231276711969977298162726941928222523464544797141812329957714866356009363861914935745207975118182966833811723664044706845207847731129336219505772833893718601825819419057471717431953601897992835582033908346998397116046369365580899868759006665351628889935594587647946796811554073758809039163703319444890860711787316692186294350180062910771860180483152240985537326837665737974072086105081591429007858987697382766650868798693024212101169297652870122729568327958629779258375463408029863902774673729692698603549762248768090302360950262068792179771304874203556781584256503067131440856389473604578859795120178476492827306744971082872861030028803971595639553063854220185280566575307797482645881434704155764917254239587927218075951473385530833
m1 = pow(c1, d1, n1)
m2 = pow(c2, d2, n2)
print('m1=', m1)
print('m2=', m2)
print(bytes.fromhex(format(m2, 'x')))
Rickshaw (OSINT)
以下の画像が渡されて、この車両を管理している人の電話番号を求めるという問題でした。
まず、問題文と画像からの情報としてこの車両をインドで見かけたということと、車両登録ナンバーの77CDがヒントになりそうです。
そのため、まずインドの車両登録ナンバーの規則について調べます。
Vehicle registration plates of IndiaというWikiページを見ると、「番号 CD」という車両登録ナンバーはDiplomatic mission、つまり在外公館所有の車両に付けられるものだと分かります。
ここからどこの在外公館が所有しているのかを77CDを検索して探してみると、
109 CD cars link to embassyという記事から、77CDの車両登録ナンバーの車両は米国公館が所有しているということが分かりました。
したがって，、米国公館の電話番号を調べてみると+91 11 2419 8000であることが分かったため、フラグはcsawctf{+91-11-2419-8000}となります。
Authentic Chinese Food (OSINT)
この問題も次の画像が渡されて、この飲食店のHealthGradeと飲食店が入っているビルの建てられた年、ビルを所有しているLLCの名前を求めるという問題でした。
この画像からヒントになるのは対象の飲食店がPANDA EXPRESSであることと、隣の電話番号が718-875-**** と *** - *** - 9500であることです（*は不明）。
ここで同じ場所であるならば前２つの電話番号718-875は共通なのでは？と考え、
718-875-9500で検索してみました。すると、Staywell Medical Groupがヒットしました。
左の建物には1段目に*ICAL、2段目GROUPと書かれているため合ってそうです。
Google Mapでこの建物の周辺を調べてみると、PANDA EXPRESSが見つかりました。
PANDA EXPRESSがどこにあるか判明したので、次に店のHealthGradeについて調べます。
店の住所423 Fulton Street, Brooklynで検索してヒットした以下のWebサイトの中でHealthScoreはGrade Pendingと書かれていました。
また、別のWebサイトではこのビルが1920年に建てられたものであることが書かれていました。
最後に、ビルを所有しているLLCの名前を求めますが、次のWebサイトで見つけました。
このWebサイトでは登録が必要なので注意が必要です。
このビルを所有しているのがBnn Fulton Flushing Ownerであると分かります。
したがって、この問題のフラグは
csawctf{Grade_Pending_1920_Bnn_Fulton_Flushing_Owner}
となります。
Baby Rev (Reversing)
baby_revというファイルを渡されるので、これを解析してフラグを入手します。
Reversingの鉄則として、まずfileコマンドを実行して何のファイルなのか確認します。
fileコマンドを実行した結果、Linuxの64bit実行ファイルであることが分かりました。
baby_rev: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=0d1b01effb08ad924b14efc1ba22cc36f331af0f, for GNU/Linux 3.2.0, not stripped
実行ファイルであることが分かったため、実際に実行してみると次の出力が出ました。
The flag is hidden nearby.
I can help you check if you got it right!
> aaaa
Nah! That doesn't look like the flag!
この出力から、baby_revがどんな動作を行うか知ることが出来ました。
さらに、1行目のThe flag is hidden nearbyという文字列からバイナリファイル中のこの文字列が配置されている付近にフラグがあると推測されます。
そこで、stringsコマンドを実行してファイルに含まれている文字列を出力してみました。
すると、The flag is hidden nearbyの文字列の上に気になる文字列が配置されていました。
Y3Nhd2N0H
ZntOM3YzH
cl9wcjA3H
M2M3X3MzH
bnMxNzF2H
M18xbmYwH
cm00NzEwH
bl91czFuH
Z19qdXM3H
XzNuYzBkH
MW5nIV8jH
M25jMGQxH
bmdfMXNfH
bjB0XzNuH
Y3J5cDcxH
MG4hfQ==H
The flag is hidden nearby.
大文字と小文字の英字と数字、それから最後の行にある==からこのブロックとなっている文字列はBase64エンコードされた結果の文字列であることが推測されます。
ただし、どの行にも最後の文字がHとなっており、==の後もHがついていることから、最後の文字のHは取り除いて良さそうだったので、取り除いてデコードを行いました。
その結果、
csawctf{N3v3r_pr073c7_s3ns171v3_1nf0rm4710n_us1ng_jus7_3nc0d1ng!_#3nc0d1ng_1s_n0t_3ncryp710n!}
というフラグを得ることができました。
ZipZipZip (Forensics)
challenge.zipが渡されるので、これを解析してフラグを入手します。
問題名からzipファイルがネストしているのではないかと推測して、uzdirというフォルダにzipファイルを入れて繰り返し解凍するプログラムを作成し、実行しました。
ネストzipファイル解凍プログラム
import glob
import os
import zipfile
target = "./uzdir/*"
while True:
files = glob.glob(target)
if files == []:
print("no file")
exit
zfiles = [file for file in files if '.zip' in file]
if len(zfiles)==0:
print("no zip file")
exit
elif len(zfiles)>1:
print("many zip file")
exit
print("zipfile=", zfiles[0])
with zipfile.ZipFile(zfiles[0]) as zf:
zf.extractall('./uzdir')
os.remove(zfiles[0])
これを実行した結果、どうやらzipファイルの他にテキストファイルも含まれていたようでchunk_0.txtからchunk_32795.txtまでの合計32796個のテキストファイルが生成されました。
このテキストファイルの中身を幾つか見てみると、/や+、大文字と小文字の英字、数字から構成される文字列が入っていました。
また、chunk_32795.txtの中身は=のみでした。
これらのことから、テキストファイルに含まれている文字列はBase64でエンコードした文字列を分割したものだということが推測されます。
そこで、テキストファイルの文字列を全て結合して、Base64でデコードした後にバイナリ列に変換することでフラグに関係する文字列が出てくると思い、試してみましたがバイナリ列へ変換することができませんでした。
そこで行き詰ってしまいましたが、調べていく中で[Python]Base64でエンコードされた画像データをデコードする。という記事を見つけました。
この記事を参考にして、Base64でエンコードされた文字列を画像に変換するプログラムを作成して実行しました。
チャンク処理プログラム
import base64
import cv2
import numpy as np
import io
data = ""
for i in range(32795+1):
fname = "./uzdir/chunk_"+str(i)+".txt"
with open(fname, "r") as f:
data += f.read()
print(data)
img_binary = base64.b64decode(data)
image = np.frombuffer(img_binary, dtype=np.uint8)
img = cv2.imdecode(image, cv2.IMREAD_COLOR)
cv2.imwrite('./out.jpg', img)
その結果、次の画像が生成されました。
この画像の右下に注目すると、薄くて見えづらいですがフラグのような文字列が見えます。
これを読み取ると、フラグが
csawctf{ez_r3cur5iv3ne55_right7?}
であることが分かります。