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. 앞 블록 비교 (1회 사용)
  2. 두 블록 xor한 값 체크 (2회 사용)
  3. 잘 잘 xor하다가보면 f^4(0)의 값을 두 가지 방법으로 생성 가능한데, 그 값 비교 (데이터베이스에 저장되는 쌍을 함수 f와 같이 표현하였다.) (3회 사용)
  4. f(a + f(b))의 값과 f^-1(a + f^-1(b))의 값을 알 수 있다는 전제조건을 놓고, 입력값 두개들을 볶다 보면 4회 사용해서 다른 경로를 통한 같은 결과를 얻을 수 있다. (4회 사용)
  5. 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}