Attack All Around

今やCTFと競プロばかりだが、トビタテ生のアメリカ留学やTOEFL奮闘記

ångstromCTF 2021 writeup

2021年度初のCTFはångstromCTFに参加しました。前回のpicoCTFに続き解ける問題も多いけど悩まされる良いCTFでした。全く歯が立たないというよりこちらの方が良いですね。

 

 

 

Result

 

f:id:partender810:20210408103617p:plain

総合結果

 

結果は1430ptで158位でした! まあまあ頑張れたと思います。

 

Writeup

Misc

Sanity Check 5pt

Join our discord to talk to us and get the flag (clam might even say hi)! https://discord.gg/Dduuscw

As repentance for last year, the music video will be separate and on a strict opt-in basis. https://www.youtube.com/watch?v=dQw4w9WgXcQ

とりあえずDiscordに入れと、入ったけど分からない…。

結局、rolesチャンネルにあったメッセージに:三角の旗:マークのリアクション付けるとgeneralチャンネルに入れトピックにflagが書いてありました。これに気付くのに時間がかかり、他の問題を先に解いてました。

 

actf{always_gonna_give_you_up}

 

 

Survey 5pt

Thank you for participating in our CTF! We hope you had fun. Please fill out this survey to help us improve the competition for next year. We encourage each individual that participated in the CTF to submit a response.

This challenge does not affect time-based tiebreakers.

アンケートに答えて終わりです。

 

actf{roly_poly_fish_heads_are_never_seen_drinking_cappuccino_in_italian_restaurants_with_oriental_women_yeah}

 

 

Archaic 50pt

The archaeological team at ångstromCTF has uncovered an archive from over 100 years ago! Can you read the contents?

Access the file at /problems/2021/archaic/archive.tar.gz on the shell server.

今回は問題サイトにshellがあり、その中のarchive.tar.gzを探せという問題でした。

 

cd / でrootディレクトリに移動し、該当ファイルのあるディレクトリへ移動します。そしてtar.gzを解凍して終わり、と思いきや権限が無いよと怒られる。しかしこの中にどうやらflag.txtがあるようです。

 

なんとかして解凍せずに閲覧できないかと模索したら、その方法を発見!

【Linux】tar.gzを解凍せずに中身を参照する | ばちブロ

tar -zxOf archive.tar.gz flag.txt でOKです。

 

actf{thou_hast_uncovered_ye_ol_fleg}

 

 

Fish 60pt

Oh, fish! My dinner has turned transparent again. What will I eat now that I can't eat that yummy, yummy, fish head, mmmmmm head of fish mm so good...

ファイル:fish.png 

とりあえずこの写真を開いてみます。何も見えません…。 

 

うーん、背景透過の画像かなぁ。それをどうやったら見れるんだろう。と色々ググって試してみたけど何も分からず…。

 

そういやパワポに図を貼り付ける時にオプションでやると背景透過の画像でも背景が黒色になる時あったな、パワポに貼ってみるか!

 

出た。

 

f:id:partender810:20210407230921p:plain

これが想定解とは到底思えない

 

actf{in_the_m0rning_laughing_h4ppy_fish_heads_in_th3_evening_float1ng_in_your_soup}

 

 

Crypto

Relatively Simple Algorithm 40pt

RSA strikes strikes again again!

ファイル:source.py, output.txt

 

p, qが分かっているRSAです。やるだけですね。

 

actf{old_but_still_good_well_at_least_until_quantum_computing}

 

 

Exclusive Cipher 40pt

Clam decided to return to classic cryptography and revisit the XOR cipher! Here's some hex encoded ciphertext:

ae27eb3a148c3cf031079921ea3315cd27eb7d02882bf724169921eb3a469920e07d0b883bf63c018869a5090e8868e331078a68ec2e468c2bf13b1d9a20ea0208882de12e398c2df60211852deb021f823dda35079b2dda25099f35ab7d218227e17d0a982bee7d098368f13503cd27f135039f68e62f1f9d3cea7c
The key is 5 bytes long and the flag is somewhere in the message.

これが先程の問題と同じ点数とは…難易度が違う…。

 

ciphertextは16進数でかなりの桁数で、keyは5bytesなら単純にciphertext xor keyなら上位桁は変わらないのでは?ととりあえずlong_to_bytesしてみました。まあそんなんで解けるわけないですよね。

 

