Wani CTF 2024 【作問者writeup(crypto)】

目次

はじめに
writeup
- beginners_rsa [beginner]
- beginners_aes [beginner]
- replacement [easy]
- dance [normal]
- speedy [hard]
おわりに
参考文献

はじめに

こんにちは、大阪大学CTFサークルWani Hackaseのぐれいしゃです。
この度はWani CTF2024にご参加いただき、ありがとうございました！
この記事は本CTFで出題された問題の内、私が作った問題のみに限定したwriteupとなっています。（cryptoの他の問題やweb, forなどの問題は後程公開されるgithubの公式writeupをご参照ください。）
各暗号の記事を参考文献の節に載せているので暗号の仕組みを知りたい方はよければそちらを見てみてください。

beginners_rsa

問題文

Do you know RSA?

配布ファイル

chall.py

from Crypto.Util.number import *

p = getPrime(64)
q = getPrime(64)
r = getPrime(64)
s = getPrime(64)
a = getPrime(64)
n = p*q*r*s*a
e = 0x10001

FLAG = b'FLAG{This_is_a_fake_flag}'
m = bytes_to_long(FLAG)
enc = pow(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'enc = {enc}')

解法

RSAを用いて暗号化していますが、普通のRSAとは異なりp, q, r, s, aという64ビットの素数の積をnとしています。

RSAの解読にあたって初めに合成数nの素因数分解が可能か考えます。
今回は64ビット程度の素数の積なので可能です。このぐらいの小さい合成数はfactordbというサイトに投げると大体答えが返ってきます。また、sagemathのfactorメソッドを使うと数十秒程度で素因数分解可能です。

素因数分解してしまえばあとは秘密鍵を求めるだけです。スクリプトは以下のように書けます。

solve.sage

from Crypto.Util.number import *

n = 317903423385943473062528814030345176720578295695512495346444822768171649361480819163749494400347
e = 65537
enc = 127075137729897107295787718796341877071536678034322988535029776806418266591167534816788125330265

fs = factor(n)
phi = 1
for f in fs:
    phi *= f[0]-1
d = inverse(e, phi)
m = pow(enc, d, n)
print(long_to_bytes(int(m)))

beginners_aes

問題文

AES is one of the most important encryption methods in our daily lives.

配布ファイル

chall.py

# https://pycryptodome.readthedocs.io/en/latest/src/cipher/aes.html
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from os import urandom
import hashlib

key = b'the_enc_key_is_'
iv = b'my_great_iv_is_'
key += urandom(1)
iv += urandom(1)

cipher = AES.new(key, AES.MODE_CBC, iv)
FLAG = b'FLAG{This_is_a_dummy_flag}'
flag_hash = hashlib.sha256(FLAG).hexdigest()

msg = pad(FLAG, 16)
enc = cipher.encrypt(msg)

print(f'enc = {enc}') # bytes object
print(f'flag_hash = {flag_hash}') # str object

解法

ブロック暗号のAESを用いた問題です。keyとivがほぼ分かっているので総当たりすることで解けますが、unpadを忘れないようにしてください。unpadを適切に行わないとフラグに似た異なる値が出てきます。（同じclerが大量に飛んできてました）

solve.py

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import hashlib

enc = b'\x16\x97,\xa7\xfb_\xf3\x15.\x87jKRaF&"\xb6\xc4x\xf4.K\xd77j\xe5MLI_y\xd96\xf1$\xc5\xa3\x03\x990Q^\xc0\x17M2\x18'
flag_hash = "6a96111d69e015a07e96dcd141d31e7fc81c4420dbbef75aef5201809093210e"
key = b'the_enc_key_is_'
iv = b'my_great_iv_is_'

for b1 in range(256):
    for b2 in range(256):
        key_ = key + bytes([b1])
        iv_ = iv + bytes([b2])
        cipher = AES.new(key_, AES.MODE_CBC, iv_)
        dec = cipher.decrypt(enc)
        try:
            m = unpad(dec, 16)
            m_hash = hashlib.sha256(m).hexdigest()
            if m_hash == flag_hash:
                print(f'decrypted = {m}')
        except:
            pass

replacement

問題文

No one can read my diary!

配布ファイル

chall.py

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))

解法

chall.pyを見ると日記内の文字を一文字ずつmd5で変換するという置換を行っています。ハッシュ関数は（内部状態が同じであれば）同じ入力に対して同じ値を返します。そのため、\x00から\xffまでハッシュ関数に掛けて入力とハッシュ値の対応表を作ることで日記を復元していくことが出来ます。

solve.py

import hashlib

