去年の分を書き忘れましたが今年はちゃんと書きます。 2021年5月22日から23日にかけて開催された SECCON Beginners CTF 2021 でCrypto問題を2問出題しました。 残りの問題についてはうしがぃさんのWriteupを見てください。

今年の頭に募集したSECCON Beginnersの新メンバーと開催する最初のイベントにもかかわらず、新メンバーの皆さんの活躍が凄まじく2問しか作るスペースがありませんでした。 今後も安泰ですね。

[Easy] GFM (222 pt, 97 solves)

SageMathで書かれたスクリプトとその出力を元にフラグを計算する問題です。 スクリプトでは行列$key$とフラグが含まれる行列$M$から$$enc=key * M * key$$を計算します。 そしてスクリプトの出力結果として法$p$と行列$key,enc$が与えられています。 ここから$M$を取り出すことができればそこに含まれているフラグも復元できます。

$key$が逆行列を持てば$enc$の両側から掛けることによって$M$を計算できそうです。 スクリプトをよく見ると、$key$は逆行列を持つようにランクが次数と一致するまで計算しなおしています。

 8
 9
10

key = MS.random_element()
while key.rank() != SIZE:
    key = MS.random_element()

したがって、$key$は正則行列であり逆行列を持ちます。 後は逆行列を計算して掛け算をするだけです。

さて計算といきたいところですが、ここで登場した行列にはすべて法が付いています。 法が付いていてもやることは同じなので多分掃き出し法とかで解ける1と思いますが、ここではSageMathを使って手抜きで解くことをお勧めします。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

p = 331941721759386740446055265418196301559
key = [[116401981595413622233973439379928029316,198484395131713718904460590157431383741,210254590341158275155666088591861364763, 63363928577909853981431532626692827712, 85569529885869484584091358025414174710,149985744539791485007500878301645174953,257210132141810272397357205004383952828,184416684170101286497942970370929735721],
[42252147300048722312776731465252376713,199389697784043521236349156255232274966,310381139154247583447362894923363190365,275829263070032604189578502497555966953,292320824376999192958281274988868304895,324921185626193898653263976562484937554, 22686717162639254526255826052697393472,214359781769812072321753087702746129144],
[211396100900282889480535670184972456058,210886344415694355400093466459574370742,186128182857385981551625460291114850318, 13624871690241067814493032554025486106,255739890982289281987567847525614569368,134368979399364142708704178059411420318,277933069920652939075272826105665044075, 61427573037868265485473537350981407215],
[282725280056297471271813862105110111601,183133899330619127259299349651040866360,275965964963191627114681536924910494932,290264213613308908413657414549659883232,140491946080825343356483570739103790896,115945320124815235263392576250349309769,240154953119196334314982419578825033800, 33183533431462037262108359622963646719],
[53797381941014407784987148858765520206,136359308345749561387923094784792612816, 26225195574024986849888325702082920826,262047729451988373970843409716956598743,170482654414447157611638420335396499834,270894666257247100850080625998081047879, 91361079178051929124422796293638533509, 34320536938591553179352522156012709152],
[266361407811039627958670918210300057324, 40603082064365173791090924799619398850,253357188908081828561984991424432114534,322939245175391203579369607678957356656, 63315415224740483660852444003806482951,224451355249970249493628425010262408466, 80574507596932581147177946123110074284,135660472191299636620089835364724566497],
[147031054061160640084051220440591645233,286143152686211719101923153591621514114,330366815640573974797084150543488528130,144943808947651161283902116225593922999,205798118501774672701619077143286382731,317326656225121941341827388220018201533, 14319175936916841467976601008623679266,112709661623759566156255015500851204670],
[306746575224464214911885995766809188593, 35156534122767743923667417474200538878, 35608800809152761271316580867239668942,259728427797578488375863755690441758142, 29823482469997458858051644485250558639,137507773879704381525141121774823729991, 29893063272339035080311541822496817623,292327683738678589950939775184752636265]]

