waniCTF 2024 Writeup

2024/06/21(~48h)に行われた大阪大学のCTFサークル主催のCTF大会にチームで出場しました。(Team Name: FCS_Zundamons, User Name: HydrangeA)(順位: 206/1503)

1週間前に出場したSECCON beginnerに続き今年度2回目のCTFでした. 今回も主にreversingを解くつもりで挑みましたが、結果としては解けそうになかったため、cryptoメインで回答を進めていきました. 私はWeb1問、Crypto3問を解答しました. その解答の軌跡を残せればと思います.

何かの参考になれば幸いです。

解答した問題

• (Web Beginner) Bad_Worker
• (Crypto Easy) replacement
• (Crypto Easy) Easy calc
• (Crypto Normal) dance

環境

• Windows 11 Home 22H2
• WSL2 Ubuntu 22.04

(Web Beginner) Bad_Worker

オフラインで動くウェブアプリをつくりました。
We created a web application that works offline.
https://web-bad-worker-lz56g6.wanictf.org

添付ファイルなどはないため、Webページに飛んで怪しい箇所を探していきます。
実際にサイトに飛ぶと、
1.Github Pagesのインストール方法
2.カウンター機能
3.Flagを表示する機能
の3つの機能を持つWebサイトであることが分かります。
今回は3つめが明らかに怪しいため、このあたりの処理を行っているファイルを探してみます。
Webページを開いて右クリック、一番下の検証をクリックしてSourceタブを選択します。

上の画像で開いているservice_worker.jsにFlag表示機能が書かれており、現在はFetch FLAG.txtをクリックするとDUMMY.txtに飛ぶようになっています。この部分をFLAG.txtに変更してctrl+sで保存してクリックするとflagが取得できます。

FLAG{pr0gr3ssiv3_w3b_4pp_1s_us3fu1}

感想

Webを構成する要素(フレームワーク等)が多いほどどこを見れば迷ってしまうため、私はFlagを表示する処理を見つけるまでに30分以上はかかりました。見つけた後もどうすれば正しいフラグのテキストが表示するか悩みました。なんとなく書き換えたら出来んのか？と思ってたまたま行動に移したら解けたので、Webの知識に関してはまだまだ良くわからないです...。

(Crypto Easy) replacement

No one can read my diary!
cry-replacement.zip

from secret import cal
import hashlib

enc = []
for char in cal:
    x = ord(char)
    x = hashlib.md5(str(x).encode()).hexdigest()
    enc.append(int(x, 16))
        
with open('my_diary_11_8_Wednesday.txt', 'w') as f:
    f.write(str(enc))

zipファイルにはchall.pyとmy_diary_11_8_Wednesday.txtが添付されていました。テキストファイルにはmd5によるハッシュ値が書かれており、実行ファイルではテキスト(英語で書かれた日記)をmd5でハッシュするプログラムが書かれていました。そのためテキストを解読することが目標になります。
この問題ではハッシュ関数の特性について知っている必要があります。今回のハッシュ関数はメッセージのみを引数に取っているため、同じ文字をハッシュした場合は同じハッシュ値を返します。
この特性を利用して解読するとフラグにあたる文字列を見つけることができます。
私はasciiコード上で文字になりえるもの(10進数で33~126)に対してハッシュした値をkey, 10進数の値をvalueとした辞書を作成し、対応するハッシュ値を文字に変換しました。

FLAG{13epl4cem3nt}

感想

md5はハッシュ関数としてよくないイメージがあるため、復号サイトなどがあるのかなーと思って結局調べきれずに終わりました(それにちょっと邪道っぽい)。別の発想を考えるときにふとハッシュ関数の特性を思い出せたことで解答できました。気づいたときめちゃ楽しい。

(Crypto Easy) Easy calc

😆
cry-easy-calc.zip

import os
import random
from hashlib import md5

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, getPrime

FLAG = os.getenvb(b"FLAG", b"FAKE{THIS_IS_NOT_THE_FLAG!!!!!!}")


def encrypt(m: bytes, key: int) -> bytes:
    iv = os.urandom(16)
    key = long_to_bytes(key)
    key = md5(key).digest()
    cipher = AES.new(key, AES.MODE_CBC, iv=iv)
    return iv + cipher.encrypt(m)


def f(s, p):
    u = 0
    for i in range(p):
        u += p - i
        u *= s
        u %= p

    return u


p = getPrime(1024)
s = random.randint(1, p - 1)

A = f(s, p)
ciphertext = encrypt(FLAG, s).hex()


print(f"{p = }")
print(f"{A = }")
print(f"{ciphertext = }")

zipファイルにはchall.pyとoutput.txtが添付されていました。実行ファイルにはAESでブロック暗号を行う処理が書かれており、テキストにはある法則性を持つAと素数pと暗号文がありました。なのでsを導出したうえで、ブロック暗号の復号関数を動かすことで解読できます。

