How to use keyboard/mouse for PS4 part1 -Sniffing HCI-UART-
If there is someone who wants to read this article in English, please contact me. I'm not good at English, so I don't want to write in English for anybody.
Motivation
最近研究室でPS4版オーバーウォッチをやった。PS4でFPSは初めてだったのだが、アナログパッドで全くエイムが合わない。規約上問題ない様なのでキーボードとマウスをPS4で使う術を考えた。
PS4で外部デバイスを使う試みはGIMXにより行われているが、デバイスを自作する必要がある。今回はそういったデバイスの自作無しで実現することを目的とする。
現状大凡の目処は立っているものの、細かい問題が解消されず未だ出来ていない。出来た時に記事にしようと思っていたが膨大になりそうなので幾つかのパートに分ける。おそらく4,5パート程度になると思われる。
Sniffing HCI-UART
PS4コントローラー（以下DS4）とPS4本体はBluetooth2.1+EDRで通信をしている。Wifiとは異なり、Bluetoothのプロミスキャスキャプチャはとても困難なようだ。これはどうやらBluetoothのスペクトラム拡散方式である周波数ホッピングによるものらしい。
加えて、PS4ではSecure Simple Pairingというプロトコルにより動的に鍵（以下Link Key）を生成しており、これを外部から盗聴することは出来ない。
DS4とPS4の内部に格納されたLink Keyを取り出すことは困難らしい（読み出しされにくい領域に置く）。実はPS4-DS4間のLink Keyを読み出す方法はあるのだが、これに外部デバイスを必要とする（どこかのパートで書く）。
果たしてBluetoothの盗聴は不可能に思われるが、実は物理的なHackでなんとかなる。BluetoothのチップにUARTで通信しているところを直接抜き取れば良い。
この記事に沿って行った。
まず、ボタンの壊れたDS4を購入（2000円程度で買えた）して分解する。
先の記事の写真と見比べると分かるが基板が違う。DS4は新旧2種があり、どうやらそれによって基板も変わったらしい。@TA7368PG氏によれば3種以上基板があるようだ。
真面目にデータシートと基板を読む。DS4に搭載されているBluetoothチップはAtheros AR3002でこれは10, 11番ピンにTx, Rxが配置されている。
基板を眺めるとおそらくデバッグ用のパッドに伸びている。ここに線をはんだ付けする。
Rx, Tx, GNDを取ってきてブレッドボードに配置する。シリアル通信モジュールは記事に倣いFT232を搭載したものを用いる。ボーレートが3Mbps以上であればなんでも良い。
その後、これをコンパイルして終わり。
ただ、このプログラムはTx, Rx用に2つモジュールがなければ動かない。そこでPORT2をコメントアウトしてfd2に-1をセットすると上手く動く。
小話
ハードウェアに関して全く詳しく無いので@TA7368PG氏と@ka1l氏にTwitterで聞きまくった。ありがとうございました。と言うか最近人々にTwitterで質問しまくってる。
どう考えてもこれを最初にやるべきなのだけど、しばらくsniffer無しで頑張っていた。しかしどうも煮詰まったので止むを得なくPS4ごと買った（これまでPS4を持っていなくて研究室においてあるもので実験していた。流石に人のコントローラーを分解するわけにはいかない）。
基板が違った時はマジで詰んだと思った。
メルカリで落としたコントローラーを分解したら犬の毛が入ってて笑った。
本当は音声端子を剥がしてそこからケーブルを出したかったのだが、はんだ剥がしがつらすぎて諦めた。
Tx, Rx用にモジュールが2つ必要で秋月で注文した。その後5年前に買ったきり一切触っていない回路箱を覗いたら何故かFT232が載ったモジュールがあったのでとりあえず実験した。
画像に情報を埋め込む -SteganographyとWatermarking-
大学でSteganography and Watermarkingについての講義があった。
SteganographyといえばCTFでたまに出題されるが、Gussingクソ問が多くあまり良いイメージを持っていなかった。実際には色々と考えられているようで面白い分野だった。試しに両方の簡単な実装を行った。
SteganographyとWatermarking
この2つは目的が異なっている。Steganographyは「データを隠す」ことが目的であり、Watermarkingは「データに埋め込んだ情報が指定の変換に対して頑健であったり、除去することが難しい」ことを目的としている（多分）。
Watermarking
Watermarkingの目的としては著作者人格権保護などが挙げられる。たまにTwitterで他人が描いた絵を自分が描いたと言い張る人間がいるが、そういう時にどうすれば描いた本人の保証できるかを考えていた。
これはkeyに依存して画像サイズの乱数列Wrを生成し、目的のbitが0であればWr, 1であれば-Wrを画像に足し込むという手法が有名らしい。足しこんだ後の画像とWrの内積を取ることで1bitの情報を得ることが出来る。
実際には内積を取るのではなく平均値を引いた後に内積を取ってベクトルの長さで正規化することで、元の画像の性質に依らずに棄却領域を割り出す事ができる（この理論で射影空間とかがちょっと出てきて面白い）。
これを拡張して1枚の画像にn-bitの情報を埋め込めるようにする。これは画像をn個に分割してそれぞれに1bit情報を埋め込むことにした。ここでどのように分割したかが分からないようにkeyに依存して生成した乱数列によってシャッフルする。
ユーザーはkeyがわからない時に画像の情報を大きく損なわずにWrを除去するのが難しいと思われる（フィルタ掛けたりされると厳しい。白色ガウスノイズの乗せたり輝度変化したりには強いことが知られている。）
しかし、これではユーザーがWatermarkingの検証を行うことが出来ない。除去の困難性を保証するのはWrがどこに埋め込まれているかを知らないからである。
何とかして万人が検証可能で除去が困難なWatermarkingを作れないか考えたがTrusted Third Partyが存在しない限りは無理そうだった。これなら簡単で、画像とkeyとメッセージをTTPに渡して埋め込んでもらうと良い。ここでどこに埋め込まれているかは画像の作成者すら知らない。乱数はkeyとTTPのみが知る情報によって生成される。keyとTTP保有のデータで新しいkeyを作るイメージ。その後に画像とkeyを公開すれば万人がTTPに対してリクエストすることで検証を行う事ができ、またどこに埋め込まれているか分からないので除去も困難である。
Steganography
Steganographyの目的としては情報を持っている事自体の秘匿が挙げられる。つまり、画像中にデータが存在していることすらバレてはいけない。
こちらはいろんな操作に対して頑健である必要はないので一般にはWatermarkingより画像に埋め込むことができるデータ量が増える。僕の実装では800x500程度の画像中にWatermarkingでは数十byteしか埋め込めなかった一方、Steganographyでは数十Kbyte埋め込むことが出来た。なんと1000倍！（Steganographyならある画像のpngにその画像のjpegを埋め込むことくらいなら出来る）。
こちらもWatermarkingと同様にkeyに依存した乱数列を作ってやり、あとはテキトーにランダムに選んだ画素の下位1bitに埋め込むだけで良い。強いて言えば埋め込むメッセージにProbabilistic Encryptionを施すとIND-CCA安全やらが保たれて良さそう。
あまりに大量のデータを埋め込むと下位bitが一様乱数に近くなるので、DCTでスペクトルを出した時に高周波成分が多く出てそれによって埋め込んでいることがバレるかもしれない。真っ白な画像に埋め込むと即バレる。自然風景画像やらに埋め込むと強そう。
Codefestival 2017 Finals Eに対する雑な考察
この問題の線形代数による考察を記しておきます。線形代数が何もわからない。
まずbjxzjaを26を法とするベクトルとして考えます。
これをあるベクトル群の一次結合によって表現出来るかを考えます。
ここで、回文の基底を考えると以下のようになります。
各操作も同様にベクトルで表すと次のようになります。
回文の基底と操作ベクトルを合わせたベクトル群の一次結合によりが表現することが出来たなら答えはYESになります。
式で書くと次のようになります。
さて、は密なので拡大行列を簡約化するコストは大きいように見えます。しかし、先に差分行列（累積行列も差分行列も正則なのは簡単に確かめられます）を掛けてやることでこれらは疎になります。
疎行列に対する簡約化のコストは小さいので十分間に合います。は体でないので諸所が面倒に見えますが解けます（ほんまか）（多分、列ベクトルに注目すると1, -1をちょうど同じ数だけ含むので逆元を持たないことが問題にならないと思う）（ユニモジュラ行列っぽい何かに思うからなんか性質良くなれ良くなれ）。
想定解のUnionFindを使う方法は、連結した頂点数 = rank(それを結んだ辺（ベクトル）で構成される行列)となるということに注目するのだと思います（この辺がよくわからない）。これはつまり連結している頂点のコストの合計が変わらないなら自由に再分配出来ることを意味します。
SMT Solver無しでXorshift128+を解く
先週のCBCTFではXorshift128+の32個の出力列が与えられた場合にその先を予測させる問題が出題された（Random RSA）。
想定解はSMT Solverを使うのだが、宗教上の理由で使えない人が居るかもしれないため別の解法を考えた。
なお、先に言っておくとこの解法は多大なリソースを必要とし、具体的にはメモリを200GBほど使用する。研究室の500万円の計算機で64Thread立てて計算しても30分ほど掛かった。要するにz3を使え、その辺のパソコンで10秒で解ける。
Xorshift128+とは
while True: s1 = s[0] s0 = s[1] s[0] = s0 s1 ^= (s1 << 23) & ((1<<64) - 1) s[1] = s1 ^ s0 ^ (s1 >> 18) ^ (s0 >> 5) yield (s[1] + s0) & ((1<<64) - 1)
Xorshiftとは主にxor, bitshiftで構成された軽量な乱数生成器である。Xorshift系の乱数生成器には様々なバリエーションが有り、その中の1つであるXorshift128+はadditionを加えることで線形性を除いている（後述）。なお、128とは状態数が128bitなことに起因すると思われる（もしかしたら周期かも？）。
Xorshift128+の難しさ
もしこの出題が普通のXorshift128であったなら簡単に解くことが出来る。
何故なら、Xorshift128に使われる処理はxorと固定長bitshiftだけであり、これらは共に状態bitをGF(2)上のベクトルと見なせば線形性を持つ。つまり、全ての演算が行列で書き表せる為に逆行列を作ることで簡単に初期状態を復元できる。
しかし、Xorshift128+の出力列は最後に加算される。この処理は線形性を持たない。この簡単な処理を付け加えるだけで問題は飛躍的に難しくなる。
Xorshift128+の線形性
しかし、Xorshift128+であっても線形性を持つ箇所がある。LSB（最下位bit）である。
LSBは下の桁が無いため、繰り上がりを気にしなくても良い。その為32個の出力列から32個の線形方程式を得ることが出来る。もう少し考察すると、注目するbitより下位が全て1である場合も繰り上がりを気にしなくてもよく、N個の出力列からおよそN/2個の方程式を得ることが出来る。
Random RSAでは新たに28個の線形方程式を得て、60個の方程式が集った。
行列に対するMITM
60個の方程式を集めたということは、128bit中60bitがleakしたと考えることが出来る。しかしまだ68bitの総当りが残る。
これを何とかしてMITMで計算量を落とせないか考えた。ここからの説明はかなり雑なので分かる人しか分からないと思う（真面目に行列の式書くのがめんどい……）。
ここから内部状態を64bitずつのx, yと表すことにする。
今60個しか式が集まっていないが、適当に4bit固定することにより64個の線形独立な式を得る。この行列を変形し、[E | M]のように左半分を単位行列とする行列を得る。これにより、xとyの関係を線形方程式で記述出来る（x + My = 64次ベクトル）。
ここで1つ目の出力列により、yを定めればxが定まる。また、先述の線形方程式からもyを定めればxが定まり、これらが一致すれば解となる。
ここでyを上位32bitと下位32bitに分割する（y1, y2）。そうすると先の線形方程式はx + M1y1 + M2y2 = 64次ベクトル という様な式に変形できる（y1, y2を定めるとxはそれぞれ繰り上がりの有無を無視すれば一意に定まることに注意）。以上から、M1'y1 + M2'y2 = 64次ベクトル という式を得る。
これは、M1'y1 - 64次ベクトル とM2'y2をそれぞれ独立に計算し、一致する場合を探せば良い。
これを実装すると64個の解が出てきた。これは最初に足りない4bitを定めた分と無視した繰り上がりの2bitで6bitの自由度を持った為だと考えられる。あとは全て試すと正しい解を得た。
enumulating all y1 merging vectors miv1: 8589934592 enumulating all y2 merging vectors miv2: 4294967296 serching 2476520362 61509141 2157264084 3353016742 656009753 1860619162 2574392452 2567461328 3446121306 463614785 3288533184 2667169677 3065249141 186478286 769889559 1500841788 540840065 3086893980 1799405833 2135579198 954749789 548963819 3960811688 2581296186 3103250995 4048812002 2904438575 287535986 1008273453 742342059 1609709208 525912563 102537622 2128507249 2446164013 1093192679 2075536625 1789293171 1195834711 2725839867 295618493 3554538105 2373988069 3548126869 1347207931 483994859 1071373495 101210017 193547184 2191692163 1021151311 519290032 1916084563 544594116 2047105320 318595631 66506444 2834209036 1251206337 3094191279 4186820173 2782881948 2114031298 3190589275 508037032 453555974 745063296 2750048806 2923802844 1177402636 2832440853 273566763 1518323354 358834199 1122617837 2403936068 1091218555 4018685749 4136247442 294350163 2928405395 1799492342 2197082799 759383716 4077570164 1016706399 3093126019 3118276782 2943083703 1649561999 3404147677 124557829 716115770 275919643 2901710221 4203208796 657711912 331906217 2690332004 2083220237 433830677 896965898 1296534180 1664930400 1977485902 3742108858 3115534102 689202550 1477097847 3976949959 378126705 2382484743 2943110840 288054401 3860062577 4057827336 1338808793 100592408 133487806 3607172407 2616266322 477564116 3764152924 916057340 1307750470 153169944 1629761026 657825298 829409657 396404147 3151417975 3300223157 2494409012 3774521208 3045576677 1401251776 1775617714 3515828845
y1, y2 = 508037032, 453555974が答え。
実装
64Threadで実行して30分くらいだった。
GF(2)上であれば行列積がandとbitcountになることを使って高速化したりしたがまだまだ重い。ソート列のマージをシングルスレッドで行っているのがボトルネックで、頑張れば10分を切るくらいにはなると思う。メモリも工夫すれば60GB程度には減らせそう。最初はy2の列だけ生成して各y1で二分探索していたのだけど期待よりかなり重くなった。研究室マシンが1.5TBのメモリを持っていたので雑に両方持ってやったほうが速いようだ。
あと普段競プロで並列化やメモリキャッシュやらに気を配ることが殆ど無いのでこのあたりのノウハウが皆無なことに気がついた。悲しい。
CBCTF Writeups
miyaji-labで参加した。これは暗号系研究室に所属している以上Cryptoを全完するという強い決意を表している（大嘘）。
結果としてはRandom RSAを時間中に解くことが出来なかった。悲しい。
Common Modulus 1
Common Modulus Attackをする。
Common Modulus 2
Common Modulus Attack 1と異なりeが3を最大公約数として持つので、m3 mod nが求まる。
mが十分に小さいのでm3 % n = m3となり、二分探索により3乗根を解けば良い。
Common Modulus 3
平文mの後ろに0をpaddingするということが左にbitshiftする(_m * = m * 2x)ということに気がつけば簡単。
これまでと同様にm17 mod nを得るが、m17 = (m * 2x)17 = m17 * 217*xとなる。
xはこれまでのフラグから適当に定めて217*xの逆元を掛けてやるとm17 mod nを得る。
Common Modulus Attack 2と同様の考察から17乗根を求めると良い。
Pailler Oracle
Pailler暗号に対する選択暗号文攻撃をする。得られる情報は復号した結果のLSBである。
Pailler暗号は加法準同型を満たす珍しい暗号である。
また、Pailler暗号は加法準同型だけで無く、mに対する暗号文cが得られている時、任意のrを選択しm*rの暗号文c'rを作成することが出来る。
これら2つの性質は今回の問題において平文に対する加減乗除が行えることを示唆する。
よってm-1とm/2の演算を行うことにより、mを右shiftした平文に対する暗号文を作成することが出来る。
つまり、LSBが0のときはm/2をし、1のときは(m-1)/2をする。これを繰り返すことで全てのbitをleakすることが出来る。
余談
準同型性でLSBの情報がleakすると言えばRSAのBleichenbacher Attackの亜種が有名である。実はこの知識があったせいで変に勘ぐりすぎて時間が掛かった。
詳細は割愛するが、nが常に奇数なことによりLSBからmの範囲を限定する（上位1bitをleakする）。これを繰り返して二分探索のようにすることでmの全体を得る。
同じような攻撃が成り立つのだろうとしばらく複雑に考えてしまったが、Pailler暗号は加法準同型を満たすことを冷静に考えたら解けた。
ちなみに僕はまだPailler暗号が何故成立するのかを理解しておらず、式を眺めれば解けた。この理解の放棄は上手く行ったと思う。
あと、netcatで上手く整数を取得する方法が分からなくてかなり汚いコードになった。良いやり方を知ってる人は教えてください。
Smoke on the water
eが大きいと言えばWiener's attackというのが相場である。これはeが大きいことが本質ではなく、その時にdが小さくなり得るのが問題である（実際にはほとんどのdが小さくならないので余り気にしなくて良いのではないかと考えている。この点について詳しい人が居れば教えてください）。
実際、式中でd_が小さいことが保証されているのでWiener's attackを使うのがほぼ確定する。
まずコード中の式を変形するとd = (p-1) * (q-1) - dよりe * d = e * ((p-1) * (q-1) - d) = -e * d_ = 1 mod phi(n)である。
普通のWiener's attackはe * d = 1 mod phi(n)においてdが十分小さい時にn, eよりdが求まるというものである。
よって既存の手法のe * d - 1とある箇所をe * d + 1（ここにおけるdはd_なことに注意）と書き直せば良い。
これによって求まる d_を用いてcd_ = m-1 mod nを求め逆元を取ると良い。
余談
Wiener's attackは名前と成立条件だけ知っていて、詳細を知らなかった。そこで既存のコードを変形することを軸に考えたのが上手く行った。問題を開いてから10分も掛からなかったと思う。
Random RSA
この問題は2つのフェイズに分かれる。乱数列を予測するフェイズとそれを元にmを復元するフェイズである。
乱数列予測で沼にハマったが、これはxorshift+と呼ばれるものでz3というSMT solverを用いれば簡単に解けるようだ。
http://inaz2.hatenablog.com/entry/2016/03/07/194034
そこからmを予測するフェイズであるが、これは実は2つの平文があれば解くことが出来る。
ある2つの暗号文c1 = (m + b1)e, c2 = (m + b2)eとb1, b2と公開鍵が得られている時、mを求めることが出来る（Franklin-Reiter related-message attack）。
これは(x + b1)e - c1 = (x + b2)e - c2 = 0において、2つの多項式が共通の多項式(x - m)を持つことを利用して多項式におけるgcdを解く。
ということを普段多変数多項式の研究をしている研究室の友人に言ってみたところMangaで解いてくれた。
余談
実はSMT solverを使わなくても32個の出力列を使えば解けるのではないかと思う。ただかなり実装が面倒な上、もしかしたらSMT solverの再開発かも知れない（SMT solverの中身を知らない）。
Franklin-Reiter related-message attackのことを何も理解していないので理解したい。
所感
久々のCTFの割に解けたほうだと思うが、勉強不足を痛感した。それに加えて下手に知識を得ていたせいで調べることを放棄して無駄に考えてしまう時間が長かった。この辺りはCTF慣れだろうか。
KRACKについての私的まとめ
技術詳細を解説した日本語記事が見当たらなかったため簡単に纏める。
なお、冗長になるため断定調で書いているが怪しい箇所も多い（間違ってたら教えてください）。
あと、図は無いです（許して）。
WPA2とは何か
新しい規格である802.11iの標準化が進められていた当時、WEPが破られた。そのため11iを部分的に実装したものがWPAである。その後、AESや1xに対応した11iに完全に準拠した実装が作られた。これがWPA2である。
WPA/WPA2はMIC（メッセージ認証コード）やreplay counterにより改竄とreplay attackを防いでいるのもWEPとの大きな違いである。
WPA2の仕組み
WPA2の接続認証には2つの方法がある。PreShared Key（事前鍵共有）と1xである。前者は小規模の環境で使われる同じパスワードを使う認証であり、後者は大学など大きな環境で使われる（認証サーバーが別途必要）。
ただ、KRACKを理解するにおいて両者の詳細を知る必要は無く、どちらの方法であっても同一のPairwise Master Key（PMK）をAPとClientが持つことさえ分かれば良い。もちろん、PMKは盗聴者に対して秘匿されている。
その後、4-way handshakeにより、PMK, Anonce/Snonce, MAC addressからPairwise Transient Key（PTK)という一時鍵を生成する。PTKを元に5つの鍵を生成する。これらはunicast通信の暗号化（PTK-TK）、後に配布するbrouadcast通信の鍵の暗号化、MICの鍵として使用される。
Msg1: APからAnonceを配布
Msg2: ClientからSnonceを配布
この時点でAPとClientはPTKを生成することが出来る。
なお、ClientはMsg1の時点でPTKを生成することが出来ているため、それを元にMsg2はMICが付加されている。
APはそのMICが合っているかを検証し、Clientが正しくPMKを知っているかの認証が行える。
Msg3: APからGroup Temporary Key（GTK)を配布
これにもMICが付加されている。この時点でClientはPTKをinstallする。
Msg4: ClientからACKを返す
この時点でようやくAPはPTKをinstallする。
PTKのinstallとは何か
セッション中は同一のPTK-TKを用いるのだが、そのセッション内での鍵が同じであった場合、同じキーストリームが生成される。それを避けるため、実際にはInitial Vector（IV)を付加して少し鍵を変える。IVは1パケットごとにインクリメントされ、二度と同じIVとPTK-TKの組み合わせが生じないようにされている。
攻撃の詳細
11iでは、ClientがMsg3を受け取れなかった場合に備えて、再送することになっている。再びMsg3を受け取った時、Clientは鍵をre-installする。この際、IVが初期値に戻ってしまうため、同じIVが使われる事となる。
Msg3を再送してもらうために、攻撃者はChannel-based MitM（APとClientに対するMan-in-the-Middle手法）によりAPとClientの間の通信を妨害する。具体的にはMsg4が届かないようにする。それによりAPはMsg3を再送し、攻撃者はそれをClientに渡すことでre-installが行われる。
前述のようにWPA/WPA2ではreplay attackが出来ないため、この様に面倒な手段を取る必要がある。
あるIVが使われている暗号文の平文が既知である場合、そのIVにおけるkey streamが分かる。それにより、同じIVが使われている全ての暗号文の平文が分かる。
なお、wpa_supplicant2.4ではre-installの際にPTK-TKが0に初期化されてしまう問題が存在した（これは11iがinstallした鍵は0で埋めることを推奨しているため）。
Q&A
WPA-TKIP（RC4）はstream cipherだがWPA-CCMP（AES）は違うのでは
CCMPのAESはCTRモードで、実質stream cipherとして用いられている。しかし、CBC-MACにより改竄が検知されるため、CCMPではinjectionが不可能である。
実際どれくらい攻撃出来るのか
筆者らの実験では、WindowsやMacOSはMsg3の再送を受けてくれず（これは11iの仕様に則っていない）、実質攻撃可能な環境はそれほど多くなかったようだ（Group Key Handshakeに対する攻撃は全ての環境で適用出来ているので、Windowsが当てたパッチはおそらくこれ）。
また、Channel-based MitMは攻撃対象のAPより攻撃者のAPのほうが電波が強い必要があり、つまりは成功率はどれほどターゲットに近いかに依存する。
ICPC2017国内予選
きゅうりが消えたため、たこの友人を新しくチームメイトに加えた。
なお彼は競プロ初心者らしいのだが、頭が良いのでアジア地区では化けてくれると信じている。
僕らのチームはどちらかというと考察が得意で実装が苦手なため、初動で遅れることは予想していた。その為焦らずに正答数を伸ばすことを心がけていた。
結局ペナルティ差で後輩チームに負けてしまったが、阪大で2チーム突破は多分初なのでめでたい。
A, B, Cはそれぞれが並列で解いてあとは流れでやろうという話をしていた。僕がC。やるだけ。
A, Bがそれぞれちょっと詰まっていたけど当初の目標であった3問1時間以内は達成された（遅すぎる……）。
その後、僕がDを読む。最初はmod 2における行列の一次独立とかrankとかそういう話なのかなぁと思いそれにハマってしまった。行列計算はちょうどO(NM)が出現するのでそれもハマりの補助となった。 DPと全探索はすぐに見えていたので、冷静に計算量を書いたら分かった。去年の筑波のI問題を彷彿とさせる問題だと思う。考察に時間がかかり過ぎた上にDPフェイズで結構バグらせた。この程度は一発で通せるようになりたい。
たこらがEを読む。最小積和形にすればいいんじゃないかとかなんとか言っていた気がする。結局文字数の制約に気がついて考察は立った。
とは言えこの時点でまだ4完。残り時間は1時間を切っていた。普通に落ちる未来が見えて焦った。
多分僕はEよりFが得意だろうと判断して考察する。紙で色々書いていると方針が立つ。残り30分。Eはバグったらしい。
Eのバグを取りつつ紙で詰める。indexが厄介なので実際に各操作を手で試してみて両端と真ん中が整合性が取れていたらOK！という経験上バグりにくく且つ高速な方法を取った。
残り15分。僕がFを実装しながらEを紙でデバッグ。Fもバグる。印刷。
残り10分。Eのバグが分かったらしい。書いてもらう。僕もFのバグを見つける。条件やら操作は全て合っていて一箇所typoが合った。これを見つけたのは奇跡だった（経験上typoのバグは焦るとマジで見つからない）。
残り4分。Eが通る。僕に代わる。
typo修正してサンプルが通る。実行して出力を確認せずに投げる（時間がなかったため）。手が震えてコマンドめっちゃtypoしてた。
残り2分。Fが通る。皆でワイワイしていた。
終了後後輩チームらと飯を食べながら解法議論していた。彼らのF問題の解き方はイミフ過ぎたし、彼ら自身も全く証明していないらしい（サンプルが強いためサンプルが通ればまずOKという見立ては非常に正しいと思う）。Gはフローじゃないかなぁということを話してご帰宅。
経験上僕は焦った時のパフォーマンスが著しく落ちるので、Fを実装するときは努めて落ち着くようにした。結果かなり良いパフォーマンスが出せたと思う。良い経験ではあったが、二度とやりたくない。
