Learning cyber security by playing and enjoying CTFs

Cyber Security関係の雑記帳です。表明されているお気持ちなどは全て個人的なものであり、筆者が所属もしくは関係する組織・団体の意向とは一切関係ありません。

Cryptoプレーヤーを始めてから今までで躓いたポイントとその解消法

1. はじめに

チームN30Z30N総帥、Edwow Mathです。

この記事は、CTF Advent Calendar 2022 の5日目の記事です。

adventar.org

CTF Advent Calendarの昨日（4日目）の記事はFurutsukiさんの「zer0pts秘伝のcrypto-writeupを公開します」でした*1。

ということで、5日目はガラッと趣向を変えて、これからCTF（特にCrypto）をやろうと思っている方や、やり始めたけどよくワカランといった感じの方向けのNoteです。これから時空を遡り、私が躓いたポイントと、どう克服したか*2を順に紹介していきたいと思います。

2. つまづきポイント

私は2019年頃から本格的にCTFをプレイするようになり、主にソロ（1人）チームで様々なCTF*3大会に参加しています。好きな分野*4はCryptoです。元々数学が好き*5でしたので、Cryptoに必要な数学的知識はそこそこ持っている状態からのスタートでした。しかし、経験を積めば積むほど「つまづきポイント」は増えていっており、それは今も変わりません。

それでは、これから主なつまづきを紹介することにしましょう。

つまづきpoint-0：参加するCTFをどうやって探したらいいのワカラン！

私の場合は、情報収集目的でTwitterを始め、最初は情報セキュリティ関連のアカウントやCTFチーム（もしくはプレイヤー）のアカウントを適当にフォローしていきました。CTFにはプレイ後に解いた問題の解法をブログ等で発表する「Writeup」という文化があり、著名チームやプレイヤーのアカウントはそこから把握することができます。そうしていくうちに、国内のプレイヤーたちが参加するローカルな（そして初心者にも優しい）CTF情報をキャッチできるようになりました。

また、それとは別にCTFtime*6の存在を知り、グローバルな大会についてはここから情報を入手しています。

まとめると、情報収集は

  • ローカルなCTFはTwitterから
  • グローバルなCTFはCTFtimeから

というスタイルで、これまでやっています。

ただし、CTFtimeの情報は実際の開催日時と異なる場合が（結構頻繁に）ありますので、必ず大会の公式サイトやコミュニケーションツール（Discordが多いです）等でのアナウンスを確認する必要があります。

CTFの難易度は大会によってまちまちですが、各大会の案内文などに掲載されているので一読してから参加を検討すると良いかと思います。また、一つの大会のでさまざまな難易度の問題が出ることが多いので、プロ向けのCTFであっても躊躇せず参加することをおすすめします*7。

なお、CTFに費やせる時間が限られていて*8、あるいは同じ日複数の大会が開催されていて、どれに出たら良さそうか迷う時などには、れっくすさんの「rex.gs」がとても参考になります。私の経験測ですが、この記事で紹介されているCTFに出て「つまらなかった」とか「出なければよかった」といったことは一度もありません*9。

つまづきpoint-1：いわゆる古典暗号問題が全くワカラン！

これは今でも変わりません*10。

とは言え、CTFを始めたばかりの頃よりは少しマシになっているかと思いますので、以下に私の対処法を挙げておきたいと思います。

古典暗号問題にはGuessing*11が付き物なのですが -- Guessing、私の苦手な言葉です。ですので、これくらいで。

つまづきpoint-2：RSA問題とかでどうやったらフラグの文字列が出るのかワカラン！

おそらく最もとっつきやすい非古典暗号問題はRSAでしょう*12。「これをやったらアウト」というポイントと、それらに対する攻撃手法がともによく知られています。しかし、RSAの仕組みを理解し、（簡単な整数で）実装できたとしても、算出した整数をどうやってフラグの文字列に変換するのかが分かりませんでした。

これについては、Big Endianでの変換である場合がほとんどです。pythonでは以下のようにして実現できます。

