BCACTF2.0参加記

#はじめに
CTF歴2週間の者です。CpawCTF埋めてたらサイトが止まってしまいました。普段は主に競技プログラミングをやっています。初めてこういった大会に参加し、楽しかったのとわからなかったことの整理、そして備忘録としてこれを書いています。Writeup?って言うんですかね?一応ルールは確認したんですけど大会後の感想戦みたいなものに言及しているものがなかったので大会後に色々書いて公開するのはたぶん大丈夫だと思います。公式ディスコでダメって言われてる問題は解けてないのでそこは大丈夫です。ダメだったらごめんなさい……
解いた順番に書いていきます。わからなくて逃げたものは最後にまとめます。

結果としてはチーム参加で個人で1100点でした。まあ簡単な問題ばっか漁ってたのでいいのか悪いのかもよくわからないんですけど、分からないなりに楽しめたかなと思います。

問題文は基本的に本題と関係ないことがい多いのでかなり ~~適当~~ 意訳です。

#1日目
Cryptoしか自信がないのでCryptoだけやっていた。

##Ciper Mishap(Crypto)

>シーザー大好きな友達がテキストファイルを送ろうとしたけど彼の妹(CapsLock大好き)が暗号化しちゃったから解いて！

テキストファイルを開いてみると、

~~~
126-Y, 113-N, 122-N, 130-N, 117-N, 107-N, 137, 114-N, 127-Y, 137, 113-Y, 104-N, 131-N, 110-N, 137, 105-Y, 110-N, 110-N, 121-Y, 137, 131-Y, 114-N, 112-N, 110-N, 121-N, 110-N, 125-N, 110-N, 137, 114-Y, 121-N, 126-N, 127-N, 110-N, 104-N, 107-N
~~~

どう見ても8進ASCIIコードで、Y,Nがおそらく大小なのでそれを元に直すと、

~~~
Vkrxog_lW_Kdyh_EhhQ_Yljhqhuh_Lqvwhdg
~~~

シーザー暗号なので1文字ずつ戻してみると3文字目でヒット、なるほど、Caesar-loving

~~~
Should_iT_Have_BeeN_Vigenere_Instead
~~~

ヴィジュネル暗号にすべきだった、とかそんな意味?
海外の"CapsLock"ってShiftなのか……?その辺だけよくわからない。

##Rainbow Passage(Crypto)

>平文と暗号文と暗号化アルゴリズムがあるので鍵を読み取ってほしい。

暗号化アルゴリズムを見てみると

~~~Python
def encode_block(m, pm):
    m = [i for i in m]
    print(m)
    c = [0] * 16
    for i, w in enumerate(pm):
        for j, l in enumerate(w):
            if l == '1':
                c[j] ^= m[i]
    return binascii.hexlify(bytes(c))
        

def encode(m, pwd):
    pm = []
    while pwd:
      a = '0'*8 + bin(ord(pwd[0]))[2:]
      a = a[-8:]
      b = '0'*8 + bin(ord(pwd[1]))[2:]
      b = b[-8:]
      pm.append(a + b)
      pwd = pwd[2:]
    c = b""
    while m:
        c += encode_block(m[:16], pm)
        m = m[16:]
    return c

~~~

鍵は32文字でないとダメということがほかの部分で明記されている。
encodeという関数で2文字ずつ鍵を16個に分解して、分解したカギを用いて16文字ずつencode_blockで暗号化していることとがわかる。
encode_block内を見ると暗号文も16文字で、カギが16bit16個、n個目のカギが平文のn文字目に、mbit目が暗号文のm文字目に対応していることがわかる。
例えば、1個目のカギが1111111100000000で、平文1文字目が78("x")であるならば、暗号文は78787878787878780000000000000000になる。ここに2個目の鍵と2文字目、3個目の鍵と3個目、と、どんどんXORされていく。
↓イメージ    この場合暗号文の1文字目がa XOR b XOR dになる。

~~~
                  平文 :  鍵
dddddddd             d:1111111100000000
        cccccccc     c:0000000011111111
bbbbbbbbbbbbbbbb     b:1111111111111111
a a a a a a a a      a:1010101010101010
~~~


実際は16文字を積み重ねているので鍵が変わったとしても平文16文字から暗号文として出うる文字のXORの組み合わせは2^16(=65536)通りになる(十分探索可能)。つまり、暗号文に対して1文字ずつ平文から取りうる組み合わせを探索(bit全探索)してやれば、上のような鍵の配列が得られる。
実際に探索してみると16文字だけでは組み合わせ候補がたくさん出てしまったので組み合わせ候補を絞り込みながら読み進めるようにしたところ、3回(48文字)で組み合わせの絞り込みができた。
実際に出てきた組み合わせがこちら