enc = [[133156758362160693874249080602263044484,293052519705504374237314478781574255411, 72149359944851514746901936133544542235, 56884023532130350649269153560305458687, 67693140194970657150958369664873936730,227562364727203645742246559359263307899, 98490363636066788474326997841084979092,323336812987530088571937131837711189774], 
[244725074927901230757605861090949184139, 63515536426726760809658259528128105864,297175420762447340692787685976316634653,279269959863745528135624660183844601533,203893759503830977666718848163034645395,163047775389856094351865609811169485260,103694284536703795013187648629904551283,322381436721457334707426033205713602738],
[17450567396702585206498315474651164931,105594468721844292976534833206893170749, 10757192948155933023940228740097574294,132150825033376621961227714966632294973,329990437240515073537637876706291805678, 57236499879418458740541896196911064438,265417446675313880790999752931267955356, 73326674854571685938542290353559382428],
[270340230065315856318168332917483593198,217815152309418487303753027816544751231, 55738850736330060752843300854983855505,236064119692146789532532278818003671413,104963107909414684818161043267471013832,234439803801976616706759524848279829319,173296466130000392237506831379251781235, 34841816336429947760241770816424911200],
[140341979141710030301381984850572416509,248997512418753861458272855046627447638, 58382380514192982462591686716543036965,188097853050327328682574670122723990784,125356457137904871005571726686232857387, 55692122688357412528950240580072267902, 21322427002782861702906398261504812439, 97855599554699774346719832323235463339],
[298368319184145017709393597751160602769,311011298046021018241748692366798498529,165888963658945943429480232453040964455,240099237723525827201004876223575456211,306939673050020405511805882694537774846,7035607106089764511604627683661079229,198278981512146990284619915272219052007,255750707476361671578970680702422436637],
[45315424384273600868106606292238082349, 22526147579041711876519945055798051695, 15778025992115319312591851693766890019,318446611756066795522259881812628512448,269954638404267367913546070681612869355,205423708248276366495211174184786418791, 92563824983279921050396256326760929563,209843107530597179583072730783030298674],
[662653811932836620608984350667151180,304181885849319274230319044357612000272,280045476178732891877948766225904840517,216340293591880460916317821948025035163, 79726526647684009633247003110463447210, 36010610538790393011235704307570914178,284067290617158853279270464803256026349, 45816877317461535723616457939953776625]]

GFp = GF(p)
keyM = Matrix(GFp, key)
encM = Matrix(GFp, enc)

inv = keyM.inverse()
flagM = inv * encM * inv
flag = []
size = 8
for i in range(size):
    for j in range(size):
        val = flagM[i, j]
        if val < 0x100:
            flag.append(val)
print(bytes(flag).decode())

% sage solve.sage
ctf4b{d1d_y0u_pl4y_w1th_m4tr1x_4nd_g4l0is_f1eld?}

フラグでは書く順番を間違えましたがGFMはGalois Field and Matrixの略でした。 SageMathを使ったことがあるか、使ったことがなくても時間内にドキュメントを読んでなんとなく問題を解ける程度まで習熟できるかがポイントの問題でした。

[Medium] Imaginary (264 pt, 75 solves)

ガワの部分が比較的上手にできたのでお気に入りの問題です。 netcat等を使って問題文で指定された接続先に繋ぐと、次のような対話型アプリケーションが待ち受けています。

% nc imaginary.quals.beginners.seccon.jp 1337
Welcome to Secret IMAGINARY NUMBER Store!
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 1
Real part> 1
Imaginary part> 3 
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 2
--------------------------------------------------
1 + 3i: (1, 3)
--------------------------------------------------
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 4
{"1 + 3i": [1, 3]}
Exported:
7027c56621e70bf48884a06348d68a1af36e1309837f85a8ef0b81de1e9a6bb2

1〜4の4種類のコマンドがあり、複素数を保存したり暗号化してエクスポート/インポートできます。 軽くコマンドを触った程度ではフラグの場所がわからないので配布されているソースコードも読みましょう。

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

    def handle(self):
        try:
            self.request.sendall(b'Welcome to Secret IMAGINARY NUMBER Store!\n')
            self.numbers = {}

            while True:
                num = self._menu()
                if num == 1:
                    self._save()
                elif num == 2:
                    self._show()
                elif num == 3:
                    self._import()
                elif num == 4:
                    self._export()
                elif num == 5:
                    self._secret()
                else:
                    break

        except Exception as e:
            try:
                self.request.sendall(f'ERR: {e}\n'.encode())
            except Exception:
                pass

メインの処理を見ると1〜4以外にも5のsecretコマンドがあるようです。 内容を読むと、1337i という複素数が保存されているときに呼び出すとフラグを出力してくれるコマンドであることがわかります。

87
88
89
90

    def _secret(self):
        if '1337i' in self.numbers:
            self.request.sendall(b'Congratulations!\n')
            self.request.sendall(f'The flag is {flag}\n'.encode())

ということで$1337i$になりそうな値を作ってsecretコマンドを呼び出してみますが、残念ながらフラグは表示されません。 なぜなら複素数を保存する辞書のキーは実数部が$0$の場合に特別な処理をするわけではなく、0 + 1337iとして保存してしまうからです。

% nc imaginary.quals.beginners.seccon.jp 1337

Welcome to Secret IMAGINARY NUMBER Store!
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 1
Real part> 0
Imaginary part> 1337
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 2
--------------------------------------------------
0 + 1337i: (0, 1337)
--------------------------------------------------
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 5
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
>

