cd ~
2023 Wacon Quals
With Team “사이코랑”
Crypto - Cry
ImaginaryCTF 2023에 출제된 sus와 컨셉이 동일하다.
중요한 점은 order = p^4 - 1이 되는 modulo를 찾고, 그 modulo에는 4, 2차항, 상수항만이 존재하게 해서, 임의의 a + bx^2꼴의 다항식의 order이 p^2 - 1이 되게 하는 것이 포인트이다.
즉 order = p^4 - 1이라면 (p^2 + 1)제곱을 해주면 1, 3차항이 0이 되어버린다(mod p). 즉 그 항과 n의 gcd를 통해서 p를 확률적으로 잘 추출해주면 해결할 수 있다.
ex.sage
import random
from Crypto.Util.number import *
exec(open("output", "r").read())
for n in [n0, n1, n2][::-1]:
P.<x> = PolynomialRing(Zmod(n))
while True:
poly = x^4 + random.randrange(0, n) * x^2 + random.randrange(0, n)
y = P.quotient(poly).gen()
p = gcd(n // 2, ZZ(list((y + 1)^n)[1]))
if p > 1: break
q = (p^2 + 1) // 2
r = n // (2 * p * q)
assert p * q * r * 2 == n
phi = (p - 1) * (q - 1) * (r - 1)
d = pow(65537, -1, phi)
c = pow(c, d, n)
print(long_to_bytes(c).decode())
WACON2023{75e7511bccf428abfb98da2226b5712ce709a9fc9b92ad1b0a3ccb5f2b1cd772}
Crypto - PSS
알려져있는 3 * 2^17개의 시드가 해쉬 후 결과가 되는 입력시드를 단 한쌍만 찾으면 된다.
시드가 40비트이므로 2^40 / (3 * 2^17) = 2^23 / 3으로 합리적 시간 안에 찾을 수 있을 것으로 생각할 수 있다. 물론 충돌쌍이 있을 수도 있지만 필자는 처음 찾은 쌍이 다행히도 올바른 결과를 나타내었다.
ex1.py (쌍 찾기)
from tqdm import *
import os
from hashlib import sha256
f = open("pss_data", "rb").read()
datas = []
for i in range(2**17):
datas.append(f[24 * i:24 * (i + 1)])
lefts = []
rights = []
left = bytes.fromhex("03eb593699")
sd = bytes.fromhex("df16fd90dd")
merkle_proof_indexes = {
0 : [2,4,8],
1 : [2,4,7],
2 : [2,3,10],
3 : [2,3,9],
4 : [1,6,12],
5 : [1,6,11],
6 : [1,5,14],
7 : [1,5,13],
}
for data in datas:
seeds = data[:15]
idx = data[15]
final_perm = data[16:]
assert idx in range(8)
assert set(bytes.hex(final_perm)) == set("0123456789abcdef")
known_idx = merkle_proof_indexes[idx]
for i in range(3):
block = seeds[5 * i:5 * (i + 1)]
if block == left:
print(data)
if known_idx[i] % 2 == 0:
rights.append(block)
else:
lefts.append(block)
rights = set(rights)
lefts = set(lefts)
def cascade_hash(msg, cnt, digest_len):
assert digest_len <= 32
msg = msg * 10
for _ in range(cnt):
msg = sha256(msg).digest()
return msg[:digest_len]
for i in trange(100000000):
sd = os.urandom(5)
res = cascade_hash(sd, 123, 10)
left, right = res[:5], res[5:]
if left in lefts:
print("left yay")
print(bytes.hex(left), bytes.hex(sd))
if right in rights:
print("right yay")
print(bytes.hex(right), bytes.hex(sd))
ex2.py (쌍에서 플래그 구하기)
from hashlib import sha256
data = b'Q\x00\xc3\xce\x84J\x0f_\xda\x13\x03\xebY6\x99\x07l\xdbS\x04z(\x9f\x1e'
left = bytes.fromhex("03eb593699")
sd = bytes.fromhex("df16fd90dd")
merkle_proof_indexes = {
0 : [2,4,8],
1 : [2,4,7],
2 : [2,3,10],
3 : [2,3,9],
4 : [1,6,12],
5 : [1,6,11],
6 : [1,5,14],
7 : [1,5,13],
}
seeds = data[:15]
idx = data[15]
final_perm = data[16:]
assert idx in range(8)
assert set(bytes.hex(final_perm)) == set("0123456789abcdef")
known_idx = merkle_proof_indexes[idx]
def cascade_hash(msg, cnt, digest_len):
assert digest_len <= 32
msg = msg * 10
for _ in range(cnt):
msg = sha256(msg).digest()
return msg[:digest_len]
assert idx == 7
# print(bytes.hex(seeds))
assert cascade_hash(sd, 123, 2 * 5)[:5] == left
sd_1 = seeds[:5]
sd_5 = seeds[5:10]
sd_13 = seeds[10:]
sd_3 = cascade_hash(sd_1, 123, 2 * 5)[:5]
sd_4 = cascade_hash(sd_1, 123, 2 * 5)[5:]
sd_6 = sd
sd_7 = cascade_hash(sd_3, 123, 2 * 5)[:5]
sd_8 = cascade_hash(sd_3, 123, 2 * 5)[5:]
sd_9 = cascade_hash(sd_4, 123, 2 * 5)[:5]
sd_10 = cascade_hash(sd_4, 123, 2 * 5)[5:]
sd_11 = cascade_hash(sd_5, 123, 2 * 5)[:5]
sd_12 = cascade_hash(sd_5, 123, 2 * 5)[5:]
assert cascade_hash(sd_6, 123, 2 * 5)[:5] == sd_13
sd_14 = cascade_hash(sd_6, 123, 2 * 5)[5:]
sds = [sd_7, sd_8, sd_9, sd_10, sd_11, sd_12, sd_13, sd_14]
def seed_to_permutation(seed):
permutation = ''
msg = seed + b"_shuffle"
while len(permutation) < 16:
msg = cascade_hash(msg, 777, 32)
msg_hex = msg.hex()
for c in msg_hex:
if c not in permutation:
permutation += c
return permutation
perms = [seed_to_permutation(s) for s in sds]
# print(perms)
final_perm = bytes.hex(final_perm)
# print(final_perm)
final_perm = [int(f, 16) for f in final_perm]
# print(final_perm)
for prm in perms[::-1]:
perm = [int(f, 16) for f in prm]
new = [0] * 16
for i in range(16):
new[i] = perm[final_perm[i]]
final_perm = new
print(final_perm)
flag = ""
for p in final_perm:
flag += hex(p)[2:]
flag = "WACON2023{" + flag + '}'
print(flag)
WACON2023{2d4b7a9c085316ef}
Crypto - Push It To The Limit
coppersmith를 사용하라는 것처럼 보이는 문제이다.
시행착오를 통해 엡실론은 0.495, 베타는 1/70일 때, 497비트만이 미정이면 거의 올바르게 복구할 수 있다는 사실을 알고, 홀수임을 이용해 한 비트를 줄여, 512 - 497 - 1 = 14비트 전수조사를 통해 해결하였다.
ex.sage
from tqdm import tqdm
n = 24712...51733
c = 19285...78159
p_msb = 16140...70880
P.<x> = PolynomialRing(Zmod(n), implementation='NTL')
my_beta = 0.495
my_epsilon = 1 / 70
for heh in tqdm(range(16383, -1, -1)):
p_my = p_msb + heh * 2^498
f = p_my + 2 * x + 1
f = f.monic()
d = f.small_roots(X=2**(498 - 1), beta=my_beta, epsilon=my_epsilon)
if len(d):
print("Wowwwwoww!!!!!")
print(heh)
print(d[0])
exit()
else:
continue
이와 같은 스크립트에서 range를 쪼개주고 여러 개의 sage를 실행하였다. 여러 개를 실행하는데도 속도가 별로 안 느려지는게 신기하였다.
약 4시간 동안 돌린 후 다행히도 해가 구해졌다.
$ sage /tmp/b.sage
90%|███████████████████████████████████████████████████████████████████████████████████▊ | 1351/1500 [2:34:39<17:02, 6.86s/it]Wowwwwoww!!!!!
2851
249800943630024136145803445084606303022516653078010197146428883394554884755273605753816967684870390326319283282607480102657345513185585350265162906557
final.sage
n = 24712...51733
c = 19285...78159
p_msb = 16140...70880
heh = 2851
root = 249800943630024136145803445084606303022516653078010197146428883394554884755273605753816967684870390326319283282607480102657345513185585350265162906557
p_my = p_msb + heh * 2^498
p = p_my + 2 * root + 1
q = n // p
assert p * q == n
phi = (p - 1) * (q - 1)
d = pow(65537, -1, phi)
m = pow(c, d, n)
from Crypto.Util.number import *
print(long_to_bytes(m))
WACON2023{flatter=>https://eprint.iacr.org/2023/237.pdf}
Crypto - White arts
재미있는 문제였던 Dark arts와 컨셉이 비슷했지만, 딱히 그때처럼 LLL을 써야 하는 기믹은 없어서 아쉬웠다. 각 단계들 모두 생각보다 straightforward했다.
- 앞 블록 비교 (1회 사용)
- 두 블록 xor한 값 체크 (2회 사용)
- 잘 잘 xor하다가보면 f^4(0)의 값을 두 가지 방법으로 생성 가능한데, 그 값 비교 (데이터베이스에 저장되는 쌍을 함수 f와 같이 표현하였다.) (3회 사용)
- f(a + f(b))의 값과 f^-1(a + f^-1(b))의 값을 알 수 있다는 전제조건을 놓고, 입력값 두개들을 볶다 보면 4회 사용해서 다른 경로를 통한 같은 결과를 얻을 수 있다. (4회 사용)
- 3, 4단계보다 훨씬 쉬웠다. 모든 256개의 값을 xor해주었을때 0인지를 체크하면 된다. 단지, 256개가 모두 필요하므로 앞 단계에서 정확히 1, 2, 3, 4회씩만 사용해야 한다.
ex.sage
from pwn import *
TEST = False
if TEST:
io = process(["python3", "prob.py"])
else:
io = remote("175.118.127.63", 2821)
def solve_gen1():
io.sendlineafter("> ", "1")
for i in range(40):
io.sendline("00" * 16)
io.sendline("n")
io.recvuntil("> ")
io.recvuntil("> ")
if io.recv(16).decode() == "00" * 8:
io.sendlineafter("> ", "0")
else:
io.sendlineafter("> ", "1")
def solve_gen2():
io.sendlineafter("> ", "2")
for i in range(40):
io.sendline("00" * 16)
io.sendline("n")
io.recvuntil("> ")
io.recvuntil("> ")
res1 = bytes.fromhex(io.recvline()[:-1].decode())
io.sendline("11" * 8 + "00" * 8)
io.sendline("n")
io.recvuntil("> ")
io.recvuntil("> ")
res2 = bytes.fromhex(io.recvline()[:-1].decode())
if xor(res1[:8], res2[:8]) == b"\x11" * 8:
io.sendlineafter("> ", "0")
else:
io.sendlineafter("> ", "1")
def solve_gen3():
io.sendlineafter("> ", "3")
for i in range(40):
io.sendline("00" * 16)
io.sendline("n")
io.recvuntil("> ")
io.recvuntil("> ")
res1 = bytes.fromhex(io.recvline()[:-1].decode())
ff0 = res1[:8]
f0_fff0 = res1[8:]
io.sendline(bytes.hex(b"\x00" * 8 + f0_fff0))
io.sendline("y")
io.recvuntil("> ")
io.recvuntil("> ")
res2 = bytes.fromhex(io.recvline()[:-1].decode())
ffff0 = res2[8:]
io.sendline(bytes.hex(b"\x00" * 8 + ff0))
io.sendline("n")
io.recvuntil("> ")
io.recvuntil("> ")
res3 = bytes.fromhex(io.recvline()[:-1].decode())
ffff0_2 = xor(res3[:8], ff0)
if ffff0 == ffff0_2:
io.sendlineafter("> ", "0")
else:
io.sendlineafter("> ", "1")
def solve_gen4():
io.sendlineafter("> ", "4")
def get_fafb(a, b):
to_send = xor(b, a) + a
io.sendline(bytes.hex(to_send))
io.sendline("n")
io.recvuntil("> ")
io.recvuntil("> ")
return xor(bytes.fromhex(io.recvline()[:-1].decode()), a)
def get_fafb_1(a, b):
to_send = xor(b, a) + a
io.sendline(bytes.hex(to_send))
io.sendline("y")
io.recvuntil("> ")
io.recvuntil("> ")
return xor(bytes.fromhex(io.recvline()[:-1].decode()), a)
for i in range(40):
zvec = b"\x00" * 8
a1 = b"\x11" * 8
a2 = b"\x22" * 8
a3 = b"\x33" * 8
step1 = get_fafb(a1, zvec)
step2 = get_fafb_1(a2, step1)
step3 = get_fafb(a3, step2)
res = get_fafb(zvec, zvec) == step3
if res:
io.sendlineafter("> ", "0")
else:
io.sendlineafter("> ", "1")
def solve_gen5():
io.sendlineafter("> ", "256")
for i in range(40):
for k in range(256):
io.sendline(bytes.hex(bytes([k])))
io.sendline("n")
tot = 0
for k in range(256):
io.recvuntil("(y/n)? > ")
tot ^^= bytes.fromhex(io.recvline()[:-1].decode())[0]
if tot == 0:
io.sendlineafter("> ", "0")
else:
io.sendlineafter("> ", "1")
solve_gen1()
solve_gen2()
solve_gen3()
solve_gen4()
solve_gen5()
io.interactive()
WACon2023{930db8b4dedb8cb86f309521011a1039}
WACon2023{c7a47ff1646698d275602dce1355645684f743f1}
Misc - Let me win
61개의 변수들을 설정하여 z3으로 조건을 부여해주면 해결된다.
처음에는 z3과 같은 걸로 안 풀리고 수학적으로 풀어야 될 줄 알고 생각보다 삽질했는데, 조건이 꽤나 널널했다.
ex.py
import os
import requests
from Crypto.Util.number import *
team_n = 61
reqscore = open("reqscore", "r").read().split("\n")
assert len(reqscore) == team_n
db = {'Upper Guesser': [3, 4, 5, 7, 8, 9, 10, 11, 15, 16, 17, 18, 20, 22, 23, 25, 26, 28, 29, 30, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 49], ... 'squareimentary': [0, 2, 3, 5, 7, 11, 16, 17, 22, 23, 29, 30, 33, 37, 38, 41, 43, 44, 46]}
assert len(db) == team_n
tot = []
for k in db:
tot += db[k]
solves = [0] * 50
for i in range(50):
solves[i] = tot.count(i)
for team in db:
res = []
for k in db[team]:
res.append(solves[k])
res.sort()
db[team] = res
# print(db)
from z3 import *
s = Solver()
arr = [Int('arr[%d]'%i) for i in range(61)]
for i in range(61):
s.add(arr[i] > 0)
# print(arr)
sc = [0] * 62
sc[61] = arr[60]
for i in range(60, 0, -1):
sc[i] = sc[i + 1] + arr[i - 1]
for i in range(60):
higher_score = 0
for k in db[reqscore[i]]:
higher_score += sc[k]
lower_score = 0
for k in db[reqscore[i + 1]]:
lower_score += sc[k]
# print(higher_score)
s.add(higher_score > lower_score)
print(s.check())
arr = s.model()
arr[0]
여기서 나온 해를 다음 코드에 집어넣는다.
ex2.py
arr = [0] * 61
arr[11] = 26,
arr[22] = 53,
...
arr[47] = 1,
arr[59] = 15,
for i in range(61):
arr[i] = arr[i][0]
# print(arr)
score = [0] * 62
score[61] = arr[60]
for i in range(60, 0, -1):
score[i] = score[i + 1] + arr[i - 1]
print(score[1:])
[3644, 3475, 3474, 2964, 2963, 2921, 2920, 2919, 2822, 2713, 2712, 2711, 2685, 2663, 2650, 2642, 2478, 2477, 2446, 2436, 2159, 2158, 2114, 2061, 1703, 1702, 1701, 1471, 1470, 1469, 1200, 1199, 1076, 1075, 1074, 982, 981, 980, 979, 841, 822, 821, 820, 640, 639, 576, 575, 525, 524, 523, 522, 267, 266, 265, 181, 180, 179, 178, 177, 176, 161]
WACON{e0d1708636f669cd7596d6d81efcb1e117f}