Attack All Around

アメリカ留学、TOEFL、トビタテ

WaniCTF Writeup

こんにちは!Ken.Sです!

 

今回は大阪大学の CTF サークル Wani Hackaseさんが開催したWaniCTFのwriteupですが、あまり解けなかったのでCrypto, Forensics以外の解法は他の方のを…

 

f:id:partender810:20201123213258p:plain

全完するとメダルマーク付くの嬉しい

 

WaniCTF 2020 - WaniCTF 2020

 

 

 

Web

DevTools_1 Beginner

ブラウザの開発者ツールを使ってソースコードをのぞいてみましょう!

https://devtools1.wanictf.org

F12を押して開発者ツールを覗くとflagが

 

FLAG{you_can_read_html_using_devtools}

 

DevTools_2 Easy

開発者ツールを使うと表示を書き換えることができます。

5000兆円欲しい!

(5000000000000000円持っていることにするとフラグを手に入れることができます。)

https://devtools2.wanictf.org

 

サイトを見ると、「あなたの総資産は0円です!」とある。

開発者ツールのElementsからこの文を表示させているところを見つけ、5k兆にするとflagがpopで出る。

 

FLAG{you_can_edit_html_using_devtools}

 

5000兆とは言わないから1億円くらいくれないかな

 

Simple Memo Beginner

問題ページ:https://simple.wanictf.org/

flag.txtというファイルに私の秘密を隠したが、 完璧にサニタイズしたため辿りつける訳がない。

(Hint) ディレクトリトラバーサルという脆弱性です。

何がサニタイズされているかを知るためにソースコード(reader.php)を参考にしてみてください。

 

ディレクトリトラバーサルについて

ディレクトリトラバーサルとは?対策の方法7選と主な被害例3つをご紹介! | テックマガジン from FEnetインフラ

 

相対パス脆弱性らしい。ふーん、、、

../したあとにflagないかな。

URLに../flag.txtと付けるとflagが見えた。

 

FLAG{y0u_c4n_get_hi5_5ecret_fi1e}

 

 

striped table Easy

テーブルの行の背景色をストライプにする作業をしてもらったら、こんなことになってしまいました!

ページにjavascript alert(19640503)を埋め込み実行させるとフラグが得られます。

https://striped.wanictf.org/?sourceにアクセスするとソースが閲覧できます。

https://striped.wanictf.org

 

どうやってalert文挿入するんだろ、メモに追加するときにねじこめないのかな。

 

ソースを見ると、背景色を変えているときのmemoの記述が他と違う。

メモを追加するときに、<script> alerm(19640503) </script>

とすると、flagがもらえる。

 

FLAG{simple_cross_site_scripting}

 

SQL Challenge 1

問題ページ: https://sql1.wanictf.org/index.php?year=2011

今まで見たアニメのリストをデータベースに登録したよ。間違えて秘密の情報(FLAG)もデータベースに登録しちゃったけど、たぶん誰にも見られないし大丈夫だよね。

(Hint)

SQL injectionの問題です。

URLの「year=」の後に続く数字(年号)をSQL injectionを起こすような文字列に変更するとFLAGが表示されます。

一部使えない文字もあるのでソースコード(index.php)を参考に考えてみてください。

必要に応じてデータベースのスキーマ(1_schema.sql)も参考にしてください。

SQL系の問題は解けてないですが、ご紹介だけ。

year=の後に必ずtrueになる文を投げればいいらしい。

 

FLAG{53cur3_5ql_a283b4dffe}

 

 

SQL Challenge 2

問題ページ: https://sql2.wanictf.org/index.php?year=2011

やっぱり前のページは危ない気がするからページを作り直したよ。これで大丈夫だね。

(Hint)

SQL injectionの問題です。

必要に応じてソースコード(index.php)とデータベースのスキーマ(1_schema.sql)を参考にしてください。

year=0で通るらしい。なんで?

 

FLAG{5ql_ch4r_cf_ca87b27723}

 

 

Reversing

strings Beginner

この問題ではLinuxのELF実行ファイル(バイナリ)である「strings」が配布されています。このバイナリは入力文字列をチェックし、正しいものかどうか判定する機能をもっています。

試しにFAKE{this_is_fake}と入力するとIncorrectと表示され、間違っている入力文字列であると示してくれます。

このバイナリが「正しい」と判定してくれる文字列を見つけ出してください。

ヒント:バイナリ解析のはじめの一歩は「表層解析」という手法です。

ファイル:strings

 

stringsコマンドで終わり。

 

FLAG{s0me_str1ngs_rem4in_1n_t7e_b1nary}

 

 

simple Normal

「strings」問題は表層解析でフラグを見つけることができましたが、この問題では同じようにフラグは見つからないようです。

次の手法は「動的解析」と「静的解析」です。

Linux実行ファイルの解析において動的解析の代表的なツールが「GDB」、静的解析の代表的なツールが「Ghidra」です。

それぞれ入門記事が多く公開されていますのでぜひ動的解析と静的解析にチャレンジしてみてください!

ファイル:simple

 

ヒントとは異なりますが、先日インストールしたIDAに投げたら一発。

flagを一文字ずつ確認しているみたいで、それがキレイに出ていました。

 

f:id:partender810:20201123171722p:plain

書き写すのがちょっと面倒だった

 

FLAG{5imp1e_Revers1ng_4rray_5trings}

 

 

Pwn

netcat Beginner

nc netcat.wanictf.org 9001
netcat (nc)と呼ばれるコマンドを使うだけです。
つないだら何も表示されなくても知っているコマンドを打ってみましょう。

ファイル:pwn01, pwn01.c

 

相手のサーバにアクセスできているよう。lsでflag.txtがあるのが分かるので、catで表示。

 

FLAG{netcat-1s-sw1ss-4rmy-kn1fe}

 

 

var rewrite Beginner

nc var.wanictf.org 9002
stackの仕組みを理解する必要があります。
ローカル変数はstackに積まれます。
ローカル変数を書き換えて下さい。

ファイル:pwn02, pwn02.c

名前を聞かれるので、とりあえず1~n文字を打ち込んで見ると10文字の時に名前が何も表示されなくなった。そしてcファイルを読むと、targetをWANIにすると良いよう。普通にするとHACKASEになるが10文字の時は何も表示されない。a*10+WANIとするとどうだろう。Congratulations!と褒められた。あとはさっきと一緒でls->cat flag.txt

 

FLAG{1ets-1earn-stack-w1th-b0f-var1ab1e-rewr1te}

 

 

Misc

Find a Number Beginner

隠された数字を当てるとフラグが表示されます.

数字は0以上500000以下であることが保証されています.
nc number.wanictf.org 60000

二部探索したらゲット。

 

FLAG{b1n@ry_5e@rch_1s_v3ry_f@5t}

 

 

Forensics

logged_flag Beginner

ワニ博士が問題を作っていたので、作っているところをキーロガーで勝手に記録してみました。

先に公開してしまいたいと思います。

(ワニ博士は英字配列のキーボードを使っています)

ファイル:key_log.txt, secret.jpg

key_log.txtを見ると、MKDIRの文字が。他にも[Space]や[Enter], [Shift]などがあり、これが英字配列キーボードか、と。TOEFLの際によくやったなぁ。

 

とりあえず、復元します。

mkdir steghide
cp original.jpg ./steghide
cd steghide
echo FLAG{k3y_l0gg3r_1s_v3ry_d4ng3r0us} > flag.txt
steghide embed -cf original.jpg -ef flag.txt -sf secret.jpg
machikanetamachikanesai
machikanetamachikanesai
steghide extract -sf secret.jpg
machikanetamachikanesai
ycat flag.txt

US版キーボードでShiftを押すと、[ ]-> { }, . -> >, (ここまでは基本的には一緒?) - -> _です。

 

FLAG{k3y_l0gg3r_1s_v3ry_d4ng3r0us}

 

 

ALLIGATOR_01 Easy

ワニ博士のPCでは,悪意のあるプロセスが実行されているみたいです。

取得したメモリダンプから、”evil.exe”が実行された日時を報告してください。

(注意: スペースはすべて半角のアンダースコアにしてください)

example: FLAG{1234-56-78_99:99:99_UTC+0000}

問題ファイル: ALLIGATOR.zip (ミラー: ALLIGATOR.zip)

推奨ツール: volatility

こういうツールを教えてくれるの本当にいいですよね!普段やらない分野でもきっかけが掴めるので、取り掛かりやすいです(作問者ありがとう)。

 

とりあえずvolatilityを入れてみます。

sudo apt update

sudo apt install volatility

 

まず、"volatility -f FILENAME imageinfo" でOSを突き止めます。(その前に-hでコマンドを確認しよう)

Suggested Profile(s) : Win7SP1x86_23418

あとはプロセスツリーを見てみます。

volatility -f ALLIGATOR.raw --profile=Win7SP1x86_23418 pstree

そして、evil.exeの実行時間をFLAGとして提出!

 

FLAG{2020-10-26_03:01:55_UTC+0000}

 

 

ALLIGATOR_02 Normal

コマンドプロンプトの実行履歴からFLAGを見つけてください。

(ALLIGATOR_01で配布されているファイルを使ってください)

 

consolesで履歴が見れるみたい。

volatility -f ALLIGATOR.raw --profile=Win7SP1x86_23418 consoles

 

FLAG{y0u_4re_c0n50les_master}

 

 

ALLIGATOR_03 Hard

Dr.WANIはいつも同じパスワードを使うらしいです。

Dr.WANIのパソコンから入手したパス付のzipファイルを開けて、博士の秘密を暴いてしまいましょう。

(ALLIGATOR_01で配布されているファイルを使ってください)

ファイル:wani_secret.zip

 

「volatility パスワード」でググるとSECCONで似た問題があったらしい。

[SECCON] Forensics300 ログインパスワードを解明せよ | ごみばこいん Blog

[SECCON 2013_WEB, Forensics 300] ログインパスワードを解明せよ – どうも、わさむすめです

ここらへんの記事が参考になりました。

 

volatility hivelist -f ALLIGATOR.raw --profile=Win7SP1x
86_23418
Volatility Foundation Volatility Framework 2.6
Virtual Physical Name
---------- ---------- ----
0x96833008 0x29f35008 \??\C:\System Volume Information\Syscache.hve
0x9a37a008 0x0edcf008 \??\C:\Users\ALLIGATOR\ntuser.dat
0x9a37c008 0x0eed1008 \??\C:\Users\ALLIGATOR\AppData\Local\Microsoft\Windows\UsrClass.dat
0x8780a6b8 0x282fb6b8 [no name]
0x8781a008 0x28349008 \REGISTRY\MACHINE\SYSTEM
0x87838218 0x28367218 \REGISTRY\MACHINE\HARDWARE
0x8b0599c8 0x248859c8 \??\C:\Windows\ServiceProfiles\LocalService\NTUSER.DAT
0x8cb07008 0x26f46008 \Device\HarddiskVolume1\Boot\BCD
0x8e7f7008 0x26313008 \SystemRoot\System32\Config\SOFTWARE
0x904655f8 0x225685f8 \??\C:\Users\IEUser\ntuser.dat
0x9144b5c0 0x260205c0 \SystemRoot\System32\Config\DEFAULT
0x937338d0 0x250778d0 \SystemRoot\System32\Config\SECURITY
0x93791458 0x1d940458 \SystemRoot\System32\Config\SAM
0x937b79c8 0x248899c8 \??\C:\Users\IEUser\AppData\Local\Microsoft\Windows\UsrClass.dat
0x937fb758 0x248dd758 \??\C:\Windows\ServiceProfiles\NetworkService\NTUSER.DAT
0x96449458 0x03f4f458 \??\C:\Users\sshd_server\ntuser.dat
0x9645d3d8 0x2830b3d8 \??\C:\Users\sshd_server\AppData\Local\Microsoft\Windows\UsrClass.dat

 

VirtualのSYSTEMとSAMのhexが必要らしい。

