nkhrlab CTF 2019 Summerに1人チームで参加し、
開始から6時間46分で100点(全完)を取って2位でした。 (Scoreboard上の44チーム中)
1点問題
Welcome
問題文に答えがそのまま書かれていた。
n5b2019summer{welcome}
4点問題
Frustrating
ダウンロードできるファイルを開いてみると、
先頭にdata:image/gif;base64,という文字が見えた。
そこで、残りの部分をbase64デコードすることで、GIF画像が得られた。
得られた画像を見ると横長の画像に1文字だけが書かれているようだったので、
GIFアニメーションの可能性があると考え、Giamで開いた。
すると、1コマに1文字ずつflagが書かれているようだったので、手動で読み取った。
n5b2019summer{Are_you_patient?}
Pip Count
ダウンロードできるファイルは拡張子が.rbであり、先頭の部分は
# frozen_string_literal: true
pos = []
eg = <<~POSITION
Calculate pip count.
X:bottom player O:top player
e.g.:
+13-14-15-16-17-18------19-20-21-22-23-24-+
| X O | | O X |
| X O | | O X |
| X O | | O |
| X | | O |
| X | | O |
| |BAR| |
| O | | |
| O | | X |
| O | | X |
| O X | | X X O |
| O X | | X X O |
+12-11-10--9--8--7-------6--5--4--3--2--1-+
X's pip count: 163
O's pip count: 167
POSITION
のようであった。意味がわからないのでまずは「pip count」でググると、
Backgammon Glossary/Pip Count
などから、コマの位置によって決まる数をコマの数だけ足せばよさそうだった。
適当に実装したところ、X's pip countのみが一致した。
そこで、O:top playerという記述をもとにOの数の判定を調整した結果、
O's pip countも一致した。
さらに、BARの部分についてはこのサイトにもサンプルにもなかったが、
Pip-count scoring | Backgammon | BoardGameGeek
ルールとマナー | 日本バックギャモン協会
に基づき、BARの部分のコマについては25を足せば良さそうだった。
ここまでの実装が以下である。
これにダウンロードできるファイルを食わせることで、pip countとやらを計算してくれる。
#!/usr/bin/perl
use strict;
use warnings;
my $skip = @ARGV > 0 ? int($ARGV[0]) : 0;
my @query = ();
my $reading = 0;
my @positions = (4, 7, 10, 13, 16, 19, 27, 30, 33, 36, 39, 42);
while (my $line = <STDIN>) {
chomp($line);
if ($reading) {
if ($line =~ /\+12-11-10/) {
# solve
my $circle = 0;
my $cross = 0;
for (my $i = 0; $i < @positions; $i++) {
# botton -> top
for (my $j = @query - 1; $j >= 0; $j--) {
my $c = substr($query[$j], $positions[$i], 1);
if ($c eq "O") {
$circle += 13 + $i;
} elsif ($c eq "X") {
$cross += 12 - $i;
} else {
last;
}
}
# top -> bottom
for (my $j = 0; $j < @query; $j++) {
my $c = substr($query[$j], $positions[$i], 1);
if ($c eq "O") {
$circle += 12 - $i;
} elsif ($c eq "X") {
$cross += 13 + $i;
} else {
last;
}
}
}
# bar
for (my $j = 0; $j < @query; $j++) {
my $c = substr($query[$j], 23, 1);
if ($c eq "O") {
$circle += 25;
} elsif ($c eq "X") {
$cross += 25;
}
}
if ($skip > 0) {
$skip--;
} else {
print "$cross\n";
print "$circle\n";
}
# reset
@query = ();
$reading = 0;
} else {
push(@query, $line);
}
} else {
if ($line =~ /\+13-14-15/) {
$reading = 1;
}
}
}
次に、得られたpip countからflagを得る作業であるが、
ダウンロードできるファイルをそのままrubyで実行しようとすると
pip_count.rb:5: syntax error, unexpected <<
eg = <<~POSITION
^
pip_count.rb:7: syntax error, unexpected tIDENTIFIER, expecting end-of-input
X:bottom player O:top player
^
というエラーになってしまった。
そこで、ファイルの内容に基づき、以下のflagを得るプログラムを実装した。
#!/usr/bin/perl
use strict;
use warnings;
my $flag = "";
while (my $line = <STDIN>) {
chomp($line);
$flag .= sprintf("%03d", int($line));
}
printf "flag: n5b2019summer{%s}\n", $flag;
これらのプログラムを用いて、
solve.pl 1 < pip_count.rb | construct.pl
を実行することで、
n5b2019summer{157157072061157067210051138159052054082084089056078078297297}
が得られた。
Sakura
MIDIファイルがダウンロードできた。
Dominoで開いて観察していると、A6 Shakuhachiに音符でflagが描かれていた。
n5b2019summer{someiyoshino}
9点問題
Nasty Regexp
regular expressionが与えられ、これにマッチする文字列を求めろとのことだった。
与えられたregular expressionには、(?=...{11}[hurt])のようなまとまりが多く含まれていた。
正規表現：否定先読み、肯定先読みについて | WWWクリエイターズ
によれば、これは入力文字列を消費せずにマッチするようである。
そこで、まとまりごとに分解して繰り返しを展開し、並べ替え、
さらにあてはまる文字列を考えていくと、以下のようになった。
ただし、\1などは直前の(～)~の内容があてはまると仮定し、
同じ位置に対する入る文字の候補の集合が複数ある場所は、積集合をとった。
また、あてはまる文字列は、一番下の部分よりアルファベット小文字19文字である。
^n5b2019summer\{ ??ky?k?nd??kih?b?r? (あてはまる文字列)
(?=.(..).\1) .XX.XX
(?=..(.).{8}\2) ..X........X
(?=.{6}(.)..\3\3...\3.\3.\3) ......X..XX...X.X.X
(?=[tomb]) [tomb]
(?=...[yarn]) ...[yarn]
(?=.{3}[yield]) ...[yield]
(?=.{7}[inch]) .......[inch]
(?=.{7}[knot]) .......[knot]
(?=..{7}[deed]) ........[deed]
(?=.{8}[and]) ........[and]
(?=.{10}.[luck]) ...........[luck]
(?=.{11}[kidney]) ...........[kidney]
(?=.{12}[inference]) ............[inference]
(?=.{12}[aim]) ............[aim]
(?=.{13}[while]) .............[while]
(?=...{11}[hurt]) .............[hurt]
(?=..{14}[bill]) ...............[bill]
(?=.{15}[butcher]) ...............[butcher]
(?=..{16}[player]) .................[player]
(?=.{17}[robust]) .................[robust]
[a-z]{19}
\}$
それでも決まりきらない場所があったので、とりあえず適当な文字を入れてみたところ、通った。
n5b2019summer{takyakxndxxkihxbxrx}
Numeral System V
ダウンロードできるファイルを見ると、base64エンコードされている感じだった。
base64デコードすると、またbase64エンコードされている感じのデータが出てきた。
それをbase64デコードすると、またまたbase64エンコードされている感じのデータが出てきた。
さらにそれをbase64デコードすると、LaTeXのソースコードっぽいデータが出てきた。
そこで、それをplatexとdvipdfmxで処理し、PDFに変換した。
読んでみると、「記数法V」における十進数の442413.392の表現を求めろとのことであった。
「記数法V」では、1桁上がると係数が5倍になり、各桁の数は十進数の-17, -1, 0, 1, 17相当の5種類がある。
まず、z3を用いて十進数の整数を「記数法V」に変換する以下のプログラムを実装した。
import z3
import sys
dchars = {-17: "R", -1: "T", 0: "0", 1: "1", 17: "K"}
answer = [z3.Int("n%d" % i) for i in range(30)]
target = -85
if len(sys.argv) > 1:
target = int(sys.argv[1])
solver = z3.Solver()
for d in answer:
solver.add(z3.Or(d == -17, d == -1, d == 0, d == 1, d == 17))
#solver.add((d == 17) or (d == 1) or (d == 0) or (d == -1) or (d == -17))
t = 0
for d in answer:
t = t * 5 + d
solver.add(t == target)
if solver.check() == z3.sat:
model = solver.model()
a = ""
for d in answer:
a += dchars[int(str(model[d]))]
print(a.lstrip("0"))
else:
print("failed")
小数を扱うのは面倒そうだったので、
442413.392に5の10乗をかけた4320443281250をこのプログラムで「記数法V」に変換すると、
T1KKTR10KRK0K0T0000000となった。
ここから小数点を右端から左に10個動かした結果、答えは
n5b2019summer{T1KKTR10KRK0.K0T}
となった。
Dominoes
PNG画像がダウンロードできた。
この画像をペイントで適当に塗りつぶすと、
「S」「T」「E」「P」「I」「C」の文字が浮かび上がった。
また、画像の左上の部分が不自然に塗りつぶされず残った。
そこで、「STEPIC」で検索した結果、
Stepic - Python image steganography
がヒットした。
online utilityはリンク切れのようだったので、stepic-0.3.tar.gzをダウンロードした。
中身のうち、stepic.pyは実行しても表面上何も起こらないようであった。
stepicが本体のようであったが、python stepicを実行すると、
File "stepic", line 76
except (TypeError, ValueError), e:
^
SyntaxError: invalid syntax
というエラーになった。
また、Python2.7を用いてstepicを実行すると、
Traceback (most recent call last):
File "stepic", line 24, in <module>
import Image
ImportError: No module named Image
というエラーになった。
そこで、virtualenvをPython2.7を用いる設定で有効化し、pip install Imageを実行した。
それでもstepicはそのままでは正常に動作しなかったが、
import Imageという行をimport PIL.Image as Imageと書き換えると、動作するようになった。
これを用いて最初の画像をデコードすることで、
n5b2019summer{1 set of double-6 domino consists of 28 tiles.}
が得られた。
Spiral
PNG画像がダウンロードでき、見るとPietのソースコードっぽく思えた。
そこで、Pietのプログラムをオンラインで実行できる
BertNase's Own - npiet fun!
で実行すると、
n5b2019summer{355/113}error: configured execution steps exceeded (1000000 steps)
と表示された。
前半部分の
n5b2019summer{355/113}
が求めるflagであった。
Translation
ダウンロードできるファイルはアーカイブであり、
解凍するとPerlのプログラムと、その出力が書かれていると考えられるテキストファイルが得られた。
Perlのプログラムは、$bの文字列をシャッフル？した後、
flagに対し$aの文字を$bの文字に変換する操作をして出力するようであった。
実験の結果、このシャッフル？操作は結果的にローテート1回で表せるようだったので、
flagの形式と出力結果の関係から、$aのnと$bのYを合わせ、逆の変換を行った。
その結果、
n5b2019summer{Not to be confused with PEARL.}
が得られた。
14点問題
Triple Loop
ダウンロードできるファイルは、Rubyのプログラムのようであり、
大きい整数mについて、b[i]と掛けてmで割ったあまりがa[i]になる数を全探索しているようであった。
巨大数向け素数判定機 - instant tools
でミラー・ラビンテストを行った結果、mは素数のようであったので、
これをm - 2乗してmで割る操作を利用して置き換え、
ついでに他の部分も書き換えた以下のプログラムを実行した。
m = 20988936657440586486151264256610222593863921
a = [20854741892953721313579450578412110250365764, 18680817802620471097741715254727912433116119, 6940806529732886823501244513145497481453282, 2867691954961114213525714459161687907853756, 10506096932732460220933844464593096212832743, 11886301775769248494192465948774166438103820, 2955671471753993505641921656109974899004833, 18084017212135061768267590190883837116164755, 11264519305196511475439088629965085272566740, 14049594801150429470609017143454509976379563, 18045652255248609272797904352185309464325008, 17711746433382383096172306706277744059338596, 14834902197252867253135308889105249615528571, 2503878433416501615362384643227733325324072, 1825492463781365862219509586566930627833200, 6414147930749259186828922841995265025000286]
b = [20242533674995851388916550430817556652144761, 17502538788421563805183983632909482554489617, 14714724621880848278824948105836909582454155, 2929312900047153647136570698883829315985771, 4405008558519366806515601459788067615615261, 8051064219618408760093004809019202742553617, 19578165392705183456962494940175485132198066, 12238084565719475487769270687337650796226881, 2868638886907752565136030100487748461345666, 9105297368066925852217457326033345342394204, 8325951035061220383896370020680742024804181, 3245885587266947438166457744621520112234683, 18794457538552281406756982277185699641297747, 18312358470491859373832076755398557441004683, 12774749986137971716348099918363467658216854, 16094280680927402640211997426473155462541614]
c = [862, 685, 688, 1796, 1269, 284, 758, 22, 767, 34, 1716, 740, 1620, 269, 517, 367]
for i in range(16):
for t in range(c[i]):
a[i] = (a[i] * pow(b[i], m - 2, m)) % m
answer = "n5b2019summer{"
for d in a:
answer += "%c" % (d % 256)
answer += "}"
print(answer)
その結果、
n5b2019summer{Pierre_de_Fermat}
が得られた。
Iterated Function
ダウンロードできるファイルは、センター試験形式の数学の問題であった。
大学受験の頃を思い出…さず、z3などでゴリ押すことにした。
n個の未知数の値はn個の式を連立させると求まることを利用し、
(1)～(4)の答えは以下のプログラムで求まった。
import z3
import sys
class Cmpl():
def __init__(self, a, b = 0):
self.a = a
self.b = b
def add(self, other):
return Cmpl(self.a + other.a, self.b + other.b)
def sub(self, other):
return Cmpl(self.a - other.a, self.b - other.b)
def mul(self, other):
return Cmpl(self.a * other.a - self.b * other.b, self.a * other.b + self.b * other.a)
def kyoyaku(self):
return Cmpl(self.a, -self.b)
def div(self, other):
t = self.mul(other.kyoyaku())
m = other.a * other.a - other.b * other.b
return Cmpl(t.a / m, t.b / m)
def str(self):
return "%g + %gi" % (self.a, self.b)
def z3Cmpl(name):
return Cmpl(z3.Int(name + "a"), z3.Int(name + "b"))
def f(z):
return Cmpl(3, 2).mul(z).add(Cmpl(2, 5).mul(z.kyoyaku()))
print("f(1) = " + f(Cmpl(1, 0)).str())
print("f(i) = " + f(Cmpl(0, 1)).str())
solver = z3.Solver()
e = z3.Int("e")
z = Cmpl(e, 1)
kaz = z3.Int("kaz")
fz = f(z).mul(z.kyoyaku())
solver.add(fz.a == kaz)
solver.add(fz.b == 0)
o = z3.Int("o")
z2 = Cmpl(3, -o)
kikuz = z3.Int("kikuz")
fz2 = f(z2).mul(z2.kyoyaku())
solver.add(fz2.a == kikuz)
solver.add(fz2.b == 0)
if solver.check() == z3.sat:
model = solver.model()
print("e = " + str(model[e]))
print("o = " + str(model[o]))
evalue = int(str(model[e]))
ovalue = int(str(model[o]))
print("ka = " + str(int(str(model[kaz])) / (evalue * evalue + 1 * 1)))
print("kiku = " + str(int(str(model[kikuz])) / (3 * 3 + ovalue * ovalue)))
else:
printf("failed")
sys.exit(1)
g1 = Cmpl(evalue, 1).sub(Cmpl(0, 1).mul(Cmpl(3, -ovalue)))
g2 = Cmpl(evalue, 1).add(Cmpl(0, 1).mul(Cmpl(3, -ovalue)))
print("g1 = " + g1.str())
print("g2 = " + g2.str())
def g(z):
return g1.mul(z).add(g2.mul(z.kyoyaku()))
gz = z3Cmpl("gz")
ggz = g(gz)
se = z3.Int("se")
sota = z3.Int("sota")
ti = z3.Int("ti")
tute = z3.Int("tute")
solver.add(sota != 0)
solver.add(tute != 0)
def gig(z):
gz = g(z)
return Cmpl(tute, 0).mul(Cmpl(se, -1)).mul(gz).add(Cmpl(sota, 0).mul(Cmpl(ti, 1)).mul(gz.kyoyaku()))
def addc(a, b):
gigres = gig(Cmpl(a, b))
solver.add(gigres.a == a * sota * tute, gigres.b == b * sota * tute)
addc(1, 1)
addc(1, 2)
addc(2, 1)
addc(3, 4)
if solver.check() == z3.sat:
model = solver.model()
print("se = " + str(model[se]))
print("sota = " + str(model[sota]))
print("ti = " + str(model[ti]))
print("tute = " + str(model[tute]))
sevalue = int(str(model[se]))
sotavalue = int(str(model[sota]))
tivalue = int(str(model[ti]))
tutevalue = int(str(model[tute]))
else:
print("failed")
sys.exit(1)
to = z3.Int("to")
na = z3.Int("na")
def ginv(z):
return Cmpl(tutevalue, 0).mul(Cmpl(sevalue, -1)).mul(z).add(Cmpl(sotavalue, 0).mul(Cmpl(tivalue, 1)).mul(z.kyoyaku()))
def tona(z):
return Cmpl(to, 0).mul(z).add(Cmpl(na, 0).mul(z.kyoyaku()))
def addc2(a, b):
z = Cmpl(a, b)
left = ginv(f(g(z)))
right = tona(z)
solver.add(left.a == right.a * sotavalue * tutevalue)
solver.add(left.b == right.b * sotavalue * tutevalue)
addc2(1, 2)
addc2(3, 4)
if solver.check() == z3.sat:
model = solver.model()
print("to = " + str(model[to]))
print("na = " + str(model[na]))
else:
print("failed")
sys.exit(1)
(5)については、まず一旦手動で考察した。
f(z) = (3+2i)z+(2+5i)z* (z*はzの複素共役)なので、
fn(z) = az + bz*と表せるとき、
f(fn(z)) = f(az + bz*)
= f(az) + f(bz*)
= (3+2i)az+(2+5i)a*z* + (3+2i)bz*+(2+5i)b*z
= ((3a+2b*)+(2a+5b*)i)z + ((2a*+3b)+(5a*+2b)i)z*
となる。さらに、a = A + Bi, b = C + Di (A, B, C, Dは実数)とおくと、
(3a+2b*)+(2a+5b*)i = 3A + 3Bi + 2C - 2Di + 2Ai - 2B + 5Ci + 5D
= (3A - 2B + 2C + 5D) + (2A + 3B + 5C - 2D)i
(2a*+3b)+(5a*+2b)i = 2A - 2Bi + 3C + 3Di + 5Ai + 5B + 2Ci - 2D
= (2A + 5B + 3C - 2D) + (5A - 2B + 2C + 3D)i
となる。これを用い、以下のプログラムで(5)の答えを得た。
import z3
# f^n(z) = (A[n] + B[n]i)z + (C[n] + D[n]i)z*
A = [1]
B = [0]
C = [0]
D = [0]
for i in range(1, 12):
A.append(3*A[i-1] - 2*B[i-1] + 2*C[i-1] + 5*D[i-1])
B.append(2*A[i-1] + 3*B[i-1] + 5*C[i-1] - 2*D[i-1])
C.append(2*A[i-1] + 5*B[i-1] + 3*C[i-1] - 2*D[i-1])
D.append(5*A[i-1] - 2*B[i-1] + 2*C[i-1] + 3*D[i-1])
v = {}
vnames = ["ni", "nu", "ne", "no", "ha", "hi", "fu", "he", "ho", "ma", "mi", "mu"]
for vname in vnames:
v[vname] = z3.Int(vname)
solver = z3.Solver()
for vname in vnames:
solver.add(0 <= v[vname], v[vname] <= 9)
solver.add(v["ne"] != 0)
solver.add(v["hi"] != 0)
solver.add(v["ho"] != 0)
solver.add(v["mu"] != 0)
# n = 0
solver.add(v["ne"] == 2)
for n in range(1, 12):
solver.add((v["ni"] ** n) + ((-v["nu"]) ** n) == A[n] * v["ne"])
solver.add((v["no"] ** n) - ((-v["ha"]) ** n) == B[n] * v["hi"])
solver.add((v["fu"] ** n) - ((-v["he"]) ** n) == C[n] * v["ho"])
solver.add((v["ma"] ** n) - ((-v["mi"]) ** n) == D[n] * v["mu"])
if solver.check() == z3.sat:
model = solver.model()
for vname in vnames:
print("%s = %s" % (vname, str(model[v[vname]])))
else:
print("failed")
答えはア～ムにあてはまる文字(数字または-)を連結したもので、
n5b2019summer{573178-2-628432021035822825825822}
となった。
Slow Query
ダウンロードできるファイルは、PostgreSQL database dumpであった。
その中で重要そうな部分は、整数から文字列を作る関数と考えられる部分
CREATE FUNCTION public.conv(n integer) RETURNS text
LANGUAGE sql
AS $$
SELECT CHR(97 + n / 26 / 26 % 26) || CHR(97 + n / 26 % 26) || CHR(97 + n % 26)
$$;
具体的なflagの条件と考えられる部分
SELECT
'n5b2019summer{' || CONV(a.n) || CONV(b.n) || CONV(c.n) || CONV(d.n) || CONV(e.n) || 'e}'
FROM
t AS a, t AS b, t AS c, t AS d, t AS e
WHERE
(a.n - b.n - 6593)::BIGINT * (a.n - b.n - 6593) +
(c.n - b.n - 9806)::BIGINT * (c.n - b.n - 9806) +
(d.n - c.n - 2143)::BIGINT * (d.n - c.n - 2143) +
(a.n - e.n - 8094)::BIGINT * (a.n - e.n - 8094) +
(a.n - b.n - 6593)::BIGINT * (c.n - b.n - 9806) +
(a.n - b.n - 6593)::BIGINT * (d.n - c.n - 2143) +
(a.n - b.n - 6593)::BIGINT * (a.n - e.n - 8094) +
(c.n - b.n - 9806)::BIGINT * (d.n - c.n - 2143) +
(c.n - b.n - 9806)::BIGINT * (a.n - e.n - 8094) +
(d.n - c.n - 2143)::BIGINT * (a.n - e.n - 8094) = 0
そして、a.n、b.n、c.n、d.n、e.nにあてはまる数値の候補と考えられる
約6600個の数値リストであった。
まずｈこの条件式にいい性質がありそうであったので、
(a.n - b.n - 6593) -> A
(c.n - b.n - 9806) -> B
(d.n - c.n - 2143) -> C
(a.n - e.n - 8094) -> D
とおいて変形すると、
A * A +
B * B +
C * C +
D * D +
A * B +
A * C +
A * D +
B * C +
B * D +
C * D = 0
となった。ここにはA～Dの掛け算すべての組み合わせが含まれているため、両辺を2倍して
(A + B + C + D) * (A + B + C + D) + A*A + B*B + C*C + D*D = 0
と変形できる。
さらに、A + B + C + DをEとおくと、
(a.n + a.n + d.n - b.n - b.n - e.n - 26636) -> E
となり、A*A + B*B + C*C + D*D + E*E = 0と表せる。
さらに、実数の2乗は0以上なので、A, B, C, D, E全てが0といえる。
すなわち、.nを省略すると、
a - b = 6593
c - b = 9806
d - c = 2143
a - e = 8094
a+a+d - b-b-e = 26636
といえる。
これをもとに、以下のプログラムで数値リストを入力してz3でa, b, c, d, eにあてはまる数を求めた。
import z3
import sys
candidates = []
while True:
l = sys.stdin.readline()
if l == "":
break
candidates.append(int(l))
a = z3.Int("a")
b = z3.Int("b")
c = z3.Int("c")
d = z3.Int("d")
e = z3.Int("e")
solver = z3.Solver()
for v in [a, b, c, d, e]:
condition = False
for n in candidates:
condition = z3.Or(condition, v == n)
solver.add(condition)
solver.add(a - b == 6593)
solver.add(c - b == 9806)
solver.add(d - c == 2143)
solver.add(a - e == 8094)
solver.add(a+a+d - b-b-e == 26636)
if solver.check() == z3.sat:
model = solver.model()
print("a = %s" % str(model[a]))
print("b = %s" % str(model[b]))
print("c = %s" % str(model[c]))
print("d = %s" % str(model[d]))
print("e = %s" % str(model[e]))
else:
print("failed")
その結果は
a = 8131
b = 1538
c = 11344
d = 13487
e = 37
であった。
この結果を用い、以下のプログラムでflagを求めた。
#!/usr/bin/perl
use strict;
use warnings;
sub conv {
my ($n) = @_;
return sprintf("%c%c%c", 97 + int($n / 26 / 26) % 26, 97 + int($n / 26) % 26, 97 + $n % 26);
}
my $a = 8131;
my $b = 1538;
my $c = 11344;
my $d = 13487;
my $e = 37;
printf "n5b2019summer{%s%s%s%s%se}\n", &conv($a), &conv($b), &conv($c), &conv($d), &conv($e);
その結果、
n5b2019summer{matchequitytable}
が得られた。