気まぐれブログ(日記・技術記事・研究のことなど)

気まぐれに更新します．温かい目で見ていただければ...

CTF Beginners Contest 2021 参戦記

2021年5月22日〜2021年5月23日に開催されていた CTF Beginners Contest 2021のWrite-upを記載します。 今年は参加チーム数が多く、最終的な参加チーム数は計 1095 チームでした。 所感として、例年よりとっつきやすい問題が多かったです。(私を含む)初心者のために間口を広げてくれたのでしょうか。 私は個人で参加し、結果は 200位/1095チーム でした。個人ながら最終的に上位20%に入れたので、まあまずまずの成績といったところでしょうか。

問題一覧は、こちらから閲覧できます(スコアサーバへの登録が必要かも？)。

crypto

simple_RSA

問題

output.txtとproblem.pyという2つのファイルから、flagを復元せよ。

output.txt

n = 17686671842400393574730512034200128521336919569735972791676605056286778473230718426958508878942631584704817342304959293060507614074800553670579033399679041334863156902030934895197677543142202110781629494451453351396962137377411477899492555830982701449692561594175162623580987453151328408850116454058162370273736356068319648567105512452893736866939200297071602994288258295231751117991408160569998347640357251625243671483903597718500241970108698224998200840245865354411520826506950733058870602392209113565367230443261205476636664049066621093558272244061778795051583920491406620090704660526753969180791952189324046618283
e = 3
c = 213791751530017111508691084168363024686878057337971319880256924185393737150704342725042841488547315925971960389230453332319371876092968032513149023976287158698990251640298360876589330810813199260879441426084508864252450551111064068694725939412142626401778628362399359107132506177231354040057205570428678822068599327926328920350319336256613

problem.py

from Crypto.Util.number import *
from flag import flag

flag = bytes_to_long(flag.encode("utf-8"))

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 3

assert 2046 < n.bit_length()
assert 375 == flag.bit_length()

print("n =", n)
print("e =", e)
print("c =", pow(flag, e, n))

解答

典型的なRSA暗号の問題です。 注目すべきところは、

  • e=3

  • assert 2046 < n.bit_length()

  • assert 375 == flag.bit_length()

の3つです。 flagを mとすると、上記の情報から、 m^{e} が n よりも小さいことが分かります。 つまり、 c = (m^{e} \bmod n) =m^{e}が成立します。 あとは、 m = c^{1/e} = c^{1/3}を計算してやればOKです。

3乗根を求める部分に関して、私は二分探索で解の導出を行いました。以下、解答プログラムです。

from Crypto.Util.number import *

# 3乗根を求めるプログラム (二分探索)
def cubit_root(c):
  low = 0
  high = c

  while True:
    half = (low + high) // 2
    if (half**3 == c):
      return half
    elif (half**3 < c):
      low = half
    else:
      high = half

flag = cubit_root(213791751530017111508691084168363024686878057337971319880256924185393737150704342725042841488547315925971960389230453332319371876092968032513149023976287158698990251640298360876589330810813199260879441426084508864252450551111064068694725939412142626401778628362399359107132506177231354040057205570428678822068599327926328920350319336256613)
print(long_to_bytes(flag))

答え：ctf4b{0,1,10,11...It's_so_annoying.___I'm_done}

Logical_SEESAW

問題

output.txtとproblem.pyから、flagを復元せよ。

output.txt