volatility hashdump -f ALLIGATOR.raw --profile=Win7SP1x
86_23418 -y 0x8781a008 -s 0x93791458
Volatility Foundation Volatility Framework 2.6
Administrator:500:aad3b435b51404eeaad3b435b51404ee:fc525c9683e8fe067095ba2ddc971889:::
Guest:501:aad3b435b51404eeaad3b435b51404ee:31d6cfe0d16ae931b73c59d7e0c089c0:::
IEUser:1000:aad3b435b51404eeaad3b435b51404ee:fc525c9683e8fe067095ba2ddc971889:::
sshd:1001:aad3b435b51404eeaad3b435b51404ee:31d6cfe0d16ae931b73c59d7e0c089c0:::
sshd_server:1002:aad3b435b51404eeaad3b435b51404ee:8d0a16cfc061c3359db455d00ec27035:::
ALLIGATOR:1003:aad3b435b51404eeaad3b435b51404ee:5e7a211fee4f7249f9db23e4a07d7590:::

 

ALLIGATORが出てきて、以降がpasswordのハッシュのようです。ophcrackやjohn the ripperに投げてもなかなか出てこない。というか出ない。

 

なんとか、ここでできた。

CrackStation - Online Password Hash Cracking - MD5, SHA1, Linux, Rainbow Tables, etc.

 

NTMLハッシュの仕様が分からず、ここで時間かかりました。後ろの方をぶん投げるとパスワード "ilovewani"が出た。そのパスワードでzipを開きます。

 

FLAG{The_Machikane_Crocodylidae}

 

 

chunk_eater Normal

pngの必須チャンクをワニ博士が食べてしまいました!

PNG ファイルフォーマット

ファイル:eaten.png

PNGはすこーし勉強してたので、必要なチャンクはIHDR,IENDチャンクだろうと。必須チャンクを食べたということで挿入すればいいのかな。

 

 

分からん。

ずっと気になっているWANIという文字列…。ここを変えたらいいらしい。そしてIDATも無い。複数あってもいいらしい。(教えてもらった。)

5個のWANIがあるので、IHDR, IDAT, IDAT, IDAT, IENDを入れ替える。

 

FLAG{chunk_is_so_yummy!}

 

 

zero_size_png Very hard

この画像のサイズは本当に0×0ですか?

PNGのチャンク(IHDR)

 ファイル:dyson.png

実はこれ、以前m1z0r3の勉強会でやったことがあって、その時のsolverをほんのちょっと変えたらOKでした。

 

FLAG{Cyclic_Redundancy_CAT}

 

解説??他当たってください。

 

 

 

Crypto

Veni, vini Beginner

SYNT{fvzcyr_pynffvpny_pvcure}

rot13ですね。

 

FLAG{simple_classical_cipher}

 

 

exclusive Easy

XORを使った暗号です🔐

ファイル:encrypt.py, output.txt

encrypt.py を見ると、flagの長さが57でkeyは3毎同じのが使われて、FLAG{.{51}}という形です。

output.txt -> ot[0~56]とすると

key[0] = ot[0] ^ ord('F')

key[1] = ot[1] ^ ord('L')

key[2] = ot[2] ^ ord('A')

でkeyを求められます。あとはそのkeyを使い回してxorしましょう。

 

FLAG{xor_c1ph3r_is_vulnera6le_70_kn0wn_plain7ext_@ttack!}

 

 

Basic RSA Normal

RSA暗号の基本的な演算ができますか?
nc rsa.wanictf.org 50000

ncすると計算しろという無言の圧力が。

1問目:(譲) p,q (求) n=p*q

2問目:(譲) m,e,n (求) c = m^e mod n

3問目:(譲) p,q,c,e (求) m = pow(c,d,n)

 

計算すればOKです。

 

FLAG{y0uv3_und3rst00d_t3xtb00k_RSA}

 

 

LCG crack Hard

安全な暗号は安全な乱数から
nc lcg.wanictf.org 50001

ファイル:server.py

このサーバーは、seedを生成するとそこから線形合同法で乱数を生成するそうです。1.で次の乱数がもらえ、2.で10連続で乱数を当てるとflagが手に入ります。

 

この方の記事がすごく分かりやすい!!

線形合同法のパラメータを乱数列から求めてみる。 - みつのCTF精進記録

 

まず、x = a*x' + c mod m とすると、mから求めます。

T_i = x_i+1 - x_i として、乱数xを5個くらい貰います。T_i*T_i+2 - (T_i+1)^2 = 0 mod m から、この値を計算して素因数分解して64bitの素数をGETします。3通りくらい計算すると、ほぼ一意にmが決まります。

 

mが分かると、次はaです。

a = T_i+1 / T_i mod m となるので(modがあるときの割り算注意)、すぐ計算できます。

c = x_i+1 - a*x_i mod m でcも簡単に求まるので、このパラメータが決まればあとは最後のxを入力としてx'を10回計算してサーバに送り付けましょう。

 

FLAG{y0u_sh0uld_buy_l0tt3ry_t1ck3ts}

 

 

l0g0n Very hard

🕵️‍♂️
nc l0g0n.wanictf.org 50002

ファイル:server.py

 

ざっくりとした手順はこんな感じです。

  1. 偶数桁hexを入力する。bytesにしたのをclient_challengeに入れる
  2. server_challengeに8bitの乱数を入れ、見せてくれる。
  3. session_keyに(psk(未知のbytes)+client_challenge+server_challenge)を入力としたsha256(ソルト付)の出力を入れる
  4. client_credentialにもう一度偶数桁hexを入力してもらう。
  5. cipherは自作のクラスのインスタンス。そのフィールドblock_sizeは常に16, フィールドcipherは先程のsession_keyをkeyとしてAES(ECBモード)。
  6. iv_plaintext = bytes(16) (\x00が16個) の後ろにclient_challengeを付けて、iv_plaintext[i:i+16]をAESのECBモードで暗号化したのとclient_challenge[i]のxorしたのをserver_credentialに入れる
  7. server_credentialとclient_credentialが一致したらflagがもらえる。

 

複雑ですね。3でもうsession_keyが予測不可能として考えるとヤマカンで当てるしかないのか…?ってなりました。実はヤマカンで当てられました。1,4での入力を2桁の入力にすると、******_credentialが1 byteになります。なので、1/256を引き当てるまでグルグル回します。つまり、こんだけの仕組みを理解してなくてもたまたまを引き当てればOKです。

1. 12, 4. 34を送り続けたら、70回目でflagが出ました。

 

これが恐らく想定解のはずです。

何故この話をしたかというと、1.,4. で空文字列を送ると一発でflagが出てきました。

 

FLAG{4_b@d_IV_leads_t0_CVSS_10.0__z3r01090n}

 

 

 

先日のPaken CTFのようにサークルの方が作問したCTFは取っ掛かりがしやすくて勉強になりました!しかし、CTFを今年始めたばかりの後輩に500点以上も差を付けられ、少し落ち込んでます(笑)

 

それでは!

 

See you next time!

連鎖行列積問題の攻略

こんにちは! Ken.Sです!

 

今回は、連鎖行列積問題という一体どこで使うのか分からない問題を解説します!行列をいっぱい掛け算する時ってどういう時なんだろう…。競技プログラミングの勉強でこの問題を行ったのですが、分かりやすいサイトがあまりなかったので、よりBeginner向けに書いていこうと思います!

数学で行列演算で苦しんだことのある方、競技プログラミングでDPを勉強したい方は是非見てください!

 

 

 

はじめに

そもそも行列とは

行列 - Wikipedia

 

うまく説明できる自信が無いので、よくわからなかった方はwikiを見てください(笑)

四角形の箱に入ったデータの集合で、線形代数を習う上で避けては通れない分野です。y=ax とかのグラフを使う問題を支えるといった感じです(本当にうまく伝わっている気がしない)

 

行列は(n*m行列)と表現されることが多く、nは行数(縦の長さ)mは列数(横の長さ)を表しています。行も列も漢字の右側の「つくり」の方でどっちが行でどっちが列か判断するって覚え方をしている人も少なくないと思います。

 

 

行列の掛け算について

行列の和、差はこのようにして求められます。

f:id:partender810:20201119144829p:plain

要素ごとの操作で、足し算引き算できます

 

サイズだけで言うと、[2*2] + [2*2] = [2*2] となり、足し算引き算では行列のサイズは等しくないと出来ません。

 

しかし、掛け算となると異なります。掛けられる行列の列と掛ける行列の行が等しいと積が求められます。

f:id:partender810:20201119150437p:plain

複雑~~~

サイズだけで言うと、[3*2] * [2*4] = [3*4] となります。

複雑ですね、要素1行1列目の計算はこのようになっています。

f:id:partender810:20201119151108p:plain

この二つの内積になります

内積は積の和って感じです(雑) (上の場合a11*b11 + a12*b21となり、1行1列目と一致します)

積の要素1行1列目の計算は、掛けられる行列の1行目と掛ける行列の1列目の内積、要素1行2列目の計算は、掛けられる行列の1行目と掛ける行列の2列目の内積となります。つまり積の要素s行t列目の計算は、掛けられる行列のs行目と掛ける行列のt列目の内積となり、積の行列のサイズは[掛けられる行列の行数 * 掛ける行列の列数]となります。

内積は同じ要素数必要なので、掛けられる行列の列数と掛ける行列の行数が必要なんです。

 

行列積について、このサイトの説明が綺麗で好きだったので気になる方はどうぞ!

行列の積の定義とその理由 | 高校数学の美しい物語

 

 

連鎖行列積問題とは

では本題に入ります。

上の図を見てもらえれば、計算する数が多いことがわかると思います。要素のかけ算の個数を考えていきます。まず、内積の計算で2回かけ算を行ってます。この2という数字は、掛けられる行列の列数=掛ける行列の行数と一致します。その内積を何回計算しているかというと、積の行列のサイズ=掛けられる行列の行数*掛ける行列の列数です。

 

つまり、[k*l]行列 * [l*m]行列のかけ算数はl*k*mとなります(l : 内積の計算でのかけ算、k*m : 積の行列のサイズ)

 

これの何が問題かを説明します。行列A[w*x], B[x*y], C[y*z] ([]内はその行列のサイズ)があるとし、A×B×Cを計算したいとします。行列のかけ算は結合法則が成り立つので、行列 (A×B)×C, A×(B×C) は等しくなります。(交換法則 AB = BA は成り立ちません。A,B共に正方行列(行数と列数が等しい行列)である場合、積AB, BAは計算できますが結果は異なります。)

 

では、行列(A×B)×C (=P), A×(B×C) (=Q)それぞれについてかけ算数を考えていきます。

P : (A×B) = [w*x] * [x*y] = w*x*y, -> サイズは[w*y] , (A×B)×C = [w*y] * [y*z] = w*y*z  計 w*x*y+w*y*z

Q : (B×C) = [x*y] * [y*z] = x*y*z, -> サイズは[x*z] , A×(B×C) = [w*x] * [x*z] = w*x*z  計 x*y*z+w*x*z

となりますね。仮にw,yがとても大きくx,zが小さいとすると、Qの方がかけ算数は少なくなります。

 

このように、行列のかけ算はどの積を先に求めるかで計算処理数が異なり、その処理数が最も小さくなるようにした場合の順序とその数を求めるのが連鎖行列積問題です。

 

 

 

解説

問題

そもそも私がこの問題を知ったのはこのサイトで勉強してたからです。修士卒業するまでに水色になりたいなぁ。

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】 - Qiita

 

先に解いてみたい方はこちらからどうぞ!

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_B&lang=ja

 

プログラミングを知らない方にもできるだけ分かりやすく書いたつもりなので、解法が気になる方は是非読んでください! 

 

解説

今回は動的計画法を利用しました。O(N^2)でした。

 

以下の入力例を用いて考えていきます。

6
30 35
35 15
15 5
5 10
10 20
20 25

 

まず、配列dp[N][N] を用意し0で初期化します。そして上三角行列のように、dp[i][j] (i > j) は今回使いません。

 

dp[i][j] ( i <= j ) には、i番目からj番目の行列の積を取った際のかけ算回数最小値が入ります。つまり、今回はdp[0][n-1] の値を求め出力すれば良いのです。

 

i = j の時は、その行列しかないのでかけ算は行いません。故に0です。

 

i < j の時を考えます。dp配列の埋め方としては、j - i の差が小さい順に入れていきます。つまり、最初は行列積2個のを計算します。