keyが5bytesならbrute forceできないしなぁ…とこの5bytesに注目しました。flagが平文にあるなら "actf{" という文字列があることが分かります。つまりxorして"actf{"となる部分があるはずなので、それを逆算してkeyの候補を絞ります。例えばciphertextの1byte目は"ae"です。aeを復号すると文字"a"になるのであれば、int("ae",16)^ord("a")がkeyの1byte目になります。となると次の"27"が文字"c"になって、と考えるとkeyの候補数は高々ciphertextの長さ程度です。

 

全て試して平文の中に"}"が含まれたものを出力していくと、その中にそれっぽいのを発見しました。

 

Congratulations on decrypting the message! The flag is actf{who_needs_aes_when_you_have_xor}. Good luck on the other crypto!

 

actf{who_needs_aes_when_you_have_xor}

 

 

Keysar v2 40pt

Wow! Aplet sent me a message... he said he encrypted it with a key, but lost it. Gotta go though, I have biology homework!

ファイル:source.py, output.txt

ふむ…難しいことしているな。outputの最後の方にflagっぽい文字列があるけど、どうやって復号するのかな。

 

あれ?これただの換字式暗号では?とquipquipに投げました。便利すぎるツールですね。ちゃんと平文と暗号文のアルファベットが全単射だったので上手くいったようです。

 

according to all known laws of aviation, there is no way a bee should be able to fly. its wings are too small to get its fat little body off the ground. the bee, of course, flies anyway because bees don't care what humans think is impossible. yellow, black. yellow, black. yellow, black. yellow, black. ooh, black and yellow! let's shake it up a little. barry! breakfast is ready! coming! hang on a second. hello? barry? adam? can you believe this is happening? i can't. i'll pick you up. looking sharp. use the stairs. your father paid good money for those. sorry. i'm excited. here's the graduate. we're very proud of you, son. a perfect report card, all b's. very proud. ma! i got a thing going here. you got lint on your fuzz. ow! that's me! wave to us! we'll be in row 118,000. bye! barry, i told you, stop flying in the house! hey, adam. hey, barry. is that fuzz gel? a little. special day, graduation. never thought i'd make it. three days grade school, three days high school. those were awkward. three days college. i'm glad i took a day and hitchhiked around the hive. you did come back different. hi, barry. artie, growing a mustache? looks good. hear about frankie? yeah. you going to the funeral? no, i'm not going. everybody knows, sting someone, you die. don't waste it on a squirrel. such a hothead. i guess he could have just gotten out of the way. i love this incorporating an amusement park into our day. that's why we don't need vacations. boy, quite a bit of pomp... under the circumstances. well, adam, today we are men. we are! bee-men. amen! hallelujah! students, faculty, distinguished bees, please welcome dean buzzwell. welcome, new hive city graduating class of... ...9:15. that concludes our ceremonies. and begins your career at honex industries! will we pick ourjob today? i heard it's just orientation. heads up! here we go. keep your hands and antennas inside the tram at all times. wonder what it'll be like? a little scary. welcome to honex, a division of honesco and a part of the hexagon group. this is it! wow. wow. we know that you, as a bee, have worked your whole life to get to the point where you can work for your whole life. honey begins when our valiant pollen jocks bring the nectar to the hive. our top-secret formula is automatically color-corrected, scent-adjusted and bubble-contoured into this soothing sweet syrup with its distinctive golden glow you know as... honey! that girl was hot. she's my cousin! she is? yes, we're all cousins. right. you're right. at honex, we constantly strive to improve every aspect of bee existence. these bees are stress-testing a new helmet technology. what do you think he makes? not enough. here we have our latest advancement, the krelman. actf{keyedcaesarmorelikesubstitution}

 

actf{keyedcaesarmorelikesubstitution}

 

 

sosig 70pt

Oh man, RSA is so cool. But I don't trust the professionals, I do things MY WAY. And I'll make my encryption EXTRA secure with an extra thicc e! You'll never crack it!

ファイル:output.txt

eが大きすぎるのでWiener's Attackですね。picoCTFでも同じ問題あったのでsolverコピペしてn,e,cだけ変えて終了です。

 

partender810.hatenablog.com

 

actf{d0ggy!!!111!1}

 

 

Home Rolled Crypto 70pt

Aplet made his own block cipher! Can you break it?

nc crypto.2021.chall.actf.co 21602

