始めに
Cyber Apocalypse 2024: Hacker RoyalにWani Hackaseとして参加していたのでそれらのwriteupを載せようと思います
目次
- Dynastic
- Makeshift
- Primary Knowledge
- Iced TEA
- Blunt
- Arranged
- Partial Tenacity
- Permuted
- Tsayaki
- ROT128
Dynastic
単純な置換暗号なので暗号化の逆操作を実装する
decrypt.py
def decrypt(m):
c = ''
for i in range(len(m)):
ch = m[i]
if not ch.isalpha():
ech = ch
else:
chi = to_identity_map(ch)
ech = from_identity_map(chi - i)
c += ech
return c
MakeShift
Dynasticと同じく逆操作を実装する
for i in range(0, len(enc), 3):
FLAG += enc[i+2]
FLAG += enc[i]
FLAG += enc[i+1]
FLAG = FLAG[::-1]
Primary Knowledge
RSAだがnが素数なのでφ(n)=n-1より秘密鍵dを簡単に求められる
solve.py
from Crypto.Util.number import *
n = 144595784022187052238125262458232959109987136704231245881870735843030914418780422519197073054193003090872912033596512666042758783502695953159051463566278382720140120749528617388336646147072604310690631290350467553484062369903150007357049541933018919332888376075574412714397536728967816658337874664379646535347
e = 65537
c = 15114190905253542247495696649766224943647565245575793033722173362381895081574269185793855569028304967185492350704248662115269163914175084627211079781200695659317523835901228170250632843476020488370822347715086086989906717932813405479321939826364601353394090531331666739056025477042690259429336665430591623215
phi = n-1
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
Iced TEA
よく分からないブロック暗号をECBモードで利用している
KEYが分かっているので復号処理を実装すればOK
decrypt.py
def decrypt_block(self, ct):
m = b2l(ct)
m0 = m >> (self.BLOCK_SIZE//2)
m1 = m & ((1 << (self.BLOCK_SIZE//2)) - 1)
K = self.KEY
msk = (1 << (self.BLOCK_SIZE//2)) - 1
s = self.DELTA << 5
for i in range(32):
m1 -= ((m0 << 4) + K[2]) ^ (m0 + s) ^ ((m0 >> 5) + K[3])
m1 &= msk
m0 -= ((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])
m0 &= msk
s -= self.DELTA
return l2b((m0 << 32) + m1)
def decrypt(self, ct):
blocks = [ct[i:i+self.BLOCK_SIZE//8] for i in range(0, len(ct), self.BLOCK_SIZE//8)]
pt = b''
if self.mode == Mode.ECB:
for block in blocks:
pt += self.decrypt_block(block)
elif self.mode == Mode.CBC:
X = self.IV
for block in blocks:
dec_block = self.decrypt_block(block)
pt += self._xor(X, dec_block)
X = block
return pt
Blunt
Diffie-Hellmanで鍵を共有した後、AES-CBCで暗号化している
素数pが32bitと通常のDHで使われるものよりも小さいので現実的な時間で離散対数問題を解くことが可能
solve.sage
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
p = 0xdd6cc28d
g = 0x83e21c05
A = 0xcfabb6dd
B = 0xc4a21ba9
ct = b'\x94\x99\x01\xd1\xad\x95\xe0\x13\xb3\xacZj{\x97|z\x1a(&\xe8\x01\xe4Y\x08\xc4\xbeN\xcd\xb2*\xe6{'
g = mod(g, p)
A = mod(A, p)
B = mod(B, p)
a = discrete_log(A, g)
C = pow(B, a, p)
key = sha256(long_to_bytes(int(C))).digest()[:16]
iv = b'\xc1V2\xe7\xed\xc7@8\xf9\\\xef\x80\xd7\x80L*'
print(f'key = {key}')
print(f'iv = {iv}')
cipher = AES.new(key, AES.MODE_CBC, iv)
pt = cipher.decrypt(pad(ct, 16))
print(f'ciphertext = {pt}')
Arranged
楕円曲線上のDiffie-Hellmanをした後AES-CBCを使って暗号化している
楕円曲線のパラメータがWeierstrass標準形でのaしか与えられない上、有限体Fの位数pが不明なので一見解けなさそうに見えるが、楕円曲線上の異なる3点の座標が与えられているので以下の合同式（楕円曲線の式2本からbを消去したもの）が3本立ち、最大公約数を計算することでpを求められる
{y_1}^2 - {y_0}^2 - ({x_1}^3 - {x_0}^3 + a(x_1 - x_0)) \equiv 0 \mod p
sub.sage
def func(x0, y0, x1, y1, a):
return y1^2 - y0^2 - (x1^3 - x0^3 + a*(x1 - x0))
gx, gy = 926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367, 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253
ax, ay = 6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997, 2456156841357590320251214761807569562271603953403894230401577941817844043774935363309919542532110972731996540328492565967313383895865130190496346350907696
bx, by = 4226762176873291628054959228555764767094892520498623417484902164747532571129516149589498324130156426781285021938363575037142149243496535991590582169062734, 425803237362195796450773819823046131597391930883675502922975433050925120921590881749610863732987162129269250945941632435026800264517318677407220354869865
a = 726
n1 = func(ax, ay, bx, by, a)
n2 = func(gx, gy, ax, ay, a)
n3 = func(gx, gy, bx, by, a)
p = gcd(n1, gcd(n2, n3))
pが分かれば楕円曲線の式を簡単に式変形したもの
b = y^2-x^3-ax \mod p
からbが得られる
あとは楕円曲線上の離散対数問題を解くだけでOK
solve.sage
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
def func(x0, y0, x1, y1, a):
return y1^2 - y0^2 - (x1^3 - x0^3 + a*(x1 - x0))
gx, gy = 926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367, 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253
ax, ay = 6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997, 2456156841357590320251214761807569562271603953403894230401577941817844043774935363309919542532110972731996540328492565967313383895865130190496346350907696
bx, by = 4226762176873291628054959228555764767094892520498623417484902164747532571129516149589498324130156426781285021938363575037142149243496535991590582169062734, 425803237362195796450773819823046131597391930883675502922975433050925120921590881749610863732987162129269250945941632435026800264517318677407220354869865
a = 726
n1 = func(ax, ay, bx, by, a)
n2 = func(gx, gy, ax, ay, a)
n3 = func(gx, gy, bx, by, a)
p = gcd(n1, gcd(n2, n3))
b = (gy^2-gx^3-a*gx)%p
E = EllipticCurve(GF(p), [a, b])
G = E(gx, gy)
A = E(ax, ay)
priv_a = discrete_log(A, G, G.order(), operation='+')
C = priv_a*E(bx, by)
secret = int(C[0])
hash = sha256()
hash.update(long_to_bytes(secret))
key = hash.digest()[16:32]
iv = b'u\x8fo\x9aK\xc5\x17\xa7>[\x18\xa3\xc5\x11\x9en'
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = b'V\x1b\xc6&\x04Z\xb0c\xec\x1a\tn\xd9\xa6(\xc1\xe1\xc5I\xf5\x1c\xd3\xa7\xdd\xa0\x84j\x9bob\x9d"\xd8\xf7\x98?^\x9dA{\xde\x08\x8f\x84i\xbf\x1f\xab'
pt = cipher.decrypt(pad(ct, 16))
print(pt)
Partial Tenacity
RSA暗号だが公開鍵に加えてpの最上位桁から0-indexedで数えて偶数桁、同様にqの奇数桁が与えられる
p, qは512bitの素数なので154桁あるいは155桁になると考えられる
与えられたpの偶数桁は78桁、qの奇数桁は77桁となっており、pは155桁で確定する、qはpとqとnの下一桁に注目すると155桁になることが分かる
イメージ図
与えられた部分的な情報から積がnとなるようなp, qを求めたいので、交互にpとqの判明していない桁を求めるような深さ優先探索を書けばよさそう
solve.py
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
import sys
sys.setrecursionlimit(10000)
n = 118641897764566817417551054135914458085151243893181692085585606712347004549784923154978949512746946759125187896834583143236980760760749398862405478042140850200893707709475167551056980474794729592748211827841494511437980466936302569013868048998752111754493558258605042130232239629213049847684412075111663446003
p_even = 151441473357136152985216980397525591305875094288738820699069271674022167902643
q_odd = 15624342005774166525024608067426557093567392652723175301615422384508274269305
ct = '7f33a035c6390508cee1d0277f4712bf01a01a46677233f16387fae072d07bdee4f535b0bd66efa4f2475dc8515696cbc4bc2280c20c93726212695d770b0a8295e2bacbd6b59487b329cc36a5516567b948fed368bf02c50a39e6549312dc6badfef84d4e30494e9ef0a47bd97305639c875b16306fcd91146d3d126c1ea476'
p_str = str(p_even)
q_str = str(q_odd)
p_str = p_str[::-1]
q_str = q_str[::-1]
def search(d, P, Q):
if d==155:
if P*Q==n:
print(f'P = {P}')
print(f'Q = {Q}')
exit()
return
tmp_p = P
tmp_q = Q
mod = 10**(d+1)
for i in range(10):
if d%2 == 0:
P = tmp_p + int(p_str[d//2])*10**d
Q = tmp_q + i*10**d
else:
P = tmp_p + i*10**d
Q = tmp_q + int(q_str[d//2])*10**d
if P*Q%mod == n%mod:
search(d+1, P, Q)
P = 10541549431842783633587614316112542499895727166990860537947158205451961334065983715903944224868775308489240169949600619123741969714205272515647199022167453
Q = 11254692541324720060752707148186767582750062945630785066774422168535575089335596479399029695524722638167959390210621853422825328846580189277644256392390351
phi = (P-1)*(Q-1)
e = 65537
d = inverse(e, phi)
key = RSA.construct((n, e, d))
cipher = PKCS1_OAEP.new(key)
print(cipher.decrypt(bytes.fromhex(ct)).decode())
TSGCTF 2019で出題されたOPQRXという問題のwriteupが参考になりました
kusanoさんのwriteup：https://qiita.com/kusano_k/items/95667153509be6e45ef2#opqrx
Permuted
対称群の写像の合成を乗法としてDiffie-Hellmanをしている
sagemathにはSymmetricGroupというクラスがあり、離散対数問題を解くメソッドを利用する事が出来るのでそれを使う
注意点として、SymmetricGroupでは1-indexedでサイクル表記なので添え字や表記を変換する必要がある
solve.sage
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from hashlib import sha256
class Permutation:
def __init__(self, mapping: list[int]):
self.length = len(mapping)
assert set(mapping) == set(range(self.length)) # ensure it contains all numbers from 0 to length-1, with no repetitions
self.mapping: list[int] = list(mapping)
def __call__(self, *args, **kwargs):
idx, *_ = args
assert idx in range(self.length)
return self.mapping[idx]
def __mul__(self, other):
ans = []
for i in range(self.length):
ans.append(self(other(i)))
return Permutation(ans)
def __pow__(self, power, modulo=None):
ans = Permutation.identity(self.length)
ctr = self
while power > 0:
if power % 2 == 1:
ans *= ctr
ctr *= ctr
power //= 2
return ans
def __str__(self):
return str(self.mapping)
def identity(length):
return Permutation(range(length))
n = 50_000
G = SymmetricGroup(n)
g, A, B, ct = None, None, None, None
with open('output.txt', 'r') as f:
lines = f.readlines()
for line in lines:
if line.startswith('g ='):
g = Permutation(eval(line.split('=')[1]))
elif line.startswith('A ='):
A = Permutation(eval(line.split('=')[1]))
elif line.startswith('B ='):
B = Permutation(eval(line.split('=')[1]))
elif line == '\n':
pass
else:
ct = line.split('=')[1].strip()
for i in range(len(A.mapping)):
g.mapping[i] += 1
A.mapping[i] += 1
B.mapping[i] += 1
g = G(g.mapping)
A = G(A.mapping)
B = G(B.mapping)
a = discrete_log(A, g)
C = B**a
def to_permutation(g):
d = g.dict()
return list(d.values())
C = to_permutation(C)
C = [x-1 for x in C]
C = Permutation(C)
sec = tuple(C.mapping)
sec = hash(sec)
sec = long_to_bytes(sec)
hash = sha256()
hash.update(sec)
key = hash.digest()[16:32]
iv = b"mg'g\xce\x08\xdbYN2\x89\xad\xedlY\xb9"
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = eval(ct)
pt = cipher.decrypt(pad(ct, 16))
print('pt =', pt)
Tsayaki
先ほどのIced TEAで出てきたよく分からないブロック暗号を用いてCBCモードで暗号化している
与えられた平文を暗号化したものが全て同じ暗号文になるように4つの異なる鍵を選ぶということを10ラウンド繰り返したらFLAGがもらえる
式変形を色々試しても特に意味のありそうなものにならなかったので、方針転換してCipherクラスのDELTA=0x9e3779b9というマジックナンバーを検索してみると次のようなwriteupが見つかった
https://ctftime.org/writeup/32328
どうやらTiny Encryption Algorithmだからそれの略であるTEAが出てきていたらしい
wikipediaを見ると、ある鍵に対して同等な鍵が他に3つ存在するため実質126bitの鍵空間しかないらしい
参考文献にあった論文"Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES"を読むと同等な鍵は、K[0]とK[1]の最上位ビットをフリップする/しない or K[2]とK[3]の最上位ビットをフリップする/しない の4種類考えられるということだったのでそれらを求めるようなスクリプトを書いたらOK
solve.py
from Crypto.Util.number import *
from tea import Cipher as TEA
from pwn import remote
r = remote('localhost', 5050)
ROUND = 10
IV = b'\r\xdd\xd2w<\xf4\xb9\x08'
def xor(a, b):
return bytes([_a ^ _b for _a, _b in zip(a, b)])
keys = []
flip_mask_1 = b'\x80'+b'\x00'*3+b'\x80'+b'\x00'*11
flip_mask_2 = b'\x00'*8+b'\x80'+b'\x00'*3+b'\x80'+b'\x00'*3
flip_mask_3 = b'\x80'+b'\x00'*3+b'\x80'+b'\x00'*3+b'\x80'+b'\x00'*3+b'\x80'+b'\x00'*3
for i in range(ROUND):
keys.append([])
suffix = long_to_bytes(i, 8)
prefix = long_to_bytes(i, 4)
key_0 = prefix*2 + suffix
key_1 = xor(key_0, flip_mask_1)
key_2 = xor(key_0, flip_mask_2)
key_3 = xor(key_0, flip_mask_3)
keys[i].append(key_0)
keys[i].append(key_1)
keys[i].append(key_2)
keys[i].append(key_3)
r.recvuntil('Here is my special message: ')
server_message = r.recvline().strip().decode()
server_message = bytes.fromhex(server_message)
print(f'server_message: {server_message.hex()}')
for i in range(ROUND):
print(f'~~~~ Round {i+1}/10 ~~~~')
r.recvuntil('Enter your target ciphertext (in hex) : ')
cipher = TEA(keys[i][0], IV)
ct = cipher.encrypt(server_message)
r.sendline(ct.hex())
print('send ciphertext:', ct.hex())
for j in range(4):
print('current key:', keys[i][j].hex())
print(r.recvuntil(f'[{i+1}/{j+1}] Enter your encryption key (in hex) : '))
key = keys[i][j]
r.sendline(key.hex())
print(r.recvline().decode())
r.close()
ROT128
32bytesの平文から32bytesのハッシュ値を出力するような独自のハッシュに対して、同じ平文から同じ出力が得られるような内部状態を考える問題
ハッシュ値を生成する処理は以下のようになっている
_ROL_ = lambda x, i : ((x << i) | (x >> (N-i))) & (2**N - 1)
def hash_step(self, i):
r1, r2 = self.state[2*i], self.state[2*i+1]
return _ROL_(self.state[-2], r1) ^ _ROL_(self.state[-1], r2)
def digest(self, buffer):
buffer = int.from_bytes(buffer, byteorder='big')
m1 = buffer >> N
m2 = buffer & (2**N - 1)
self.h = b''
for i in range(2):
self.h += int.to_bytes(self.hash_step(i) ^ (m1 if not i else m2), length=N//8, byteorder='big')
return self.h
もう少し分かりやすく表すとハッシュ値とその計算に使われるhash_stepは次のような値である
hash_step(0) = left_rotation(state[4], state[0]) ^ left_rotation(state[5], state[1])
hash_step(1) = left_rotation(state[4], state[2]) ^ left_rotation(state[5], state[3])
hash = m1^hash_step(0) + m2^hash_step(1)
m1, m2が既知の値であることに着目すると、この問題は次のような問題に帰着させることが出来る
問題
$128\ bit$の整数$N_1, N_2$が与えられる
このとき
N1 = left_rotation(x, r_0) ^ left_rotation(y, r_1)
N2 = left_rotation(x, r_2) ^ left_rotation(y, r_3)
を満たすような整数$x,\ y,\ r_i\ (0 \leq i < 4)$を構成せよ$(0 < x,\ y < 2^{128} - 1,\ 0 < r_i < 128)$
ここで
N1 = hash_step(0)
N2 = hash_step(1)
である（それぞれサーバから与えられるメッセージに対するhash_step）
このような条件では$N_1,\ N_2$のpopcountの偶奇が等しいとき解が存在し、それ以外は存在しない
実はこの問題は$r_i$を固定して解くことが出来る
例えば、$r_0 = r_1 = r_2 = 1,\ r_3 = 2$と置くと、以下のような式が得られる
（left_rotation(x, i)をf_i(x)と表記した）
$$f_1(x)\ xor\ f_1(y)\ =\ N_1$$$$f_1(x)\ xor\ f_2(y)\ =\ N_2$$
式を整理すると
$$f_1(y)=\ N_1 \ xor\ N_2 \ xor\ f_2(y)$$
つまり、
$$y[0]\ =\ (N_1 \ xor\ N_2)[127]\ xor\ y[1]$$
が成立する
同様にして、yのi番目のビットはi+1番目のビットが判明していたら計算する事が出来る
どのビットでも構わないが、起点となるビットを0と置いて順に計算していくことでyを取得し、
$$f_1(x)=\ N_1\ xor\ f_1(y)\ $$
からxを計算する（right_rotationを実装する必要がある）
以上の手順を踏むことでこの問題を解くことが出来る
（チームメイトがこの解法を考えてくれました、天才すぎる...）
ここまでで、ハッシュを衝突させるような内部状態を計算できるようになったのでそれらを送るようなスクリプトを書けばOK
ただし、一度使った(r_0, r_1, r_2, r_3)はもう使えないので、r_iにroundを足した値を利用してx, yを求める
solve.py
from Crypto.Util.number import *
from pwn import *
ROUNDS = 3
_ROL_ = lambda x, i : ((x << i) | (x >> (N-i))) & (2**N - 1)
_ROR_ = lambda x, i : ((x >> i) | (x << (N-i))) & (2**N - 1)
N = 128
def make_state(N1, N2, round=0):
pc_N1 = bin(N1).count('1')
pc_N2 = bin(N2).count('1')
if (pc_N1 - pc_N2) % 2 != 0:
return None
y_bits = [0]*128
num = N1^N2
num_bits = [0]*128
for i in range(0, 128):
num_bits[i] = bin(num & (1<<(127-i))).count('1')
assert num_bits[i] in [0, 1]
x, y = 0, 0
for i in range(0, -127, -1):
y_bits[(i+round)%128] = num_bits[127+i] ^ y_bits[(i+round+1)%128]
for i in range(128):
y += y_bits[i] << (127-i)
x = _ROR_((N1^_ROL_(y, 1+round)), 1+round)
assert _ROL_(x, 1+round)^_ROL_(y, 1+round) == N1
assert _ROL_(x, 1+round)^_ROL_(y, 2+round) == N2
assert 0 < x < 2**N-1 and 0 < y < 2**N-1
return [1+round, 1+round, 1+round, 2+round, x, y]
def make_hash(buffer: bytes, hash: bytes, round: int) -> list[int]:
buffer = int.from_bytes(buffer, byteorder='big')
m1 = buffer >> N
m2 = buffer & (2**N - 1)
former = bytes_to_long(hash[:16])
latter = bytes_to_long(hash[16:])
N1 = former ^ m1
N2 = latter ^ m2
lst = make_state(N1, N2, round)
if lst:
return lst
else:
return None
r = remote('localhost', 5050)
print(r.recvline())
for round in range(ROUNDS):
print(r.recvline())
line = r.recvline().strip().decode()
lst = line.split(' ')
server_msg = lst[2][2:-1]
server_hash = lst[4]
print(f'server_msg: {server_msg}')
print(f'server_hash: {server_hash}')
r.recvuntil('Send your hash function state (format: a,b,c,d,e,f) :: ')
msg = bytes.fromhex(server_msg)
hash = bytes.fromhex(server_hash)
user_state = make_hash(msg, hash, round)
if user_state:
send = ','.join(map(str, user_state))
r.sendline(send)
else:
r.close()
exit()
print(r.recvline())
print(r.recvline())
r.close()
チームメイトのおかげで解けた問題である
Team Mottoの友情・努力・勝利がここで伏線回収となった
感想
最初の問題は結構サクサク解けたのでこの調子でやっちまうか～と思いきや、Partial Tenacityで結構苦労した...（cryptoでDFSを書いたのは初めてだったので良い経験になった）Arrangedでは楕円曲線のパラメータを求める方法があったり、Permutedでは対称群でのDHが出来たりととても勉強になった。
また、今回のCTFで初めてTEAを知ったが、RSAやAES（や古典暗号・エスパー）以外の暗号を見ることが少ないので新鮮でいいなと思った。
全体的に学びが多く、楽しいCTFだった。来年度は時間をしっかり確保して他のジャンルにも挑戦していきたい。