picoCTF 2021 writeup
こんにちは！Ken.Sです！
つい最近に留学の研究後記ブログを書いたばかりですが(と書いて保存してたらangstromCTFの方を先に公開することになるとは…)、今回もwriteupを書いていきます！今回かなり頑張ったので読んでくださると本当に嬉しいです！
picoCTFはチーム上限5人で、m1z0r3からは8人の参加希望があったので2チームに分けて対決してました！私率いるm1z0r3チームはなんとかもう一つのkum0r1に勝てましたドヤァ。AtCoderやってる人ならわかるtourist出しをやりました(笑)
また、picoCTFはpicoGymという形で問題が残るのであとで復習が出来るのが素晴らしい！勉強会で扱う問題を探しているときに実際の問題が残ってるの本当に助かるので有難いですね。
※問題文にヒントがありましたが、使ってないのは記載してません。
※もしこれを読んでくれているm1z0r3メンバーがいたら、一部問題を勉強会に使います！どれを使うかはもう決めているのでその問題の解説の最初に一言書いておきます。読んでもいいけど勉強会つまらなくなっちゃうよ！
Result
Ranking
全体で181位、日本人学生チームで6位でした！！
1位のチーム1万pt超えすごいなぁ…
Solves
Rev 9/17問
For 8/13問
Bin 6/16問
Cry 15/17問
Web 9/18問
Gen 7/7問
担当したcryptographyをこんなに解けてかなり嬉しいです！他の方に参考になれば幸いです。
Writeup
General skill
Obedient Cat 5pt
This file has a flag in plain sight (aka "in-the-clear").
ファイル：flag
見たらFlagがありました。
picoCTF{s4n1ty_v3r1f13d_1a94e0f9}
Python Wrangling 10pt
Python scripts are invoked kind of like programs in the Terminal... Can you run this Python script using this password to get the flag?
ファイル：ende.py, flag.txt.en, pw.txt
コード内に書いてあるusageの通りにやってもエラーを吐いてしまい…ende.pyに直接貰ったファイルの文字列を入れてみるとFlagが出ました。
picoCTF{4p0110_1n_7h3_h0us3_192ee2db}
Wave a flag 10pt
Can you invoke help flags for a tool or binary? This program has extraordinarily helpful information...
ファイル：warm
./warmしてみます。
Hello user! Pass me a -h to learn what I can do!
./warm -hしてみます。
Oh, help? I actually don't do much, but I do have this flag here: picoCTF{b1scu1ts_4nd_gr4vy_616f7182}
strings warm | grep "pico" でも見つけられますね
picoCTF{b1scu1ts_4nd_gr4vy_616f7182}
Nice netcat... 15pt
There is a nice program that you can talk to by using this command in a shell:
$ nc mercury.picoctf.net 7449, but it doesn't speak English...
ncしてみると8bit程度の数値がいくつか送られてきます。
最初の数値は112でchrしてみると'p'。これはASCIIですね。
picoCTF{g00d_k1tty!_n1c3_k1tty!_f2d7cafa}
Static ain't always noise 20pt
Can you look at the data in this binary: static? This BASH script might help!
ファイル：static, ltdis.sh
strings static でも一発で出ますがちゃんとやるならば ./ltdis.sh static -> static.ltdis.strings.txtを見るでOKです。
picoCTF{d15a5m_t34s3r_f5aeda17}
Tab, Tab, Attack 20pt
Using tabcomplete in the Terminal will add years to your life, esp. when dealing with long rambling directory structures and filenames:
ファイル：Addadshashanammu.zip
まずunzipで解凍します。
そうするとこんな感じに
Tabキー使って長いディレクトリ名を打つ手間を省きます。fang-なんちゃらのディレクトリまで行きfileコマンドでこのファイルを調べるとELFだということが分かります。./f(Tabキー) で実行するとflagを出してくれました。
picoCTF{l3v3l_up!_t4k3_4_r35t!_6f332f10}
Magikarp Ground Mission 30pt
Do you know how to move between directories and read files in the shell? Start the container, `ssh` to it, and then `ls` once connected to begin. Login via `ssh` as `ctf-player` with the password, `ee388b88`
問題文の横にLaunch Instanceがあるのでクリックしてsshすべきサーバを教えてくれます。
lsコマンドで何入ってるか見ると「1of3.flag.txt」と「instructions-to-2of3.txt」が入ってます。前者を見るとflagの途中しか見せてくれません。1of3だから仕方ないですね。次のflagを教えてくれそうなtxtファイルがありますね。
Next, go to the root of all things, more succinctly `/`
cd / ですね。lsとcatで「2of3.flag.txt」と「instructions-to-3of3.txt」を見ます。後者はこう書かれてました。
Lastly, ctf-player, go home... more succinctly `~`
cd ~ で移動し最後のflagの欠片を貰います。
picoCTF{xxsh_0ut_0f_\/\/4t3r_3ca613a1}
Web Exploitation
Ancient History 10pt
I must have been sleep hacking or something, I don't remember visiting all of these sites... http://mercury.picoctf.net:52731/ (try a couple different browsers if it's not working right)
このサイトにアクセスしてソースを見ると変な関数が定義されてますね…長すぎる。
よくみたら同じ内容でした。ただ、同じに見えて実は違うところがあるのでは？という発想になるまで時間がかかり、調べてみたら上の画像の中央下部分にある/index.html?pとある箇所が次の行と異なりました。あとはここを抽出したらOK! と思ったのですが…incorrect
前の行と違うところだけを見ていたのでflag内で同じ文字が続いた場合、そこを飛ばしてしまってました。そこを注意してcorrectでした。
picoCTF{th4ts_k1nd4_n34t_bb660d55}
Binary Exploitation
What's your input 50pt
We'd like to get your input on a couple things. Think you can answer my questions correctly?
nc mercury.picoctf.net 56827ファイル：in.py
Hint : What version of python am I running?
ヒントを基にコードを見ると2系。print("...") とあったのでよく見ないと分からないですね。
31行目のif res == city: がTrueになればFlagが手に入りますが、変数cityに何が入っているか分かりません。
これはチームメイトに教えてもらいましたが、2系はinput関数に脆弱性があるとのことで、入力された文字列と同じ名前の変数があるときにその内容がコピーされてしまうとのことです。なので都市の入力の際に"city"と打ち込めばOKです。
2系のあからさまな脆弱性を初めて体感したなぁ。
picoCTF{v4lua4bl3_1npu7_1599789}
Forensics
Wireshark doo dooo do doo... 50pt
Can you find the flag?
ファイル：shark1.pcapng
pcap系の問題はあまり解いたことがないのですがsolve数が多いので行けるのかなと思ったのが苦戦しました(笑)
Wiresharkのfilterを使ってパケットを絞るのだろう、どんなfilterが良いのかは過去のwriteupを見てました。
「http.request && tcp.port == 80 」とやればパケットが二個に絞られました。あとはそのパケットをTCPストリームすると…
Gur synt vf cvpbPGS{c33xno00_1_f33_h_qrnqorrs}
あとはrot13ですね。
picoCTF{p33kab00_1_s33_u_deadbeef}
Cryptography
Mod 26 10pt
Cryptography can be easy, do you know what ROT13 is?
cvpbPGS{arkg_gvzr_V'yy_gel_2_ebhaqf_bs_ebg13_jdJBFOXJ}
rot13ですね。さっきやったよ。
picoCTF{next_time_I'll_try_2_rounds_of_rot13_wqWOSBKW}
Mind your Ps and Qs 20pt
In RSA, a small
evalue can be problematic, but what aboutN? Can you decrypt this?ファイル：values
そりゃNが小さいのは問題でしょうよ…。NをfactorDBで殴って終了です。
picoCTF{sma11_N_n0_g0od_73918962}
Easy Peasy 40pt
A one-time pad is unbreakable, but can you manage to recover the flag? (Wrap with picoCTF{})
nc mercury.picoctf.net 41934ファイル：otp.py
Hint : Maybe there's a way to make this a 2x pad.
この問題、配点の割には時間がかかってしまいました。
keyの長さが50000で入力された文字列のchrとxorしてくれます。初めにflagをxorしたのをくれますが、keyが分からないので復元できません。10文字を入力に対してkey[i:i+10]を使うとしたら、次の入力に対してはkey[i+10:]が使われます。
最初にflagのxorにkeyを使っており、与えられた値とソースよりflagは32文字ということと、key[0:32]を使ってxorしたことが分かります。
このkey[0:32]を知りたいのですが、keyの並びに規則性あるのかな…全く見えず…ここでかなり苦戦しました。
入力の文字列長の合計が50000越えるようにして、keyを一周させればいいじゃん。"a"*(50000-32)をぶん投げ、次の入力でkeyの0文字目から使えるようにします。また"a"*32でも投げて得られた暗号文よりkey[0:32]を求めます。それを使って最初にもらった暗号化されたflagを復号して完了です。
picoCTF{abf2f7d5edf082028076bfd7a4cfe9a9}
New Caesar 60pt
We found a brand new type of encryption, can you break the secret code? (Wrap with picoCTF{})
ihjghbjgjhfbhbfcfjflfjiifdfgffihfeigidfligigffihfjfhfhfhigfjfffjfeihihfdieieihファイル：new_caesar.py
new_caesar.pyによってこの暗号文が作られたようです。復元頑張りましょう。
flagという文字列を引数としたb16_encode関数によってb16文字列を生成し、その文字列を一文字ずつkeyによってshift関数で暗号文を生み出した結果こんなものになりました。
b16_encode関数はflagの一文字ずつをASCIIコードにして前4bit, 後4bitに分けます。その値によってa~pを決めます。0000ならaで1111ならpですね。flagの二倍の文字列長になります。
shift関数はkeyの文字によってa~pの間でrotateします。
復号はやるだけ、って感じでしたね。実装が面倒ですが…。
流れとしては、keyの長さが1でa~pのどれかと分かるのでkeyについてはbrute forceしてnew_caesar.py内の変数b16を求めます。
shift(c,k)の返り値をalfとすると、(t1+t2)%16 = alfとなるt1を求めます。alfは暗号文の1文字であり、kはbrute forceのkeyでt2はそれに基づく値です。t1に対応する文字列を足していくとb16となります。
最後のステップはb16からflagを復元します。
b16を2文字毎に見ていき、(前1文字 - "a")*16+(後1文字 - "a") をchrすれば復元できました。
brute forceしているので16種類のflagの候補が出てきます。その中で一番ぽいのを選んで終わりです。
gbgcgdgegfggghgi
qQqRY[YSVUT[UYWWWYUYTS
v`@`AHJHwBEDvCurJuuDvHFFFuHDHCvvBssv
et_tu?_0797f143e2da9dd3e7555d7372ee1bbe
TcNcd.N/&(&U #"T!SP(SS"T&$$$S&"&!TT QQT
CR=RS=DCBOBBCBCC@@C
321>112122??2
!01ûóõó"ýðÿ!þ -õ ÿ!óñññ óÿóþ!!ý..!
/
/ ê
ëâäâìïîíäîâàààâîâíì
ùÙùÚÑÓÑÛÞÝÜÓÝÑßßßÑÝÑÜÛ
ÈèÉÀÂÀÿÊÍÌþËýúÂýýÌþÀÎÎÎýÀÌÀËþþÊûûþ
íü×üý·×¸¿±¿î¹¼»íºìé±ìì»í¿½½½ì¿»¿ºíí¹êêí
ÜëÆëì¦Æ§® ®Ý¨«ªÜ©ÛØ Û۪ܮ¬¬¬Û®ª®©ÜܨÙÙÜ
ËÚµÚÛµÌËÊÇÊÊËËËÈÈË
ºÉ¤Éʤ»º¹¶¹¹º¹ºº··º
©¸¸¹st{}{ªuxw©v¨¥}¨¨w©{yyy¨{w{v©©u¦¦©
§§¨bcjljdgfelfjhhhjfjed
keyは"d"でした。
et tu? は「(ブルータス、)お前もか？」らしい。
picoCTF{et_tu?_0797f143e2da9dd3e7555d7372ee1bbe}
↓m1z0r3勉強会採用問題
Mini RSA 70pt
What happens if you have a small exponent? There is a twist though, we padded the plaintext so that (M ** e) is just barely larger than N. Let's decrypt this:
ファイル：ciphertext
ciphertextにはN, e, cが書いてあります。
e=3であることとM^eがNよりちょっと大きいことから、c+N*k (k : 自然数)が立方数かを判断して、違うのであればkをインクリメントする、立方数ならばその3乗根を出してlong_to_bytesで終わりです。
picoCTF{e_sh0u1d_b3_lArg3r_60ef2420}
Dachshund Attacks 80pt
What if
dis too small? Connect withnc mercury.picoctf.net 58978.
serverに繋げるとn, cととてつもなく大きなeが送られてきます。
eが大きいとdが小さくなって成立する攻撃あったな、Wiener's attackか。
公開鍵暗号 - RSA - Wiener's Attack - ₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです
実装例を丸パクリで終了。
picoCTF{proving_wiener_6907362}
No Padding, No Problem 90pt
Oracles can be your best friend, they will decrypt anything, except the flag's ciphertext. How will you break it? Connect with
nc mercury.picoctf.net 28517.Hint : What can you do with a different pair of ciphertext and plaintext? What if it is not so different after all...
このserverは、flagの暗号文以外は復号してくれるオラクルとなっています。
最初に送られてくる「Padding oracle attack」が本当にそうか怪しい。平文は恐らくb"(パディング)picoCTF{temp}(パディング)"と予想(違った)。cの値を変えて送ったら復号して違うパディングの平文が手に入るのかなと最初はこんな感じでした。
上手くいかないので、RSA Oracle Attackでググってみると、以下のサイトが。
plain RSAに対するLSB decryption oracle attackをやってみる - ももいろテクノロジー
mのbit数だけ問い合わせをするのに対して、このoracleは途中で止まってしまう仕様…。とりあえずこのサイトにある別の方法(リンクがある)をやってみます。
RSAに対する適応的選択暗号文攻撃とパディング方式 - ももいろテクノロジー
これやってみたら一発。
picoCTF{m4yb3_Th0se_m3s54g3s_4r3_difurrent_4005534}
It's Not My Fault 1 100pt
What do you mean RSA with CRT has an attack that's not a fault attack? Connect with
nc mercury.picoctf.net 47414.ファイル：not_my_fault.py
はじめに、これ解けたの本当に嬉しい！！今回解けた中で一番solves数が少ない問題でした！
このserverはまずProof-of-Workをします。これはやるだけで特に問題に関係ないですね。
次に512bitの素数p,q (※gcd(p-1,q-1) = 2) を生成し公開鍵n(=p*q)を公開します。d_pは1~2^20の間で、d_qは1~q-1の間でランダムで決めます。秘密鍵dは中国人剰余定理の要領で、(p-1)で割ったらd_pかつ(q-1)で割ったらd_qとなる(p-1)*(q-1)=phi以下の自然数が採用されます。phiを法としたdの逆元eを公開鍵として公開します。
最後に15分以内でp+qの値をserverに送り一致すればflagが手に入ります。
最初はp-1とq-1でCRTしているところに注目しました。gcd(p-1,q-1) = 2 なのでd_p, d_qが偶数である場合、秘密鍵dは偶数になり(p-1)*(q-1)での逆元は存在しないことになります。この点が何かしらの脆弱性なのかなと調べてみたけど分からず…。
次に気になった点としては、p+qを答えさせるのに15分もの猶予があることです。計算させるにもこれだけの時間がかかるとしたらbrute forceだろう。brute forceするとしたらd_pの値は最大100万程度だからいけるはず。けどd_pの値を仮に置いたところで何が分かるんだろう…。
このサイトを見て直感的に思ったこととして、自分でmをテキトーに設定し与えられたe, n で暗号化する。d_pをbrute forceして仮に置きd_pを秘密鍵のようにpow(c, d_p, n)を計算しm'を得る。m = m' ならいいなと思ったけどそんなことはありませんでした。
貰ったファイルを手元で動かしp, q, d_p, d_q, dなどを出力し色々確かめてみます。本来の秘密鍵を使えばm = m'になるはずですがそうはならないのでこの差分に何があるのかと調べたところなんと(m' - m)%p = 0でした！
終わってから考えるとフェルマーの小定理を使えば証明できました！
正しいd_pを選ぶとm' - m = pow(c, d_p, n) - pow(c, d, n) = k*p (kは整数)となります。なのでd_pをbrute forceしてgcd(m' - m, n) != 1になるようなd_pを見つけます。gcdが1出ない時それはpの値と合致するので p+q は簡単に求められます。
手元で動かすと分かるのですが、上記の式はe*d = 1 mod φ(n) である時しか成り立ちません。m = c^d mod nとならないためですね。d_p, d_qが偶数の時は逆元は存在しないので、上手くいくためには何回かserverにつなげて運良く奇数になることを願うのみです。
秘密鍵dを(p-1) or (q-1)で割った余りが分かると解読される脆弱性があるとは知りませんでした。
It's Not My Fault 2 ではd_pの範囲が1 ~ 1<<36 に増えてました。brute force出来ないようになってますね。どうにかしてd_pの候補を1<<36から1/(2^16)ほどカットできる方法があるのかな…？
picoCTF{1_c4n'7_b3l13v3_17'5_n07_f4ul7_4774ck!!!}
↓m1z0r3勉強会採用問題
Play Nice 110pt
Not all ancient ciphers were so bad... The flag is not in standard format.
nc mercury.picoctf.net 21003ファイル：playfair.py
Playfair cipherという暗号があるらしい。もらったコード内にもそのwiki URLがあるけどこの問題ではこのwikiを理解する必要は全くなく、コードを読んで暗号アルゴリズムを理解すれば良かったです。言ってみればただの換字式暗号でした。
暗号化するためのmatrix(6*6の大きさでアルファベット小文字と半角数字をランダムで散りばめたもののよう)：既知 ncすれば教えてくれる＆コード内にもある
暗号化されたメッセージ：既知 ncすれば教えてくれる元のplaintext = msgを二文字ずつ暗号化していく。(msgが奇数長なら"0"を加えるが今回はそこまで重要じゃない)
その二文字をs1,s2とすると、まず両者のindexを調べ("0" -> (0,0) "f" -> (5,2) etc)、p1,p2に格納する。
enc_msg = ""
if s1,s2が同じ行にある文字:
enc_msg += s1の一つ右+s2の一つ右の文字
elif s1,s2が同じ列にある文字:
enc_msg += s1の一つ下+s2の一つ下の文字
else:
p1x : s1の行番号, p1x : s1の列番号だとする
enc_msg = matrix[p1x][p2y] + matrix[p2x][p1y]このenc_msgが暗号化されたメッセージである
復号はこんな感じです。
enc_msgを2文字毎見る -> e1,e2
if 同じ行: 一つ左の文字を足す
elif 同じ列: 一つ上の文字を足す
else: matrix[e1x][e2y] + matrix[e2x][e1y]
cryptoというよりかはプログラミングでしたね。
3f4b60ebf36369258d8638d2038c7ad1
↓m1z0r3勉強会採用問題
Double DES 120pt
I wanted an encryption service that's more secure than regular DES, but not as slow as 3DES... The flag is not in standard format.
nc mercury.picoctf.net 31991ファイル：ddes.py
このserverは、まずKEY1, KEY2と生成します。0~9から6文字と空白2文字です。そこから入力を受け付けunhexlifyやpaddingなどをしたあと、DES方式でKEY1で暗号化しさらにKEY2で暗号化したものを送ってくれます。
DESを2回やる2DESが悪いって何か聞いたことあるな…。これだ！
つまりは平文と暗号文が分かっている場合、鍵1と鍵2をbrute forceして求めることが出来ます。暗号文を鍵2でdecodeして鍵1でdecodeするというやり方ですと、鍵の長さをNとした際にO(N^2)とかなり時間がかかってしまいます。
そこで、平文を鍵1でencodeしたもの(Aとする)と、暗号文を鍵2でdecodeしたもの(Bとする)を記録しておきます。Aの中からBに含まれているものを探し、一致していればそのencode/decodeしたものが正しい鍵ペアとなり、探索を二分探索で行えばO(N log N)で済みます。birthday attackですね。
今回、ddes.pyを見ると0~9の中からランダムに構成された6文字と2文字分のスペースがそれぞれ鍵1,2に採用されています。つまり鍵1,2ともに10^6=100万通りしかありません。
サーバは初めに2DESによって暗号化されたflagを公開し、平文を入力すると同じ鍵ペアで暗号化してくれます。この平文と暗号文を頼りに上記の方法でbrute forceします。
pythonで「平文-(鍵1)->暗号文1」と「暗号文2-(鍵2)->暗号文1」の生成を行い、テキトーなファイルに"暗号文1 鍵1(もしくは鍵2)"という形で出力します。次に暗号文1が一致しているかの探索はpythonでやると遅いのでc++で記述しました。「暗号文2-(鍵2)->暗号文1」で生成された文字列をソートしておき、「平文-(鍵1)->暗号文1」を二分探索します。O( (KEY1の個数) * log(KEY2の個数) ) = O(10^7)程度ですね。競プロをやってた経験がここで生きました。
鍵長が短いためか異なる鍵ペアでも同じ結果となるものが多かったです。
あとは見つけた鍵で暗号化されたflagを復号して終わりです。
6d4e063d16d250b953d009e2ef07e241
↓m1z0r3勉強会採用問題
Compress and Attack 130pt
Your goal is to find the flag.
nc mercury.picoctf.net 29350ファイル：compress_and_attack.py
Hint : The flag only contains uppercase and lowercase letters, underscores, and braces (curly brackets)
この問題が一番悩みましたね…。
このserverは文字列を入力として受け付け、flag文字列の後ろに足してzlib.compress() でバイト列に圧縮します。次にSalsa20方式によって暗号化します。暗号化に必要なkeyは32バイトでos.urandom(32)によって定義されます。最後に暗号文と暗号化に使用したnonce, 暗号文の長さを表示します。
oracleのように入力を何回でも受け付けてくれ全て暗号化してくれます。
zlib.compress() を見ていきましょう。
str型をbytes型に圧縮します。どのように圧縮しているかは分からなかったのですが、zlib.decompressで元に戻せるとのことでした。
次にSalsa20について考えます。
色々調べたのですが、chacha20と同じように書かれていることが多く理解が難しかったです。wikiなどあるので参考にしてみて下さい。
自分なりの理解とすると長さ16のサイズが8bytesの配列を用意し、複雑な計算で値を決定します。その配列を2bytes毎にリトルエンディアン方式で長さ64の配列に格納します。この配列と平文をxorしたのが暗号文となります。
ではこの長さ64の配列を特定できたらflag+inputの圧縮bytesが分かりzlib.decompressで元に戻せるのではないのか、とこの配列のことだけを考えていきましたがどの文献を調べてもCrypto.Cipher.Salsa20と同じ挙動をするプログラムを作れず…。ここに数日使って考えてました。
ふと問題名について考えると、攻撃すべきはSalsa20ではなくzlib.compressじゃないのか？len()とれば分かるのにわざわざ暗号文の長さを表示させてるのは意味があるのではないのか？flagは55種類で構成されているというヒントからbrute forceでもするのか？
ここまで想像したらあと一歩頑張るだけで良かったです。
データの圧縮ですがzlib.compressがどのような挙動をしているかは不明ですが、辞書を作って圧縮しているそうです。例えばaaabbという文字列ならaが3個並んでbが2個並ぶという意味で圧縮すればa3b2のような形となり元の文字列が5文字なのに対し書き換えると4文字を圧縮することとなりさらに圧縮後の文字列長が短くなります。
つまり、flag+inputの形で圧縮するのでflagと同じ文字列をinputとすれば圧縮後の長さは他の文字をinputとした時より短くなり特定できるのでは？という考えに行きつきました。
flag+(flagの部分文字列)+(何か一文字) の (何か一文字)をbrute forceして圧縮率の良い入力を探します。有難いことに毎回一文字だけ他の文字と比べて暗号文の長さが短くなる時がありました。それをflagの部分文字列に追加していき、"}"が当てはまる時まで回します。serverに空文字送ると45の長さが返って来るのでそれを使っても良いですね。
私の部屋の通信が遅いせいか途中でタイムオーバーしてしまい、途中まで求めたflagの部分文字列をスタートにして求めました。solverには最初から求めるようなものを掲載しています。
この問題だけで6日かかった…。
picoCTF{sheriff_you_solved_the_crime}
↓m1z0r3勉強会採用問題
Scrambled: RSA 140pt
Hmmm I wonder if you have learned your lesson... Let's see if you understand RSA and how the encryption works. Connect with
nc mercury.picoctf.net 6276.Hint1 : Look at the ciphertext, anything fishy, maybe a little bit long?
Hint2 : What happens if you encrypt the same input multiple times?
Hint3 : Is RSA deterministic, why would outputs vary?
serverにつなげると公開鍵e, nに加えやけに値の大きい暗号文cが送られてきます。その後oracleのように任意の平文を暗号化してくれます。
まずcがnより大きいのでただのRSAではないことが分かります。c mod nを取っても何も分かりません…。
ヒントを参考に何回か同じ平文をoracleに投げてみます。ここで気付いたことは平文長1の時は何度やっても同じ暗号文が返ってくるのに対し、平文長2の時は異なる暗号文が送られてきて計2種類ありました。平文長3の時はもっと種類がありました。
さらに気付いたこととして平文"12"の暗号文の中に平文"1"の暗号文が含まれており"b"は含まれていない点です。
I will encrypt whatever you give me: 1
Here you go: 13124115897409148690175503414678311002550072264931973692606617424840875394178924924667165806108832225382916928826588194202873207482242336795957858653898547865981328797617704615680916248306354749186650700653148182638263380446877489886302315539251194333627159551808654634412960860616807864577972598755285353671
I will encrypt whatever you give me: 2
Here you go: 101313714858161761634424992049701340225225901427102268968811128642939843971178700310220868193986270827880834443468869250035948793946978960836348254108084878497428993736369171344812715172293673578722333182457607039902800607183698449846158886607662435088015414390779614690393026603998035663690508448583587232108
I will encrypt whatever you give me: 12
Here you go: 1312411589740914869017550341467831100255007226493197369260661742484087539417892492466716580610883222538291692882658819420287320748224233679595785865389854786598132879761770461568091624830635474918665070065314818263826338044687748988630231553925119433362715955180865463441296086061680786457797259875528535367153230702539676627077713255043960931601547634062672474402191718157569789042884730190065962186209672390181875607152200181525682605899965673289841280220588582699750835635714680926113598794384506889798456369904349419599058763732276368570777636231103073162515084138617288828974174983151895993498712348576936738885
I will encrypt whatever you give me: 123
Here you go: 462421867967343899092247904339366104356633194458564599507361558221364994129967069812583568887596621514840256516950454547665458461766413255685426477319761146914988512715132189205891743864191787311225979337320579909727351783274773056270868986792549936307841261246031472338304220554727128192453579090999110003105323070253967662707771325504396093160154763406267247440219171815756978904288473019006596218620967239018187560715220018152568260589996567328984128022058858269975083563571468092611359879438450688979845636990434941959905876373227636857077763623110307316251508413861728882897417498315189599349871234857693673888513124115897409148690175503414678311002550072264931973692606617424840875394178924924667165806108832225382916928826588194202873207482242336795957858653898547865981328797617704615680916248306354749186650700653148182638263380446877489886302315539251194333627159551808654634412960860616807864577972598755285353671
1文字毎に分け暗号化しそれを付け足してるのかと思いきや、"2"の暗号文は"12"に含まれていないので違うよう…。けど平文の長さに比例して暗号文の長さも長くなります。
ここで"12"の暗号文をSとTに分け、"1"の暗号文と一致するものをS、そうでないのをTとすると、"123"の暗号文にはSとTがともに含まれており、さらに異なる文字列Uがありました。
つまり平文をmとすると、{m[0:1], m[0:2], m[0:3], ... , m[0:n]} をそれぞれRSAで暗号化し暗号文をごちゃ混ぜにして繋げていると予想しました。
なので後の実装としては、{ p, pi, pic, pico, picoC, picoCT, picoCTF, picoCTF{ }の暗号文を配列に記憶します。次にstring.printableで回し、貰った暗号文の内記憶した暗号文を除いた文字列S'が最初に渡されるflagの暗号文に含まれていたら、その入力はflagの部分文字列であることが分かります。この際に記憶配列に今の暗号文を追加します。
これを繰り返しflagを求めます。
Compress and Attackと同様途中でタイムオーバーに...。通信弱いとつらい。
picoCTF{bad_1d3a5_2268684}
It is my Birthday 2 170pt
問題文が見れませんでした…。
内容的には、渡したpdfと後ろ1000バイトは同じである異なるpdfをこの二つ作り、このウェブサイトにアップロードしてください。この二つのpdfのSHA-1ハッシュ値は同じになるようにしてください。
ファイル：invite.pdf
Hint : SHAttered (他にもあったけど覚えてません…)
問題文がもう見れなくなっておりなんとなくこんな感じでしたとだけ…。
うーーん、Forensicsぽい。苦手だ。とりあえずSHA-1が良くないということは知ってるけど理由までは知らない…。昔SHA-1の衝突を使ったCTFあったらしいと聞いたことがあるぞ。ググりつつ人に聞いたりしてました。
とりあえずSHA-1の理解を。
バイナリデータが二つ
xxxxABCxxxxxxxx
xxxxDEFxxxxxxxx
このようにある時SHA-1のハッシュ値がABCとDEFで衝突するとき、上の二つのSHA-1ハッシュ値も衝突します。まあそのABCとDEFのペアを見つけるのにかなりな時間がかかるんですけどね。
SHA-1 pdf collisionなどでひたすらググってました。githubとかで色んなコードコピペしたのに上手くいかず…。かなり唸ってました。
チームメイトとzoomで議論した時にふと「既に出てる衝突する二つのpdfの後ろに1000バイト引っ付ければ良くね？」と。ビンゴでした！！
picoCTF{h4ppy_b1rthd4y_2_m3_ed9cc7d0}
Pixelated 200pt
I have these 2 images, can you make a flag out of them?
ファイル：scrambled1.png, scrambled2.png
Hint : Visual cryptography - Wikipedia , Think of different ways you can "stack" images
(実はチームメイトが解いたんですけど、自分も惜しかったので紹介させていただきます)
pngファイルは前回のutctfで初めて使ったPILを利用してみます。貰ったpngを重ねたらいいのだろう。PIL使ったり、片方のpngの透過度半分にしたりとかやったんですけど灰色の画像しか出てこない…。
PILのImage.composite() では上手くいかないようでNumpy arrayで画像を読み込み和を取れば一発で出たようです。チームメイトすごいなぁ。
picoCTF{2a4d45c7}
↓m1z0r3勉強会採用問題
New Vignere 300pt
Another slight twist on a classic, see if you can recover the flag. (Wrap with picoCTF{})
ioffdcjbfjmcifelcaloifgcjecgpgiebpfeiafhgajafkmlfcbpfbioflgcmacgファイル：new_vignere.py
Hint : Vigenère cipher - Wikipedia
new_vignere.pyで定義されているb16_encode(), shift関数はNew Caesarで与えられたファイルと同じ挙動です。ただ前問と違うのはkeyの長さが15未満とあるのでbrute forceできません。
Vigenere暗号のKEYの長さを特定するのにカシスキーテストというのが利用されます。平文内にある単語が複数回登場しその単語を同じKEYの部分で暗号化することで、同じ暗号文になります。その同じ暗号文が登場するindexを調べることでKEYの長さの候補をある程度絞ることが出来ます。
今回の場合、"iof"という暗号文が2回出てきています。1~3文字目と55~57文字目が"iof"となっており、差は54です。54を素因数分解すると {1, 2, 3, 6, 9, 18, 27, 54}となり、keyの長さが15未満であるから {1, 2, 3, 6, 9} に絞ることができます。
keyの長さが6以下であればbrute forceできそうです。長さ6の場合、keyは16種類の文字で構成されるので16^6 ≒ 16m 程度なのでちょっと待てば行けそうです。今回flagが"abcdef0123456789"のみで構成されているので復号した際にこれと合致すればOKです。
(brute force中…)
出ない……。keyの長さは9なのか？それは求められないからkeyの長さが6まで全て試したけど出ず…。
カシスキーテストを言及していることから恐らくkey長は9なのだろう…。brute force出来ないので別の方法を考えます。
今回flagの文字が制限されているのでkeyの選び方によってはその通りに復号されません。ということは、正しく復号できるようなkeyを探すのはそんなに難しくないのでは？となりました。
例えば暗号文の2文字2文字"io"が正しく復号される時のkeyの候補は、{(f, i), (f, j), (f, k), (f, l), (f, m), (f, n)}です。keyの1文字目は"f"であることが確定しました。このように暗号文の2文字毎見ていき合計18文字見たところで長さ9のkeyが特定できました。
こんな感じ↓ 最初の数字をiとすると、i*2, i*2+1文字目を正しく復号出来るのは(s, t)です、という形です。s, tは"a"を0, "p"を15としています。
0
(5, 8)
(5, 9)
(5, 10)
(5, 11)
(5, 12)
(5, 13)
1
(2, 2)
(2, 3)
(2, 4)
2
(0, 12)
(0, 13)
(0, 14)
(0, 15)
3
(6, 11)
(6, 12)
(6, 13)
(6, 14)
(6, 15)
4
(15, 4)
(15, 5)
(15, 6)
5
(9, 2)
(9, 3)
(9, 4)
(9, 5)
6
(2, 0)
(2, 1)
(2, 2)
(2, 14)
(2, 15)
7
(14, 6)
(14, 7)
(14, 8)
(14, 9)
(14, 10)
(14, 11)
(14, 12)
(14, 13)
(14, 14)
(14, 15)
8
(15, 0)
(15, 14)
(15, 15)
keyが[5, 9, 2, 2, 0, 14, 6, 15, 15]となれば上記の候補に全て当てはまるようになります(隣り合う2つのペアは必ず上に含まれています)。つまりkeyは"fjccaogpp"でした。
綺麗にkeyが復元されてめっちゃ気持ちよかった！！
picoCTF{5342d0ee1ecd51dd9e75b1e929b59da1}
solverや問題などはこちらから！
picoCTFは簡単な問題や難しいけど誘導がそれなりにされている問題、普通に難しい問題と幅広く楽しかったです！ 何より解ける問題が多かったのは有難いですね。しかも得点がsolves数によって影響しない方式だったので、せっかく解いたのに得点が下がるなんてこともなくて精神的に嬉しい(笑) でもIt's Not My Fault 1を解けた時はもっと点数欲しかったなぁと…(笑)
何より日本人6位で嬉しかった上に解いてて楽しかったです！！ありがとうございました！
それでは！
See you next time!