ファイル:server.py

このサーバは1を選ぶと任意の平文を暗号化してくれ、2を選ぶと「この平文を暗号化せよ」と言われ10回連続でサーバでの暗号化した結果と一致すればflagを出してくれます。

 

暗号化方式をざっくり言うと、まずkeyを96の長さで生成します。前1/3をk1, 真ん中1/3をk2, 残りをk3とし、平文をm(16 bytesとします)と置くと

c <- m & k1

c <- c ^ k1

c <- c & k2

c <- c ^ k2

c <- c & k3

c <- c ^ k3

としcが暗号文となります。平文が16bytes以上の場合は区切って同じように暗号化します。keyの値が分かれば簡単に暗号化できますね。

 

これって数学的に解くのかなとandしてからのxorに法則を見つけようとしたけど無理でした。

 

でもこれってbit演算だけだからk1,k2,k3が各々0,1である場合を出してみればいけるのでは?と考えたけど、結果からkeyは特定できず…。

 

でも各bitが他のbitに影響を及ぼさないから、全てのbitに対して0だった時の暗号文と1だった時の暗号文を記憶すればいけるのでは?となりました。つまり、平文のi bit目が0だった時に暗号文のi bit目が0か1かをans[2*i]に格納し、平文のi bit目が1だった時に暗号文のi bit目が0か1かをans[2*i+1]に格納しました。

 

1を選ぶのは2回だけで良くて、"0"*32と"f"*32を暗号化した結果を上記のようなans配列に記憶します。

 

次に2を選択し暗号文を2進数にして各bitを確認しans配列を用いて暗号文を生成します。これを10回繰り返して終了です。

 

actf{no_bit_shuffling_is_trivial}

 

 

Follow the Currents 70pt

go with the flow... 

ファイル:source.py, enc

keyをまず2bytesランダムで生成し、そこからzlib.crc32というのでkeyの長さを増やします。そのkeyとflagをxorした結果がencです。

 

zlib.crc32はチェックサムを計算しているようですが、詳しいことは分かりません(笑) ただ、最初のkeyの2bytesが決まれば、その後は一意に決まります。故にその2bytesをbrute forceしてkeyを作ってencとxorして、"actf"の文字列が含まれるのを出力して終わりです。

 

there are like 30 minutes left before the ctf starts so i have no idea what to put here other than the flag which is actf{low_entropy_keystream}

 

actf{low_entropy_keystream}

 

 

I'm so Random 100pt

Aplet's quirky and unique so he made my own PRNG! It's not like the other PRNGs, its absolutely unbreakable!

nc crypto.2021.chall.actf.co 21600

ファイル:server.py

第一にserver.pyについて、r1, r2(10進数でちょうど8桁)がこの乱数発生プログラムのseedになります。serverに"r"を送ると、getNum関数にて乱数を発生してくれます。r1の値を二乗すると16桁になります。その真ん中の8桁がr1(.seed)になります。r2についても同様です。そして、r1*r2を出力します。これは3回までやってくれます。

 

解法としては、r1*r2を素因数分解して8桁*8桁の形にします。自分はその作業が面倒だったので、素因数分解した際に片方が8桁の素数になるまでサーバとつなぎ直していました。

 

r1, r2が決まれば16桁の自然数の内真ん中8桁がr1(もしくはr2)となる平方数をbrute forceします(もっといい方法があるかも?)。gmpy2.irootで平方数かどうかチェックします。8桁をbrute forceするのでかなりの時間がかかりますが、サーバのコネクションは切れずに待っててくれます。

 

真ん中8桁がr1となる16桁の平方数はいくつか候補が出てきますが、次に乱数を発生した際にr1*r2の形なので、割り切れる候補が正しいr1の最初のseedになります。最初のseedが分かれば、次の乱数を予想するのは容易です。

 

最後に2回連続次の乱数を予想して当てればflagをくれます。

 

actf{middle_square_method_more_like_middle_fail_method}

 

 

Substitution 130pt

nc crypto.2021.chall.actf.co 21601

ファイル:server.py

これは個人的に物議をかm...失礼いたしました。

 

まずserver.pyの挙動の理解に時間がかかりました。flagのASCIIコードをm[0],m[1],...,m[n-1]とすると、valueが入力の値でlambda式とreduceを使って、