cipher = ['11000010111010000100110001000000010001001011010000000110000100000100011010111110000010100110000001101110100110100100100010000110001001101000101010000010101000100000001010100010010010001011110001101010110100000010000010111110000010100010100011010010100010001001111001101010011000000101100', '11000110110010000100110001000000010001001111010010000110110000000110011010101110011010100110000010100110101100000100000000001110001001001000101000001010101001100000001010101010010110001001110001101010110100000110011010010110011000000100100011010000110010001001011001101010011000001101100', '11000010110010000100110001101000010001001111001000000110000100000110011000111110010010100110000000101110101101100000000010010110001001101000101010000010101000100000001000101110000010001001111001101010110100000010011010010110011000100000100011010010100010001001111001101010011000001101100', '11000110110010001100110000101000110001000111000000000110000000000110011010101110011000100110000010100110101101100100100010000100101001001000101010000010101000100000001010100110010010001001110001101010110000000110000010110110000000000000100011010010110010001011011001101010001000000111101', '11000110100010001100110000000000010001000111001010000110110100000110011010111110001010100110100011101110101110100010000000110100001001101000101010000010101001101000001000101000010010001001111001101010110000000010000010111110000000000010000011010010100010001001011001101010011000001111101', '11000010110010001100110001001000010001000011000000100110000000000110011010101110000010100110100011100110101110100010000000101100101001101000101010000010101001101000001010100010000010001011111001101010110100000110001010010110001010100100000011010010110010001011111001101010011000000101100', '11000110110010000100110001101000110001001011010000100110110000000110011000101110010000100110100001100110100110000000100010000110101001001000101010000010101001100000001000101110010010001011111001101010110000000010001010110110001010100110000011010000110010001011111001101010011000000101100', '11000010110010000100110000100000010001000111011000100110100000000110011000111110000010100110000001101110101111100100000010111110001001001000101000001010101001101000001000101010000110001011110001101010110000000110001010011110000010100010100011010010110010000011011001101010001000000111100', '11000010101010000100110001001000010001000011000000100110010000000100011000111110011000100110000001100110100101000010000000011100101001101000101000001010101001101000001010101110010110001001110001101010110000000010010010110110011000000010100011010000100010001011111001101010001000000101100', '11000010101010001100110000100000010001001111001010000110000000000100011010101110011000100110000011100110100111100110100000000110001001001000101010000010101000100000001000101100010010001011110001101010110000000110011010010110011010000000000011010010100010001011011001101010011000001101101', '11000010101010001100110001000000010001001011010010000110010100000100011000111110011000100110000010100110100111000100000000000100101001101000101010001010101000100000001000100000000110001001111001101010110000000110011010010110000010000100100011010000110010000011011001101010001000001101100', '11000110101010001100110001000000110001001111001010000110110000000110011010101110011000100110100001100110101111000100100010011110101001001000101010001010101000101000001000101100000110001011111001101010110100000010011010011110001000000100100011010010100010000001011001101010011000001111100', '11000110100010001100110001000000010001001011011010100110000000000100011000101110001000100110100001101110101101000110100010001100101001001000101010000010101000100000001010101100000010001001111001101010110100000110011010010110010000100110100011010010110010001001111001101010011000001101101', '11000110101010000100110000000000010001001111001010100110100100000100011010111110001000100110100001101110101100000000100000111110001001101000101000001010101001101000001010100110010010001011110001101010110100000110000010010110001010000010100011010010110010001001011001101010001000000101100', '11000010101010000100110000000000110001001011011010100110110000000110011000101110010010100110100000100110101111000010000000100100001001001000101000001010101001100000001000100000000010001011110001101010110000000010011010011110001010000000000011010010100010001001011001101010001000000101101', '11000110101010001100110001000000110001001111011000000110010100000100011000101110001010100110000001101110101110000100100000101110101001101000101000000010101000100000001010101010000010001011110001101010110000000010000010010110001000100100100011010000100010000001011001101010001000001111101']

problem.py

from Crypto.Util.number import *
from random import random, getrandbits
from flag import flag

flag = bytes_to_long(flag.encode("utf-8"))
length = flag.bit_length()
key = getrandbits(length)
while not length == key.bit_length():
    key = getrandbits(length)

flag = list(bin(flag)[2:])
key = list(bin(key)[2:])

cipher_L = []

for _ in range(16):
    cipher = flag[:]
    m = 0.5
    
    for i in range(length):
        n = random()
        if n > m:
            cipher[i] = str(eval(cipher[i] + "&" + key[i]))
            
    cipher_L.append("".join(cipher))


print("cipher =", cipher_L)

解答

for文で何をやっているか分かれば、特に難しくない問題です。 for文では、cipher(=flag)のビットをある確率に基づいて0にする試行を16回行っています。 1回の試行につき、1/2の確率で、cipher[i] = str(eval(cipher[i] + "&" + key[i]))が実行され、さらに確率1/2の確率(トータルで1/4の確率)でcipher[i]の値が0になってしまいます。