$f()$がAを導出していますが、計算量が

$O(p)=O(2^{1024})$のため、そのまま実行してはコンテスト中に解読できません。そのため漸化式を解くことで計算量を削減します。

$f()$は

$(((p\ast s+p-1)\ast s+p-2)\ast s\dots +1)\ast s$と表せるため、この式は

${\mathrm{\Sigma }}_{i=0}^{p}i{s}^i$と等価になります。(良くわからない人は

$p=3$の時の式を書いて見てみるとよいかも)
この式を微積分を用いて式変形すると(コンテスト中はChatGPTに教えてもらいました…)

$\frac{s(1-(p+1)s^p+p{s}^{p-1})}{(1-s{)}^2}$
となります。
この式に

$modp$を適応し、フェルマーの小定理も適応すると

$\frac{s}{1-s}$
となります。この値が

$A$と一致するためこれを計算することでsが求まります。
次にAESで復号を行いますが、今回暗号文の先頭にAESで用いる初期ベクトル

$iv$が付与されているため、先頭

$16$バイトの文字列を

$iv$として切り出してAESの復号関数を動作させればフラグが獲得できます。

FLAG{Do_the_math396691ba7d7270a}

感想

明らかに計算量的にsを復号できないことが分かったので、式変形を行おうという気持ちになりました。あとはとにかく折れずに解き切るのみ、という精神でやり抜きました。バイト列の扱いがこのとき微妙だったのでどこまでが16バイトの文字列だ...？と少し悩みながら解いたのもありました。

(Crypto Normal) dance

step by step
cry-dance.zip

chall.py

from mycipher import MyCipher
import hashlib
import datetime
import random

isLogged = False
current_user = ''
d = {}

def make_token(data1: str, data2: str):
    sha256 = hashlib.sha256()
    sha256.update(data1.encode())
    right = sha256.hexdigest()[:20]
    sha256.update(data2.encode())
    left = sha256.hexdigest()[:12]
    token = left + right
    return token

def main():
    print('Welcome to the super secure encryption service!')
    while True:
        print('Select an option:')
        print('1. Register')
        print('2. Login')
        print('3. Logout')
        print('4. Encrypt')
        print('5. Exit')
        choice = input('> ')
        if choice == '1':
            Register()
        elif choice == '2':
            Login()
        elif choice == '3':
            Logout()
        elif choice == '4':
            Encrypt()
        elif choice == '5':
            print('Goodbye!')
            break
        else:
            print('Invalid choice')

def Register():
    global d
    username = input('Enter username: ')
    if username in d:
        print('Username already exists')
        return
    dt_now = datetime.datetime.now()
    minutes = dt_now.minute
    sec = dt_now.second
    data1 = f'user: {username}, {minutes}:{sec}'
    data2 = f'{username}'+str(random.randint(0, 10))
    d[username] = make_token(data1, data2)
    print('Registered successfully!')
    print('Your token is:', d[username])
    return

def Login():
    global isLogged
    global d
    global current_user
    username = input('Enter username: ')
    if username not in d:
        print('Username does not exist')
        return
    token = input('Enter token: ')
    if d[username] != token:
        print('Invalid token')
        return
    isLogged = True
    current_user = username
    print(f'Logged in successfully! Hi {username}!')
    return

def Logout():
    global isLogged
    global current_user
    isLogged = False
    current_user = ''
    print('Logged out successfully!')
    return

def Encrypt():
    global isLogged
    global current_user
    if not isLogged:
        print('You need to login first')
        return
    token = d[current_user]
    sha256 = hashlib.sha256()
    sha256.update(token.encode())
    key = sha256.hexdigest()[:32]
    nonce = token[:12]
    cipher = MyCipher(key.encode(), nonce.encode())
    plaintext = input('Enter plaintext: ')
    ciphertext = cipher.encrypt(plaintext.encode())
    print('username:', current_user)
    print('Ciphertext:', ciphertext.hex())
    return

if __name__ == '__main__':
    main()

mychpher.py

from utils import *