m[0]*pow(value,n-1) + m[1]*pow(value,n-2) + ... + m[n-2]*pow(value,1) + m[n-1] mod 691

を計算し出力してくれます。

 

ここからが長かった…。valueを0とすると125が返ってきてm[n-1]に該当します。chrすると"}"となるのでflagの最後の文字ということが分かります。ではここからどう他の文字を特定するのでしょう…。

 

こんな数学的な問題を扱うのは久しぶりな上、どうあがいても式が立てられない…。ググっても分からない…。

 

数学が得意そうなm1z0r3メンバーのAtCoder黄色ランク(上位数%)の凄腕に聞いてみました。

 

「それはラグランジュ補間をやるだけですね。」

 

なんだそれは。わざわざ解説記事も教えてくれたのに理解できないポンコツに成り下がり…。AtCoderでも全く同じ問題が出てたので、それをACしてた彼のソースコードをコピペして終了!

 

Submission #10506051 - AtCoder Beginner Contest 137

 

彼にこの問題の難易度聞くと、彼レベルでないと解けない程だと…。緑coderの僕には無理な話でした!なのになんで3桁solvesもあるの!?みんなプログラムスキルが高いのかググり力が高いのか…。

 

期間終盤でみんなが停滞している中、この問題correctになったことで1000pt台に乗ったのは嬉しかったです!

 

actf{polynomials_20a829322766642530cf69}

 

 

Oracle of Blair 160pt 

Not to be confused with the ORACLE of Blair. 

nc crypto.2021.chall.actf.co 21112

ファイル:server.py

出ました苦手なAES問題…。でも自力で解けたの本当に嬉しい!

m1z0r3の方、この問題勉強会で使うのであまり見ないよう…

 

このサーバは第一にkeyを32bytesランダムに決めます。次にwhile文に入り、入力をunhexlifyして、その結果"{}"が含まれていたらflagにreplaceしてくれます。7b7dを入力するとb"{}"になります。次に長さが16の倍数になるようpadしてivをランダムに決めます。そしてkeyとivを用いてAESのCBCモードでdecryptして出力します。

 

CBCモードと言ったらpadding oracle attackですよね。でも今回はpaddingを勝手にしてくれるので使えません。

 

そしてdecryptしてくれるのに全然気付かず、ずっとencryptを見ていました。

 

f:id:partender810:20210408004329p:plain

AES CBC decrypt

 

ここで、7b7dを送った時の返ってきた16進数と7b7d+"07"*7を送った時の返ってきた16進数の後半半分が一致していることが試して分かりました。その16進数の桁数の結果も踏まえて、flagの長さが25bytesということが分かりました。

 

上の図でCiphertextを左からc1, c2, c3 Plaintextをp1, p2, p3とすると、

p3 = enc(c3) xor c2

となります。ここでenc()とはkeyによって暗号化された値です。このサーバを使うとc2, c3は自分で決められp3は与えられることからenc(c3)を求めることができます。なぜenc(c3)を求めたいかというと、ここが分かると欲しいc2の値が分かります。

 

c2, c3は全て0としてenc(c3)を求めます。その後、7b7d + "07"*7 + "00"*16を送り付けます。c1, c2はflagとpaddingが該当し、c3は"00"*16です。enc("00"*16)は先程求めたので、貰った復号16進数の後ろ1/3がp3に該当するのを使うと

c2 = enc(c3) xor p3

とc2が求まり、long_to_bytesするとflagの後ろの部分とpaddingが見えました。

 

同じようにenc(c2)を求めます。c1 = "00"*16として送るとp2に該当する部分を利用し

enc(c2) = c1 xor p2 

 で求まります。その後、7b7d + "07"*7 + "00"*16を送り、

c1 = enc(c2) xor p2

でc1が求まり、flagの前半部分が分かりました。

 

これできたの本当に気持ち良かったです!苦手分野であるだけに喜びもひとしおです!

でもアメリカ大統領選挙のようなURLが問題文にあったのなんでだろう。

 

actf{cbc_more_like_ecb_c}

 

 

solverや問題はこちらから!

github.com

 

 

前回のpicoCTFに続いて(まだwriteupは公開で来てませんが)、結構crypto問題を解けたと思います(個人比)。3桁solvesのものをほとんど解けるようになったのは嬉しいなぁ。m1z0r3がもっと有名になると嬉しいですね!

 

それでは!

 

See you next time!