⛳
UIUCTF 2024 脆弱Writeup
結果
UIUCTF 2024をチーム「脆弱エンジニア(full_weak_engineer)」で参加してきました。
Cryptography
X Marked the Spot (93 Passengers, 531 Solves)✅
問題
暗号ファイルctが与えられている
from itertools import cycle
flag = b"uiuctf{????????????????????????????????????????}"
# len(flag) = 48
key = b"????????"
# len(key) = 8
ct = bytes(x ^ y for x, y in zip(flag, cycle(key)))
with open("ct", "wb") as ct_file:
ct_file.write(ct)
キーとXORをしているという暗号。
キーが不明なので、自明な復号文「uiuctf{}」と暗号のXORをとることでキーを特定した。
def decrypt(ciphertext, key):
return bytes(c ^ k for c, k in zip(ciphertext, cycle(key)))
with open("ct", "rb") as ct_file:
ct = ct_file.read()
dt = decrypt(ct, b"uiuctf{}")
print(dt)
# b'hdiqbfjb-yCxc5eSie/Met%~iR~gb_%`(=Cf~3N?si=37!0q'
これでkeyが hdiqbfjq であると判明する。
key = b"hdiqbfjq"
dt = decrypt(ct, key)
print(dt)
# b'uiuctf{n0t_ju5t_th3_st4rt_but_4l50_th3_3nd!!!!!}'
uiuctf{n0t_ju5t_th3_st4rt_but_4l50_th3_3nd!!!!!}
Without a Trace (246 Passengers, 298 Solves)✅
問題
ncatで接続して入出力をするタイプの問題
import numpy as np
from Crypto.Util.number import bytes_to_long
from itertools import permutations
from SECRET import FLAG
def inputs():
print("[WAT] Define diag(u1, u2, u3. u4, u5)")
M = [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
]
for i in range(5):
try:
M[i][i] = int(input(f"[WAT] u{i + 1} = "))
except:
return None
return M
def handler(signum, frame):
raise Exception("[WAT] You're trying too hard, try something simpler")
def check(M):
def sign(sigma):
l = 0
for i in range(5):
for j in range(i + 1, 5):
if sigma[i] > sigma[j]:
l += 1
return (-1)**l
res = 0
for sigma in permutations([0,1,2,3,4]):
curr = 1
for i in range(5):
curr *= M[sigma[i]][i]
res += sign(sigma) * curr
return res
def fun(M):
f = [bytes_to_long(bytes(FLAG[5*i:5*(i+1)], 'utf-8')) for i in range(5)]
F = [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
]
for i in range(5):
F[i][i] = f[i]
try:
R = np.matmul(F, M)
return np.trace(R)
except:
print("[WAT] You're trying too hard, try something simpler")
return None
def main():
print("[WAT] Welcome")
M = inputs()
if M is None:
print("[WAT] You tried something weird...")
return
elif check(M) == 0:
print("[WAT] It's not going to be that easy...")
return
res = fun(M)
if res == None:
print("[WAT] You tried something weird...")
return
print(f"[WAT] Have fun: {res}")
if __name__ == "__main__":
main()
ncatで接続すると、5つの数字を入力して値が得られる。
[WAT] Welcome
[WAT] Define diag(u1, u2, u3. u4, u5)
[WAT] u1 = 1
[WAT] u2 = 1
[WAT] u3 = 1
[WAT] u4 = 1
[WAT] u5 = 1
[WAT] Have fun: 2000128101369
uiを対角成分とする行列と、flagを5分割したlongを対角成分とする行列の積のトレース(対角成分の和)がfunとして出力される。
uiの一つだけを2として、差分を取ると、flagの一部がわかる。
[WAT] u1 = 2
[WAT] u2 = 1
[WAT] u3 = 1
[WAT] u4 = 1
[WAT] u5 = 1
[WAT] Have fun: 2504408575853
f1 = 2504408575853 - 2000128101369
long_to_bytes(f1)
# b'uiuct'
f1 = 2504408575853 - 2000128101369
>>> long_to_bytes(f1)
b'uiuct'
>>> f2 = 2440285994541-2000128101369
>>> long_to_bytes(f2)
b'f{tr4'
>>> f3 = 2426159182680-2000128101369
>>> long_to_bytes(f3)
b'c1ng_'
>>> f4 = 2163980646766-2000128101369
>>> long_to_bytes(f4)
b'&&_mu'
>>> f5 = 2465934208374-2000128101369
>>> long_to_bytes(f5)
b'lt5!}'
uiuctf{tr4c1ng_&&_mult5!}
Naptime (363 Passengers, 180 Solves)✅
問題
a = [66128, 61158, 36912, 65196, 15611, 45292, 84119, 65338]
ct = [273896, 179019, 273896, 247527, 208558, 227481, 328334, 179019, 336714, 292819, 102108, 208558, 336714, 312723, 158973, 208700, 208700, 163266, 244215, 336714, 312723, 102108, 336714, 142107, 336714, 167446, 251565, 227481, 296857, 336714, 208558, 113681, 251565, 336714, 227481, 158973, 147400, 292819, 289507]
from random import randint
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
import numpy as np
def get_b(n):
b = []
b.append(randint(2**(n-1), 2**n))
for i in range(n - 1):
lb = sum(b)
found = False
while not found:
num = randint(max(2**(n + i), lb + 1), 2**(n + i + 1))
if num > lb:
found = True
b.append(num)
return b
def get_MW(b):
lb = sum(b)
M = randint(lb + 1, 2*lb)
W = getPrime(int(1.5*len(b)))
return M, W
def get_a(b, M, W):
a_ = []
for num in b:
a_.append(num * W % M)
pi = np.random.permutation(list(i for i in range(len(b)))).tolist()
a = [a_[pi[i]] for i in range(len(b))]
return a, pi
def enc(flag, a, n):
bitstrings = []
for c in flag:
# c -> int -> 8-bit binary string
bitstrings.append(bin(ord(c))[2:].zfill(8))
ct = []
for bits in bitstrings:
curr = 0
for i, b in enumerate(bits):
if b == "1":
curr += a[i]
ct.append(curr)
return ct
def dec(ct, a, b, pi, M, W, n):
# construct inverse permuation to pi
pii = np.argsort(pi).tolist()
m = ""
U = pow(W, -1, M)
ct = [c * U % M for c in ct]
for c in ct:
# find b_pi(j)
diff = 0
bits = ["0" for _ in range(n)]
for i in reversed(range(n)):
if c - diff > sum(b[:i]):
diff += b[i]
bits[pii[i]] = "1"
# convert bits to character
m += chr(int("".join(bits), base=2))
return m
def main():
flag = 'uiuctf{I_DID_NOT_LEAVE_THE_FLAG_THIS_TIME}'
# generate cryptosystem
n = 8
b = get_b(n)
M, W = get_MW(b)
a, pi = get_a(b, M, W)
# encrypt
ct = enc(flag, a, n)
# public information
print(f"{a = }")
print(f"{ct = }")
# decrypt
res = dec(ct, a, b, pi, M, W, n)
if __name__ == "__main__":
main()
encodeにaしか使っていないので、全てのascii文字をaでencしたのちに、対応するものに置換すればいい
import string
a = [66128, 61158, 36912, 65196, 15611, 45292, 84119, 65338]
ct = [273896, 179019, 273896, 247527, 208558, 227481, 328334, 179019, 336714, 292819, 102108, 208558, 336714, 312723, 158973, 208700, 208700, 163266, 244215, 336714, 312723, 102108, 336714, 142107, 336714, 167446, 251565, 227481, 296857, 336714, 208558, 113681, 251565, 336714, 227481, 158973, 147400, 292819, 289507]
strings = string.printable
encrypt_all = enc(strings, a)
dict = {}
for s, al in zip(strings, encrypt_all):
dict[al] = s
for c in ct:
print(dict[c], end='')
uiuctf{i_g0t_sleepy_s0_I_13f7_th3_fl4g}
Determined (322 Passengers, 222 Solves)✅
問題
ncatで接続して入出力をするタイプの問題
from SECRET import FLAG, p, q, r
from Crypto.Util.number import bytes_to_long
n = p * q
e = 65535
m = bytes_to_long(FLAG)
c = pow(m, e, n)
# printed to gen.txt
print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
n = 158794636700752922781275926476194117856757725604680390949164778150869764326023702391967976086363365534718230514141547968577753309521188288428236024251993839560087229636799779157903650823700424848036276986652311165197569877428810358366358203174595667453056843209344115949077094799081260298678936223331932826351
e = 65535
c = 72186625991702159773441286864850566837138114624570350089877959520356759693054091827950124758916323653021925443200239303328819702117245200182521971965172749321771266746783797202515535351816124885833031875091162736190721470393029924557370228547165074694258453101355875242872797209141366404264775972151904835111
from Crypto.Util.number import bytes_to_long, long_to_bytes
from itertools import permutations
from SECRET import FLAG, p, q, r
def inputs():
print("[DET] First things first, gimme some numbers:")
M = [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
]
try:
M[0][0] = p
M[0][2] = int(input("[DET] M[0][2] = "))
M[0][4] = int(input("[DET] M[0][4] = "))
M[1][1] = int(input("[DET] M[1][1] = "))
M[1][3] = int(input("[DET] M[1][3] = "))
M[2][0] = int(input("[DET] M[2][0] = "))
M[2][2] = int(input("[DET] M[2][2] = "))
M[2][4] = int(input("[DET] M[2][4] = "))
M[3][1] = q
M[3][3] = r
M[4][0] = int(input("[DET] M[4][0] = "))
M[4][2] = int(input("[DET] M[4][2] = "))
except:
return None
return M
def handler(signum, frame):
raise Exception("[DET] You're trying too hard, try something simpler")
def fun(M):
def sign(sigma):
l = 0
for i in range(5):
for j in range(i + 1, 5):
if sigma[i] > sigma[j]:
l += 1
return (-1)**l
res = 0
for sigma in permutations([0,1,2,3,4]):
curr = 1
for i in range(5):
curr *= M[sigma[i]][i]
res += sign(sigma) * curr
return res
def main():
print("[DET] Welcome")
M = inputs()
if M is None:
print("[DET] You tried something weird...")
return
res = fun(M)
print(f"[DET] Have fun: {res}")
if __name__ == "__main__":
main()
行列式からp, qを求めて、そのp, qでRSAを復号するという問題。
行列式の値は a*c*g*h*r - a*d*g*h*q + b*c*e*i*r - b*c*f*h*r - b*d*e*i*q + b*d*f*h*q - c*g*i*p*r + d*g*i*p*q であり、b, d, e, iのみを1にすれば行列式がqになる。
このことは、pythonで以下のように計算できる。
from sympy import symbols, Matrix
p, q, r = symbols('p q r')
# a, b, c, d, e, f, g, h, i = symbols('a b c d e f g h i')
a = b = c = d = e = f = g = h = i = 0
b = d = f = h = 1
M = Matrix([
[p, 0, a, 0, b],
[0, c, 0, d, 0],
[e, 0, f, 0, g],
[0, q, 0, r, 0],
[h, 0, i, 0, 0]
])
det_M = M.det()
print(det_M) # -> q
これをncatに接続して、それらの値を入力するとqが得られる。
[DET] Welcome
[DET] First things first, gimme some numbers:
[DET] M[0][2] = 0
[DET] M[0][4] = 1
[DET] M[1][1] = 0
[DET] M[1][3] = 1
[DET] M[2][0] = 0
[DET] M[2][2] = 1
[DET] M[2][4] = 0
[DET] M[4][0] = 1
[DET] M[4][2] = 0
[DET] Have fun: 12538849920148192679761652092105069246209474199128389797086660026385076472391166777813291228233723977872612370392782047693930516418386543325438897742835129
pはnから求められるので、これで復号できる。
from Crypto.Util.number import *
n = 158794636700752922781275926476194117856757725604680390949164778150869764326023702391967976086363365534718230514141547968577753309521188288428236024251993839560087229636799779157903650823700424848036276986652311165197569877428810358366358203174595667453056843209344115949077094799081260298678936223331932826351
e = 65535
c = 72186625991702159773441286864850566837138114624570350089877959520356759693054091827950124758916323653021925443200239303328819702117245200182521971965172749321771266746783797202515535351816124885833031875091162736190721470393029924557370228547165074694258453101355875242872797209141366404264775972151904835111
q = 12538849920148192679761652092105069246209474199128389797086660026385076472391166777813291228233723977872612370392782047693930516418386543325438897742835129
p = n//q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)
print("flag:", flag)
Snore Signatures (416 Passengers, 122 Solves)✅
問題
ncatで接続して入出力をするタイプの問題
#!/usr/bin/env python3
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long
from Crypto.Random.random import getrandbits, randint
from Crypto.Hash import SHA512
LOOP_LIMIT = 2000
def hash(val, bits=1024):
output = 0
for i in range((bits//512) + 1):
h = SHA512.new()
h.update(long_to_bytes(val) + long_to_bytes(i))
output = int(h.hexdigest(), 16) << (512 * i) ^ output
return output
def gen_snore_group(N=512):
q = getPrime(N)
for _ in range(LOOP_LIMIT):
X = getrandbits(2*N)
p = X - X % (2 * q) + 1
if isPrime(p):
break
else:
raise Exception("Failed to generate group")
r = (p - 1) // q
for _ in range(LOOP_LIMIT):
h = randint(2, p - 1)
if pow(h, r, p) != 1:
break
else:
raise Exception("Failed to generate group")
g = pow(h, r, p)
return (p, q, g)
def snore_gen(p, q, g, N=512):
x = randint(1, q - 1)
y = pow(g, -x, p)
return (x, y)
def snore_sign(p, q, g, x, m):
k = randint(1, q - 1)
r = pow(g, k, p)
e = hash((r + m) % p) % q
s = (k + x * e) % q
return (s, e)
def snore_verify(p, q, g, y, m, s, e):
if not (0 < s < q):
return False
rv = (pow(g, s, p) * pow(y, e, p)) % p
ev = hash((rv + m) % p) % q
return ev == e
def main():
p, q, g = gen_snore_group()
print(f"p = {p}")
print(f"q = {q}")
print(f"g = {g}")
queries = []
for _ in range(10):
x, y = snore_gen(p, q, g)
print(f"y = {y}")
print('you get one query to the oracle')
m = int(input("m = "))
queries.append(m)
s, e = snore_sign(p, q, g, x, m)
print(f"s = {s}")
print(f"e = {e}")
print('can you forge a signature?')
m = int(input("m = "))
s = int(input("s = "))
# you can't change e >:)
if m in queries:
print('nope')
return
if not snore_verify(p, q, g, y, m, s, e):
print('invalid signature!')
return
queries.append(m)
print('correct signature!')
print('you win!')
print(open('flag.txt').read())
if __name__ == "__main__":
main()
シュノア署名という署名をもとにしているプログラムが与えられる。
ncatで接続すると、以下のようなシステムが起動する。
p, q, g, yが与えられて、mを入力すると、署名 s, eが返ってくる。
それとは別のm'とs'で、署名eに一致させろという問題。
p = 109209066141807392469405595465187459273369967921728111542567242595112404916342690454285397621930076453496003590991838351066774673306928855520193745287564950083813139764854414615127205988933586905505281819217599581479252971612472652136366988245976618823829452863749997238139763588956861758186037025761304760753
q = 7629750578096748202658418580547995112281126470301009906044508404386239120434292891314177422914820906892607425104293040733175910558998798909913656934725267
g = 47191888352053227759059858012922735775503179004565929629913888638329033309064641922299429307318787464741060946313753098359304033263361786559984184147807821868176788122588498592208714175922593903199328200693389254427447333113429193259817107981388613361140866202042332337044180718447663065213503819629478794554
y = 93950421061185658286946016516247433692440797277471726012824619469670179000923983402424032659446290145701798840673201585209025702749878145639892622862530192709911385665826038654500647099216849667118966959826346506619961501563563381870909161548759421120786635473446164491814183713143543354496966379170466888877
you get one query to the oracle
m = 1
s = 1311307973298048076172640907309448458296284528052358967047212185866127049738255201502110203408969734911175170859675235750454088044489705899729154509473374
e = 2209494284037388945668860814495759837405234531881097574297892162532500854607997679357265122793766710538983958001113271513227831185188099974339413709322190
can you forge a signature?
m = 109209066141807392469405595465187459273369967921728111542567242595112404916342690454285397621930076453496003590991838351066774673306928855520193745287564950083813139764854414615127205988933586905505281819217599581479252971612472652136366988245976618823829452863749997238139763588956861758186037025761304760754
s = 1311307973298048076172640907309448458296284528052358967047212185866127049738255201502110203408969734911175170859675235750454088044489705899729154509473374
correct signature!
これを同じp, q, gに対して、異なるmで10回繰り返せばflagが手に入る。
eとe'を一致させるには、それらを求める際のハッシュの中身 (r + m) % p, (rv + m') % p を一致させる必要がある。
pを法とするため、m' = m + p とすると、ハッシュの中身が一致させられる。
つまり、m'= m + p, s' = s と入力すれば署名を一致させられる。
y = 34035276224524954893208000980628600711865976201265455073865551772967144412294024713810700021506557604284873534824461902953673000689918595670242254793730451153307019792783593355702978412641727843766177970606168841765832573180897511369114367451577952325632598607912472467975608809696595694795051700662709943633
you get one query to the oracle
m = 10
s = 6545618322499217781242137816051026179532863801702111986787221541670833168959449990150459641411960703898862679733406192645787359378343949680317712429535529
e = 107879661878472587768713432955786342109615785097730937435435535599927027392760832059010236262836172951504508512330129324297542606019958141697808331330764
can you forge a signature?
m = 109209066141807392469405595465187459273369967921728111542567242595112404916342690454285397621930076453496003590991838351066774673306928855520193745287564950083813139764854414615127205988933586905505281819217599581479252971612472652136366988245976618823829452863749997238139763588956861758186037025761304760763
s = 6545618322499217781242137816051026179532863801702111986787221541670833168959449990150459641411960703898862679733406192645787359378343949680317712429535529
correct signature!
you win!
uiuctf{add1ti0n_i5_n0t_c0nc4t3n4ti0n}
uiuctf{add1ti0n_i5_n0t_c0nc4t3n4ti0n}
Key in a Haystack (461 pt, 65 Solves)
問題
ncatで接続して入出力をするタイプの問題
from Crypto.Util.number import getPrime
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import md5
from math import prod
import sys
from secret import flag
key = getPrime(40)
haystack = [ getPrime(1024) for _ in range(300) ]
key_in_haystack = key * prod(haystack)
enc_flag = AES.new(
key = md5(b"%d" % key).digest(),
mode = AES.MODE_ECB
).encrypt(pad(flag, 16))
sys.set_int_max_str_digits(0)
print(f"enc_flag: {enc_flag.hex()}")
print(f"haystack: {key_in_haystack}")
exit(0)
解けなかったので復習。
AESのkeyが40bitの素数だが、これが1024bitの素数300個と掛けられていて、この巨大すぎる数をどうにかして素因数分解しなければならない。
p-1法(Pollard's p − 1)という素因数分解のアルゴリズムを用いるらしい。
もしくは、素因数分解サイトで2時間ぐらいかけて出てくるらしい。自分もこれを使っていたのだけど、30分ほどで99%に達して以降動きがなかったので、断念してしまった。そのまま放置していればよかったのか？
参考
Groups (431 pt, 105 Solves)
問題
ncatで接続して入出力をするタイプの問題
from random import randint
from math import gcd, log
import time
from Crypto.Util.number import *
def check(n, iterations=50):
if isPrime(n):
return False
i = 0
while i < iterations:
a = randint(2, n - 1)
if gcd(a, n) == 1:
i += 1
if pow(a, n - 1, n) != 1:
return False
return True
def generate_challenge(c):
a = randint(2, c - 1)
while gcd(a, c) != 1:
a = randint(2, c - 1)
k = randint(2, c - 1)
return (a, pow(a, k, c))
def get_flag():
with open('flag.txt', 'r') as f:
return f.read()
if __name__ == '__main__':
c = int(input('c = '))
if log(c, 2) < 512:
print(f'c must be least 512 bits large.')
elif not check(c):
print(f'No cheating!')
else:
a, b = generate_challenge(c)
print(f'a = {a}')
print(f'a^k = {b} (mod c)')
k = int(input('k = '))
if pow(a, k, c) == b:
print(get_flag())
else:
print('Wrong k')
解けなかったので復習。
この問題は大きく2つやることがあります。その両方がわかりませんでした。
- 512bit以上の巨大なカーマイケル数
cを求めて入力すること - 入力した
cよりも小さい数aとkに対して、a^k(mod c)が与えられたときに、kを答えること
1. 巨大なカーマイケル数を求める
英語版のWikipediaには、以下の式で求める方法が載っていて、みんなこれで計算して求めていた。
当然、日本語版には載っていない。英語版しか勝たん。
2. 離散対数問題を解く
そもそも a^k(mod c)からkを求めるような問題を離散対数問題（DLP: Discrete Logarithm Problem）というらしい。（知らなかった）
今後この問題が出てきたら離散対数問題でggろう。
他の人のwriteupには、Pohlig–Hellman法やBaby-step Giant-step法を使って解いているみたい。
参考
おわりに
チーム「脆弱エンジニア(full_weak_engineer)」では、SECCON CTF決勝進出を目指してCTFに参加しています！
チームでCTFをやりたいメンバーを常に募集していますので、YouTubeの概要欄にあるDiscordリンクから、気軽にご参加ください！
Pwn, Rev担当大歓迎（切実）
Discussion