dp[0][1] = (0番目の行列 * 1番目の行列のかけ算回数) = 0番目の行数 * 0番目の列数(もしくは1番目の行数) * 1番目の列数

です。2個の行列の積のかけ算回数は1通りしかないのでそのまま計算すればOKです。これをdp[n-2][n-1] まで繰り返してdpに値を入れます。

 

現時点でdpはこうなっています。

f:id:partender810:20201119211534p:plain

本来は?部分も0が入っています

 

次に3個の場合を考えます。

考えられるかけ算の順序は以下の二つです。

  1. (A * B) * C
  2. A * (B * C)

(A * B)のかけ算回数はdp[0][1]に入っています。なので、dp[0][1]に加えて( (A * B)で生じた行列) * C のかけ算回数を足したものが1.のかけ算回数になります。同様に2についてもかけ算回数を算出し、小さい方をdp[0][2]に格納します。

 

dp[0][1] + (Aの行数 * Bの列数(or Cの行数) * Cの列数) or dp[1][2] + (Aの行数 * Aの列数(or Bの行数) * Cの列数)

 

f:id:partender810:20201119214650p:plain

行列3個までのdp

 

 

では、行列4つの場合について考えていきます。考えられるかけ算の順序は以下の五つです。

  1. ( (A * B) * C) * D
  2. (A * (B * C) ) * D
  3. (A * B) * (C * D)
  4. A * ( (B * C) * D)
  5. A * (B * (C * D) )

 

1.2.について、A~Cの積とDを掛けています。A~Cのかけ算回数はdp[0][2]に入っています。同様に、4.5.についてもB~Dのかけ算回数はdp[1][3]に入っています。3.については、dp[0][1]及びdp[2][3]に加えて、(A*Bの行列) * (C*Dの行列)のかけ算回数を計算します。dpを使うことで、2通り削除することが出来ました。dp[0][3]に入るのは以下の3つの内最小のものになります。

 

dp[0][2] + (A~C) * D のかけ算回数

dp[0][1] + dp[2][3] + (A~B) * (C~D) のかけ算回数

dp[1][3] + A * (B~D) のかけ算回数

 

f:id:partender810:20201119214752p:plain

行列4個までのdp

 

 

このように、行列i個(i : 2~n)を順々に求めていきます。(dp[0][1], dp[1][2],..., dp[4][5], dp[0][2], dp[1][3],..., dp[0][5])

 

dp[i][j] ( i < j ) の式を一般化していきます。

行列3個のかけ算最小回数を求める時には2個*1個 or 1個*2個の行列のかけ算回数に加えて今までのdp配列を利用しています。行列4個のかけ算最小回数を求める時には3個*1個 or 2個*2個 or 1個*3個の行列のかけ算回数に加えて今までのdp配列を利用しています。

行列掛け算順序をわざと()を付けて表現したのでこのイメージがすぐ持てればうれしいです。規則性があるのでfor文で表現できそうだなってなりますね。

 

x個*y個という形にしたのは一般化しやすいためで、以下の事が成り立つからです。

X * Y のかけ算最小回数 = Xを出すまでのかけ算最小回数 + Yを出すまでのかけ算最小回数 + (行列X行数 * 行列X列数(行列Y行数) * 行列Y列数)

 

X(Y)を出すまでのかけ算最小回数はdp配列に格納されています。また、Xが1つの行列の積、つまり何もかけ算していないときでもそれはdp[x][x]の値を指すことになります。dp[i][j] (i = j) の時は0なので問題ないですね。

dp[0][1~3]を求める時は以下のようなイメージです。

 

f:id:partender810:20201119224446p:plain

dp[0][1]を求めたい時のイメージ図

 

f:id:partender810:20201119224352p:plain

dp[0][2]を求めたい時のイメージ図

 

f:id:partender810:20201119220126p:plain

dp[0][3]を求めたい時のイメージ図

dp[0][3]は以下の最小値です。

  • dp[赤セル2つ] + (0~0番目の行列) * (1~3番目の行列)
  • dp[緑セル2つ] + (0~1番目の行列) * (2~3番目の行列)
  • dp[水色セル2つ] + (0~2番目の行列) * (3~3番目の行列)

 

dp[0][3]と赤のセルは左に3と下に1離れており、緑のセルは左に2と下に2、水色は左に1と下に3離れており、4行列の積を2つに分けて考えた時と同じ個数になりました。

このように考えると、n個の行列の積のかけ算最小回数を求めるにはn-1通りの順序があり、それらの最小値を求めるのです。

 

疑似コードとしてはこんな感じですかね。

x : x個の行列積のかけ算最小回数を求めたい

n : 行列数

dpm : かけ算回数の最小値

m[n][2] : m[i][0] i番目の行列の行数, m[i][1] i番目の行列の列数 を格納している配列

dpm = INF;

for(i=0;i<n-x+1;i++) {

  //n個の内x個の行列積は、n-x+1個ある。

  for(j=1;j<x;j++) {

    //jはx個の配列をどこで区切って二つの行列と捉えるかを判断する

    //j個 * (x-j)個と考える

    // (i~i+j-1番目の行列のかけ算最小回数) + (i+j~x+i-1番目の行列のかけ算最小回数) + (i~j行列行数) * (i~j行列列数) (j+1~x+i行列列数)

    t = dp[i][i+j-1] + dp[i+j][i+x-1] + m[i][0] * m[i+j-1][1] * m[x+i-1][1];

    if ( t < dpm) dpm = t; //最小値の更新

  }

  //dp配列の更新

  dp[i][i+x-1] = dpm;

}

 

 

以下、私のコードです。

AIZU ONLINE JUDGE: Code Review

 

 

dp配列の扱いが難しく、また上のコードでのdynamic関数のfor文内の添え字で苦労しました…。最初は解法のイメージがいろんなサイトを見ても持てず、イメージがなんとなくできてからはデバッグの繰り返しでした(笑) DPという割には再帰的に行っていないので、少し変な感じはありますね…。

 

面白かったと思っていただけたら是非コメントをください!

 

 

それでは!

 

See you next time!

SunshineCTF 2020 Magically Delicious writeup

こんにちは! Ken.Sです!

 

ついさっきまで行われてたSunshine CTFのMagically Deliciousについての解説です!他の問題は解けてもすごく簡単なものなのでさらっと紹介します。

 

解説

Welcome! 1pt

Welcome to SunshineCTF 2020. Glad to have you here.

To show that you made it here okay and still have a pulse, enter the following flag: sun{yes_competitor_is_here}

 

sun{yes_competitor_is_here}

 

Disboard Round 2pt

Don't worry, this year we made the discord challenge much easier, just check out the announcements channel.

Discordに入ってannouncementsチャンネルのトピックを見るとflagがありました。

 

sun{see_i_was_here_all_along}

 

User Guide 10pt

While bored during the holidays because the Wi-Fi at your family's house is infuriatingly slow, you decided to go poking around through the garage. You come across a dusty cardboard box containing a very unusual computerized device along with some program cartridges. The first cartridge is labelled "PEGASUS User Guide". Why not pop it in, power the machine up, and see what happens?

続きを読む

Newark Academy CTF writeup

こんにちは!Ken.Sです!

 

昨日まで行われてたNACTFのwriteupを書いていきます!といっても、solves数多い問題しかやってないので参戦記の方が近いかもですが(笑)

 

www.nactf.com

 

 

 

 

結果

今回も個人で参加しました。存在自体に気付いたのが最終日だったので、ちゃんと考察しないといけない問題は解けなかったです。Crypto問題むずかった…。

f:id:partender810:20201105132334p:plain

総合結果

f:id:partender810:20201105132417p:plain

カテゴリー別

 

解説

問題が並んでた順です。解説と言いながら取り掛かったけど分からなかった問題も書いていきます。解けた方はご一報ください(笑)

 

Reverse Engineering

Generic Flag Checker® 1 75pt

Flag Checker Industries™ has released their new product, the Generic Flag Checker®! Aimed at being small, this hand-assembled executable checks your flag in only 8.5kB! Grab yours today!

ファイル:gfc1

 

解けている人多いし最初の問題だからRE初心者でもいけるだろうと、高を括ってやってみました。見事stringsでflagが出ました。

 

nactf{un10ck_th3_s3cr3t5_w1th1n_cJfnX3Ly4DxoWd5g}

 

Generic Flag Checker® 2 150pt

Flag Checker Industries™ is back with another new product, the Generic Flag Checker® Version 2℠! This time, the flag has got some foolproof math magic preventing pesky players from getting the flag so easily.
Hint : When static analysis fails, maybe you should turn to something else...

ファイル:gfc2

調子に乗って二問目。静的解析がダメなら実行だろうと動かしてみる。stringsでflagが書いてありそうな部分は見つけたけど、これgdbとかのデバッガー知らんとできないやつだ。断念。いつか勉強します。

 

 

General Skills

Survey 1pt

アンケートに答えるとflagがもらえます。解いている人少なかったのでみんな1点はいらないということかな。

nactf{survey_flag12f93}

 

Join the Discord 10pt

これもSurveyほどではないけど、みんな回答しているわけではなさそう。Discord内にflagが落ちてました。

nactf{n1c3_j0b_h4v3_fun}

 

Intro to Flags 10pt

NACTF flags are case-sensitive and should be inputted with the format nactf{...}

Practice entering your flag here: nactf{fl4gz_4_d4yz}

 

これはsolves数多かった。みんなアンケート答えるとか一手間かけての少ないポイントは眼中にないの?

nactf{fl4gz_4_d4yz}

 

Basics 30pt

Tiffany no longer communicates in normal text. Weird, I know. She randomly sent me this message: bmFjdGZ7YmE1MzVfYXIzX3N3MzN0fQ==

Can you figure out what it means?

 

やっと問題らしくなりました。末尾が=なのでbase64なのでしょう。久しぶりに使った気がする。

nactf{ba535_ar3_sw33t}

 

Grep 0 50pt
Sophia created this large, mysterious file. She might have said something about grap.. grapes? Find her flag!

ファイル:flag.zip -> flag.txt

 

テキストファイルは83MBと大きい。中は文章がめちゃくちゃありました。

問題名からgrepしてflagを持ってくればいいのでしょうが、メモ帳の検索機能で見つけたひねくれものは私です。

nactf{gr3p_1s_r3ally_c00l_54a65e7}

 

Numbers 50pt

What do the numbers mean?

ファイル:flag.txt

 

中にあった数字はいかにもASCII変換しろって数字。chrしてみたけど文章にならない…。

 

f:id:partender810:20201105134516p:plain

ASCII変換したのに

 

違うのか?と思ったけど最初の五文字を一つ前にするとnactfになることに気付く。全て-1してchrすればOK。

nactf{asc11_XB4RCR5}

 

Hashbrowns 50pt

MD made 5 hashbrowns this morning and forgot to add salt and pepper. He took a bite out of one of them and found a piece of paper with this written on it: 5af554431d976fdc57ea02908a8e0ce6.

 

まあMD5なのでしょう。なんかセキュリティ界隈でsalt and pepperって聞いたことあるな。最後の16進数はハッシュ値なのだろうけど、逆引きのように元の平文なんて分かるの?でもsolves数多いしポイントも低いから簡単なんじゃ?

と、50ptのくせに時間をめちゃくちゃ取られました。salt and pepperはパスワードをハッシュ化するときに必要なんですね。Adversarial Exampleでもそんな言葉あったような…。

ソルト (暗号) - Wikipedia

 

MD5はどうやらレインボーテーブル攻撃という、平文->ハッシュ値のセットをたくさん持っていると、ハッシュ値から平文を予測できてしまうという攻撃があるようです。上のソルトを入れると、この攻撃を受けにくくできるようです。

なんかそんなことやってくれるサイトやツールないかなと「MD5 逆変換」でググると、Hash Toolkit というのがあるみたいです。これの使い方が分からず苦労しましたが、もう一度ここに訪れるとあっさり解けました。なんだったんだろう。

 

https://hashtoolkit.com/decrypt-hash/?hash=5af554431d976fdc57ea02908a8e0ce6

 

nactf{secure_password}

 

Dr. J's Vegetable Factory #1 50pt

