技術めいた何か

社会人になってしまった

SECCON Beginners CTF 2021 Writeup(Crypto: Logical_SEESAW, GFM, Imaginary)

2021/5/22-23にオンラインで開催された ctf4b 2021にチームr0b5stのメンバーとして参加しました。

主にCRYPTO問を担当しました。write upを記録します。

Logical_SEESAW

ソースコードが与えれている。 同じ平文に対して、AND演算でマスクされた16個のデータが与えられる。 16個すべてのORを取るとflagが手に入る。

from Crypto.Util.number import long_to_bytes

cipher = ['11000010111010000100110001000000010001001011010000000110000100000100011010111110000010100110000001101110100110100100100010000110001001101000101010000010101000100000001010100010010010001011110001101010110100000010000010111110000010100010100011010010100010001001111001101010011000000101100', '11000110110010000100110001000000010001001111010010000110110000000110011010101110011010100110000010100110101100000100000000001110001001001000101000001010101001100000001010101010010110001001110001101010110100000110011010010110011000000100100011010000110010001001011001101010011000001101100', '11000010110010000100110001101000010001001111001000000110000100000110011000111110010010100110000000101110101101100000000010010110001001101000101010000010101000100000001000101110000010001001111001101010110100000010011010010110011000100000100011010010100010001001111001101010011000001101100', '11000110110010001100110000101000110001000111000000000110000000000110011010101110011000100110000010100110101101100100100010000100101001001000101010000010101000100000001010100110010010001001110001101010110000000110000010110110000000000000100011010010110010001011011001101010001000000111101', '11000110100010001100110000000000010001000111001010000110110100000110011010111110001010100110100011101110101110100010000000110100001001101000101010000010101001101000001000101000010010001001111001101010110000000010000010111110000000000010000011010010100010001001011001101010011000001111101', '11000010110010001100110001001000010001000011000000100110000000000110011010101110000010100110100011100110101110100010000000101100101001101000101010000010101001101000001010100010000010001011111001101010110100000110001010010110001010100100000011010010110010001011111001101010011000000101100', '11000110110010000100110001101000110001001011010000100110110000000110011000101110010000100110100001100110100110000000100010000110101001001000101010000010101001100000001000101110010010001011111001101010110000000010001010110110001010100110000011010000110010001011111001101010011000000101100', '11000010110010000100110000100000010001000111011000100110100000000110011000111110000010100110000001101110101111100100000010111110001001001000101000001010101001101000001000101010000110001011110001101010110000000110001010011110000010100010100011010010110010000011011001101010001000000111100', '11000010101010000100110001001000010001000011000000100110010000000100011000111110011000100110000001100110100101000010000000011100101001101000101000001010101001101000001010101110010110001001110001101010110000000010010010110110011000000010100011010000100010001011111001101010001000000101100', '11000010101010001100110000100000010001001111001010000110000000000100011010101110011000100110000011100110100111100110100000000110001001001000101010000010101000100000001000101100010010001011110001101010110000000110011010010110011010000000000011010010100010001011011001101010011000001101101', '11000010101010001100110001000000010001001011010010000110010100000100011000111110011000100110000010100110100111000100000000000100101001101000101010001010101000100000001000100000000110001001111001101010110000000110011010010110000010000100100011010000110010000011011001101010001000001101100', '11000110101010001100110001000000110001001111001010000110110000000110011010101110011000100110100001100110101111000100100010011110101001001000101010001010101000101000001000101100000110001011111001101010110100000010011010011110001000000100100011010010100010000001011001101010011000001111100', '11000110100010001100110001000000010001001011011010100110000000000100011000101110001000100110100001101110101101000110100010001100101001001000101010000010101000100000001010101100000010001001111001101010110100000110011010010110010000100110100011010010110010001001111001101010011000001101101', '11000110101010000100110000000000010001001111001010100110100100000100011010111110001000100110100001101110101100000000100000111110001001101000101000001010101001101000001010100110010010001011110001101010110100000110000010010110001010000010100011010010110010001001011001101010001000000101100', '11000010101010000100110000000000110001001011011010100110110000000110011000101110010010100110100000100110101111000010000000100100001001001000101000001010101001100000001000100000000010001011110001101010110000000010011010011110001010000000000011010010100010001001011001101010001000000101101', '11000110101010001100110001000000110001001111011000000110010100000100011000101110001010100110000001101110101110000100100000101110101001101000101000000010101000100000001010101010000010001011110001101010110000000010000010010110001000100100100011010000100010000001011001101010001000001111101']
c = [list(i) for i in cipher]

