m1z0r3CTF 2020 作問してみた
こんにちは！ Ken.Sです！
今回は私が所属しているCTFチームのm1z0r3でチーム内CTFを行ったので、私が作問した問題を公開してみます！！ writeupは最後にリンクを貼っておきますので、そちらを確認していただければと思います。
flagの正誤判定用のサイトとかは用意できないので、以下にスクリプトを書いておきます。正しいハッシュ値であったらOKということで許してください…。スコアサーバ代わりなので、このハッシュをクラックするとかbruteforceするとかはこの問題の想定ではないので控える用お願いします。
flag format はm1z0r3{ [a-z], [A-Z], [0-9], !, ?, _, - }です。ファイルはgithub上に載せています。
該当ファイルはこちらから！ problemディレクトリに入っています！ solverには解答が入っているので、解き終わったら見てみてください。
GitHub - ksbowler/m1z0r3CTF2020
correct.py
------------------------------------------------------
import hashlib
flag = "m1z0r3{test_flag}"
print(hashlib.sha256(flag.encode()).hexdigest())------------------------------------------------------
解いてみた感想を是非聞きたいので、挑戦してくださった方、コメント頂けると大変嬉しいです！！！
- Searchable Encryption (crypto)
- almost EDO (crypto)
- Let's play Nimmt! (misc)
- Sum Min and Sum Max (misc)
Searchable Encryption (crypto)
nc ys5441.tk 51696
ファイル：server.py
難易度：warmup
flag hash : a3bf8e2dc06862d61b962d820cdb55c74d00f6acfd005485f0ff323aea13fe57
almost EDO (crypto)
There are a lot of ways to encrypt FLAG.
ファイル：problem.py, data.txt
難易度：medium ~ hard
flag hash : 9b4795f58a2926828ac32246a6e7ad22d17d3e74aac009bed36daf8ce7c22f16
ヒントとして、最後には背景が青色のサイトを参考にしました。
Let's play Nimmt! (misc)
Do you know Nimmt?
nc ys5441.tk 51608
難易度：easy
flag hash : e45e1e8037fc55588d45d3c96c3e156bbfe577a7a684848ddb087418867ccd09
Nimmtのルールはここから！
Play board games online from your browser • Board Game Arena
6枚目はダメ！定番カードゲーム「ニムト！(6 Nimmt!)【放課後さいころ倶楽部 第4話】 - 親子ボードゲームで楽しく学ぶ。
Sum Min and Sum Max (misc)
Tsubasa was interested in the method of calculating bowling scores. He wants to find the maximum and minimum game score for a limited number of strikes and spares in a game. However, he does not yet fully understand the score calculation. Please find the following instead of him.
flag is m1z0r3{(answer Q1)_ (answer Q2)}.
Q1: The sum of the minimum score in all possible combinations of number of strikes and number of spares in a game. In other words, the answer to Q1 is: (minimum value when there are 0 strikes and 0 spares) + (minimum value when there are 0 strikes and 1 spare) + ...
Q2 : The sum of the maximum score for all possible combinations of strikes and spares in a game, with the minimum value in Q1 being the maximum value. Note, however, that tsubasa does not like the word 'miss', so both questions require that you knock down at least one pin every time he throws a ball.
難易度：medium
flag hash : f53843cd76b3e6f4f6fffe9e54f7e3ca345f6ef07efb44d9ce916ee8a22345c2
writeupはこちらから！
感想を是非お待ちしております！！
それでは！
See you next time!
m1z0r3CTF 2020 writeup
こんにちは！ Ken.Sです！
前回のブログはこちらから！
ということで、この記事はm1z0r3CTFで作問したもののwriteupです。こちらを見る前に是非問題を解いてみてください！！
パワポ資料をgithubに載せたのでそちらをご覧ください！solverも掲載しております。
ご質問等ございましたらお気軽にご連絡ください！
GitHub - ksbowler/m1z0r3CTF2020
こちらでは裏話などを話していきたいと思います(笑)
Searchable Encryption
m1z0r3は研究室チームで毎年メンバーが変わるので、CTF歴の短い方がほとんどです。歴1年以下などのそういった方でも解けるくらいな簡単な問題にしようということで、これを作りました。ただ、実際は相手チームのcrypto担当に新入生がおらずちょっと悲しかったです(笑)
暗号の本を家で読んでいる時に「検索可能暗号」というものを知りまして、実際には複雑で暗号学的に安全な仕組みになっているのですが、誰でも検索可能な状態にすればCTFの問題になるのかな？と思ったのが作成背景です。秘密鍵で検索キーワードを暗号化するはずが、SHA-256ハッシュが暗号化となっているのが今回の脆弱性で、適当な文字入れたら"Contain"か"No"が返って来ることと問題文から推測できたかなと思います。
almost EDO
この問題が一番物議を醸すのではないでしょうか…(笑)
No.6はtokyo westerns ctfのtwin-dの改良問題でした。
TokyoWesterns CTF 6th 2020 一問も解けなかった話 - Attack All Around
この問題では、
e2 + 2*e1*e2 - e1 = 0 mod phi_n
となっており、式変形することでCommon Modulus Attackが出来るのですが、この左辺がphi_nの倍数になることからphi_nを推測できる…という問題ができないのかな？と思いました。上記の問題では左辺が素因数分解できなかったのですが、今回はCommon Modulus Attackは出来ない且つ0 mod phi_nとなる式が作れてそれが素因数分解できるように作問してみました。
No.7は「RSAでやってはいけないNのこと」より一度も遭遇したことのないHastad's Broadcast Attackをやりたかったです。言っちゃえば中国人剰余定理を使うだけです。
そしてこの問題の肝である、48個のFLAGを欠片をいくつか集めて暗号化している部分ですが、復号できたら(英単語)_(一文字)に気付いて、その(一文字)が求めるFLAGのアナグラムだと分かっても…。といった感じだったと思います。
実際のm1z0r3CTFではチーム間でヒントの出し合いをしていたので、
「エスパー要素しかない」
「48がヒント」
「日本人しか解けない」
「単語の意味が重要」
「順番が存在していて、48個しかない」
などとヒントを出していました。ノーヒントで解けた方いたらすごい！！！！
エスパーというか謎解きになってしまいましたが、flag formatの"m1z0r3{"に並べたら「いろはにほへと」になるかな？なんて思ってたり…。まあ1と0はflag内に2つあるので、それを無くせばよかったなと反省しております。
作問意図はNo.6, 7をやりたかったのですが、これだとすぐ解かれると思いこの謎解き要素を追加しました。結果、謎は解けても英単語->日本語訳が分からん！！と尤もな批評を頂きました。そりゃtattered clothesを「綴れ」だとは無理がありました(翻訳してても難しかった)。次回は無理のない謎解き要素を加えたいです(笑)「いろはにほへと」を思いついたのは、最近U-NEXTに加入しまして昔2,3話だけ見た「花咲くいろは」を見つけたからです(笑)
Let's play Nimmt!
最近研究室メンバーでオンラインボドゲ会をほぼ毎週行っており、このゲームなら実装できるかなと思いやってみました。カード毎にポイントが異なると実装が面倒だったので1pointでも取ったら負けとしました。国内CTFでもMISCで二部探索ゲームとかあったので、新入生とかに楽しんでもらえればと思っていました。
各プレイヤーの所持カードの内、最小値を持っているプレイヤーは初期状態でその値以下のカードが場に出ていないと必ずポイントを回収してしまうので、そういったことは避けるように実装しています。
問題文にはいくつか誤植があり申し訳ないです…。(GameBoardArena -> BoardGameArena, All cards has 1 point. -> All cards have 1 point. etc)
Sum Min and Sum Max
弊研の黄coderから「競プロ問題作れ」というプログラミングハラスメントを受けまして、緑coderの私がどうやっても簡単に解かれてしまうだろうということで、得意分野のプログラミング問題にしてみました。が、競プロ問題の恐れてたことで私の解答が正しくないといったことがありました…。solverにあがっているのは正しいものですので…。
一投で一本も倒さないということがあるとQ1が簡単かなと思い制約を付けてみました。AtCoderには無い問題なので、色んな競プロerに解いてもらえると嬉しいです。
来年が私にとって最後のm1z0r3CTFになるので、とびっきり難しい問題を作ってやろうかなと思っています(笑)
それでは！
See you next time!
WaniCTF Writeup
こんにちは！Ken.Sです！
今回は大阪大学の CTF サークル Wani Hackaseさんが開催したWaniCTFのwriteupですが、あまり解けなかったのでCrypto, Forensics以外の解法は他の方のを…
Web
DevTools_1 Beginner
ブラウザの開発者ツールを使ってソースコードをのぞいてみましょう！
F12を押して開発者ツールを覗くとflagが
FLAG{you_can_read_html_using_devtools}
DevTools_2 Easy
開発者ツールを使うと表示を書き換えることができます。
5000兆円欲しい！
(5000000000000000円持っていることにするとフラグを手に入れることができます。)
サイトを見ると、「あなたの総資産は0円です！」とある。
開発者ツールのElementsからこの文を表示させているところを見つけ、5k兆にするとflagがpopで出る。
FLAG{you_can_edit_html_using_devtools}
5000兆とは言わないから1億円くらいくれないかな
Simple Memo Beginner
問題ページ：https://simple.wanictf.org/
flag.txtというファイルに私の秘密を隠したが、 完璧にサニタイズしたため辿りつける訳がない。
(Hint) ディレクトリトラバーサルという脆弱性です。
ディレクトリトラバーサルについて
ディレクトリトラバーサルとは？対策の方法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にアクセスするとソースが閲覧できます。
どうやってalert文挿入するんだろ、メモに追加するときにねじこめないのかな。
ソースを見ると、背景色を変えているときのmemoの記述が他と違う。
メモを追加するときに、<script> alert(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が表示されます。
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を一文字ずつ確認しているみたいで、それがキレイに出ていました。
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の必須チャンクをワニ博士が食べてしまいました！
ファイル：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ですか？
実はこれ、以前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
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
ざっくりとした手順はこんな感じです。
- 偶数桁hexを入力する。bytesにしたのをclient_challengeに入れる
- server_challengeに8bitの乱数を入れ、見せてくれる。
- session_keyに(psk(未知のbytes)+client_challenge+server_challenge)を入力としたsha256(ソルト付)の出力を入れる
- client_credentialにもう一度偶数桁hexを入力してもらう。
- cipherは自作のクラスのインスタンス。そのフィールドblock_sizeは常に16, フィールドcipherは先程のsession_keyをkeyとしてAES(ECBモード)。
- iv_plaintext = bytes(16) (\x00が16個) の後ろにclient_challengeを付けて、iv_plaintext[i:i+16]をAESのECBモードで暗号化したのとclient_challenge[i]のxorしたのをserver_credentialに入れる
- 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を勉強したい方は是非見てください！
はじめに
そもそも行列とは
うまく説明できる自信が無いので、よくわからなかった方はwikiを見てください(笑)
四角形の箱に入ったデータの集合で、線形代数を習う上で避けては通れない分野です。y=ax とかのグラフを使う問題を支えるといった感じです(本当にうまく伝わっている気がしない)
行列は(n*m行列)と表現されることが多く、nは行数(縦の長さ)mは列数(横の長さ)を表しています。行も列も漢字の右側の「つくり」の方でどっちが行でどっちが列か判断するって覚え方をしている人も少なくないと思います。
行列の掛け算について
行列の和、差はこのようにして求められます。
サイズだけで言うと、[2*2] + [2*2] = [2*2] となり、足し算引き算では行列のサイズは等しくないと出来ません。
しかし、掛け算となると異なります。掛けられる行列の列と掛ける行列の行が等しいと積が求められます。
サイズだけで言うと、[3*2] * [2*4] = [3*4] となります。
複雑ですね、要素1行1列目の計算はこのようになっています。
内積は積の和って感じです(雑) (上の場合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はこうなっています。
次に3個の場合を考えます。
考えられるかけ算の順序は以下の二つです。
- (A * B) * C
- 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の列数)
では、行列4つの場合について考えていきます。考えられるかけ算の順序は以下の五つです。
- ( (A * B) * C) * D
- (A * (B * C) ) * D
- (A * B) * (C * D)
- A * ( (B * C) * D)
- 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) のかけ算回数
このように、行列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]を求める時は以下のようなイメージです。
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数多い問題しかやってないので参戦記の方が近いかもですが(笑)
- 結果
- 解説
- Reverse Engineering
- General Skills
- Survey 1pt
- Join the Discord 10pt
- Intro to Flags 10pt
- Basics 30pt
- Grep 0 50pt
- Numbers 50pt
- Hashbrowns 50pt
- Dr. J's Vegetable Factory #1 50pt
- Arithmetic 150pt
- Dr. J's Vegetable Factory #2 150pt
- Zip Madness 175pt
- Dr. J's Vegetable Factory #3 175pt 104
- Grep 1 200pt
- World Trip 300pt
- Dr. J's Vegetable Factory #4 350pt
- Cryptography
- Forensics
- Web
結果
今回も個人で参加しました。存在自体に気付いたのが最終日だったので、ちゃんと考察しないといけない問題は解けなかったです。Crypto問題むずかった…。
解説
問題が並んでた順です。解説と言いながら取り掛かったけど分からなかった問題も書いていきます。解けた方はご一報ください(笑)
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してみたけど文章にならない…。
違うのか？と思ったけど最初の五文字を一つ前にすると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でもそんな言葉あったような…。
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 30267Give 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, EggplantHint : 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)。あとはgrepとsedの駆使と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ヶ国すら巡れなかったです…。
ちなみに、引っ張ってきたのはここの情報のようです。
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は得られなかったのですがソートはなんとかできました。恐らく命令が長すぎて実行時間がかかりダメだと判定されたのだと思います。以下、私なりの解法です。
- sortedを利用し、得られた野菜をソートした結果(以後vとする)を持っておく
- x,yについて、x > yなら、x,yの値を入れ替える(計算しやすくするため)
- 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 野菜の個数と求まった。
- swapした際にソート済みの部分を壊してしまったらその野菜をFirst in Last outのキューで格納。そうすると、元に戻すために各野菜1回のswapで済む。First in First outだと、swap回数が増えてしまう。
- 野菜を一つ左にスライドする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か」と。久しぶりでした。
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ファイルと同じ画像を発見。なんだったんだろう。
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だ。
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...
URLにアクセスすると、真緑な画面。F12で覗いてみると、画像(http://challenges.nactf.com/flag.png)が出てこないとのこと。サブドメインが違うということで、アクセスURLと同じようにhiddenを付けてみる。はい出た。
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.
1000個のログインフォームの内一つは本物。とりあえずF12でソースを見てみましょう。10000行を超えるソースですが、1つのフォームに対して10行近くあってそれが1000個あります。その下に行くとログインできそうな関数がありました。
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.
なんか裏で計算してるんだな、変な命令流せばなんかflag出るのかってF12で覗いたけど分からず…。ソースにあんま書いてない？とか思ったけどもうよく分からない、無理。
例によって、問題やsolverはGithubに載せてます！
それでは！
See you next time!
PakenCTF writeup
こんにちは！Ken.Sです！
先程まで行われてたPakenCTFのwriteupです！楽しいCTFでした！
今回は初心者用でしたので、m1z0r3では参加せず個人で参加しました。しかしそのm1z0r3にボコボコにされました(笑)
結果
解説
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{}で囲ったものを提出して下さい。
厳密に偶数文字目である事に気をつけて下さい。
theanswerisrandomstring」
簡単じゃんと思ったのですが、トラップが仕掛けてありました。pythonで偶数文字目だけ取ろうとしたらこんな表記になりました。
the ans w eri sra n domst rin g
よく見てみるとゼロ幅スペースと呼ばれる\u200bが入ってます。
しかも偶数文字目と言っても、一番最初は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}
— 筑駒パ研@第69回筑駒文化祭『彩雲』 【Paken.flush();】 (@tk_paken) 2020年10月29日
pakenCTF{Y0u_are_tvv1tter_m45ter}
Address 100pt
問題文：「この中央の建築物の場所を答えよ フラグの形式は pakenCTF{<郵便番号(間に_)>_<丁目>_<番地>_<号>}」
これとpicture.jpgが与えられます。
どこかのクリエイトのようですが、白黒で画素も荒いためなかなか判別が難しいです。
しかし、店の壁のところに「武蔵野」や「三〇中央病院」という文字が見えました。恐らくその場所への案内なのでしょう(→が一緒にあるやつ)。武蔵野の近くにある地名で三から始まるのは三鷹でしょう。調べてみたら三鷹中央病院という病院は存在しました。その近くにあるクリエイトは3店ほどあり、あとはストリートビューで探せばOKです。
pakenCTF{181_0013_4_14_16}
kaishuu 150pt
問題文：「ハッシュタグの中身を当てて下さい。FLAGはハッシュタグの中身 ( '#' なし) をpakenCTF{}で括ったものです。」
これとimage0,1,2,3の4枚が与えられます。
（重かったので直接問題を見てください）
これはm1z0r3の人達と話しながらやってたのですが、一人が渋谷っぽいと「渋谷 落書き」とググったところ以下のサイトがヒット。
良い話なような気がするけど、落書きっていいのかな。
pakenCTF{391045428}
Station 250pt
問題文：「この駅の名称とこの線の名称をローマ字で答えよ
ただし「都営」などは不要で、地名のような固有名詞で回答せよ
回答形式は、英字はすべて小文字、ヘボン式で
pakenCTF{<駅の名前>_station_<線の名前>_line}」
これと、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ファイルを読み込みます。
p23あたりに$を末端文字とするという問題文と同じ文章が出てきます。そしてBW変換というのを行って暗号化しているみたいです。
後ろn文字目(n:0~文字列の長さ)から最後までの文字列を辞書順に並べます。例えばapple$だと出来る文字列は、$,e$,le$,ple$,pple$,apple$となり辞書順に並べると
$
e$
le$
ple$
pple$
となります。
辞書順の上から順にその文字の一つ前に来る文字を暗号文とします。上記の例だと、
$ -> e
apple$ -> $
e$ -> l
le$ -> p
ple$ -> p
pple$ -> a
暗号文：e$lppa
となります。
なので、暗号文を一文字ずつを辞書順に並べることで、ある文字が何の文字の前に来るかが分かります。その結果がこんな感じです。
これをあとはしりとりの要領で繋げる…としたのですが、なかなか上手くいきません。しばらく経っても分からずtr4nsfornとVVheelみたいな文章が出てきた頃、BW変換とググると以下のサイトが…
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でしょう。
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を忘れずに) で復元できました！！
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に負けて悔しかったのでこれをお供えします。
solverなどは後日GitHubに掲載します！
問題やsolverはこちらです！
それでは！
See you next time!