enc = None
with open('my_diary_11_8_Wednesday.txt') as f:
       enc = f.readline().strip()
       enc = eval(enc)

d = {}
for i in range(0, 256):
    x = hashlib.md5(str(i).encode()).hexdigest()
    num = int(x, 16)
    d[num] = i
    
dec = ''
for i in enc:
    dec += chr(d[i])
    
print(dec)

dance

問題文

step by step

配布ファイル

chall.py

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()

mycipher.py

mycipher.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

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 ])

解法

mycipher.pyを見るとquarter_roundという特徴的な関数があります。これを手掛かりに調べていくと、この暗号がChacha20であることが分かります。

Chacha20はkeyとnonceがあれば復号出来ます。今回はどちらもトークンのハッシュ値の一部から生成されているためトークンを復元することが目標になります。トークンはユーザーネームとregisterした時の時刻、ランダムな0~10の値を用いて生成されているため、総当たりすることが可能です。

solve.py

import hashlib
from mycipher import MyCipher

username = 'gureisya'
ciphertext = '3da5f9fa6998a991cb244a12fa72d311f3e6e9fbcac9984c0c'

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

for sec in range(60):
    for minutes in range(60):
        data1 = f'user: {username}, {minutes}:{sec}'
        for i in range(10):
            data2 = f'{username}{i}'
            token = make_token(data1, data2)
            sha256 = hashlib.sha256()
            sha256.update(token[:32].encode())
            key = sha256.hexdigest()[:32]
            nonce = token[:12]
            cipher = MyCipher(key.encode(), nonce.encode())
            decrypted = cipher.encrypt(bytes.fromhex(ciphertext))
            if b'FLAG' in decrypted:
                print(decrypted)
                exit()

speedy

問題文

I made a super speedy keystream cipher!!

配布ファイル

chall.py

from cipher import MyCipher
from Crypto.Util.number import *
from Crypto.Util.Padding import *
import os

s0 = bytes_to_long(os.urandom(8))
s1 = bytes_to_long(os.urandom(8))

cipher = MyCipher(s0, s1)
secret = b'FLAG{'+b'*'*19+b'}'
pt = pad(secret, 8)
ct = cipher.encrypt(pt)
print(f'ct = {ct}')

cipher.py

from Crypto.Util.number import *
from Crypto.Util.Padding import *

def rotl(x, y):
    x &= 0xFFFFFFFFFFFFFFFF
    return ((x << y) | (x >> (64 - y))) & 0xFFFFFFFFFFFFFFFF

class MyCipher:
    def __init__(self, s0, s1):
        self.X = s0
        self.Y = s1
        self.mod = 0xFFFFFFFFFFFFFFFF
        self.BLOCK_SIZE = 8
    
    def get_key_stream(self):
        s0 = self.X
        s1 = self.Y
        sum = (s0 + s1) & self.mod
        s1 ^= s0
        key = []
        for _ in range(8):
            key.append(sum & 0xFF)
            sum >>= 8
        
        self.X = (rotl(s0, 24) ^ s1 ^ (s1 << 16)) & self.mod
        self.Y = rotl(s1, 37) & self.mod
        return key
    
    def encrypt(self, pt: bytes):
        ct = b''
        for i in range(0, len(pt), self.BLOCK_SIZE):
            ct += long_to_bytes(self.X)
            key = self.get_key_stream()
            block = pt[i:i+self.BLOCK_SIZE]
            ct += bytes([block[j] ^ key[j] for j in range(len(block))])
        return ct

解法

cipher.pyを見ると、二つの整数（内部状態）をxorやrotationを用いて更新しつつ疑似乱数を生成してそれらとのxorを行うような暗号であることが分かります。この疑似乱数生成手法はXoroshiro128+と呼ばれます。

Xoroshiro128+はある時点での内部状態が二つとも分かっていれば任意の時点の内部状態を計算することが出来ます。（それ以降の内部状態の計算は当然として、xorやshiftを用いる疑似乱数生成手法は逆行列を考えることで復元できます。）

ある時点の内部状態を(X, Y)と表記すると、片方は暗号文から直接取り出すことが出来ます。（こちらをXとしておきます。）

chall.py

    def encrypt(self, pt: bytes):
        ct = b''
        for i in range(0, len(pt), self.BLOCK_SIZE):
            ct += long_to_bytes(self.X)
            key = self.get_key_stream()
            block = pt[i:i+self.BLOCK_SIZE]
            ct += bytes([block[j] ^ key[j] for j in range(len(block))])
        return ct

ctに直接Xを足しているのでスライスなどで取り出したらOKです。

