Zenn
😁

WaniCTF2024 writeup(Crypto)

2024/06/24に公開
CTF
writeup
wanictf2024
tech

waniCTF2024にKGUCSLで参加しました！
今回僕はCryptoだけ解いてました！まだCrypto勉強初めて数ヶ月ですが、とても頭を使いながら楽しんで解けました．
https://x.com/pppp46497/status/1804858281330123055
めちゃくちゃ余談ですが、僕の名前の由来はポッチャマなので、作問者のGureisyaさんの名前みたときに勝手に喜んでた

beginners_aes

# 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

keyとivがほぼわかっている状況でurandom(1)を追加しているので、総当たりで求めることができる。flag_hashが与えられているので、一致するものを探せばOK！

from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
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'

base_key = b'the_enc_key_is_'
base_iv = b'my_great_iv_is_'

for i in range(256):
    for j in range(256):
        test_key = base_key + bytes([i])
        test_iv = base_iv + bytes([j])

        cipher = AES.new(test_key, AES.MODE_CBC, test_iv)
        try:
            decrypted_msg = unpad(cipher.decrypt(enc), 16)

            msg_hash = hashlib.sha256(decrypted_msg).hexdigest()

            if msg_hash == flag_hash:
                print(f'Decrypted message: {decrypted_msg.decode()}')
                break
        except Exception:
            pass

FLAG{7h3_f1r57_5t3p_t0_Crypt0!!}

beginners_rsa

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

この程度だったら普通に素因数分解できるはず。
が、factorDBでやったら何故か出てこなかったのでPython内で素因数分解してフラグを出しました。

from Crypto.Util.number import inverse, long_to_bytes
from sympy import factorint

n = 317903423385943473062528814030345176720578295695512495346444822768171649361480819163749494400347
e = 65537
enc = 127075137729897107295787718796341877071536678034322988535029776806418266591167534816788125330265

factors = factorint(n)
primes = list(factors.keys())

phi = 1
for p in primes:
    phi *= (p - 1)

d = inverse(e, phi)

m = pow(enc, d, n)
FLAG = long_to_bytes(m)
print(FLAG.decode())

FLAG{S0_3a5y_1254!!}

replacement

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

文字列を一つずつMD5で変換していることがわかります。
今回1文字ずつハッシュ化しているため、レインボーテーブル攻撃が通ることがわかります。
後は、これを実装するだけ！

import hashlib

cipher = eval(open('my_diary_11_8_Wednesday.txt', 'r').readline().strip())

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

すると、以下の文章が現れた。

Wednesday, 11/8, clear skies. This morning, I had breakfast at my favorite cafe. Drinking the freshly brewed coffee and savoring the warm buttery toast is the best. Changing the subject, I received an email today with something rather peculiar in it. It contained a mysterious message that said "This is a secret code, so please don't tell anyone. FLAG{13epl4cem3nt}". How strange!

Gureisya

FLAG{13epl4cem3nt}

Easy calc

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 = }")

pとAが与えられているが、普通にやっても絶対間に合わない．

まず、数式で考える．
u_i \equiv ((u_{i-1} + (p - i)) \cdot s) \mod p
ここで、u_i = Aなので、
A \equiv ((u_{i-1} + (p - i)) \cdot s) \mod p
となる．
ただ、ここで止まってしまった．
pを極端に小さい素数にして、数値の変化を追って見ると、以下のようになった。

p = 23, s = 4, A = 14
i=20:
u += p-i: 25
u *= s: 225
u %=: 18
i=21:
u += p-i: 20
u *= s: 180
u %=: 19
i=22:
u += p-i: 20
u *= s: 180
u %=: 19

p = 97,s = 47,A = 77
i=94:
u += p-i: 14
u *= s: 658
u %=: 76
i=95:
u += p-i: 78
u *= s: 3666
u %=: 77
i=96:
u += p-i: 78
u *= s: 3666
u %=: 77

つまり、u_i = u_{i-1} = Aであることがわかる。

s \equiv A \cdot (A + 1)^{-1} \mod p
後はこれは実装すれば解ける！

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from hashlib import md5
import binascii
from sympy import mod_inverse

def find_s(A, p):
    A_plus_1_inv = mod_inverse(A + 1, p)
    s = (A * A_plus_1_inv) % p
    return s

def decrypt(ciphertext: bytes, key: int) -> bytes:
    iv = ciphertext[:16]
    ciphertext = ciphertext[16:]
    
    key = long_to_bytes(key)
    key = md5(key).digest()

    cipher = AES.new(key, AES.MODE_CBC, iv=iv)
    plaintext = cipher.decrypt(ciphertext)
    return plaintext