~~~
[0, 61305, 65535, 49218, 5788, 16015, 51722, 61942, 0, 63481, 65535, 49518, 48144, 31473, 4382, 48859]
~~~

それぞれの数字が上の例での縦の行に該当するので、各要素を2進にして0と1の二次元配列に直して転置すれば、上の例のような鍵の配列が得られる。そのカギの配列は2文字ずつになっていることに気を付けながらASCIIで戻すと、

~~~
system-of-linear-equations-273de
~~~

この意味を成す文字列が出てきた時の達成感がたまらん。
意味は分からんが。(線型方程式？？)


##􃗁􌲔􇺟􊸉􁫞􄺷􄧻􃄏􊸉(Crypto)
>暗号化されたテキストを解読してフラグを発見してください。

テキストファイルを見ると明らかにURLっぽいところがあったり注釈の大かっこだったりWikipediaかなぁ……と。
バイナリエディタで開いてみると文字化けしている部分に大体似たような文字コードが入っているので検索。Unicodeの未使用部分だの豆腐(フォント未対応の文字化け)だのがヒットして色々わかってくる。
出現する未知の文字コードを抽出してみると23種類、なるほど。
URLとかから地道に文字をに入れていって完成。

~~~
"never gonna give you up" is the debut single recorded by english singer and songwriter rick astley, released on ' july 1987. it was written and produced by stock aitken waterman, and was released as the first single from astley's debut album, whenever you need somebody (1987). the song was a worldwide number2Done hit, initially in the united kingdom in 1987, where it stayed at the top of the chart for five weeks and was the best2Dselling single of that year. it eventually topped the charts in 25 countries, including the united states and west germany.[6] the song won best british single at the 1988 brit awards.
the music video for the song has become the basis for the "rickrolling" internet meme. in  08, astley won the mtv europe music award for best act ever with the song, as a result of collective voting from thousands of people on the internet, due to the popular phenomenon of rickrolling.[7] the song is considered astley's signature song and it is often played at the end of his live concerts.
in  19, astley recorded and released a 'pianoforte' version of the song for his album the best of me, which features a new piano arrangement.[8]
shamelessly copied from [wikipedia's article on the subject](https://en.wikipedia.org/wiki/never_gonna_give_you_up)
bcactf{sorry_we_ran_out_of_runes_sjrhwbg}
~~~


##Sailing Thru Decryption(Crypto)

>航海中に何かを失ってしまった。それがペットであることは覚えているが名前が思い出せない。思い出せるようにしてほしい。

画像を見ると明らかに国際信号旗なのでとりあえず解読。

~~~
011001110110101001110011011011010111011101110011011110110011000101111000010111110110111100110001011010110101111101111000001101000111000001110010010111110110110000110011011110010011010001101010011011100011111101111101
THISKEYISFHSKDN
~~~

2進をASCIIで戻す。

~~~
gjsmws{1x_o1k_x4pr_l3y4jn?}
This_key_is_fhskdn
~~~

明らかにフラグが出てきた。
gjsmwsとbcactfを比較するとその差がfhskdn(5,7,18,10,3,13)になっていることがわかる。
これをアルファベットにのみ適用すると、

~~~
bcactf{1s_h1s_n4me_g3r4rd?}
~~~

gerard、ほかの問題でも言及されてた気がするが、何者なのか……


##RSAtrix(Crypto)

>RSAtrixを作ったよ！

二つのファイルからただのRSA暗号であることがわかるので復号。
Python3.8だか9だかから逆元を楽にとれるようになったので復号も簡単。

~~~Python
from math import gcd

def lcm(p,q):
  return (p*q) // gcd(p,q)

p = 35953130875571662629774552621633952493346190947047
q = 68201352784431955275947627343562102980308744031461
c = 1879922562037963072325125556499104095457740584077567873217970367519076380025989311243974742849996920
n = p * q
e = 3

pri_key=pow(e,-1,lcm(p-1,q-1))
m=pow(c,pri_key,n)
m=hex(m)[2:]


for i in range(len(m)//2):
  print(chr(int(m[i*2:i*2+2],16)),end="")
print()
~~~

~~~
bcactf{just-rsa-with-matrices-9385dax}
~~~

ただRSAを行列にしただけ、確かに。

#2日目
1日目夜更かしして疲れたのと昼過ぎからバイト行ってシンエヴァ見てARC参加してで何もできませんでした……
シンエヴァ面白かったです。

#3日目
binexが簡単という情報が入る
やってみる

##BCA Mart(binex)

>オンラインショップを開いたので来てね！

フラグが\$100で売っているが\$15しかない、どうしたものか。
コードを一部抜粋

~~~C
    if (amount > 0) {
        cost *= amount;
        printf("That'll cost $%d.\n", cost);
        if (cost <= money) {
            puts("Thanks for your purchse!");
            money -= cost;
        } else {
            puts("Sorry, but you don't have enough money.");
            puts("Sucks to be you I guess.");
            amount = 0;
        }
    } else {
        puts("I'm sorry, but we don't put up with pranksters.");
        puts("Please buy something or leave.");
    }
~~~

amountが1以上でないとそもそも判定に入らない、そしてそれが値段の倍率になって判定される。
ありもしない金で払ったことにするにはどうするか、cost*amountがオーバーフローするようにすればよい。

~~~
How many super-cool ctf flags would you like to buy?
> 300000000
That'll cost $-64771072.
Thanks for your purchse!
bcactf{bca_store??_wdym_ive_never_heard_of_that_one_before}
~~~

##Honors ABCs(binex)

>アルファベットのお勉強の時間！

コード内の条件分岐を見るとgrade(スコア)を100以上にしなければならない。
getsで読み取っているのでそれを用いて適当に書き換えればよい。


~~~
Answer for 1: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
How did you end up here?
You must have cheated!
Let me recite the BCA plagarism policy.

(中略)

also also have the flag!
bcactf{now_i_know_my_A_B_Cs!!_next_time_wont_you_cheat_with_me??}
~~~

個人的に一番好きなフラグ。

##AP ABCs

>テストでズルするなよ！

Honors ABCsから条件分岐が変わり、フラグのファイルを読むにはscoreを0x73434241にしてやらなければならない。
0x73434241って何だ、sCBAか、なるほど。

~~~
Answer for 1: ABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCsABCs

You got a 1933787713 on your APs.
Tsk tsk tsk.
Cheating on the AP® tests is really bad!
Let me read you the College Board policies:

(中略)

Shamelessly copied from
https://apstudents.collegeboard.org/ap-2020-2021/about-2021-ap-exams/terms-conditions
And take your flag: bcactf{bca_is_taking_APs_in_june_aaaaaaaa_wish_past_me_luck}
~~~

解答の形式がいかにもズルって感じがして面白い。

##Secure Zip(foren)

>Geraldが宿題をzipファイルにしまってしまったので彼のために見つけてあげてほしい。

適当に3つくらいzipこじ開けるやつを並行で動かしてたら開いた。
朝5時くらいに死にかけながらやってたので覚えてない……
記録し忘れた……
8文字で4文字2回の繰り返しだったはず。

##Zstegosaurus(foren)

>恐竜の絵の中に名前が隠れてるから探してね

75点だからと舐めてかかったら思いのほか苦戦……
色々調べてみると、画像に情報を隠す方法にステガノグラフィーというものがあるらしい。
さらに調べると「青い空を見上げればいつもそこに白い猫」というアナライザがあった。
それを使って調べてみる(ビット抽出)と、

~~~
h15_n@m3_i5nt_g3
rard
~~~

おお、なんか出てきた、あと少しか、と思って1時間ほど色々いじっても出てこない……
まさか、と思って先ほどの文字列をよく見てみると、

~~~
h15_n@m3_i5nt_g3rard
~~~

フラグじゃん……

ここで朝5時半、力尽きて就寝



#解けなかった問題たち

##RSAtrix2(Crypto)
sageファイルを実行してGをとってきて復号した行列と照らし合わせてみたが全く合わない……

##American Literature, Math analysis(binex)
番地とかを見て書き換えに行くやつだと思うんだけど知識が足りなかった……

##Storytime:The Tragic Interlude(rev)
ファイルを解析して出力されない部分の文章を見つけたり、原文を発見したりしたもののフラグは未発見。




#感想
初めての大会、とても楽しかったです。個人的にはRainbow Passageが解けただけで大満足。Crypto楽しい。
その反面、知らない分野の知識不足を痛感しました。調べている過程でハリネズミ本なるもの(競プロで言う蟻本みたいなもの?)を発見したので今度書店で探してみようと思います。
また、解けなかった問題等何か進展があれば追記していこうと考えています。