ですが、当然のことながら、もともとcipher[i]の値が0であれば、ずっとcipher[i]の値は0です。もともとcipher[i]の値が1であれば、たまに値が0になってしまうケースもありますが、3/4の確率でcipher[i]は1のままです。

従って、リストcipher_Lの各要素において、ビット位置iで一回でも1が登場したことがあれば、flag[i] = 1、一回も1が登場しなかったらflag[i] = 0となります。

以下、解答プログラムです。

from Crypto.Util.number import *
cipher = ['11000010111010000100110001000000010001001011010000000110000100000100011010111110000010100110000001101110100110100100100010000110001001101000101010000010101000100000001010100010010010001011110001101010110100000010000010111110000010100010100011010010100010001001111001101010011000000101100', '11000110110010000100110001000000010001001111010010000110110000000110011010101110011010100110000010100110101100000100000000001110001001001000101000001010101001100000001010101010010110001001110001101010110100000110011010010110011000000100100011010000110010001001011001101010011000001101100', '11000010110010000100110001101000010001001111001000000110000100000110011000111110010010100110000000101110101101100000000010010110001001101000101010000010101000100000001000101110000010001001111001101010110100000010011010010110011000100000100011010010100010001001111001101010011000001101100', '11000110110010001100110000101000110001000111000000000110000000000110011010101110011000100110000010100110101101100100100010000100101001001000101010000010101000100000001010100110010010001001110001101010110000000110000010110110000000000000100011010010110010001011011001101010001000000111101', '11000110100010001100110000000000010001000111001010000110110100000110011010111110001010100110100011101110101110100010000000110100001001101000101010000010101001101000001000101000010010001001111001101010110000000010000010111110000000000010000011010010100010001001011001101010011000001111101', '11000010110010001100110001001000010001000011000000100110000000000110011010101110000010100110100011100110101110100010000000101100101001101000101010000010101001101000001010100010000010001011111001101010110100000110001010010110001010100100000011010010110010001011111001101010011000000101100', '11000110110010000100110001101000110001001011010000100110110000000110011000101110010000100110100001100110100110000000100010000110101001001000101010000010101001100000001000101110010010001011111001101010110000000010001010110110001010100110000011010000110010001011111001101010011000000101100', '11000010110010000100110000100000010001000111011000100110100000000110011000111110000010100110000001101110101111100100000010111110001001001000101000001010101001101000001000101010000110001011110001101010110000000110001010011110000010100010100011010010110010000011011001101010001000000111100', '11000010101010000100110001001000010001000011000000100110010000000100011000111110011000100110000001100110100101000010000000011100101001101000101000001010101001101000001010101110010110001001110001101010110000000010010010110110011000000010100011010000100010001011111001101010001000000101100', '11000010101010001100110000100000010001001111001010000110000000000100011010101110011000100110000011100110100111100110100000000110001001001000101010000010101000100000001000101100010010001011110001101010110000000110011010010110011010000000000011010010100010001011011001101010011000001101101', '11000010101010001100110001000000010001001011010010000110010100000100011000111110011000100110000010100110100111000100000000000100101001101000101010001010101000100000001000100000000110001001111001101010110000000110011010010110000010000100100011010000110010000011011001101010001000001101100', '11000110101010001100110001000000110001001111001010000110110000000110011010101110011000100110100001100110101111000100100010011110101001001000101010001010101000101000001000101100000110001011111001101010110100000010011010011110001000000100100011010010100010000001011001101010011000001111100', '11000110100010001100110001000000010001001011011010100110000000000100011000101110001000100110100001101110101101000110100010001100101001001000101010000010101000100000001010101100000010001001111001101010110100000110011010010110010000100110100011010010110010001001111001101010011000001101101', '11000110101010000100110000000000010001001111001010100110100100000100011010111110001000100110100001101110101100000000100000111110001001101000101000001010101001101000001010100110010010001011110001101010110100000110000010010110001010000010100011010010110010001001011001101010001000000101100', '11000010101010000100110000000000110001001011011010100110110000000110011000101110010010100110100000100110101111000010000000100100001001001000101000001010101001100000001000100000000010001011110001101010110000000010011010011110001010000000000011010010100010001001011001101010001000000101101', '11000110101010001100110001000000110001001111011000000110010100000100011000101110001010100110000001101110101110000100100000101110101001101000101000000010101000100000001010101010000010001011110001101010110000000010000010010110001000100100100011010000100010000001011001101010001000001111101']

