チームTambourineKissでBeginners CTF 2019に参加してきました。
デビュー戦にしては大きな一歩です！(笑)
自分は、Party, Sliding puzzle, Seccompareの3問と
終了後にContainersを解きました。
Party
暗号化のコードと、暗号結果が与えられる。
encrypt.py
from Crypto.Util.number import bytes_to_long, getRandomInteger, getPrime, long_to_bytes
def f(x, coeff):
y = 0
for i in range(len(coeff)):
y += coeff[i] * pow(x, i)
return y
N = 512
M = 3
secret = bytes_to_long(FLAG)
assert(secret < 2**N)
coeff = [secret] + [getRandomInteger(N) for i in range(M-1)]
party = [getRandomInteger(N) for i in range(M)]
val = map(lambda x: f(x, coeff), party)
output = list(zip(party, val))
print(output)
encrypted
[
(5100090496682565208825623434336918311864447624450952089752237720911276820495717484390023008022927770468262348522176083674815520433075299744011857887705787, 222638290427721156440609599834544835128160823091076225790070665084076715023297095195684276322931921148857141465170916344422315100980924624012693522150607074944043048564215929798729234427365374901697953272928546220688006218875942373216634654077464666167179276898397564097622636986101121187280281132230947805911792158826522348799847505076755936308255744454313483999276893076685632006604872057110505842966189961880510223366337320981324768295629831215770023881406933),
(3084167692493508694370768656017593556897608397019882419874114526720613431299295063010916541874875224502547262257703456540809557381959085686435851695644473, 81417930808196073362113286771400172654343924897160732604367319504584434535742174505598230276807701733034198071146409460616109362911964089058325415946974601249986915787912876210507003930105868259455525880086344632637548921395439909280293255987594999511137797363950241518786018566983048842381134109258365351677883243296407495683472736151029476826049882308535335861496696382332499282956993259186298172080816198388461095039401628146034873832017491510944472269823075),
(6308915880693983347537927034524726131444757600419531883747894372607630008404089949147423643207810234587371577335307857430456574490695233644960831655305379, 340685435384242111115333109687836854530859658515630412783515558593040637299676541210584027783029893125205091269452871160681117842281189602329407745329377925190556698633612278160369887385384944667644544397208574141409261779557109115742154052888418348808295172970976981851274238712282570481976858098814974211286989340942877781878912310809143844879640698027153722820609760752132963102408740130995110184113587954553302086618746425020532522148193032252721003579780125)
]
FLAGという文字列をlong型整数に変換し、多項式計算した結果を出力している。
コードを読むとつまりはこうなっている。
secret + c_1 \times p_0 + c_2 \times p_0^2 = v0 \\
secret + c_1 \times p_1 + c_2 \times p_1^2 = v1 \\
secret + c_1 \times p_2 + c_2 \times p_2^2 = v2 \\
encryptedには[(p0, v0), (p1, v1), (p2, v2)]が与えられているので、連立方程式を解いてsecretを求める。
import sympy
s = sympy.Symbol('s')
c1 = sympy.Symbol('c1')
c2 = sympy.Symbol('c2')
expr1 = s + c1 * p0 + c2 * p0**2 - v0
expr2 = s + c1 * p1 + c2 * p1**2 - v1
expr3 = s + c1 * p2 + c2 * p2**2 - v2
print(sympy.solve([expr1, expr2, expr3]))
secret = 175721217420600153444809007773872697631803507409137493048703574941320093728 となり、これをlong_to_bytes(secret, N)でFLAGに戻す。
long_to_bytes(secret, N)
>>> b'\x00\x00\x00 ... \x00\x00ctf4b{just_d0ing_sh4mir}'
ctf4b{just_d0ing_sh4mir}
Sliding puzzle
ncコマンドでサーバーから送られてくる8パズルの問題を解いて、答えを送信する。
----------------
| 06 | 03 | 02 |
| 01 | 05 | 08 |
| 07 | 04 | 00 |
----------------
3秒くらい経つと遮断される。
8パズルをpythonで解くコードがあったので、それを拝借。
8 Puzzle (GitHub) - 8パズル - summer_tree_home
8-puzzle_solver.py
from collections import deque
MOVE = {'0': (0, -1), '2': (0, 1), '3': (-1, 0), '1': (1, 0)}
def get_next(numbers):
for d in '0231':
zero_index = numbers.index(0)
tx, ty = zero_index % 3 + MOVE[d][0], zero_index // 3 + MOVE[d][1]
if 0 <= tx < 3 and 0 <= ty < 3:
target_index = ty * 3 + tx
result = list(numbers)
result[zero_index], result[target_index] = numbers[target_index], 0
yield d, tuple(result)
def checkio(puzzle):
queue = deque([(tuple(n for line in puzzle for n in line), '')])
seen = set()
while queue:
numbers, route = queue.popleft()
seen.add(numbers)
if numbers == (0, 1, 2, 3, 4, 5, 6, 7, 8):
return route
for direction, new_numbers in get_next(numbers):
if new_numbers not in seen:
queue.append((new_numbers, route + direction + ','))
あとはpythonでNetcat通信をする。
Pythonによる通信処理
solver.py
import socket
import numpy as np
host = "XXX.XXX.XXX.XXX"
port = xxxx
client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
client.connect((host, port))
while True:
response = client.recv(4096)
print(response)
p = response.decode('utf-8').replace(' ','').split('|')
puzzle = p[1:4] + p[5:8] + p[9:12]
puzzle = np.array(list(map(int, puzzle))).reshape(3, 3)
print(puzzle)
ans = checkio(puzzle.reshape(3,3)).rstrip(',').encode('utf-8')
print(ans)
client.send(ans)
ctf4b{fe6f512c15daf77a2f93b6a5771af2f723422c72}
Seccompare
seccompareという実行ファイルが与えらる。
$ file seccompare
seccompare: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/l, for GNU/Linux 3.2.0, BuildID[sha1]=4a607c82ea263205071c80295afe633412cda6f7, not stripped
とりあえずのstringsでも特に何も無い。
Ubuntu環境で実行してみたら、文字列を引数としてflagとして正しいか否かを出力するというものだった。
ファイルの中身を確認してみる。
$ hexdump -C seccompare
...
00000620 00 e8 ba fe ff ff b8 01 00 00 00 e9 b1 00 00 00 |................|
00000630 c6 45 d0 63 c6 45 d1 74 c6 45 d2 66 c6 45 d3 34 |.E.c.E.t.E.f.E.4|
00000640 c6 45 d4 62 c6 45 d5 7b c6 45 d6 35 c6 45 d7 74 |.E.b.E.{.E.5.E.t|
00000650 c6 45 d8 72 c6 45 d9 31 c6 45 da 6e c6 45 db 67 |.E.r.E.1.E.n.E.g|
00000660 c6 45 dc 73 c6 45 dd 5f c6 45 de 31 c6 45 df 73 |.E.s.E._.E.1.E.s|
00000670 c6 45 e0 5f c6 45 e1 6e c6 45 e2 30 c6 45 e3 74 |.E._.E.n.E.0.E.t|
00000680 c6 45 e4 5f c6 45 e5 65 c6 45 e6 6e c6 45 e7 30 |.E._.E.e.E.n.E.0|
00000690 c6 45 e8 75 c6 45 e9 67 c6 45 ea 68 c6 45 eb 7d |.E.u.E.g.E.h.E.}|
000006a0 c6 45 ec 00 48 8b 45 c0 48 83 c0 08 48 8b 10 48 |.E..H.E.H...H..H|
...
おったw
テキストエディタなどで.E.などを除去して、
ctf4b{5tr1ngs_1s_n0t_en0ugh}
Containers
containersというバイナリファイルが与えられる。
binwalkかforemostコマンドで中身のデータを抽出できるようだが、アホなのでforemostコマンドしたoutputファイルが生成されたことに気づかず、binwalkでゴリ押した。
foremostだと一発じゃ〜ん何だよ〜言ってくれよ
stringsすると、最後の方に怪しげなpythonコードがある。
VALIDATOR.import hashlib
print('Valid flag.' if hashlib.sha1(input('Please your flag:').encode('utf-8')).hexdigest()=='3c90b7f38d3c200d8e6312fbea35668bec61d282' else 'wrong.'.ENDCONTAINER
binwalkするとPNGがたくさんあることがわかる。
$ binwalk -e containers
DECIMAL HEXADECIMAL DESCRIPTION
--------------------------------------------------------------------------------
16 0x10 PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
107 0x6B Zlib compressed data, compressed
738 0x2E2 PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
829 0x33D Zlib compressed data, compressed
1334 0x536 PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
...
抽出されたものは、115D、115D.zlibなどがたくさんあった。
115Dがヘッダーが無い画像の値のみのファイルだという推測の元、画像として無理やり開いた。
list = ['115D', '147F', '1731', '1A9D', '1EA8', '20ED', '2476', '28AA', '2B7D', '2FB1', '3264', '33D', '3670', '395B', '3D0A', '4093', '43FC', '4785', '4B0E', '4E31', '51E0', '5549', '581C', '591', '5BCB', '5E10', '6145', '64F4', '68FF', '6B', '6C2A', '6FB3', '71F8', '74CB', '78D7', '7B7F', '7D5', 'B83', 'EAD']
for name in list:
f = open(name, mode='rb')
topo = np.fromfile(f, dtype='uint8',sep='')[:65536].reshape(128,128,4)
plt.imshow(topo[:,:,:4])
plt.show()
無理やり開いた画像
(正しい画像はこう)
順番がめちゃくちゃだったので、先ほどのstringsで出てきたハッシュ値が一致するように順列で総当りする。
普通じゃ終わらない長さだけど、運が良いのでできた。
import itertools
text = 'e52df60c058746a66e4ac4f34dbc6f81'
for element in itertools.permutations(text, len(text)):
if hashlib.sha1(('ctf4b{'+''.join(element)+'}').encode('utf-8')).hexdigest()=='3c90b7f38d3c200d8e6312fbea35668bec61d282':
print('ctf4b{'+''.join(element)+'}')
ctf4b{e52df60c058746a66e4ac4f34db6fc81}
以上です。
Biginners向けとしてはちょっとかなりだいぶ難しかったですね。お疲れ様でした。