After years of collecting plush vegetable toys, Dr. J decided to take on his true passion: starting a vegetable factory. Dr. J is incredibly organized, so he likes all of his vegetables to be in the proper order. In fact, he built a robot "Turnipinator-1000" to alphabetize his vegetables for him! Unfortunately, Dr. J doesn't know what instructions to give Turnipinator-1000. Can you help him out?


nc challenges.ctfd.io 30267

Give instructions in the form of numbers separated by spaces. Entering the number x will swap the vegetable in position x with the vegetable in position x+1. Positions start at zero, not one. (Dr. J is a programmer after all.) For example, given the following vegetables: Avocado, Brocolli, Eggplant, Daikon Radish, Carrot, one possible solution is "3 2 3"

Avocado, Brocolli, Eggplant, Daikon Radish, Carrot

(swap 3 and 4)
Avocado, Brocolli, Eggplant, Carrot, Daikon Radish

(swap 2 and 3)
Avocado, Brocolli, Carrot, Eggplant, Daikon Radish

(swap 3 and 4)
Avocado, Brocolli, Carrot, Daikon Radish, Eggplant

Hint : Try sorting the vegetables by hand! For example: insertion sort.

 

まあ、アルファベット順に並び替えるだけです。ソートを多少知っていればそんなに問題ないです。これはsolver作らず手で解きました。3回正解するとflagが出ました。

nactf{1f_th3r3s_4_pr0b13m_13ttuce_kn0w_db4d736fd28f0ea39ec}

 

Arithmetic 150pt

Ian is exceptionally bad at arthimetic and needs some help on a problem: x + 2718281828 = 42. This should be simple... right?

nc challenges.ctfd.io 30165

Hint : What does uint32_t mean?

ファイル:arithmetic.c

 

x = 42 - 2718281828 ではないのか、と思ったら負の数はrejectされてしまいます。まあ、そうなればC言語だしオーバーフロー起こせばいいんですね。あとはそれ用にCプログラムを書けばいいです。

nactf{0verfl0w_1s_c00l_6e3bk1t5}

 

Dr. J's Vegetable Factory #2 150pt

Dr. J expanded his vegetable factory! Now he's got hundreds of vegetables. Same problem as last time: can you give Turnipinator-1000 the right instructions to sort Dr. J's vegetables?

nc challenges.ctfd.io 30267

Hint : It seems like there are too many vegetables to sort by hand this time. But not too many for a computer!

Check out the example script if you're unsure of how to connect to the server with code! example.py

 

#1の野菜数を多くしただけですね。100個あるのでプログラム組まないと死んでしまいます。

i番目に(アルファベット順で)小さいものをi番目にまでswapする形を取ります。初めにpythonのsortedでソートしたやつも持っておいて、それを0から順にindexで探せばOKです。一番小さいものが58番目にあれば、57 56 55 ... 1 0, で0番目まで来ます。二番目に小さいものが5番目にあれば、4 3 2 1で1番目まで来ます。これを記述するプログラムを組めばOKです。

nactf{d0n7_w0rry_p34_h4ppy_f27ae283dd72cb62f685}

 

Zip Madness 175pt

Evan is playing Among Us and just saw an imposter vent in front of him! Help him get to the emergency button by following the directions at each level.

ファイル:flag.zip

 

zipファイルを開くと1000left.zip, 1000right.zip, direction.txtの3つがあり、leftの方のサイズが大きいです。direction.txtを見ると"left"しか書いてなく、とりあえず1000left.zipを展開すると999left.zip, 999right.zip, direction.txtがあって…。これは途轍もないことだなと観念し、なんとかプログラムでLinuxのコマンド実行できないかと調べてました。そういえばPakenCTFでやったな。subprocessだ。

「unzip -o (階層)(左右).zip」を1000回実行すれば良さそうです。-oはoverwriteできるようなオプションです。階層はfor文で指定すれば良くて、左右はdirection.txtから読み取った方向を入れます。実行にはcallで行って、引数はリストで[unzip, -o, zipファイル名]とします。

nactf{1_h0pe_y0u_d1dnt_d0_th4t_by_h4nd_87ce45b0}

 

 

Dr. J's Vegetable Factory #3 175pt 104

Rahul hates vegetables. Rahul hates vegetables so much that he snuck into Dr. J's factory at night to sabotage Dr. J's vegetable production! He brought a sledgehammer and broke the wheels of Dr. J's robot! 😓 Now the robot is stuck in place, and instead of being able to swap any adjacent elements, it can only swap the elements in positions 0 and 1!

But Dr. J won't let this incident stop him from giving the people the vegetables they deserve! Dr. J is a problem solver 🧠. He organized his vegetables in a circle, and added a conveyor-belt that allows him shift the positions of the vegetables. He thinks that the conveyor belt should make it possible to sort his vegetables, but he's not 100% sure. Can you help him out?

nc challenges.ctfd.io 30267

Enter letters separated by spaces to sort Dr. J's vegetables. Entering "c" will activate the conveyor belt and shift all vegetables left one position. Entering "s" will swap the vegetable in position 0 with the vegetable in position 1.

 

cは野菜が左に一つずれ(一番左のは一番右に行く)、sは0,1番目をswapします。#2ではswapを好きなところでできたのに対し、#3では0,1番目しかできません。その代わりに野菜を一つずらすことができます。

 

解法としては、まず後ろからZの方からソートしていきます。

まず、sortedで先にソートしたのも持っておきます。一番後ろの野菜を0番目までに来るまでcを連打します(実際には変数mesに記憶させます)。0番目まで来たら[0:1]までソートしたこととします(swap一切してないけど)。

次に、後ろから二番目のを0番目まで持ってきます(c連打)。1番目が既にソートされているもの = 0番目にある野菜よりも後ろになるはずのものが来たらソートしたこととし、そうでないならsでswapします。三番目以降も同様に考えて行うと命令が完成します。

要はバブルソートですね。

nactf{1t_t4k35_tw0_t0_m4n90_8a51c7b47fbe227}

 

こういうプログラミング問題はやってて楽しいです(解けるかは別として)。

 

Grep 1 200pt

Elaine hid a REGULAR flag among more than 1,000,000 fake ones! The flag was an EXPRESSION of her love for nactf, so the first 10 characters after "nactf{" only have the characters 'n', 'a', 'c', and the last 14 characters only have the characters 'c', 't' and 'f'. There are 52 characters in total, including nactf{}.

ファイル:flag.zip -> flag.txt

txtファイルの中には"nactf{"から始まるflag候補が大量にあります。flagになるのは"nactf{"のあとに[n,a,c]のどれかが10個、任意の文字が21個、[c,t,f]のどれかが14個、"}"

です。これをコマンドで書けばOKです。

cat flag.txt | grep -E "nactf{[n,a,c]{10}.{21}[c,t,f]{14}}"

nactf{caancanccnxfynhtjlgllctekilyagxctftcffcfcctft}

 

(実は正規表現を調べるのが面倒でpythonで書きました)(そのあと勉強した)

 

World Trip 300pt

Will has been travelling the world! Here's a list of the coordinates of the places he's been to. There might be a secret message hidden in the first letter of all of the countries.

Note: The flag is all uppercase without spaces or "_"

Hint : This would be really tedious to do by hand...

Hint : The last part of the flag is just random characters and is not supposed to make sense

ファイル:enc.txt

 

enc.txtには座標(緯度経度)が194個入ってて、その座標の国名の頭文字を並べてnactf{}で括ればいいようです。

座標から国を特定するのってどうするんだ…。とりあえず、enc[0]を調べてみるとItalyに旅行できました。194個ってことは全部の国に行けるのかな?(194ヶ国は違いました。世界の国は196ヶ国、国連加盟国は193ヶ国、バカがバレる)

 

 

そういえばcurlコマンドでURL指定で情報持って来れるなぁ、とgooglemapのURLをぶったたくといっぱい情報が来ました。まず、日本語だとgrepしにくいので英語に変換します(URLの最後に?hl=en)。あとはgrepsedの駆使とbashでやりました。og:descriptionって単語をgrepするとItalyが含む列を持ってこれます。あとはsolverに書いておきます。Githubを見てください。

得られた文字列をtxtファイルに書き込んでいったのですが、192行でした…。2個抜けてる…。それを探すのに30分近くかかった…。

 

 

次は、国名は-2番目にあるのでそれを引っ張ってこうと思ったら「Dominican Republic」のように国名が一単語ではないやつがいくつかあって、それを直すのに時間がかかりました(一番最後の","の次という選び方をすればよかった)。

それを直すのにtxtファイル見直したら、South Pacific Ocean と Lake Kivuがありました。Lake Kivuはともかく海はどこの国でもないやろ!!ちゃんと調べたらトンガという世界で三番目に小さい国でした。Lake Kivuはちゃんと地図を見ずwikiの情報でコンゴだと思ってたらincorrect。座標で検索するとルワンダ寄りでした…。ただそれでもincorrect。DiscordでAdminに聞きまくってました。

 

 

結局、(一番最後の","の次という選び方をすればよかった)が重要でした = 二単語のやつを一つ直し忘れてた!!! めっちゃ時間かかったし、何よりしょうもないミスを直せばcorrectというのも悔しい…。

英語名知らない国もあったし、そもそも聞いたことない国もありました。ちなみに被っている国がいくつかあったので193ヶ国すら巡れなかったです…。

ちなみに、引っ張ってきたのはここの情報のようです。

f:id:partender810:20201105220804p:plain

一つ下の情報だと、Lake kivuとかの場合も地名が書いてあった

 

nactf{IHOPEYOUENJOYEDGOINGONTHATREALLYLONGGLOBALTOURIBOFAIQFUSETZOROPZNQTLENFLFSEMOGMHDBEEIZOIUOCGSLCDYMQYIRLBZKNHHFGBPDIVNBUQQYPDCQIAVDYTRFOCESEQUOUUMSKYJOVKVJGMRGNATNIRESHRKHCEDHHZYQRZVOGCHSBAYUBTRU}

 

Dr. J's Vegetable Factory #4 350pt

Thanks to you solving Dr. J's conveyor belt conundrum, Dr. J's vegetable factory is up and running once again. But this time, Juliet breaks into the factory to finish what Rahul started. For some reason, she doesn't break Turnipinator-1000 completely. First, she spins Turnipinator-1000 in a random direction. Then, she pulls the arms of Turnipinator-1000 a random distance apart so it can no longer swap adjacent elements! Now, it can only swap the vegetable in position x with the vegetable in position y!

Initially, Dr. J is very sad. 😥 Even with the conveyor belt, he doesn't think he can sort his vegetables anymore. But then, Dr. J has a brilliant revelation! 💡 He scribbles on scratch paper for a few minutes, then he gets up and removes a few of the vegetables from the conveyor belt.

Proudly, he declares, "Dr. J's Vegetable Factory is back in business!"

nc challenges.ctfd.io 30267

Same instructions as in part #3. Enter letters separated by spaces to sort Dr. J's vegetables. Entering "c" will activate the conveyor belt and shift all vegetables left one position. Entering "s" will swap the vegetable in position x with the vegetable in position y. (x and y will be given.)

何してくれてんねん!!!!

 

#3では0,1番目をswapできたのに今度はx,y番目となりました。先程は隣りあった野菜をswapできたのに、離れた場所でのswapだとソート済みな部分も壊してしまう可能性があります。最初はそこに気付かず、なぜできないんだ、(自分のソート後の結果を見て)なぜこんなぐちゃぐちゃになっているんだ、となってました。

 

 

結果、Flagは得られなかったのですがソートはなんとかできました。恐らく命令が長すぎて実行時間がかかりダメだと判定されたのだと思います。以下、私なりの解法です。

  1. sortedを利用し、得られた野菜をソートした結果(以後vとする)を持っておく
  2. x,yについて、x > yなら、x,yの値を入れ替える(計算しやすくするため)
  3. p = 野菜の個数-2を初期値として、v[p]を何回swapすればv[p+1]の一つ左にいくか、与えられた野菜の配列(以後gとする)から計算する。v[p],v[p+1]のindexをs,tとすると、s+(y-x)*(swap_count) = t-1 mod 野菜の個数の式が成り立ち、(y-x)は一回のswapで移動する長さであり(野菜の個数)とは互いに素になる(そうでないとそもそもソートできない)。なので(swap_count) = (t - 1 - s)*(y-x)^-1 mod 野菜の個数と求まった。
  4. swapした際にソート済みの部分を壊してしまったらその野菜をFirst in Last outのキューで格納。そうすると、元に戻すために各野菜1回のswapで済む。First in First outだと、swap回数が増えてしまう。
  5. 野菜を一つ左にスライドするcについては、1回ずつ行うのではなく任意の回数一気にできるよう関数を作っておく

 

