DownUnderCTF 2024 脆弱Writeup
結果
DownUnderCTF 2024をチーム「脆弱エンジニア(full_weak_engineer)」で参加してきました。
60位/1515チームでした!👏
むっずー!と言いながらずっと解いていました。
解けた問題
自分は5問解くことができました。面白かった2問の解法を書いておきます。
DNAdecay (misc, 143pt, 148 Solves)✅
DNAが欠損したかのようなソースコードが与えられている。
require "doublehelix"
AT
A--T
T- -A
G----C
G----
--C
T---A
G--C
AT
GC
T--
G- -
T----A
A--- T
T ---A
G---C
C--G
AT
CG
-T
A---T
G---
A -- T
G----C
G C
--C
C
C
T--A
A-- T
A-- T
G- --C
A----T
G---C
G--C
GC
CG
G--C
A---
G----C
T- --A
C----G
T---
G--C
A
GC
T--A
A- T
----T
C----G
-- -T
G---C
T--A
AT
A
A -T
---A
T - -A
G----C
G----C
G---C
T--A
AT
C
G- C
C --G
C-- -G
G----C
-- -T
G - C
T--A
G
AT
--T
T---
----T
T-- -A
----
C---G
G--C
AT
C
A -
C
T----A
T----A
A----
G -C
C- G
T
C
G- C
--
G----
C- --G
G- -
C-- G
A--T
G
GC
G--C
C---G
C-- -G
G--- C
A---
G- -C
T--A
A
TA
T--A
--
----
G-- -C
A- --T
T- -
A--T
GC
GC
T- A
A---T
T-- -A
T----A
----
G-- C
T--A
GC
A
A-
A --T
C----G
C----
G----C
G---C
G -C
CG
GC
T--A
T---
G----C
G-- -C
A---
A--
G--
GC
AT
A--T
T---
A -- T
T----A
G ---
T --A
G--C
C
GC
A- T
G---C
C ---G
--- T
- - A
G---C
--A
A
G
G--C
A --T
C- --G
A ---T
----C
T -
T -
CG
C
G -C
G---C
G - C
G ---
---
---T
- A
G
C
G-
A --T
G----C
T ---A
T--- A
G --C
G-
TA
A
C--G
G---
C----
G----C
C----G
G---C
T- A
TA
G--C
A---T
-- -C
----T
G----
G---
A--T
AT
GC
- A
T---
G- --C
G ---C
T- --A
A-- T
A--T
C
TA
A- T
T- -
A----T
A----T
T----A
A --T
G--C
A
TA
A -T
---
G- --C
T----A
T ---A
- -C
C--
T
CG
A- T
https://github.com/mame/doublehelix というRubyの難読化ライブラリがあり、これの通り動くように復元しようとした。
しかし、---
のように(A,T)のペアなのか(C,G)のペアなのかわからない部分が存在する。
ライブラリにある仕組みに基づいて、バイナリで読むことにした。
行頭はputs
で始まることに注意すると、バイナリを逆順にして解釈していることがわかる。
dict = { "AT"=>"00", "CG"=>"01", "GC"=>"10", "TA"=>"11" }
これに基づいて、余分な-
とスペースを取り除いて、以下のように変換。
with open('dna.rb') as f:
file = f.read()
table = {"AT":"00", "CG":"01", "GC":"10", "TA":"11", "SS":"??"}
dna = file.split('\n')
for i in range(len(dna)//4):
s = ''
s += table[dna[4*i]]
s += table[dna[4*i+1]]
s += table[dna[4*i+2]]
s += table[dna[4*i+3]]
s_reversed = ''.join(list(reversed(s)))
try:
print(chr(int(s_reversed, 2)), end='')
except:
print('?', end='')
puts"DUCTF{7H3_Mit0?HOn?Ri4?15?7he_P0wEr_HoU?E_of?DA_C3L?}"
?の部分は、bitの組み合わせでが4通りあるので、その中から当てはまりそうな文字を選ぶ。
DUCTF{7H3_Mit0cHOndRi4_15_7he_P0wEr_HoUsE_of_DA_C3LL}
V for Vieta (Crypto, 228pt, 55 Solves)✅
ncatで接続して入出力をするタイプの問題。
巨大な平方数k(4096bitくらい)が与えられ、kと以下等しくなるようなaとbを送信する。
ただし、aとbは2048bitよりも大きい必要がある。
送信すると次のkが与えられてこれを繰り返すが、kは20bitくらいまで小さくなるが、aとbは2048bitよりも大きいという条件は変わらない。
#!/usr/bin/env python3
import os
import random
import json
from enum import Enum
FLAG = os.getenv("FLAG", "DUCTF{dummy_flag}")
class State(Enum):
INITIAL = 1
TEST = 2
QUIT = 3
class Server:
def __init__(self):
self.level = 2048
self.target = 2048
self.finish = 8
self.state = State.INITIAL
def win(self):
return {
"flag": FLAG,
}
def generate_k(self):
self.k = random.getrandbits(self.level) ** 2
self.state = State.TEST
return {
"k": self.k,
"level": self.level,
}
def test(self, challenge):
a, b = challenge["a"], challenge["b"]
if a <= 0 or b <= 0:
self.state = State.QUIT
return {"error": "Your answer must be positive!"}
if a.bit_length() <= self.target or b.bit_length() <= self.target:
self.state = State.QUIT
return {"error": "Your answer is too small!"}
num = a**2 + a * b + b**2
denom = 2 * a * b + 1
if num % denom != 0 or num // denom != self.k:
self.state = State.QUIT
return {"error": "Your answer wasn't a solution!"}
self.level -= self.level // 5
if self.level <= self.finish:
self.state = State.QUIT
return self.win()
else:
return self.generate_k()
def main():
server = Server()
print("V equals negative V plus or minus the squareroot of V squared minus 4 V V all divided by 2 V!")
while True:
if server.state == State.INITIAL:
print(json.dumps(server.generate_k()))
elif server.state == State.TEST:
challenge = json.loads(input())
print(json.dumps(server.test(challenge)))
elif server.state == State.QUIT:
exit(0)
if __name__ == "__main__":
main()
スプシでaとbそれぞれ1〜100までの値で、平方数を取るかを確認したところ、以下の値があった。
a | b | k |
---|---|---|
2 | 14 | 4 |
14 | 96 | 4 |
3 | 51 | 9 |
51 | 864 | 9 |
kの二乗根をmとすると、aがmであるときに解が存在すると仮説を立てられる。
また、bをaとすることで、別の解を求めることができそうなことがわかった。
あとは、与えられたkに対して、kの二乗根とaとbを計算して、2048bitを超えるまで計算を繰り返した値を送信することで、最後までたどり着くことができた。
import json
import math
from pwn import *
address = '2024.ductf.dev'
port = 30018
io = remote(address, port)
start = io.recvline()
print(start)
while True:
json_data = io.recvline()
data = json.loads(json_data)
if "k" not in data:
print(data)
io.interactive()
k = int(data["k"])
m = math.isqrt(k)
a = 0
b = m
while a.bit_length() <= 2048:
a = b
b = (a*(2*k-1) + math.isqrt(4*a**2*k**2-4*a**2*k-3*a**2+4*k))//2
ans = {
"a": b,
"b": a
}
json_ans = json.dumps(ans).encode('utf-8')
io.sendline(json_ans)
{'flag': 'DUCTF{jump1n6_4nd_fl1pp1n6_up_7h3_hyp3r8011c_14dd3r}'}
解きたかった問題
decrypt then eval (crypto, 118pt, 197 Solves)
AESでの復号結果をevalするという問題。byteの1文字をブルートフォースして数字が出力される挙動までを確認できたものの、そこから手が出ず。
KEY = os.urandom(16)
IV = os.urandom(16)
FLAG = os.getenv('FLAG', 'DUCTF{testflag}')
def main():
while True:
ct = bytes.fromhex(input('ct: '))
aes = AES.new(KEY, AES.MODE_CFB, IV, segment_size=128)
try:
print(eval(aes.decrypt(ct)))
except Exception:
print('invalid ct!')
公式Writeup:
my array generator (crypto, 220pt, 60 Solves)
暗号の内容まできっちり理解したものの、無理じゃんってなった。
公式WriteupはSMTソルバで解いている。どういうこと?要復習。
class MyArrayGenerator:
def __init__(self, key: bytes, n_registers: int = 128):
self.key = key
self.n_registers = n_registers
def prepare(self):
self.registers = [0 for _ in range(self.n_registers)]
self.key_extension(self.key)
self.carry = self.registers.pop()
self.key_initialisation(F)
def key_extension(self, key: bytes):
if len(key) != KEY_SIZE:
raise ValueError(f"Key length should be {KEY_SIZE} bytes.")
for i in range(len(self.registers)):
j = (4 * i) % KEY_SIZE
subkey = key[j : j + 4]
self.registers[i] = int.from_bytes(subkey)
def key_initialisation(self, F: int):
for _ in range(F):
self.update()
def shift(self):
self.registers = self.registers[1:]
def update(self):
r0, r1, r2, r3 = self.registers[:4]
self.carry ^= r1 if r2 > r3 else (r1 ^ 0xFFFFFFFF)
self.shift()
self.registers.append(self.registers[-1] ^ self.carry)
def get_keystream(self) -> int:
byte_index = random.randint(0, 3)
byte_mask = 0xFF << (8 * byte_index)
return (self.registers[-1] & byte_mask) >> (8 * byte_index)
def encrypt(self, plaintext: bytes) -> bytes:
self.prepare()
ct = b""
for b in plaintext:
self.update()
ct += int.to_bytes(self.get_keystream() ^ b)
return ct
def decrypt(self, ciphertext: bytes) -> bytes:
return self.encrypt(ciphertext)
公式Writeup:
おわりに
チーム「脆弱エンジニア(full_weak_engineer)」では、SECCON CTF決勝進出を目指してCTFに参加しています!
チームでCTFをやりたいメンバーを常に募集していますので、YouTubeの概要欄にあるDiscordリンクから、気軽にご参加ください!
Pwn, Rev担当大歓迎(切実)
Discussion