[Codegate CTF 2020 Finals] sculptor

chall.py

#!/usr/bin/env python3.6
from secrets import randbelow
from operator import mul, xor
from functools import reduce
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from Crypto.Util.number import bytes_to_long as b2l

N = 32
RING = (1 << 64) - 1
HINT = 100
HIDDEN = 32


class Random:

    def __init__(self, ring, n):
        self.ring = ring
        self.n = n
        self.c = [randbelow(ring) for _ in range(n)]
        self.s = [randbelow(ring) for _ in range(n)]

    def f(self):
        return sum(map(mul, self.c, self.s)) % self.ring

    def update(self):
        self.s = self.s[1:] + [self.f()]
        return self.s[-1]


if __name__ == '__main__':
    r = Random(RING, N)
    print(r.c)

    [r.update() for _ in range(N ** 2)]

    hints = [r.update() >> HIDDEN for _ in range(HINT)]
    print(hints)

    [r.update() for _ in range(N ** 2)]

    size = RING.bit_length() // 4
    flag = pad(open('flag.txt', 'rb').read(), size)

    key = reduce(xor, r.s + r.c) ** 2
    key = key.to_bytes(size, byteorder='big')
    cipher = AES.new(key, AES.MODE_ECB)
    enc_flag = cipher.encrypt(flag).hex()

    print(enc_flag)

 

32bits hints 100개, c가 주어져 있다.

100개의 update 값에 대해 하위 모르는 32bit를 y라고 두자.

f 함수와 주어 값들을 통해 후 68개의 y 값들을 앞의 32개의 y 값으로 표현 가능하다.

n = (1 << 64) - 1
y = PolynomialRing(Integers(n), 32, 'y').gens()

y2 = []
for i in range(32):
    y2.append(0)

for i in range(32, 100):
    tmp = 0
    for j in range(32):
        if (i-32+j) < 32:   
            tmp += y[i+j-32] * c[j]
        else:
            tmp += y2[i-32+j] * c[j]
        tmp += (h[i + j - 32] << 32) * c[j] 
    tmp -= (h[i] << 32)
    y2.append(tmp)

data = []
data1 = []

for i in range(x):
    data.append(vector(ZZ, y2[99-i].coefficients()))
    data1.append(int(y2[99-i].coefficients()[32]))
data1 = vector(data1)

 

y 값을 알아내기 위해서는 CVP(Closet Vector Problem)을 풀어야한다는 사실을 추측할 수 있다.

 

앞서 구한 값들을 통해 lattice를 만들면, 크기가 100*100인 matrix와 y 값들로 이루어진 벡터가 그 lattice에 속한다.

CVP를 효과적으로 수행하기 위해 1<<31을 더해주어 벡터의 차이가 최소화되고 그 차이가 음수도 될 수 있도록 만들어준다.

x=64
def babai1(A, w):
    C = max(max(row) for row in A.rows())
    B = matrix([list(row) + [0] for row in A.rows()] + [list(w) + [C]])
    B = B.LLL(delta=0.9)
    return w - vector(B.rows()[-1][:-1])

data0 = vector([1<<31] * 32 + list(data1))

for i in range(32, 32+x):
    data0[i] = n-data1[i-32] + (1<<31)

M = matrix(32+x)
for i in range(32+x):
    if i < 32:
        M[i, i] = 1
        for j in range(x):
            M[i, 32 + j] = data[j][i]
    else:
        M[i, i] = (1 << 64) - 1

data2=(babai1(M, data0))
tmp = []
for i in range(32):
    tmp.append(data2[i])
for i in range(32,32+x):
    tmp.append(data2[i] + data1[i-32] - n)

print(tmp[:32])

[1972144224, 2627872095, 25616827, 2546659650, 1486700945, 3135390776, 1645382154, 3270169363, 4022243039, 1105862731, 1531958259, 858484709, 2387452042, 2898936390, 2232410918, 2656271523, 2681765966, 314333569, 1103213179, 2785173453, 3238467204, 1214172424, 3198812070, 676224441, 1206100467, 280956036, 3219171367, 46386436, 3748391170, 1850995786, 2975153847, 945238126]

최종적으로 32개의 y 값을 구할 수 있었고, 주어진 hints 값과 합쳐 초기 32개의 s 값을 알아낼 수 있었다.

이를 통해 key를 구한 후 flag를 딸 수 있었다.

CODEGATE2020{Lattices_are_so_fxxking_cool}

추가적으로 cvp를 통해 원하는 해가 나오는 조건에 대해서 공부해야겠다.

(아마 Minkowski theorem과 연관있지 않을까...)

#github.com/timmykang/study/blob/master/codegate2020/final/sculptor/sol.sage