これで、ソートは上手くいくのですが命令長が800万ほどとなりそれがflagが出ない原因のようです。手元でやればすぐ終わるのですが…。解けた方はご一報を(solves数少なかったけど…)

 

 

Cryptography

Caesar's Challenge 25pt

Zabelo wrote this message on a note he passed to me. anpgs{q3p1cu3e1at_e0px5!} He also told me his favorite number was 13. What could this mean?

13が好きだとは珍しいですが、人それぞれですからね。rot13でしょう。

nactf{d3c1ph3r1ng_r0ck5!}

 

YAMS 100pt

Instead of turnips, Yavan loves YAMS. Day and night, he sings about YAMS, dreams about YAMS and runs to the store to catch the newest released batch of YAMS. Hes cryptic too. I wonder what this could mean.

Uexummq lm Vuycnqjc. Hqjc ie qmud xjas: fycfx{waY5_sp3_Y0yEw_w9vU91}

Hint : I can't believe he also eats them with vinaigrette!

 

fycxfがnactfになるんだろうな、3文字目がc->cだからなんかあるのかなと考えてたらヒントを見逃してて「ああVigenereか」と。久しぶりでした。

ヴィジュネル暗号 - Wikipedia

keyがVigenereには必要ですが、c->cがあるのでAが入っている & a->yがあるからYがある、つまりyaと続くkeyがある。はい、問題名がkeyですね。

nactf{yaM5_ar3_Y0mMy_w9jC91}

 

Error 0 150pt

Rahul has been trying to send a message to me through a really noisy communication channel. Repeating the message 101 times should do the trick!

ファイル:enc.txt

最後まで解けなかった…。中は01だけで記述されてて、長さが23432でした。今23432と書いてて101の倍数じゃん!ってなってます。長さが8の倍数だから、長さ8毎持って来てASCII変換したら最初にnactf(aはホモグリフでaの上になんかついてるやつ)となり、ここからなんか行けるか…と思ったけど、時間切れ。23432 = 232*101 を気付いた今もいい案は思いつかず…。101が二進数かなとも思いましたが、5をどうしていいか分からず。

 

Oligar's Tricky RSA 175pt

The crypto master Oligar just sent this file with three numbers. What do they mean?

ファイル:rsa.txt

やっとRSA問題。NをFactorDBにぶん投げて素因数分解可能。終了

nactf{sn3aky_c1ph3r}

 

Random Number Generator 250pt

Dr. J created a fast pseudorandom number generator (prng) to randomly assign pairs for the upcoming group test. Austin really wants to know the pairs ahead of time... can you help him and predict the next output of Dr. J's prng?

nc challenges.ctfd.io 30264

heck out the hint for "Dr. J's Vegetable Factory #2 🥕" to see an example of how to connect to the server with code.

ファイル:rand0.py

seedを上手く使えば、randintの結果を予測出来てflagが手に入るんだな、でもどうしたらいいの?で時間切れ。こういうのをスッと解けないとcrypto得意なんて言えないな(笑)

 

Forensics

Gummies 50pt

Kylie is obsessed with gummies. With her collection of miscellaneous gummy bears, she took this incredible picture which is now her phone's wallpaper. Can you find her flag?

ファイル:gummy.png

Steganographyってやつですかね。PNGのヘッダーもちゃんとしてるし他に何したらいいの?状態。ただ、このサイトでpngファイルと同じ画像を発見。なんだったんだろう。

unsplash.com

 

Meta-morphosis 75pt

Mikey really likes Metamorphosis by Franz Kafka, so much so that he sent this meme to the class.

ファイル:meme-3.jpg

また同じ部類かな、ととりあえずstringsしてみました。あ、flagだ。

nactf{m3ta_m3ta_m3ta_d3f4j}

 

 

Web

Inspect 50pt

Lola's new to website-building. Having just learned HTML and CSS, she built this site and embedded some dark secrets. I wonder where I could find them.

http:/inspect.challenges.nactf.com/

とりあえずF12。あ、flagだ。

f:id:partender810:20201105231525p:plain

右下にホラ

nactf{1nspect1ng_sp13s_4_lyf3}

 

Missing Image 75pt

Max has been trying to add a picture to his first website. He uploaded the image to the server, but unfortunately, the image doesn't seem to be loading. I think he might be looking in the wrong subdomain...

https://hidden.challenges.nactf.com/