それではどうするかというと、まだ使っていないインポート/エクスポートの機能に注目します。

このIMAGINARY NUMBER Storeでは接続ごとに複素数がリセットされてしまいますが、インポート/エクスポート機能のおかげで過去の状態を復元できます。 このときの出力はJSON形式で、さらにAESのECBモードを使って暗号化されています。

ECBモードといえば入力と出力が完全に対応してしまうため、ブロックを使い回せることで知られています。 つまり、エクスポートした暗号文をうまく繋ぎ変えてインポートしたときに 1337i が出現するようなデータを作れそうなことがわかります。 あとは1ブロックが16バイトであることを考慮しつついい感じに欲しいブロックをかき集めます。 エクスポート時にはどんなJSONが暗号化されているかも教えてくれるので楽勝ですね。

まずはうまく長さを調整して

  • [a, b], " で終わるブロック
  • 1337i": [a, b] で始まるブロック

の2つを準備します。 この2つのブロックを繋げると ...[a, b], "1337i": [a, b]...という平文を持つ暗号文が完成します。

これらのブロックの作り方は無数にあるので試行錯誤することになりますが、以下の様な2つのJSON出力の暗号文があれば1337iを作るには十分です。

{"23456789123 + 1337i": [23456789123, 1337]}
4690bcdd9077065bf5f52712003dd51060d56314d465f7bf6dd0279e1b95f951f46e71373d85fcc3bf4c2b07aa496b19

{"23456789123 + 1337i": [23456789123, 1337], "0 + 0i": [0, 0], "1 + 1i": [1, 1]}
4690bcdd9077065bf5f52712003dd51060d56314d465f7bf6dd0279e1b95f9511416d2af204cbdd814a9fc126b4889742e348d960da74ebe98c2f8096ad24380450ebe4d6d0ea85378c0212781ca5cdd8db4341b6d2b363abdc9d13de3042f42

これを1ブロック単位で区切るとこうなります。

|0123456789ABCDEF|
|================|
|{"23456789123 + |
|1337i": [2345678| (1)
|9123, 1337]}_PAD| (2)
|----------------|
|{"23456789123 + | (3)
|1337i": [2345678| (4)
|9123, 1337], "0 | (5)
|+ 0i": [0, 0], "| (6)
|1 + 1i": [1, 1]}|
|_____PADDING____|

そして、これらのブロックを組み替えて1337iを作ります。

|0123456789ABCDEF|
|================|
|{"23456789123 + | (3)
|1337i": [2345678| (4)
|9123, 1337], "0 | (5)
|+ 0i": [0, 0], "| (6)
|1337i": [2345678| (1)
|9123, 1337]}_PAD| (2)

JSONとして正しく組み替えられたので、あとはこれに対応する暗号文ブロックを並べ替えるだけです。

4690bcdd9077065bf5f52712003dd51060d56314d465f7bf6dd0279e1b95f9511416d2af204cbdd814a9fc126b4889742e348d960da74ebe98c2f8096ad2438060d56314d465f7bf6dd0279e1b95f951f46e71373d85fcc3bf4c2b07aa496b19

それではサーバにインポートしてsecretコマンドを叩いてみましょう。

% nc imaginary.quals.beginners.seccon.jp 1337
Welcome to Secret IMAGINARY NUMBER Store!
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 3
Exported String> 4690bcdd9077065bf5f52712003dd51060d56314d465f7bf6dd0279e1b95f9511416d2af204cbdd814a9fc126b4889742e348d960da74ebe98c2f8096ad2438060d56314d465f7bf6dd0279e1b95f951f46e71373d85fcc3bf4c2b07aa496b19
Imported.
--------------------------------------------------
23456789123 + 1337i: (23456789123, 1337)
0 + 0i: (0, 0)
1337i: (23456789123, 1337)
--------------------------------------------------
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 5
Congratulations!
The flag is ctf4b{yeah_you_are_a_member_of_imaginary_number_club}

無事フラグが手に入りました。 ECBモードの特性は比較的よく知られていると思いますが、実際に攻撃に応用するときの手順はきちんと考察をする必要がありますよという問題です。

まとめ

GFMは見てわかるのでそれをどう実現するか、Imaginaryは実験で挙動を確かめるというところをポイントで作問しました。 作問以外の担当としてCryptoの難易度評価もやってたんですが、異なる条件を持つ問題（Field_tripとp-8RSA）の評価に失敗したらしいです。 作問者が問題の難易度を想定するのは非常に難しく、CTFを開催するときには毎回苦労しています。

今年のCrypto問題はいろんな分野にバランスよく出題が分布しているのでぜひ復習してみてください。

  1. AtCoderとかにありそう ↩︎