p = 108159532265181242371960862176089900437183046655107822712736597793129430067645352619047923366465213553080964155205008757015024406041606723580700542617009651237415277095236385696694741342539811786180063943404300498027896890240121098409649537982185247548732754713793214557909539077228488668731016501718242238229
A = 60804426023059829529243916100868813693528686280274100232668009387292986893221484159514697867975996653561494260686110180269479231384753818873838897508257692444056934156009244570713404772622837916262561177765724587140931364577707149626116683828625211736898598854127868638686640564102372517526588283709560663960

s = find_s(A, p)
ciphertext_hex = '9fb749ef7467a5aff04ec5c751e7dceca4f3386987f252a2fc14a8970ff097a81fcb1a8fbe173465eecb74fb1a843383'
ciphertext = binascii.unhexlify(ciphertext_hex)
plaintext = decrypt(ciphertext, s)
print(plaintext.decode())

FLAG{Do_the_math396691ba7d7270a}

dance

複数ファイル渡された問題．
重要なところだけ．


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

まず，data1がuser: {username}, {minutes}:{sec}でdata2が{username}'+str(random.randint(0, 10))と定義されている。一方で、output.txtにusername = 'gureisya'と記載されているため、minutesとsec、 random.randint(0,10)の3つだが、minutesもsecも60通り、randintも11通りなので、たかだか39600通りなので総当りできる．後は、Encrypt関数を参考にkeyとnonceを生成し、復号する関数作ればOK

import hashlib
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]) -> bytes:
    return b''.join([struct.pack('<I', int(s)) for s in state])

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

    def __quarter_round(self, a: F2_32, b: F2_32, c: F2_32, d: F2_32):
        a += b; d ^= a; d = d << 16
        c += d; b ^= c; b = b << 12
        a += b; d ^= a; d = d << 8
        c += d; b ^= c; b = b << 7
        return a, b, c, d

    def __update_state(self):
        for _ in range(10):
            self.state[0], self.state[4], self.state[8], self.state[12] = self.__quarter_round(self.state[0], self.state[4], self.state[8], self.state[12])
            self.state[1], self.state[5], self.state[9], self.state[13] = self.__quarter_round(self.state[1], self.state[5], self.state[9], self.state[13])
            self.state[2], self.state[6], self.state[10], self.state[14] = self.__quarter_round(self.state[2], self.state[6], self.state[10], self.state[14])
            self.state[3], self.state[7], self.state[11], self.state[15] = self.__quarter_round(self.state[3], self.state[7], self.state[11], self.state[15])
            self.state[0], self.state[5], self.state[10], self.state[15] = self.__quarter_round(self.state[0], self.state[5], self.state[10], self.state[15])
            self.state[1], self.state[6], self.state[11], self.state[12] = self.__quarter_round(self.state[1], self.state[6], self.state[11], self.state[12])
            self.state[2], self.state[7], self.state[8], self.state[13] = self.__quarter_round(self.state[2], self.state[7], self.state[8], self.state[13])
            self.state[3], self.state[4], self.state[9], self.state[14] = self.__quarter_round(self.state[3], self.state[4], self.state[9], self.state[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)

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]
    return left + right

def decrypt_with_token(token: str, ciphertext: str):
    sha256 = hashlib.sha256()
    sha256.update(token.encode())
    key = sha256.hexdigest()[:32]
    nonce = token[:12]
    cipher = MyCipher(key.encode(), nonce.encode())
    ciphertext_bytes = bytes.fromhex(ciphertext)
    plaintext = cipher.encrypt(ciphertext_bytes)
    return plaintext.decode(errors='ignore')

def get_flag():
    username = 'gureisya'
    ciphertext = '061ff06da6fbf8efcd2ca0c1d3b236aede3f5d4b6e8ea24179'
    
    for minute in range(60):
        for second in range(60):
            data1 = f'user: {username}, {minute}:{second}'
            for rand in range(11):
                data2 = f'{username}{rand}'
                token = make_token(data1, data2)
                decrypted_text = decrypt_with_token(token, ciphertext)
                if decrypted_text.startswith('FLAG'):
                    print('Token:', token)
                    print('Decrypted text:', decrypted_text)
                    return```

get_flag()

添付されたコードに継ぎ足ししたのでデットコードあるかも。。。
FLAG{d4nc3_l0b0t_d4nc3!!}

Discussion