2024/07/11に公開

# 結果

UIUCTF 2024をチーム「脆弱エンジニア(full_weak_engineer)」で参加してきました。

# Cryptography

## X Marked the Spot (93 Passengers, 531 Solves)✅

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:

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


このことは、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!')

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!


## Key in a Haystack (461 pt, 65 Solves)

ncatで接続して入出力をするタイプの問題

from Crypto.Util.number import getPrime
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

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:

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つやることがあります。その両方がわかりませんでした。

1. 512bit以上の巨大なカーマイケル数cを求めて入力すること
2. 入力したcよりも小さい数akに対して、a^k(mod c) が与えられたときに、kを答えること

### 1. 巨大なカーマイケル数を求める

(6k+1)(12k+1)(18k+1)

### 2. 離散対数問題を解く

そもそも a^k(mod c)`からkを求めるような問題を離散対数問題（DLP: Discrete Logarithm Problem）というらしい。（知らなかった）

# おわりに

チーム「脆弱エンジニア(full_weak_engineer)」では、SECCON CTF決勝進出を目指してCTFに参加しています！