URLにアクセスすると、真緑な画面。F12で覗いてみると、画像(http://challenges.nactf.com/flag.png)が出てこないとのこと。サブドメインが違うということで、アクセスURLと同じようにhiddenを付けてみる。はい出た。

https://hidden.challenges.nactf.com/flag.png

nactf{h1dd3n_1mag3s}

 

Forms 125pt

Skywalker has created 1000 login forms and only managed to make one of them work. Find the right one and login! He also went a bit crazy with the colors for some reason.

https://forms.challenges.nactf.com/

1000個のログインフォームの内一つは本物。とりあえずF12でソースを見てみましょう。10000行を超えるソースですが、1つのフォームに対して10行近くあってそれが1000個あります。その下に行くとログインできそうな関数がありました。

f:id:partender810:20201105232513p:plain

この関数を呼んでるフォームを探そう

f:id:partender810:20201105232714p:plain

Ctrl+F でverifyとすると…

Form 673にUser:admin, pass:password123でログインするとflagが出ます。

nactf{cl13n75_ar3_3v11}

 

Calculator 150pt

Kevin has created a cool calculator that can perform almost any mathematical operation! It seems that he might have done this the lazy way though... He's also hidden a flag variable somewhere in the code.

https://calculator.challenges.nactf.com/

なんか裏で計算してるんだな、変な命令流せばなんかflag出るのかってF12で覗いたけど分からず…。ソースにあんま書いてない?とか思ったけどもうよく分からない、無理。

 

 

例によって、問題やsolverはGithubに載せてます!

github.com

 

それでは!

 

See you next time!

 

 

PakenCTF writeup

こんにちは!Ken.Sです!

 

先程まで行われてたPakenCTFのwriteupです!楽しいCTFでした!

今回は初心者用でしたので、m1z0r3では参加せず個人で参加しました。しかしそのm1z0r3にボコボコにされました(笑)

 

 

 

結果

 

f:id:partender810:20201101170909p:plain

総合結果

f:id:partender810:20201101170929p:plain

カテゴリー別

 

 

解説

 

pwn

store 100pt

問題文:

「以下のコマンドからサーバープログラムに接続して、FLAGを入手して下さい。

nc 3.131.69.179 17693」

そして、store.cと実行ファイルstoreが与えられます。

 

store.cを見ると、所持金998244353円の状態から100円のリンゴをいくつか買ってください。その後の所持金が1000000007円以上だったらflagが出ますというもの。

現実世界だとあり得ませんが、このプログラムではint型で定義されているのでオーバーフローを起こせばいいのです。手元でリンゴをいくつ買うとオーバーフローが起きるかというプログラムを組めば、あとはそれをサーバーに送ればOKです。

 

pakenCTF{6ef1ne_Int_l0n9_l0ng}

 

 

forensics

amazing sound 100pt

amazing_sound.mp3 が与えられます。linux上でstringsとかやってみましたが一切分からず。聞けばいいのかと思ったが何言ってるか分からず。問題名から何かすごい音なのかな、逆再生とかできんのかなと思ったらまさかのビンゴ!

逆再生した音声は英語で数字を言っているものでした。数字と言っても1~9だけなのでなんとか聞き取れました。

 

pakenCTF{3426543712456783}

 

 

web

F12

問題文、ファイルなどは一切無いのでとりあえずF12キーを押します。そうしたらElementにflagがありました。

 

pakenCTF{deve10per_t0015}

 

 

unreadable2

u.js が与えられます。中を見ると、_0x*****という変数に文字が代入されています。Javascriptはあまり分からないのですが、CTF{}の文字があったのでおそらくflagをバラバラにしているだけと見たので、中身をコピってpythonで解きました。

 

pakenCTF{h0w_d0_yOu_re4d_th1s_text}

 

 

misc

Hello World 10pt

問題文:以下の提出フォームに pakenCTF{HelloWorld} と入力して提出して下さい。

 

終了!!

 

pakenCTF{HelloWorld}

 

 

kangaetenai 150pt

問題文:

「以下の文字列の偶数文字目を取り出して、pakenCTF{}で囲ったものを提出して下さい。

厳密に偶数文字目である事に気をつけて下さい。

​the​ans​w​eri​sra​n​domst​rin​g」

 

簡単じゃんと思ったのですが、トラップが仕掛けてありました。pythonで偶数文字目だけ取ろうとしたらこんな表記になりました。

 

the ans w eri sra n domst rin g

 

よく見てみるとゼロ幅スペースと呼ばれる\u200bが入ってます。

ゼロ幅スペース - Wikipedia

 

しかも偶数文字目と言っても、一番最初は0文字目として数えられるようでした。tが1文字目だとばかり思っていたので何回もincorrect出しました。

 

pakenCTF{teasweisandmtrng}

 

 

Unbearable to read 250pt

問題文:

「丸止无和川加奴周利加宇奴和川加奴最毛末幾左川止宇久川仁久知分加数二十個答衣左安

カッコの内部は算用数字

pakenCTF{〇○○}」

 

は??????????

中国語じゃね?とgoogle翻訳にぶち込んだが意味のある文章になりません。最後に20個答えろみたいなことを言っているようです。

 

一晩寝かせてみたら、「加」とか「和」とか「宇」とかひらがなの原型となった漢字が多く使われているな、って思い調べてみるとほとんどがそうでした。そこから、知り合いにヒントをもらった形にはなりましたが、ひらがなの原型でない漢字を除くと「丸周最分数二十個答」となるっことが分かりました。

 

丸、周、分数から円周率じゃね!?とエスパーして、円周率の下20桁を提出したがincorrect。flag形式をよく見ると一番最初の〇だけ大きいことから3.14=3桁の容量で3と小数点以下19桁提出したら通りました!!

 

最終日に通ったのですが、自分も含めてsolve数は3でした。めちゃくちゃ嬉しい。

 

pakenCTF{31415926535897932384}

 

 

OSINT

ネットストーカーに向いている問題達でした。

Twitter 50pt

問題文:「パ研の公式Twitterを知っていますか?僕は知っています。」

「pakenCTF パ研 Twitter」で検索。公式アカウントがflagをツイートしてました。

 

 

pakenCTF{Y0u_are_tvv1tter_m45ter}

 

 

Address 100pt

問題文:「この中央の建築物の場所を答えよ フラグの形式は pakenCTF{<郵便番号(間に_)>_<丁目>_<番地>_<号>}」

これとpicture.jpgが与えられます。

 

f:id:partender810:20201102161820p:plain

picture.jpg

 

どこかのクリエイトのようですが、白黒で画素も荒いためなかなか判別が難しいです。

 

しかし、店の壁のところに「武蔵野」や「三〇中央病院」という文字が見えました。恐らくその場所への案内なのでしょう(→が一緒にあるやつ)。武蔵野の近くにある地名で三から始まるのは三鷹でしょう。調べてみたら三鷹中央病院という病院は存在しました。その近くにあるクリエイトは3店ほどあり、あとはストリートビューで探せばOKです。

 

答えは、クリエイト薬局 三鷹下連雀店でした。

 

pakenCTF{181_0013_4_14_16}

 

 

kaishuu 150pt

問題文:「ハッシュタグの中身を当てて下さい。FLAGはハッシュタグの中身 ( '#' なし) をpakenCTF{}で括ったものです。」

これとimage0,1,2,3の4枚が与えられます。

(重かったので直接問題を見てください)

 

これはm1z0r3の人達と話しながらやってたのですが、一人が渋谷っぽいと「渋谷 落書き」とググったところ以下のサイトがヒット。

news.yahoo.co.jp

 

良い話なような気がするけど、落書きっていいのかな。

 

pakenCTF{391045428}

 

 

Station 250pt

問題文:「この駅の名称とこの線の名称をローマ字で答えよ

ただし「都営」などは不要で、地名のような固有名詞で回答せよ

回答形式は、英字はすべて小文字、ヘボン式

pakenCTF{<駅の名前>_station_<線の名前>_line}」

これと、station.jpgが与えられます。

 

f:id:partender810:20201102162341p:plain

station.jpg

 

写真から見るに、渋谷と吉祥寺を結んでいることから京王井の頭線、吉祥寺行きと永福町方面のホームが別であるからその間の駅、2つの線路に対してホームが一つという形の駅ということが分かります。あとはgoogleビューで最後を満たす駅を探せばOKです。

 

すぐに駅は分かったのですが、固有名詞なので頭文字を大文字にしたり線の名前にkeioと入れていたのでincorrectが続きましたが、なんとか通りました。

 

pakenCTF{kugayama_station_inokashira_line}

 

 

このように、写真から簡単に場所を特定できてしまいます。皆さんSNSの投稿などには気を付けましょう。水曜日のダウンタウンに目を付けられます

 

 

kyopro

JOISS2020 70pt

問題文:「これは何でしょう?
}rerv{nTC__Vr5pehk1sVaer4nf$rTeoun8v0Fn
ただし、ここでは $ を他の文字より真に小さい末端文字として扱っています。」

 

8割方OSINT問題でした。

 

まず、これもflagを並び替えたものだろうと推測できます。アナグラムだけでは特定できない上に$が気になります。

 

問題名でググると以下のgithubがヒットします。どうやら作成者のものみたいです。その中のpdfファイルを読み込みます。

github.com

 

p23あたりに$を末端文字とするという問題文と同じ文章が出てきます。そしてBW変換というのを行って暗号化しているみたいです。

 

後ろn文字目(n:0~文字列の長さ)から最後までの文字列を辞書順に並べます。例えばapple$だと出来る文字列は、$,e$,le$,ple$,pple$,apple$となり辞書順に並べると

$

apple$

e$

le$

ple$

pple$

となります。

 

辞書順の上から順にその文字の一つ前に来る文字を暗号文とします。上記の例だと、

$ -> e

apple$ -> $

e$ -> l

le$ -> p

ple$ -> p

pple$ -> a

暗号文:e$lppa

となります。

 

なので、暗号文を一文字ずつを辞書順に並べることで、ある文字が何の文字の前に来るかが分かります。その結果がこんな感じです。

 

f:id:partender810:20201101192527p:plain

並び変えてみた結果

 

これをあとはしりとりの要領で繋げる…としたのですが、なかなか上手くいきません。しばらく経っても分からずtr4nsfornとVVheelみたいな文章が出てきた頃、BW変換とググると以下のサイトが…

smrmkt.hatenablog.jp

BW変換ってこの略か、と分かりあとはleetに沿ってflagを作れば一発でした。8->Bであったり、二つの同じ文字を並べて一つの文字を作る(VV->W, vv-> w, nn-> m)というleetは初めてでした。

 

pakenCTF{8urr0vv5_VVhee1er_Tr4nsfornn}

 

 

Let's play Nim 150pt

問題文:「Zipファイルをダウンロード・解凍して遊んでみて下さい!
勝つとFLAGを得られます。」
これとLetsPlayNim.zipが与えられます。

 

遊び方がしばらく分からなかったのですが、実行ファイルということで./Gameで良かったです。

 

以下、問題のNimのルールです。

<Nimのルール>
2人のプレイヤーがいくつかのコインの山からコインを取り合う。ゲームの目的は、最後のコインを取ることである(コインの代わりに石や豆を使ってもよい)。
まず、コインの山を複数準備する。
各々のプレイヤーは自分の順番のとき、コインの山を1つ選んでその山から1枚以上のコインを取り去る(複数の山からコインを取ったり、コインを一枚も取らなかったりするのは反則である)。これが終わったら次のプレイヤーの手番になる。
すべての山のコインがなくなったとき、ゲームは終わりである。そして、最後のコイン(複数のときもある)を取ったときのプレイヤーが勝者である。


※入力の際に整数以外を入力した際の動作は未定義である。
※プログラムに勝利することでFLAGを得られる。
※プレイヤーが先手である。
※初期値は乱数で決定される。
※Mountainの入力の際に-1を入力することで中止できる。

 

つまり、最後一つの山しかない状態で自分の番が来ればいいのです。そして、1:1, 2:1の状態で来ると詰みます。一回目は案の定負けてその反省を活かしたら二回目に勝てました。ちゃんとした考察は出来ていないのですが、山を2つにして、1:2,2:2の形で相手に送ると勝ち確です。まず、二つの山だけにするよう他の山を全て無くし、あとは二つの山のコインの数が同数になるようにすればOKです。

 

pakenCTF{Y0v_4r3_N1m_M4s7er}

 

 

shortest 150pt

問題文:「N頂点M辺の全ての重みが1の無向グラフがあります。

define君は頂点0からの全頂点への最短経路を求めるプログラムを書きましたが、どうやらバグっているようです。

撃墜テストケースを作成して下さい。

フォーマット

N M
A_1 B_1
...
A_M B_M
ただし、N, M共に5以下である必要があります。

入力例

3 2
0 1
1 2
撃墜テストケースをnc 3.131.69.179 18293でサーバープログラムに接続、提出するとFLAGを得られます。

プログラム : WA.cpp」

 

とりあえずWA.cppを見てみます。最初は全然わからなかったのですが、21行目でd[u]が-1なら更新するってとこに疑問を感じ、以下のような入力を行ったらflagが出ました。

5 5

0 1

1 2

2 3

3 4

0 4

 

0->4はコスト1で行けるが、前の4つの命令で0->4のコストが3となり-1ではないので更新されなかったって感じです。競プロ強者曰く、stackを使っているのがいけないみたいです。

 

pakenCTF{d0_u_l1ke_c0de40rces}

 

 

binary 200pt

問題文:

「1以上1000以下の10000個の数字が1列に並んでいます。

1番先頭の数字は1、1番最後(つまり、先頭から10000番目)の数字は1000で、隣り合う数字の差の絶対値は1以下です。

? x を入力することで、先頭からx番目の数字を得ることができます。

この操作を高々10回行った後、500がある位置のうち1つを、その位置をxとして ! x の形で入力し、出てきたフラグを答えてください。

ただし、この問題の設定で数字の列に500が含まれていることは証明可能です。

nc 3.131.69.179 19292」

 

例えば1~3の数字が一列に並んだ場合、1->3に飛ぶことは出来ない(隣り合う数字の差の絶対値は1以下)ので、2は必ず登場します。この要領で考えると500という数字が必ず出てきます。

 

正しい解法かは分かりませんが、まず5000番目の数字が何か聞きます。500より小さかったら、5000+(500とその数字の差)番目以降にあることが分かります。500より大きかった時も同様です(5000-(その数字と500の差)以前にある)。これを繰り返すと10回以内で大抵見つかります。500に近くなったら、たとえば480とかでたらちょっと大きい数字番目を聞いて、[a,b]みたいに範囲を限定するとかなり楽でした。

 

pakenCTF{pvvnt0o1s_1s_usefu1}

 

 

cycle 250pt

問題文:

「N頂点M辺の重みなし有向グラフがあります。各頂点には1からNの番号が、各辺には1からMの番号が振られており、i番目の辺はAiからBiに向かって張られています。

あなたは、このグラフに閉路が出来るように、辺を0本以上追加します。

追加する辺の候補はK個あります。i番目の候補は、PiからQiに向かって新たに辺を追加するということを表し、また、その辺を追加するにはCiのコストがかかります。

閉路を作るのにかかるコストの最小値を求めてください。

ただし、辺を追加する必要がない場合は0を出力し、どのように辺を追加しても閉路が作れない場合は-1を出力してください。

入力フォーマット N M K
A_1 B_1
A_2 B_2
:
A_M B_M
P_1 Q_1 C_1
P_2 Q_2 C_2
:
P_K Q_K C_K

制約

1≦N≦1000
1≦M≦1000
1≦K≦1000
1≦A_i, B_i, P_i, Q_i≦N
1≦C_i≦10^9
グラフは連結とは限らない
この問題に対する正しい出力をAnsとすれば、FLAGはpakenCTF{Ans}です。

入力ファイル : input.txt」

 

まず問題文の解釈に時間がかかりました。全ての頂点を訪れる必要は無く、一つ閉路作ればいいのです。それに気付くのが遅れ-1でないのか?と思ってました。

 

方法としては深さ優先探索で元の頂点まで戻ってこれるか調べその時のコストを記憶します。そのコストより小さいコストで閉路が出来たら更新します。

 

結局調べたら閉路は一個しか作れないみたいです。

 

pakenCTF{751878637}

 

 

inversion 250pt

問題文:

「長さ N の 要素が1〜 N からなる順列Aで、転倒数が K であるようなものの個数を10^9+7で割った余りを求めて下さい。

ただし、数列Aの転倒数とは i < j かつ A_i > A_j であるような (i, j) の組の個数を言います。

この問題の答えを
Test1 : N=245,K=18946
Test2 : N=489,K=75634
の場合について求め、
pakenCTF{(Test1の答え)_(Test2の答え)} の形で提出して下さい。(括弧は入れない)」

 

この問題面白かった!!

 

初めはNC2 (combinationのやつ)で考えるのかと思いましたが、回数が多すぎる…。ということで、Nが小さい場合で考えていきました。

 

i) N=2のとき

(1,2), (2,1)の2通りなので、転倒数とその個数は[1,1](i番目に転倒数がiの時の個数と表現していきます)となります。

 

ii) N=3のとき

1番目に1を置いた場合、その1と転倒数になるペアは存在しません。故にこの場合は(1,2,3), (1,3,2)の[1,1]です

1番目に2を置いた場合、2,3番目どちらに1を置こうが2と転倒数になります。あとは3と転倒数になるかどうかなので(2,1,3), (2,3,1)の[0,1,1]です

1番目に3を置いた場合、2,3番目どちらに1,2を置こうが3と転倒数になります。あとは1,2と転倒数になるかどうかなので(3,1,2), (3,2,1)の[0,0,1,1]です。

全て合わせると、[1,2,2,1]となります。

 

ここで、(1,1)という並びが上記3つ全てあります。ここから数学的帰納法で考えます。

N=kのとき、1番目にxを置いた場合、x-1以下の数字と必ず転倒数になる。2番目以降は

N=k-1のときに求めた。と考えると、あとは足し算するだけです。

 

[1,2,2,1]のような配列を作ると、i番目には転倒数iの時に何通りのペアがあるかが格納されます。

 

実行時間は時間がかかりましたが(2分程)、正しい結果が出力されました。

 

pakenCTF{965917879_825627234}

 

 

3BHR 400pt

問題文:「時は2050年。自治会によって奪われた自由を取り戻すべく、我々筑駒革命軍は自治会率いる筑駒防衛軍に宣戦布告した。

決闘の場所は筑駒のグラウンドである。

グラウンドは南北にHm、東西にWmの長方形である。ここで、北西の端からx m南に、y m東に行った点を(x,y) と表現することにしよう。

グラウンドにはN人の防衛軍がおり、i 人目は(X_i,Y_i) に立っている。いずれも南北両方向または東西両方向に向かってビームを撃っており、南北方向ならp_i=0, 東西方向なら p_i=1 である。

我々は任意の回数だけ防衛軍の射程圏外の任意の場所に移動、東西または南北にビームを撃ってその方向にいる防衛軍を倒す事ができる。なお、グラウンドの外から撃つこともできるが、防衛軍のビームはグラウンド外にも貫通することに注意だ。

さて、最大で何人の防衛軍を倒す事ができるだろうか?

入力フォーマット

H W N
X_1 Y_1 p_1
...
X_N Y_N p_N

制約