あとはYを求めるパートですが、フラグのパディングが7バイト分であることを利用するとX+Yは256通りに絞ることが出来ます。Xは判明しているのでX+YからYを求めて復号に成功するまで試せばよいです。

これらをまとめると以下のようなスクリプトが書けます。

solve.py

from Crypto.Util.number import *
from Crypto.Util.Padding import *
import os

def rotl(x, y):
    x &= 0xFFFFFFFFFFFFFFFF
    return ((x << y) | (x >> (64 - y))) & 0xFFFFFFFFFFFFFFFF

class MyCipher:
    def __init__(self, s0, s1):
        self.X = s0
        self.Y = s1
        self.mod = 0xFFFFFFFFFFFFFFFF
        self.BLOCK_SIZE = 8
    
    def get_key_stream(self):
        s0 = self.X
        s1 = self.Y
        sum = (s0 + s1) & self.mod
        s1 ^= s0
        key = []
        for _ in range(8):
            key.append(sum & 0xFF)
            sum >>= 8
        
        self.X = (rotl(s0, 24) ^ s1 ^ (s1 << 16)) & self.mod
        self.Y = rotl(s1, 37) & self.mod
        return key
    
    def set_seed(self, s0, s1):
        self.X = s0
        self.Y = s1
    
    def encrypt(self, pt: bytes):
        ct = b''
        for i in range(0, len(pt), self.BLOCK_SIZE):
            ct += long_to_bytes(self.X)
            key = self.get_key_stream()
            block = pt[i:i+self.BLOCK_SIZE]
            ct += bytes([block[j] ^ key[j] for j in range(len(block))])
        return ct
    
    def decrypt(self, ct: bytes, s0=None, s1=None):
        pt = b''
        if s0 is not None and s1 is not None:
            self.set_seed(s0, s1)
        for i in range(0, len(ct), 2*self.BLOCK_SIZE):
            key = self.get_key_stream()
            block = ct[i+self.BLOCK_SIZE:i+2*self.BLOCK_SIZE]
            pt += bytes([block[j] ^ key[j] for j in range(len(block))])
        return unpad(pt, self.BLOCK_SIZE)
    
def rotl(x, y):
    x &= 0xFFFFFFFFFFFFFFFF
    return ((x << y) | (x >> (64 - y))) & 0xFFFFFFFFFFFFFFFF

def back(x, y, times):
    s0 = x
    s1 = y
    for _ in range(times):
        s0 = (rotl(x, 40) ^ rotl(y, 3) ^ rotl((rotl(y, 27)<<16), 40)) & 0xFFFFFFFFFFFFFFFF
        s1 = (rotl(x, 40) ^ rotl(y, 3) ^ rotl((rotl(y, 27)<<16), 40) ^ rotl(y, 27)) & 0xFFFFFFFFFFFFFFFF
        x = s0
        y = s1
    return s0, s1

ct = b'"G:F\xfe\x8f\xb0<O\xc0\x91\xc8\xa6\x96\xc5\xf7N\xc7n\xaf8\x1c,\xcb\xebY<z\xd7\xd8\xc0-\x08\x8d\xe9\x9e\xd8\xa51\xa8\xfbp\x8f\xd4\x13\xf5m\x8f\x02\xa3\xa9\x9e\xb7\xbb\xaf\xbd\xb9\xdf&Y3\xf3\x80\xb8'
flag = b''
for b in range(0x00, 0x100):
    sum = 0
    pred = long_to_bytes(b)+b'\x07'*7
    for i in range(8):
        sum += (ct[-8+i] ^ pred[i]) << 8*i

    x = bytes_to_long(ct[-16:-8])
    y = (sum-x) & 0xFFFFFFFFFFFFFFFF
    seed0, seed1 = back(x, y, 3)
    cipher = MyCipher(0xdeadbeef, 0x12345678)
    pt = cipher.decrypt(ct, seed0, seed1)
    if pt.startswith(b'FLAG{'):
        flag = pt
        break

print(flag)

おわりに

Wani CTF運営も二回目ということで、前回よりも幅広く出題出来たかなと思っています。solve数を見る限りhardはもう少し難易度を上げても良さそうなので次回はパズル要素多めの問題を作るのに挑戦します。
それでは参加してくださった皆さんありがとうございました！

参考文献

RSA：https://zenn.dev/anko/articles/ctf-crypto-rsa
AES：https://zenn.dev/anko/articles/ctf-crypto-commonkey
Chacha20：https://tex2e.github.io/blog/crypto/chacha20poly1305
Xoroshiro128+の復元：https://hackmd.io/@yatsuna827/r1ez2-n3S