part_of_c = [int(j) for j in c[0]]
for i in c[1:]:
    tmp = [int(j) for j in i]
    part_of_c = [j|k for j,k in zip(part_of_c, tmp)]

s = [str(i) for i in part_of_c]
b = int("".join(s), 2)
ret = long_to_bytes(b)
print(ret.decode('utf-8'))

ctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}

GFM

ソースコードとMatrixとしてKey, encが与えられている。 encはMatrix M(=flag)とKeyを用いて次の演算で得ている。

enc = Key * M * Key

行列の積が非可換であることに注意して、次の式で Mを得る

M = Key^-1 * enc * Key^-1

この問題を解くときに docker版のsagemath/sagemathhttps://hub.docker.com/r/sagemath/sagemath/ を使いました。

SIZE = 8
p = 331941721759386740446055265418196301559
MS = MatrixSpace(GF(p), SIZE)

key = MS.matrix([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 = MS.matrix([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])

# enc = key*M*key
flag = key^(-1)*enc*key^(-1)
print(flag)

得られた出力をflagにする

"".join(list(map(lambda x: chr(x), [99, 116, 102,  52,  98, 123, 100,  49, 100,  95, 121,  48, 117,  95, 112, 108, 52, 121,  95, 119,  49, 116, 104,  95, 109,  52, 116, 114,  49, 120,  95,  52, 110, 100,  95, 103,  52, 108,  48, 105, 115,  95, 102,  49, 101, 108, 100,  63, 125])))

ctf4b{d1d_y0u_pl4y_w1th_m4tr1x_4nd_g4l0is_f1eld?}

Imaginary

Flagの出力条件

self.numbers = dict() のindexに'1337i'があること。

self.numbers は暗号文を入力することで上書きできる(後述)

与えられている機能

  • 実数と虚数を入力してself.numbersに保存する機能

ただし、int型の実数re, 虚数imのとき、

name = f'{re} + {im}i'
self.numbers[name] = [re, im]

の形式となる。また、入力をint()でキャストしているため、re, imともに空文字は弾かれる

  • 任意の暗号文を入力でき、復号してjson stringであればself.numbersを上書きする機能

  • self.numbers暗号化し、hex形式で暗号文を出力する機能

  • self.numbersのindexに'1337i'があればflagを出力する機能

利用している暗号

AESのECBモード。 ECBモードはブロック単位で見ると、同じ鍵のときにある平文ブロックに対してどのブロックで暗号化しても常に同じ暗号文を出力する。 (リナックスのペンギンの画像をECBモードで暗号化したものが有名)

暗号利用モード - Wikipedia

方針

name = f'{re} + {im}i'
self.numbers[name] = [re, im]

のname部分に'1337i'を入れることができればflagを得ることができる。

具体的には128bitごとのブロックが分割されることを意識しながら、 暗号文の2ブロック目の先頭が 1337i": [re, im]}になるように調整する。

まず、実数に11111111111虚数1337と入力すると

暗号化時に 1ブロック目: Enc('{"11111111111 + ', key) 2ブロック目: Enc('1337i": [1111111', key) 3ブロック目: Enc('1111, 1337]}'+padding, key) となる。

また、一度サーバーとの接続を切ってから再接続し、 実数に1111111虚数0と入力すると 1ブロック目: Enc('{"1111111 + 0i":', key) 2ブロック目: Enc(' [1111111, 0], "', key) 3ブロック目: Enc('1 + 1i": [1, 1]}'+padding, key)

といった暗号文が手に入る。 ECBの性質によって、暗号文のブロックを入れ替えても暗号文として成り立つため、 2回目のクエリの1,2ブロック目と1回目のクエリの2,3ブロックをつなげてflagを通す条件を満たす、 M = {"1111111 + 0i": [1111111, 0], "1337i": [11111111111, 1337]} に対応する暗号文 C = Enc( {"1111111 + 0i": [1111111, 0], "1337i": [11111111111, 1337]}, key) を手に入れる。

最後に、もう一度サーバーから切断した後に再接続し、 手に入れた暗号文を入力すればflagが手に入る。

ctf4b{yeah_you_are_a_member_of_imaginary_number_club}

その他

CRYPTO以外はkawasin73、mopisecが担当してくれたので、CRYPTOに集中して取り組むことができました。 (そして、僕がField_tripやp-8RSAに苦しんでいる間に @mopisec君がreversingを全完してました。すごい。)

mopisec.hatenablog.com

久々に時間をとって取り組みましたが、楽しかったです。 社会人になってしまいましたが、継続していきたいな〜という気持ちです。 Field_tripやp-8RSAは解けなくて、悔しかったのでぼちぼち精進します。