H,Wは10^9以下
Nは10^5以下
0<=X_i < H
0<=Y_i < W
入力例1
5 5 2
1 1 1
1 3 0

出力例1
2

入力例2
5 5 4
1 1 1
1 3 0
3 3 1
3 1 0

出力例2
0

この問題の 入力1 , 入力2 についての正しい出力をそれぞれAns1,Ans2とすればFlagは pakenCTF{Ans1_Ans2} です。」

 

さすがは400点問題、めちゃくちゃてこずりました。最初は、縦横それぞれにビームの通っている座標を格納する配列を作り、ある防衛軍隊員が一方向にしかビームが通っていない座標にいたら死んだこととし、その防衛軍が出しているビームを消すという作業を繰り返し、更新されなくなったら終わる(その消えたビームによって一方向しかビームが無い座標が増えそこに隊員がいた場合は更新)というプログラムを組みましたがincorrectを連発しました。

 

結局、O(N^2)というクソ長いプログラムを書き、二日目の夜就寝しました。起きたら見事答えをはじき出しcorrect! 良い子は真似しないでね!

 

内容としては、ある隊員の放っているビームとは垂直のビームを放っていて且つそのある隊員の座標を通るビームを放つ隊員達を格納する配列を組み、その配列が空になると死ぬという感じです。

 

pakenCTF{55157_80517}

 

 

CTFでのプログラミング問題はオーダーめちゃくちゃでも時間かけてでも通ればいいから良い(だから成長しない)

 

crypto

salad 70pt

問題文:「これはなんでしょう?」
sdnhqFWI{wklv_lv_wrr_hdvb}

 

まあROTですね、FWIだからrot23でしょう。

rot13.com

 

pakenCTF{this_is_too_easy}

 

 

Mr.Taher 200pt

Mr-Taher.zipが与えられます。中にはcodeとpycが与えられ、codeの中にはcode1,2があります。この時点でブロック暗号か?いやだな?とか思ってました。

pycの中が分からず、見たらなんかplaintextとか書いてあって、ここからソース復元できないかなって思ったら、pycってpythonの逆コンパイルした時の拡張子なんですね、このファイルは拡張子ないですが…。

unpyclibはインストールしたんですけど、pipが3系だったので2系で書かれてるこのpycは復元できず…。途方に暮れてたら、悔しいことにtechacademyのサイトに助けられました…。

Pythonのuncompyleモジュールの使い方を現役エンジニアが解説【初心者向け】 | TechAcademyマガジン

uncompyle6 pyc.pyc(cp pyc pyc.pycを忘れずに) で復元できました!!

f:id:partender810:20201101231347p:plain

コンパイル結果

 

ElGamal暗号でした。ご丁寧に秘密鍵を書いてくれているので、あとはwikiみて復号の仕方を思い出します。c1^(-x)*c2 mod pでした。-x乗する時にc1でinverse取るのを忘れないように。

 

pakenCTF{7a6er_4_31GaMa1}

 

 

Easy RSA 200pt

問題文:
RSA暗号の説明をよく読んで、復号して下さい。部誌のP45〜を読むのも良いと思います。」
これとhttps://paken2020.web.app/assets/2020_paken_bushi.pdf, RSA.txtが渡されます。

RSA.txtにp,qがあるのでちゃっちゃと復号させます。

 

pakenCTF{d16_y0u_un6erstand_r5a}

 

 

kazoeage 250pt

問題文:
RSA暗号の公開鍵と暗号文から復号してください。」
これとkazoeage.txtが与えられ、中にはN, e, cがあります。kazoeageとかいうからNが素因数分解できないのかと思ったら普通に出来ました。あとは前問と同じです。

 

pakenCTF{k4z0e4ge_1s_4un}

 

 

Coprime Crypto 500pt

問題文:

「---Decrypt this cryptograph---

"c1ys{4_C0_ky_}_hhaFrnn75ar5!y7p3T8aep1p"

---Examples of plain texts and codes' pair---

"Tsukukoma-Paken" "ea-mkksnkPaouuT"

"kenkenken2004" "4002nekneknek"

"We_love_CTF" "oCevT_eFl_W"

"Prime_Number_Is_Still_Veiled" "lerlri__mVIees_i_NlSuetmdibP"

"Are_You_Enjoying_This_CTF?" "?FTC_sihT_gniyojnE_uoY_erA"

"abcdefghijk" "eibfjcgkdha"」

 

とりあえず並び替えされていて、平文の頭文字が暗号化されると一番後ろに行くことが分かります。そして中には逆から読めば平文になる暗号文もあります。Coprimeということで互いに素からエスパーします。平文を等間隔で書いたものだろう、逆読みのやつはn-1を互いに素としているのだろう、ということで復元します。pの次はa,k,e,nですから、p-a間とa-k間が等しいaを見つけて、その差分でグルグルまわして終了です。

 

pakenCTF{7h15_15_an_3asy_cryp708r4phy!}

 

 

Black Box X 600pt

BlackBoxX.zipだけが与えられます。この問題はその中のblackboxxファイルが実行ファイルだということに気付けば7割方OKです。何か文字入れたら16進数が出てきてencodeと同じだと気づきます。そして、aと入れたら毎回同じ出力であること、入力をa,abとしたとき前6桁が変わってないこと、入力をb,abとすると後ろ6桁は変わることが分かります。暗号の仕方がブラックボックスということでしょう。あとは、string.printableで一致するかのbruteforce確認作業です。一致したらその文字を加えてまた回しましょう。

 

pakenCTF{Y0u_1i8hte6_7he_dArKNe55}

 

 

 

解けた問題は以上になります。cryptoの150ptが解けなかったのは悔しいです。対象が初心者用ということで、普段やらないWeb, misc, pwnなどやってみましたが面白いですね!アンケートで50pt貰えるのも嬉しいですね(笑) 最近のCTFは難しすぎるのでこのくらいの難易度が丁度良くめちゃくちゃ楽しかったです!!

 

そして、m1z0r3に負けて悔しかったのでこれをお供えします。

 

f:id:partender810:20201101233157p:plain

一緒にマラソン走ろうねと言って、異常なラストスパート見せる奴

 

solverなどは後日GitHubに掲載します!

問題やsolverはこちらです!

github.com

 

それでは!

 

See you next time!

 

 

 

Syskron Security CTF 2020 writeup

皆さん、こんにちは! Ken.Sです!

 

今回は、先程まで行われてたSyskron Security CTF 2020のwriteupです!最近のCTFはかなり難しいものが多いのですが、今回のCTFは問題数が多かったりtriviaという問題があったりで自身最高の6問解けました!(簡単なものしかないけど…)

 

ctf2020.syskron-security.com

 

 

結果

個人

解いた問題:6問

得点:395pt (20-25*3-100-200) ヒントで50pt使ったのでスコア上では345pt

 

m1z0r3

解いた問題:14問

得点:1500pt

順位:122th

 

Welcome letter

問題概要

分野:reading

得点:20pt (888 solves)

 

問題ファイル

  • welcome-letter.pdf

 

解法

pdf内上部にflagがある。

 

syskronCTF{th4nk-you}

 

 

Deadly malware

問題概要

分野:trivia (malware)

得点:25pt (645 solves)

 

問題文

Which malware targets safety systems of industrial networks and caused deaths due to explosion?

Flag format: syskronCTF{name-of-the-malware}

 

解法

初めて挑むtrivia問題です。とりあえず、問題文を訳してみます。

「産業ネットワークの安全システムを標的とし、爆発による死亡事故を起こしたマルウェアは?」

ということで、「マルウェア 爆発 産業ネットワーク」とこんな風にググってみると…

 

wired.jp

 

triton」っていうマルウェアが出てきました。爆発事故が起こったかどうかこの記事からは分かりませんが、調べてみると2009, 2010年にイラン国内の核燃料施設でウラン濃縮用遠心分離機を破壊したらしいです。wikiを見ても危なっかしい文章が並んでます。怖い。

 

syskronCTF{Triton}

 

 

Security framework

問題概要

分野:trivia (framework, standard)

得点:25pt (538 solves)

 

問題文

In 2018, the NIST published version 1.1 of their Cybersecurity Framework. What are the abbreviated names of the five core functions?

Flag format: syskronCTF{F1-F2-F3-F4-F5} (e.g., syskronCTF{AB-CD-EF-GH-IJ})

 

解法

「2018年、NISTは「Cybersecurity Framework」のバージョン1.1を発表しました。5つのコア機能の略称は?」

ということで、「Cybersecurity Framework version 1.1」とググります。そしたら以下のpdfを頂きました。

 

https://www.ipa.go.jp/files/000071204.pdf

 

p24 2.1 Framework Core で分かりやすい5個の略称が書いてあります。Flag formatからも問題ないでしょう。

 

syskronCTF{ID-PR-DE-RS-RC}

 

これって、5!通りのflagでも通るのでしょうか…。

 

 

Check digit

問題概要

分野:trivia (standard)

得点:25pt (487 solves)

 

問題文

We need a check digit in our keys. What do IMEI numbers, credit card numbers and UIC wagon numbers have in common?

Flag format: syskronCTF{relevant-ISO/IEC-standard} (e.g., syskronCTF{ISO/IEC-27001}).

 

解法

「鍵にチェックデジットが必要なんです IMEI番号、クレジットカード番号、UICワゴン番号の共通点は?」

 

知らない番号が二つ出てきました。

 

IMEI番号について (wikipediaより)

International Mobile Equipment Identity - Wikipedia

全ての携帯電話や一部の衛星電話に付与される識別番号。携帯電話のバッテリを外すと、そこに書いてあることが多い。また、*#06# と入力すれば携帯電話の画面にも表示できる。

 

UICワゴン番号について (wikipediaより)

客車のUIC分類記号 - Wikipedia

国際鉄道連合 (UIC) が開発した鉄道客車を分類する記号の国際的な体系について説明する。

 

まあ、なんかの識別番号って感じですね。結局クレジットカード番号を調べて規定が分かりました。

 

クレジットカードの番号 - Wikipedia

 

1行目にご丁寧に書いてあります。とりあえず、これをflag formatで囲って提出して通りました。出した後に気付いたんですが、ちゃんと他二つもこの規定に従っていました。IMEI番号は上記のwikipediaのところから「チェックディジットの計算」とこれもまた分かりやすく書いてありました。UIC番号は少し難しかったのですが、下のwikipediaから、check digitの計算方法がLuhn algorithmで行っていることが分かります。このアルゴリズムwikiに行くと同じ規定が出てきました。

 

UIC wagon numbers - Wikipedia

Luhn algorithm - Wikipedia

 

 

syskronCTF{ISO/IEC-7812}

 

 

Ladder password

問題概要

分野:plc-programming

得点:100pt (141 solves)

 

問題ファイル

  • 「A BB engineer encoded her password in ladder logic. Each "r" can be either 0 or 1 and represents a character in her password. "r1" is the first character, "r2" the second one, and so on. We assume that n1 is a small value and n3 is big. n2 may be between n1 and n3.

    Please decode the password to demonstrate that this technique of storing passwords is insecure.

    Flag format: r1r2r3…r9r10 (e.g., 1101…001).

    Be aware: BB deployed brute-force detection. You only have 3 attempts until lockout!

  • ladder-password.png

f:id:partender810:20201025154043p:plain

ladder-password.ong

解法

なんだこれ。そんな一言から始まりました。とりあえず、「ladder logic password」と調べましたが、良いサイトはヒットしません。そんなのありませんから…。

とりあえず、r1~10には0か1が入るみたいで1024通り考えられるのでbrute forceを防ぐために3回までしか試せないんですね。

 

与えられたpngファイルはラダー図と呼ばれるもので、回路設計の話です。詳しくは以下のサイトを…!

elec-tech.info

 

 

-||- みたいなのと、これに斜線が入ったもの、そして真ん中にRが入った3種類の接点が、黒と緑色に2種類あることが分かります。ではどういう風に考えたらいいかはwikipediaを参考にしました。

 

ラダー・ロジック - Wikipedia

 

基本は直列回路がANDで並列回路がORという感じでb1~b10がリテラル(0か1)となって、その結果がr1~r10に格納されるというイメージを持ちました。

