[crypto][HITCON CTF 2023] Share

- 서버는 256비트의 비밀 정보를 가지고 있다.
- 서버는 이 비밀을 여러 조각으로 나눈다. (Shamir Secret Sharing 알고리즘을 사용)
- 각 입력에 대해 서버는 여러 조각 중 n-1개를 제공한다.

Shamir Secret Sharing은 비밀을 분할하고 나누어진 조각 중 일부를 가지고 있어도 원래 비밀을 복원할 수 있는 방법을 제공하는 암호학적인 기술이다. 이 경우  n-1개의 조각을 받고 나머지 하나를 알려주지 않는 서버로부터 비밀을 복원해야 한다.

 

 

약점은 다항식 계수를 생성하는 방법에 있다

getRandomRange(0, self.p - 1). getRandomRange(a, b)가 a와 b 사이의 숫자를 생성한다는 것을 알 수 있으므로 계수는 [a, b) 범위 내에 있을 것이다. 다시 말해 계수는 p-1이 될 수 없다. 즉, 계수는 항상 0부터 p-2 사이의 값을 가질 것이다.

 

 

서버에는 30초의 타임아웃이 있으므로 네트워크 지연을 처리하기 위해 동시에 여러 (p, n) 쌍을 쿼리해야 한다.

이 문장은 서버의 응답 시간이 30초로 제한되어 있으며 네트워크 지연이 발생할 수 있으므로, 동시에 여러 (p, n) 쌍을 동시에 요청하고 처리해야 한다는 것을 의미한다.

이것은 효율적으로 동작하고 시간 내에 작업을 완료하기 위해 여러 요청을 병렬로 처리하는 것을 나타낸다.

 

 

 

공격 코드

from pwn import process, remote
from Crypto.Util.number import sieve_base, long_to_bytes
import ast
from sage.all import GF, crt

primes = list(sieve_base[6:46])  # product > 2**256

# io = process(["python", "server.py"])
io = remote("chal-share.chal.hitconctf.com", 11111)


def batch_oracle(queries):
    payload = "".join([f"{p}\n{n}\n" for p, n in queries])
    io.send(payload.encode())
    ret = []
    for _ in range(len(ps)):
        io.recvuntil(b"shares = ")
        ys = ast.literal_eval(io.recvlineS().strip())
        ret.append(ys)
    return zip(ps, ret)


n = 14
tbl = {p: set(range(p)) for p in primes}
while not all(len(tbl[p]) == 1 for p in primes):
    # a kinda stupid prime selection strategy
    ps = []
    for p in primes:
        if len(tbl[p]) > 1:
            ps += [p] * len(tbl[p]) * 2
    while len(ps) < 4 * max(ps):
        ps += ps
    print("query", len(ps))
    for p, ys in batch_oracle([(p, n) for p in ps]):
        # f(x)=-x^(n-1)+g(x)
        # find g(x) by interpolating (x, y + x^(n - 1)), then we have f(x)
        # note that the coefficient of f(x) must not be -1, so f(0) will be a impossible value of the real F(0)
        R = GF(p)["x"]
        g = R.lagrange_polynomial([(i + 1, y + (i + 1) ** (n - 1)) for i, y in enumerate(ys)])
        f = -R.gen() ** (n - 1) + g
        for i, y in enumerate(ys):
            assert f(i + 1) == y
        tbl[p].discard(f(0))
    for p in primes:
        print(p, tbl[p])

ms = [next(iter(tbl[p])) for p in primes]
secret = int(crt(ms, primes))
io.send(b"0\n0\n")
io.sendlineafter(b"secret = ", str(secret).encode())
print(io.recvallS().strip())

 

 

 

 

참고 github

https://github.com/maple3142/My-CTF-Challenges/blob/master/HITCON%20CTF%202023/Share/solve.py