class MyCipher:
    def __init__(self, key: bytes, nonce: bytes):
        self.key = key
        self.nonce = nonce
        self.counter = 1
        self.state = List[F2_32]

    def __quarter_round(self, a: F2_32, b: F2_32, c: F2_32, d: F2_32):
        a += b; d ^= a; d <<= 16
        c += d; b ^= c; b <<= 12
        a += b; d ^= a; d <<= 8
        c += d; b ^= c; b <<= 7
        return a, b, c, d
    
    def __Qround(self, idx1, idx2, idx3, idx4):
        self.state[idx1], self.state[idx2], self.state[idx3], self.state[idx4] = \
            self.__quarter_round(self.state[idx1], self.state[idx2], self.state[idx3], self.state[idx4])

    def __update_state(self):
        for _ in range(10):
            self.__Qround(0, 4, 8, 12)
            self.__Qround(1, 5, 9, 13)
            self.__Qround(2, 6, 10, 14)
            self.__Qround(3, 7, 11, 15)
            self.__Qround(0, 5, 10, 15)
            self.__Qround(1, 6, 11, 12)
            self.__Qround(2, 7, 8, 13)
            self.__Qround(3, 4, 9, 14)

    def __get_key_stream(self, key: bytes, counter: int, nonce: bytes) -> bytes:
        constants = [F2_32(x) for x in struct.unpack('<IIII', b'expand 32-byte k')]
        key = [F2_32(x) for x in struct.unpack('<IIIIIIII', key)]
        counter = [F2_32(counter)]
        nonce = [F2_32(x) for x in struct.unpack('<III', nonce)]
        self.state = constants + key + counter + nonce
        initial_state = self.state[:]
        self.__update_state()
        self.state = [x + y for x, y in zip(self.state, initial_state)]
        return serialize(self.state)
    
    def __xor(self, a: bytes, b: bytes) -> bytes:
        return bytes([x ^ y for x, y in zip(a, b)])

    def encrypt(self, plaintext: bytes) -> bytes:
        encrypted_message = bytearray(0)

        for i in range(len(plaintext)//64):
            key_stream = self.__get_key_stream(self.key, self.counter + i, self.nonce)
            encrypted_message += self.__xor(plaintext[i*64:(i+1)*64], key_stream)

        if len(plaintext) % 64 != 0:
            key_stream = self.__get_key_stream(self.key, self.counter + len(plaintext)//64, self.nonce)
            encrypted_message += self.__xor(plaintext[(len(plaintext)//64)*64:], key_stream[:len(plaintext) % 64])

        return bytes(encrypted_message)

utils.py

import struct
from typing import List

class F2_32:
    def __init__(self, val: int):
        self.val = val & 0xffffffff
    def __add__(self, other):
        return F2_32(self.val + other.val)
    def __sub__(self, other):
        return F2_32(self.val - other.val + 0xffffffff + 1)
    def __xor__(self, other):
        return F2_32(self.val ^ other.val)
    def __lshift__(self, nbit: int):
        left = (self.val << nbit) & 0xffffffff
        right = (self.val & 0xffffffff) >> (32 - nbit)
        return F2_32(left | right)
    def __rshift__(self, nbit: int):
        left = (self.val & 0xffffffff) >> nbit
        right = (self.val << (32 - nbit)) & 0xffffffff
        return F2_32(left | right)
    def __repr__(self):
        return hex(self.val)
    def __int__(self):
        return int(self.val)
    
def serialize(state: List[F2_32]) -> List[bytes]:
    return b''.join([ struct.pack('<I', int(s)) for s in state ])

output.txt

username = 'gureisya'
ciphertext = '061ff06da6fbf8efcd2ca0c1d3b236aede3f5d4b6e8ea24179'

zipファイルの中身としてはchall.pyとmycipher.pyとutils.pyとoutput.txtでした。
ファイルと中身が多くて大変ですが、今回は必要な部分を抜粋しながら読みます。
まず解読のために読むべき部分はchall.pyのRegister()とEncrypt(), mycipher.pyのencrypt()です。Registerで登録したユーザ名+αを基にトークンを作成し、ユーザ名とトークンを対応させて管理し、その情報を基にEncryptを行っています。mycipherのencryptでは指定されたユーザ名に対応するトークンを基にブロック暗号による暗号化を行います。
この問題を解くうえでやりたいことは、テキストに与えられたユーザ名に対応するトークンをencryptに与えることです。
理由は、Registerで生成されるトークンに脆弱性があるためです。詳しく言うと現在時刻の分と秒、そして適当な0~9までのランダムな値がトークンのランダム性に依存しているため、

$60\ast 60\ast 10=36000$のパターンを全通り試すことで一致するトークンが見つかるためです。
この情報をmycipherのencryptに与えることで解くことができます。

FLAG{d4nc3_l0b0t_d4nc3!!}

感想

とにかく情報量が多かったため、全体の動きを把握することにとても力を割いた感覚があります。しかし一つずつ必要そうな情報を取捨選択できたからこそ解読まで至れたという感覚もあります。トークンの通りを全通りしつつ、grepコマンドできれいな文字列になったものだけを出力したこともいい方法だったと自分で思いました。

まとめ

reversingの問題はlambda式の問題がきつくてあきらめてしまった部分があります。その先で解き始めたcryptoでしたが、思った以上にすいすい進む感覚が得られたため、暗号を専攻している身としてはとても嬉しい結果も残せました。
最後まで読んでいただきありがとうございました。