#整数x⇒バイト列s:
s = x.to_bytes((x.bit_length()+7) // 8, 'big') 
#バイト列s⇒整数x:
x = int.from_bytes(s, 'big')

ただし、暗号問題を解く場合は、PyCryptodomeというライブラリが便利なので、私は普段このライブラリにある「long_to_bytes」や「bytes_to_long」を使っています。

from Crypto.Util.number import *
#整数x⇒バイト列s:
s = long_to_bytes(x)
#バイト列s⇒整数x:
x = bytes_to_long(s)

つまづきpoint-3：netcatでサーバに繋ぐ問題で、サーバから得られる値をプログラム上から取得する方法がワカラン！

問題文に「nc hogehoge.xxx 1337」のようにnetcatでサーバ接続する問題が出題されることが多々あります。Linuxのコンソールからコマンド叩いて済むものはそれで良いのですが、多数の試行を伴う場合とても手作業ではやっていられないケースがあります。

私の場合、pythonでtelnetを扱うライブラリ（Telnetlib）を使用してサーバに繋ぐプログラムを作成しています。

import telnetlib

#接続
conn = telnetlib.Telnet("hogehoge.xxx", 1337)

#1行読み込み
conn.read_until(b"\n")

#「12345」+改行を送信
conn.write(b"12345\n")

このあたりはもっとスマートに処理している方が多いので、いろいろなWriteupから自分に合った方法を選ぶのが良いと思います。

つまづきpoint-4：数式処理をしたいけど、自力で実装するの辛すぎるしどうしたらいいかワカラン！

SageMathを使えばOKです。

www.sagemath.org

私の場合、CTFの問題で.sageという拡張子のファイルが提示され「pythonっぽいけどなんじゃこりゃ？」となったのが最初のSageMathとの出会いです。

マニュアルがよく整備されており、インストールは比較的スムーズにできます。但し、Windowsインストーラはver.9.3までしかないので、それより新しいものを使いたい場合はLinux等の上に展開することになります。

使える関数は多彩ですが、数学の知識がある方はある程度直感的にこのツールを扱うことができるでしょう。そうでない方も、Writeupを読んで定番の関数を押さえておくとよいでしょう。例えば、行列計算（特に、最近流行っているLLLなど）は、SageMathの力を借りると相当楽になります*13。

つまづきpoint-5：暗号技術は勉強して理解したけど、問題で提示された情報からどう攻めていいのかワカラン！

Try Harder! これは現在進行形で躓いているところですので、具体的な話はまだできません。

メジャーな暗号技術のキーワード（たとえばRSA）ググってみると、攻撃手法などをまとめている記事が見つかりますが、情報が希薄な暗号も少なくありません。

ですので、そこからは自分で「どげんかせんといかん」のですが、当面の構想として以下のようなことを企んでいます。

  • 解けなかった問題は勿論、解けた問題ついても Writeupを読んでupsolveする。その後でなぜ解けたのかを整理する。
  • （↑がある程度できるようになったら）論文等で発表された攻撃手法を（論文からの情報だけで）実装できるようにする（結構ツライ）。
  • （↑がある程度できるようになったら）自分で攻撃手法を研究する（さらにハードルは上がるがここを目指したい！）。

つまづきpoint-6：背景にある数学がワカラン！

こちらも現在進行形で躓いていますが、ある程度見通しが立っているので*14少しだけ語ろうかと思います。

最初に持っておいた方が良いセットは、初等数論と線形代数です。

初等数論は中国式剰余定理、オイラーの定理など一通りマスターしておくと便利です。

線形代数はジョルダン標準形くらいまででしょうか。ともかく、行列演算はサクサクできるようにしておきたいです。

あと、有限群・有限体（いわゆるがロア体）の性質や剰余環 Z/ｍZ の性質など、代数学の基礎は押えておきたいです。

あとは各暗号技術（と、それらに対する攻撃手法）がもつ数学的背景を補充することになりますが、例としては以下のようなものがあります。

理論的な理解も大切ですが、具体的な計算ができないとフラグはとれないので計算演習も怠らず実施しましょう*15。

3. おわりに

ここまで拙文をご高覧いただき、ありがとうございました。皆様の「スッキリ」に少しでもつながれば幸いです。

CTF Advent Calendar の明日（6日目）の記事はptr-yudaiさんの「Best Pwnable Challenges 2022」*16です。

*1:これをしっかりとキャッチアップすれば相当ツヨツヨになれると思います。なんといっても最強「zer0pts」の秘伝ですから！

*2:克服できていないものも多々ありますが。

*3:ほぼ、オンラインでクイズ形式にしか出ていません。

*4:解けるとは言っていません。

*5:できるとは言っていません。

*6:英語必須ですが、難しく考えなくて大丈夫です。

*7:ただし、TSG CTFの難易度Beginnerは要注意です。解けなくても落ち込む必要は全くありません。

*8:いわゆる社会人は、ほぼそうでしょう。

*9:問題が解けなかったことは多々あります。

*10:作問者の皆様ごめんなさい。古典暗号無理っす。

*11:非自明な推測。エスパーとも言います。

*12:個人の価値観です。

*13:ただし、SageMathにも「つまづきpoint」があります。そのあたりは、別の機会に紹介したいと思います。

*14:見通しが立っているだけで、理解できるとは言っていないのです。

*15:私の場合、楕円曲線を除き学生時代に一通りトレースしていたのですが、実装ができないものも少なくなく、理解が十分であるとは言えない状態でした。

*16:最強Pwnerであるptr-yudaiさんの記事を見逃す手はありません！