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はもう少し難易度を上げても良さそうなので次回はパズル要素多めの問題を作るのに挑戦します。
それでは参加してくださった皆さんありがとうございました！