print("len(cipher) = {0}".format(len(cipher)))
counter_list = [0]*287
for item in cipher:
  for index, c in enumerate(item):
    counter_list[index] += int(c)

print(counter_list)

ans = ""
for i in counter_list:
  if (i > 0):
    ans += "1"
  else:
    ans += "0"

print(long_to_bytes(int(ans, 2)))

答え：ctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}

GFM

問題

output.txtとproblem.sageから、flagを復元せよ。

output.txt

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]

problem.sage

FLAG = b'<censored>'

SIZE = 8
p = random_prime(2^128)
MS = MatrixSpace(GF(p), SIZE)
print(MS)

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

M = copy(MS.zero())
for i in range(SIZE):
    for j in range(SIZE):
        n = i * SIZE + j
        if n < len(FLAG):
            M[i, j] = FLAG[n]
        else:
            print(i, j, SIZE, len(FLAG))
            M[i, j] = GF(p).random_element()

enc = key * M * key
inv_key = key.inverse()


print('p:', p)
print('key:', key)
print('enc:', enc)

解答

sageという見かけないファイルが出てきました。 調べると、

Sage は，代数学，幾何学，数論，暗号理論，数値解析，および関連諸分野の研究と教育を支援する，フリーなオープンソース数学ソフトウェアである (https://doc.sagemath.org/pdf/ja/tutorial/tutorial-jp.pdf)

と出てきました。 プログラムを見てみると、どうやら行列の計算をしてるっぽいですね。 とりあえず、Mを復元するために、見よう見まねでsageプログラムを書いてみました。

SIZE = 8
p = 331941721759386740446055265418196301559

key = matrix(GF(p),
  [[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 = matrix(GF(p),
  [[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]]
)

inv_key = key.inverse()
M = inv_key * enc * inv_key
print(M)

すると、

[                                     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 299874036478097449921680569674270449076  78313956149379326243971992208332842951 327226201592994132731095913667371497964 313102235287242360753049665908275948842  67049960660712250081503091849025260343 248290952297957062940275450722399860860 269291320227258725106609060732491009052]
# [220658601671619686519292673663329962459 301252534665220612936717033315754638138 195965589989033004660898442625447000198 160757164035005766598705084730459536481 112986659451024798658573623593539960466  29597742012660940046364385563937276149 217053364052085783101705935012612334241 148296482483328225203414489314538575852]

答えっぽいもの(asciiの十進値)が出てきたので、復元してみます。以下の解答プログラムで、flagを復元できました。

ans_list = [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]

for c in ans_list:
  print(chr(c), end="")

答え：ctf4b{d1d_y0u_pl4y_w1th_m4tr1x_4nd_g4l0is_f1eld?}

Web

osoba

問題

美味しいお蕎麦を食べたいですね。フラグはサーバの /flag にあります！ https://osoba.quals.beginners.seccon.jp/

サーバ側のプログラム https://beginners-dist-production.s3.isk01.sakurastorage.jp/osoba/osoba.tar.gz

解答

サーバ側のflaskプログラムを見てみます。

from flask import Flask, request, send_file, make_response

app = Flask(__name__)

@app.route("/", methods=["GET", "POST"])
def index():
    page = request.args.get('page', 'public/index.html')
    response = make_response(send_file(page))
    response.content_type = "text/html"
    return response

if __name__ == '__main__':
    app.run(host="0.0.0.0", port=8080)

注目すべきところは、page = request.args.get('page', 'public/index.html')です。 pageクエリパラメータに、ファイルパスを通してやれば、その値が変数pageに格納され、該当ファイルが返されます。

また、サーバ側のディレクトリ構造は以下の通りです。

.
├── app
│   ├── Dockerfile
│   ├── flag  // 対象のflagファイル
│   └── src
│       ├── app.py
│       ├── public
│       │   ├── index.html
│       │   ├── kikin.html
│       │   ├── neck.html
│       │   └── wip.html
│       ├── requirements.txt
│       └── uwsgi.ini
├── docker-compose.yml
└── nginx
    └── nginx.conf

対象のflagファイルは、../flagに存在しているので、https://osoba.quals.beginners.seccon.jp/?page=../flagでアクセスしてやれば、フラグが返ってきます。

f:id:tomonori4565:20210523154054p:plain

答え：ctf4b{omisoshiru_oishi_keredomo_tsukuruno_taihen}

Werewolf

問題

I wish I could play as a werewolf...

https://werewolf.quals.beginners.seccon.jp/

サーバ側プログラム https://beginners-dist-production.s3.isk01.sakurastorage.jp/werewolf/app.py

解答

サーバ側プログラムを見てみます。

import os
import random
from flask import Flask, render_template, request, session

# ====================

app = Flask(__name__)
app.FLAG = os.getenv("CTF4B_FLAG")

# ====================

class Player:
    def __init__(self):
        self.name = None
        self.color = None
        self.__role = random.choice(['VILLAGER', 'FORTUNE_TELLER', 'PSYCHIC', 'KNIGHT', 'MADMAN'])
        # :-)
        # self.__role = random.choice(['VILLAGER', 'FORTUNE_TELLER', 'PSYCHIC', 'KNIGHT', 'MADMAN', 'WEREWOLF'])

    @property
    def role(self):
        return self.__role

    # :-)
    # @role.setter
    # def role(self, role):
    #     self.__role = role


# ====================

@app.route("/", methods=["GET", "POST"])
def index():
    if request.method == 'GET':
        return render_template('index.html')

    if request.method == 'POST':
        player = Player()

        for k, v in request.form.items():
            player.__dict__[k] = v

        return render_template('result.html',
            name=player.name,
            color=player.color,
            role=player.role,
            flag=app.FLAG if player.role == 'WEREWOLF' else ''
        )

# ====================

if __name__ == '__main__':
    app.run(host=os.getenv("CTF4B_HOST"), port=os.getenv("CTF4B_PORT"))

注目すべきところは、flag=app.FLAG if player.role == 'WEREWOLF' else ''です。 どうやら、player.roleに WEREWOLFという文字を仕込めたらOKらしいです。 player.roleに値を代入する作業は、以下のコードで行われています。

 for k, v in request.form.items():
            player.__dict__[k] = v

よって、form-dataに、_Player_role = WEREWOLFを仕込んでリクエストを送信します。するとフラグを抽出できます。

f:id:tomonori4565:20210523154645p:plain

答え：ctf4b{there_are_so_many_hackers_among_us}

check_url

問題

Have you ever used curl ? https://check-url.quals.beginners.seccon.jp/

サーバ側プログラム https://beginners-dist-production.s3.isk01.sakurastorage.jp/check_url/index.php

解答

サーバ側プログラムを見てみます。

<!-- HTML Template -->
          <?php
            error_reporting(0);
            if ($_SERVER["REMOTE_ADDR"] === "127.0.0.1"){
              echo "Hi, Admin or SSSSRFer<br>";
              echo "********************FLAG********************";
            }else{
              echo "Here, take this<br>";
              $url = $_GET["url"];
              if ($url !== "https://www.example.com"){
                $url = preg_replace("/[^a-zA-Z0-9\/:]+/u", "👻", $url); //Super sanitizing
              }
              if(stripos($url,"localhost") !== false || stripos($url,"apache") !== false){
                die("do not hack me!");
              }
              echo "URL: ".$url."<br>";
              $ch = curl_init();
              curl_setopt($ch, CURLOPT_URL, $url);
              curl_setopt($ch, CURLOPT_CONNECTTIMEOUT_MS, 2000);
              curl_setopt($ch, CURLOPT_PROTOCOLS, CURLPROTO_HTTP | CURLPROTO_HTTPS);
              echo "<iframe srcdoc='";
              curl_exec($ch);
              echo "' width='750' height='500'></iframe>";
              curl_close($ch);
            }
          ?>
<!-- HTML Template -->

どうやら、サーバからサーバにアクセス($_SERVER["REMOTE_ADDR"] === "127.0.0.1")させることができれば、フラグをゲットできるみたいです。 ただプログラムを見てみると、.が👻に変換させられたり、ループバックアドレスlocalhostを入力できなくされています。つまり、単純にurlクエリパラメータとして、127.0.0.1やlocalhostを入力しても、$_SERVER["REMOTE_ADDR"] === "127.0.0.1"とはなりません。

そこで私は、ループバックアドレスを違う形で表せないかと考えました。調べてたら、以下の記事が出てきました。

qiita.com

どうやら、0x7F000001でlocalhostにアクセスできるみたい。これなら、ピリオドも含まれていないし、localhostやapacheというワードも含まれていないので、うまく通りそう。 実際に、https://check-url.quals.beginners.seccon.jp/?url=https://0x7F000001 と入力してみると、フラグが出てきました。

f:id:tomonori4565:20210523155333p:plain

答え：ctf4b{5555rf_15_53rv3r_51d3_5up3r_54n171z3d_r3qu357_f0r63ry}

misc

git-leak

問題

後輩が誤って機密情報をコミットしてしまったらしいです。ひとまずコミットを上書きして消したからこれで大丈夫ですよね？

https://beginners-dist-production.s3.isk01.sakurastorage.jp/git-leak/git-leak.zip

解答

git reflogして、flag.txtが含まれているコミットまで遡って終わり。

$ git cat-file -p 4cbb035d2ff072127b4e22919485127d2273e88e

答え：ctf4b{0verwr1te_1s_n0t_c0mplete_1n_G1t}

mail_adress_validator

問題

あなたのメールアドレスが正しいか調べます．

nc mail-address-validator.quals.beginners.seccon.jp 5100

プログラム https://beginners-dist-production.s3.isk01.sakurastorage.jp/Mail_Address_Validator/main.rb

解答

プログラムを見てみます。

#!/usr/bin/env ruby
require 'timeout'

$stdout.sync = true
$stdin.sync = true

pattern = /\A([\w+\-].?)+@[a-z\d\-]+(\.[a-z]+)*\.[a-z]+\z/i

begin
  Timeout.timeout(60) {
    Process.wait Process.fork {
      puts "I check your mail address."
      puts "please puts your mail address."
      input = gets.chomp
      begin
        Timeout.timeout(5) {
          if input =~ pattern
            puts "Valid mail address!"
          else
            puts "Invalid mail address!"
          end
        }
      rescue Timeout::Error
        exit(status=14)
      end
    }
    print(Process.last_status.to_i)
    case Process.last_status.to_i >> 8
    when 0 then
      puts "bye."
    when 1 then
      puts "bye."
    when 14 then
      File.open("flag.txt", "r") do |f|
        puts f.read
      end
    else
      puts "What's happen?"
    end
  } 
rescue Timeout::Error
  puts "bye."
end

ここでポイントなのは、以下の部分です。

   ... 

      begin
        Timeout.timeout(5) {
          if input =~ pattern
            puts "Valid mail address!"
          else
            puts "Invalid mail address!"
          end
        }
      rescue Timeout::Error
        exit(status=14)
      end

   ... 


   when 14 then
      File.open("flag.txt", "r") do |f|
        puts f.read
      end
    else

   ...

入力したメールアドレスがパターンマッチしているかどうかの判定に、5秒以上要せば、status=14でexitされます。 exitされると、フラグを抽出できます。

では、どうやって判定を5秒以上にすることができるのでしょう。 これは知識ゲーなのですが、ReDoS攻撃を知っていれば簡単に解法が思いつきます。

ReDoS攻撃については、以下の記事を参照してください。 qiita.com

よってメールアドレスとして、AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA@等を入力してみると、以下のフラグをゲットできます。

答え：ctf4b{1t_15_n0t_0nly_th3_W3b_th4t_15_4ff3ct3d_by_ReDoS}