はまやんはまやんはまやん

hamayanhamayan's blog

CTFにおけるCrypto入門とまとめ

Security

はじめに

CTFのCrypto問題を2024年の末からコツコツ解いてきたのだが、明らかにAIの方が強く、この進捗だと抜かせそうにない雰囲気なので、ここらでcrypto関連の集めた知見をまとめておいておくことにする。
そこそこ勉強したと思うのだが、未だに解説が読めないときがあるので、数学をもっと勉強しないとですね...（こういう記事を書いている場合ではない）
ちなみに、ここでは"Crypto"を暗号通貨を指しては使わない。CTFではどちらかというと"Web3"とか"Blockchain"とかのカテゴリに入れられることが多いように思う（私見です）。

CTF入門

CTFとは何なのか

CTFとはセキュリティ的な問題を解く競技のことであり、色々なジャンルに分かれている。
全体的な話は他の記事に譲るとして、Crypto問題に絞って話すことにしよう。
大体のCTFは一問一答の形をとっており、とある暗号システムが与えられて、そのシステムの脆弱性を突くことで暗号を復元したり、内部で生成される乱数を推測することで「お宝」を出力させるのが目的である。
このお宝をFlagと呼んでおり、一般的にはハッカーが暗号システムを攻撃して手に入れたい情報という風に解釈されている。
分かりやすい問題の例を挙げておくと、秘密鍵が分からないにも関わらず脆弱性があるために、暗号文が復号できてしまうといった感じである。

初学者に向けて

中級者になったとは思ってはいないが、初学者は脱したかなと思うので、これからCTFのCryptoをやってみたい初学者が取るとよさそうな道筋を考えて残しておくことにする。

  • 現状、まっさらな状態でCryptoに取り組もうとする場合は、CryptoHackのコースやチャレンジに取り組むのが良いのではと思う。英語ではあるが、特にコースでは1歩1歩教えてくれるので非常に参考になる。
  • 書籍で勉強するのが好きな人向け
    • 本を1冊オススメするとしたら結城先生の「暗号技術入門 秘密の国のアリス」を挙げておく。日本語で非常に分かりやすく書かれており、内容の濃さもさすが結城先生といった1冊になっている。
    • 他にも分厚いので1冊目としてはオススメしにくいがIPUSIRON先生の「暗号技術のすべて」も日本語で暗号について広く書かれている良書であり、「暗号の理論と技術 量子時代のセキュリティ理解のために」も難しいテーマやあまり日本語では解説が分厚くない分野を易しく説明していてとても参考になった。
  • インターネットでアクセスできるもの
  • 各トピックで色々参考になる

…と色々書いたが、トライアンドエラーで試行錯誤していく他無いのが現状ではないだろうか。
CTFは毎週何かしらやっている。
CTFtimeというサイトでActiveなCTFが見られるので、そこで毎週出てみよう。
大会開催後は有志による解説、CTF用語で言う所のWriteupが公開されるので、解けなかった問題を復習していく。
Writeupが公式から提供される確証は無いので、なるべく参加人数が多いCTFに出ると復習できる可能性が上がるだろう。
YouTubeで動画形式で上げてくれている人もいるので、理論だけでなく実践的なやり方をこれで学ぶこともできる。

なお、Cryptoで最初に勉強する分野に迷ったら"RSA"から始めることを推奨する。

Crypto問への取り組み方

ここからは入門者が知識として得づらい部分や話しておくべきこと、暗黙知的や経験則をつらつら書いていくことにする。

  • 問題にhoge.ctf.example 1337のように接続情報が書かれている場合は問題サーバが与えられていることを指している
    • 単純なテストであればnc hoge.ctf.example 1337としてインタラクティブに操作してみると良い
    • 大体はサーバから得られた値を使って計算することになるので、Pythonであればptrlibやpwntoolsを使って通信も含めたソルバーを書いて解く
  • Pythonっぽいけど何か違うというソルバーを見かけたら、SageMathで書かれているので注意
    • CryptoではSageMathという数学ソフトウェアを使ってソルバーを書くことが多々ある。SageMathには計算を簡潔に書くための便利なアレコレが揃っているので、より本質的な解法に集中しやすい。Pythonで動かしてみたが、なんか構文エラーになるぞというとき、SageMathであることを疑うと良い（慣れれば、見ればすぐSageMath向けのソルバーであることが分かってくるようになる）
    • またfrom Crypto.Util.number import *みたいにPythonで使われているのは、PyCryptodome。PyCryptoは古いので使わないこと
  • 古典暗号というのがあるが、真に面白い（個人差有り）のは近代暗号
    • 暗号というとシーザー暗号などが最初に持ち出されがちではあり、歴史的には正しい順番ではあるのだが、古典暗号と近代暗号は暗号システムとしての考え方や取り組み方がまったくもって異なることに注意すること。
    • 個人的には近代暗号に面白さが詰まっているので、古典暗号を頑張ってCryptoはこういうものだと理解するのはとてももったいない。古典暗号にもある種の面白さはあるのかもしれないが、個人的には近代暗号をやってほしい
    • だが、実際にはCTFに出てくるときがあるので、本まとめでは最後に古典暗号を取り扱っておく。エニグマまでが古典暗号っぽい。
  • 数学知識は必要か
    • 最初から必要とは思わないが、合同式の理解が前提とされていたり、数論の記法を使って説明されることもよくあるため、数学知識が無いと解説が読めないという事態が発生する
    • だが、あると有利なのは確実で、特に数論・代数論の背景があると良い。情報学部ではやらない（多分）ので、数学科や物理学科の方が向いてそうではある（多分）
    • それ以外にも競技プログラミングでも良く出る解析まわりも使われるので、競技プログラミングをやっていると幾分有利な気もする
      • 正確には「数オリ上がりの競プロer」にはとても得意そうである
  • たまにうまく検索するとばっちり使える論文があるので解けますみたいな問題があったりする
    • Webにおけるワンデイ問題みたいな雰囲気なのかも
    • 論文を検索するのにも論文を読むのにも英語と数学知識が必要
  • （AIが無茶苦茶賢いので分からなかったら聞くといいです。Writeupでもソルバーだけポンと置かれて数学的背景が全く分からんという状況でもそれっぽく答えてくれます（ですが、ソルバー読んで分からない場合は前提知識が付いていない場合も多く、その場合AIから色々言われても正しいのか分からんという問題もありますが...））

まとめ

これからはまとめ記事をいつものように書いていく。手取り足取りという解説記事ではなく、キーワード集であり、勉強の足掛かりや全体像の把握に活用してほしい。

より強くなるために

解説も読めないときが多々あるので強くなったら書き足します。