-||(b1)--|\|(b2)-(r1) という場合は r1 = b1 and not b2, つまりb1=1かつb2=0ならr1=1, そうでないならr1=0という意味になります。

 

途中に出てくる値n1~3は問題文にあるようにn1<n2<n3という関係です。n2 is between n1 and n3. とありますが、これってn1 <= n2 <= n3という意味にもなるのでしょうか…。四角で囲われて上から順に[< n1, n2] とあれば n1 < n2 なら1, そうでないなら0となります。なので、後はb1~b10を2^10=1024通り全て試してr1~10の取り得る値を調べていこうと思いました。その結果答えが3通り以下に絞られるから3回まで試せるのかなと思っていました。

これを計算するプログラムを作る前に思い返したのですが、接点の種類は分かっても色の違いが分かりません。緑色がなんとなく蛍光色に見えたので、もしかして緑色は電気が通って黒は通らないのでは?とふと思いました。r1,r2で言うと

r1 = 黒 and 緑 and 緑 = 0, r2 = (n1 = n2は偽) and 緑 and 黒 = 0

といった感じです。r10まで求めると、0011100011となり提出したら通りました!

え、これで通ったの?と少し拍子抜けしましたが、まだ10 solves程度と時に解けたのは嬉しかったです!

 

後から調べてみたのですが、-|R|-は制御回路?らしきもので片方がtrueならもう片方はfalseになるような感じみたいです。間違ってたらごめんなさい…。また、「b1~b10を2^10=1024通り全て試してr1~10の取り得る値を調べ」ましたが26通りありました。この色の違いに気付かないといけないみたいですね。

 

0011100011

 

 

 

Leak audit

問題概要

分野:sql

得点:200pt (391 solves)

 

問題ファイル

  • We found an old dump of our employee database on the dark net! Please check the database and send us the requested information:

    1. How many employee records are in the file?
    2. Are there any employees that use the same password? (If true, send us the password for further investigation.)
    3. In 2017, we switched to bcrypt to securely store the passwords. How many records are protected with bcrypt?

    Flag format: answer1_answer2_answer3 (e.g., 1000_passw0rd_987).

  • Hint : Knowing SQL doesn't hurt.
  • BB-inDu57rY-P0W3R-L34k3r2.db

 

解法

SQLを知っている人はこの問題ササっと解けます。ヒントは役に立たないですね…SQL使わない解法は、まあ全部表示して手で数えるとかかな…。

 

1.How many employee records are in the file? (ファイルに何人の従業員が記載されていますか?)

table名を確認してCOUNTすればOKです。

 

sqlite> .tables
personal
sqlite> SELECT COUNT(*) FROM personal;
376

 

 

2.Are there any employees that use the same password? (If true, send us the password for further investigation.) (同じパスワードを使っている従業員はいますか?いたらそのパスワードを教えて)

まあ、flag formatからいるんでしょうね。

 

SQL初心者なのでググって調べました。

重複したデータを抽出する|プログラムメモ

 

sqlite> SELECT password FROM personal GROUP BY password HAVING COUNT(password) > 1;
mah6geiVoo

 

 

3.In 2017, we switched to bcrypt to securely store the passwords. How many records are protected with bcrypt? (2017年にbcryptでセキュアにパスワードを管理するようにしたけど、そうしている従業員は何人いる?)

 

bcryptってなんやねん、となったので調べてみました。

bcrypt - Wikipedia

 

簡単に言うと、パスワードをデータベース内に保存する際にハッシュを取って保存することで、仮にデータベース内を見られてもパスワードがバレることはないという感じです。

以下のクエリでそんなパスワードがあるか確認します。

 

sqlite> SELECT password FROM personal ORDER BY password;
$2b$10$/dd1tLbClIU85/pkthZvee9NvDvOYADy6/iSXGIEQxSVAhvRSASj6
$2b$10$1YdjEQ97.itIoDM3WQLBZORGQJuekq6OYFwaB6actkNzJZyU3ZFUy
$2b$10$5VRLne6dbC.qgBrnj9AFTeXpWn6Hkiv2UIUepqCChNOE2YmMCp5qm

 

ORDER BYでアルファベット順にしたら固まって出てきました。wikiにあるように$2b$という列から始まりました。

 

あとはそんな文字列から始まるpasswordをクエリでCOUNTします。

 

sqlite> SELECT COUNT(password) FROM personal WHERE password LIKE "$2b$%";
21

 

よって、flagは以下の通りです。

 

376_mah6geiVoo_21

 

 

 

 

ここまでは自力で解けました。以降は自力では解けなかったものを紹介します(チームで解けたり解けなかったり)

 

解けなかった問題

Vulnerable RTOS

問題概要

 分野:vulnerability

得点:25pt (708 solves)

 

問題文

What are the names of 11 zero-day vulnerabilities that affect a wide range of real-time operating systems?

Flag format: syskronCTF{name-of-the-vulnerability}

 

解法

 「広範囲のリアルタイムOSに影響を与える11のゼロデイ脆弱性の名前は?」とあるので、「11 zeroday」とググったら以下のサイトを発見! しかし、脆弱性の名前などは出てこず…

FireEye、2013年に11件のゼロデイ攻撃を検出 | FireEye

 

チームメイトが「11個 ゼロデイ リアルタイムOS」とググったら一発で正解しました…。悔しい。

monoist.atmarkit.co.jp

 

syskronCTF{URGENT/11} 

 

 

DoS Attack

問題概要

分野:packet-analysis

得点:100pt (340 solves)

 

問題ファイル
  • 「One customer of Senork Vertriebs GmbH reports that some older Siemens devices repeatedly crash. We looked into it and it seems that there is some malicious network traffic that triggers a DoS condition. Can you please identify the malware used in the DoS attack? We attached the relevant network traffic.

    Flag format: syskronCTF{name-of-the-malware}」 

  • dos-attack.pcap

 

 

解法

パケットを見て何のマルウェアか特定する問題です。

パケット調べると毎回60バイトでDNSプロトコルで1024回送っています。DNSを介してのDDoS攻撃だからDNSリフレクター攻撃かと思ったが、マルウェアを特定できない…。 DNSクエリなのにドメイン名が無いということも教えてもらいました(こういった基礎知識の無さが滲み出た)。

結果として、ヒントを使いました。

 

They bought some older SIPROTEC 4 protection relays.

 

とりあえず、「SIPROTEC」でググると「siemens」というドイツの企業が出てきました。私はここから動けなかったのですが、チームメイト曰く「SIPROTEC siemens malware」とググったら「CVE-2015-5374」という脆弱性が出てきて、「malware CVE-2015-5374」でググったら以下のサイトが出たとのことです。

eset-info.canon-its.jp

 

 

syskronCTF{Industroyer}

 

Security advisory

問題概要

分野:crypto

得点:400pt (16solves)

この問題はチームでも解けず…

 

問題ファイル
  • Senork published another security advisory. You have to review it (but maybe, there is some hidden information).

    https://www.senork.de/files/BSA-2020-11.pdf

  •  

    Hint : Sometimes, metadata exposes sensitive information. 

 

解法

最初はpdfだけ与えられて全く分からず…。ヒントを使ってpdfのメタデータに何かあるのだろうと見てみました。Acrobatで開いてファイル→プロパティで見れます。

 

f:id:partender810:20201025192342p:plain

メタデータ

 

アプリケーションが変な16進数ですね。とりあえず、long_to_bytesしてみました。

 

b'damn metadata; here you go: 2ZdkKTtprGGddHh33' 

 

 

うおお!文字になった!

けど、2Z~33をsyskronCTF{}で囲ってもIncorrectでした…。まあこれじゃcrypto要素ゼロですもんね。pdfはBlowfish暗号について書いているので調べてみました。Leak auditでのbcryptと同じ方式らしいです。そして、pdf内の「Technical description of the vulnerabilities」に16進数12桁が8個ありました。Blowfish暗号はブロック暗号だからこれが暗号文か!?とか思いましたが、復号できず…。OFBモードとか書いてあるなとか思いつつ、ここでタイムアップでした。

 

writeup見つけたら更新しますね。見つけたので紹介します。

 

ctftime.org

 

足りなかったものは、メタデータのアプリケーションで得られた2Z~33の文字列が16bytesだったということに気付くところと、Cyberchefと友達になれなかったところです。

2Z~33の文字列をhexに直して前半16桁をkey, 後半をivとします。あとはpdf内の16進数を全て繋げたものを暗号文として、Blowfishのdecryptを行うとflagが手に入ります。

 

7,8割は出来てたのになぁ…悔しい!!!

 

syskronCTF{you-Just-anaLyzed-your-1st-advisorY}

 

 

 

 

 

問題ファイルはGitHubに載せてます。solverは今回無いので…

github.com

 

6回もcorrect!と出ると非常に気持ちが良い!Ladder passwordは得点の割に難しくてsolves数も少なかったし、その分解けたというか予想が当たった時は嬉しかったですね!

 

それでは!

 

See you next time!

SECCON CTF 2020 This is RSA writeup

こんにちは!Ken.Sです!

 

昨日まで開催されていたSECCON CTF 2020のwriteupを書いていこうと思います!

開催期間中には解法が一切分からず、チームメイトからヒント(ほぼ答え)を貰ってなんとかフラグを出せました…。実力じゃあないです(笑)

 

 

score.lmt.seccon.jp

 

 

 

 

問題概要

問題名:This is RSA

分野:crypto (warmup)

得点:124pt (62 solves)

 

 

問題ファイル

  • rsa.rb
  • output.txt

 

f:id:partender810:20201012120128p:plain

rsa.rb

 

解法

rsa.rbを見るとp,qをget_primeという関数で生成しており、その後はいつも通りの暗号化を行っています。このget_primeに何かあるのだろうとにらめっこしてたら時間切れ…。rubyの仕様調べたのに、結局何も分かりませんでした。

 

肝となるのはunpack1のところ。これ、一文字ずつASCIIコードに直してたんですね。つまりget_primeの流れとして

  1. 512bitsの乱数を生成する。
  2. 一桁ずつ上からASCIIコードに直す(16進数)。
  3. その16進数が素数だったらその値を返す。そうでないなら1. へ戻る。

 

という感じです。2. が伝わりにくそうなので仮に1234を1.で生成したとすると、

0x31323334という数字を作ります。(1->0x31, 2->0x32, 3->0x33, 4->0x44)

ASCII文字コードの数字は0x30~0x39なので、p,qを16進数に直すと偶数桁目に必ず3が出てきます。これが分かれば解けてたなぁ。

 

0x3*3*3*3*...3*3*3* × 0x3*3*3*3*...3*3*3* = N となります(* : 0~9)。*に0~9を当てはめていくbruteforceをします。全通り調べると10^64くらいになります(512bitsを16進数にすると128桁、その内不明なのは半分)。普通にbruteforceすることはできません。

 

ではここでかけ算の筆算を利用します。例えば、123456×987654の下二桁を求めてください。この際、必要な計算は掛けられる数掛ける数の下二桁だけ計算すればいいです。つまり、56×54の下二桁です。実際に計算してみると分かります。123456 × 987654 = 121931812224, 56 × 54 = 3024。下二桁は一致しました。では、下四桁を求めるにはどうしたらいいでしょうか。3456 × 7654の下四桁と同じです。この性質は筆算をしてみれば分かります。

 

f:id:partender810:20201012122748p:plain

筆算するとこんな感じ

 

p,qを求めるにはその積であるNと先の性質を利用します。pの下二桁とqの下二桁を掛けるとNの下二桁と一致します。これは16進数にしても同じ話です。p,qの下二桁は3*と分かっているので10×10通りで求められます。下二桁を求めたら下四桁を求めます。下二桁3m×3nが一致したとすると今度は3*3m × 3*3n = Nの下四桁を求めればいいのです。これを繰り返すと、128×10×10程度で求まります。注意すべき点としてはNを16進数に変換して行ってください。

 

p,qが求まったらあとはいつも通りに復号すればOKです。

 

 solverや問題ファイルはこのgithubに載せてます。

github.com

 

 

最近、rubyで書かれた問題が多くなりました。前回出た時は特に気にしなくてよかったですが、今回は細かい点を突かれました。rubyの勉強もしないと…!

 

 

それでは!

 

 

See you next time!