DownUnderCTF 2024 脆弱Writeup

2024/07/07に公開

結果

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よりも大きい必要がある。

\frac{a^2+ab+b^2}{2ab+1}

送信すると次の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とすることで、別の解を求めることができそうなことがわかった。

b = \frac{a(2m^2 - 1)}{2} + \frac{\sqrt{4a^2m^4 - 4a^2m^2 - 3a^2 + 4m^2}}{2}

あとは、与えられた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:
https://github.com/DownUnderCTF/Challenges_2024_Public/tree/main/crypto/decrypt-then-eval

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:
https://github.com/DownUnderCTF/Challenges_2024_Public/tree/main/crypto/my-array-generator

おわりに

チーム「脆弱エンジニア(full_weak_engineer)」では、SECCON CTF決勝進出を目指してCTFに参加しています!

チームでCTFをやりたいメンバーを常に募集していますので、YouTubeの概要欄にあるDiscordリンクから、気軽にご参加ください!

https://www.youtube.com/@full-weak-engineer


Pwn, Rev担当大歓迎(切実)

Discussion