March 15, 2021 00:00

서론

이 글은 제가 CTF 대회에서 자주 사용하는 toolkit인 github.com/rkm0959/Inequality_Solving_with_CVP의 설명서입니다. 이미 README에 많은 설명이 있지만, 설명서라기에는 부실한 점이 많아 이를 보강합니다.

제가 이 글을 작성하는 목적은

• 이 repository의 존재를 더 많은 사람들에게 홍보하기 위해서
• 이 repository의 기본적인 아이디어를 CTF를 하지 않는 사람들에게도 알리기 위해서
• 이 repository가 더 많은 사람들에게 사용되기를 바라기 때문
• 이 repository의 부족한 점을 보충하기 위해서

입니다. 이 점을 참고하시고 글을 읽어주시면 감사하겠습니다.

이 글에서 모든 나눗셈은 floor function을 거친 결과로 생각하시기 바랍니다.

본론

CVP란 무엇인가

우선 CVP가 무엇인지 알아야 이 도구를 이해할 수 있습니다. 이는 소프트웨어 멤버십 블로그에 있는 rbtree님의 글 “SVP and CVP”에서 이미 잘 설명되어 있지만, 다시 한 번 설명합니다.

선형독립인 $n$차원 벡터 $v_1, \cdots , v_d$가 있다고 합시다. 이때,

라고 합시다. 즉, 각 벡터들의 정수 계수 선형결합을 모은 집합을 생각합니다. 이를 Lattice라고 합니다.

Lattice와 관련된 중요한 문제 중 하나가 바로 CVP, Closest Vector Problem으로, 목표 벡터 $v$가 주어졌을 때 $v$와 가장 가까우면서 $L$에 속한 벡터를 찾는 문제입니다. NP-hard 문제 중 하나지만, 가장 가까운 벡터를 찾는 게 아니라 “꽤 가까운 벡터를 찾는 것”, 즉 문제를 근사적으로 해결하는 것은 Babai’s Nearest Plane Algorithm으로 할 수 있습니다. 자세한 결과는 여기서는 생략하도록 하겠습니다.

이제부터 Babai의 알고리즘의 강력한 힘을 믿으며 논의를 진행하겠습니다.

부등식에서 CVP로

$n$개의 변수와 $m$개의 부등식이 있다고 합시다. 각 변수의 이름을 $x_1, x_2, \cdots, x_n$이라 하고, 부등식의 형태는 모두

형태라고 가정하겠습니다. 단, $lb_j, ub_j$ 및 $a_{ij}$ 들은 모두 정수이며, 원하는 해 $x_i$ 역시 정수입니다.

이제부터 $a_i \le b_i$가 모든 $i$에 대해서 성립할 경우 $(a_1, \cdots , a_n) \preceq (b_1, \cdots , b_n)$이라고 정의합시다.

그러면 우리가 해결하는 문제는

이라 했을 때

라고 쓸 수 있습니다. 이제 ${v_i}$들로 생성되는 Lattice

를 생각하면, 결국 우리가 푸는 문제는 $lb$와 $ub$ 사이에 들어오는 $L$의 원소를 찾는 문제가 됩니다.

이러한 문제를 CVP로 바꾸는 가장 직관적인 방법은

• $lb$와 $ub$의 가운데에 있는 벡터 $v_{target} = (lb + ub) / 2$를 생각한 다음
• 이 벡터를 목표 벡터로 하는 CVP를 해결

하는 것입니다. 성공했다면, 적당한 $v_{result} = \sum_{i=1}^n x_i v_i \in L$을 얻을 수 있습니다.

이제 $x_i$를 복구하는 것이 문제인데, 이에 대해서는 다양한 접근이 가능합니다.

• 많은 경우에서 $lb_j \le x_i \le ub_j$ 형태의 부등식이 사용되고, 이때 $v_{result}$의 $j$번째 항이 $x_i$가 됩니다.
• 많은 경우에서 $n \le m$이고 $v_i$들이 선형독립입니다. 이때는 $v_{result} = \sum_{i=1}^n x_i v_i$를 system of linear equations로 보고 직접 풀 수 있습니다. 이 toolkit은 이 접근을 선택했습니다.

가중치의 사용

위 논의에서 가장 큰 논리의 구멍은

라는 요구조건을

로 바꾼 것에 있습니다. 여기에는 사실 허점이 있는데, 아래의 극단적인 예시를 보면 더욱 명확해집니다.

$lb = (0, 0)$, $ub = (10^{300}, 2)$이 있다고 합시다. 우리의 새로운 요구조건은 $(10^{300}/2, 1)$에 가까운 벡터를 만드는 것입니다. 그렇다면, CVP 알고리즘은 두 번째 entry가 $0$ 이상 $2$ 이하여야 한다는 기존의 요구조건을 무시하고, 첫 번째 entry가 $10^{300}/2$에 최대한 가까워지도록 노력할 것입니다. CVP는 각 entry의 대소를 중요하게 보는 것이 아니라, 두 벡터의 차이의 크기만을 보기 때문에 이러한 문제가 발생하게 되는 것으로 해석할 수 있습니다.

다르게 생각하면, 이는 $lb, ub$ 벡터들의 entry의 스케일이 다르기 때문에 발생하는 문제라고도 볼 수 있습니다. $ub_i - lb_i$의 값이 전체적으로 비슷하다면 위와 같은 문제가 발생할 가능성이 줄어듭니다.

그러니 이 값이 비슷하도록 가중치를 부여합시다.

라고 정의합시다. 이제 $j$번째 부등식에서 $lb_j \neq ub_j$라면, 그에 대한 가중치를 $w_j = M/(ub_j - lb_j)$로 둡시다. 즉,

와 같이 식을 변형합시다. 만약 $lb_j = ub_j$라면 어떻게 할까요? 이 경우에는 $w_j$를 매우 큰 정수로 잡아줍시다.

특히, $lb_j = ub_j$인 경우에 큰 가중치를 잡으면 된다는 것은 직접적으로 설명할 수 있습니다. 큰 가중치 $w_j$를 걸어

를 얻었다고 합시다. 만약 $\sum_{i=1}^n (a_{ij}w_j) \cdot x_i$가 $w_j \cdot lb_j = w_j \cdot ub_j$와 달랐다면, 그 차이는

가 됩니다. 즉, CVP 결과가 $j$번째 부등식을 만족시키지 못한다면 차이 벡터의 크기가 $w_j$ 이상이라는 결론을 얻습니다. CVP는 차이 벡터의 크기를 최소한으로 만들고자 하는데, $j$번째 부등식을 만족시키지 못한다면 매우 큰 크기의 벡터가 나오는 게 강제되므로, CVP는 $j$번째 부등식을 만족시킬 수 밖에 없습니다. 더욱 정확한 논의를 위해서는 CVP 문제와 determinant의 관계 등 더 많은 정보가 필요하지만, 직관적으로는 이미 충분히 납득할 수 있을 것이라고 생각합니다. 이렇게 가중치까지 걸어주면, 문제를 해결하기 위한 모든 준비가 끝납니다.

휴리스틱

CTF와 암호 체계를 깨는 context에서 중요한 또 다른 점은, 주어진 식을 만족하는 $x_i$들의 유일성입니다. 이를 증명하는 것은 어려운 일이지만, 휴리스틱을 통해서 해의 개수를 근사하는 것은 어렵지 않습니다. $n = m$과 $v_i$들의 선형독립성을 가정하겠습니다. CTF 문제풀이에서는 많은 경우에서 성립합니다.

에서 시작합시다. $lb$와 $ub$ 사이에 있는 벡터들이 이루는 영역의 부피는

라고 쓸 수 있습니다. 또한, $\sum_{i=1}^n x_i v_i$ 형태의 선형결합에 대응되는 부피는, $B$를 $v_1, v_2, \cdots, v_n$을 column vector로 갖는 행렬이라 했을 때 $\lvert \det(B) \rvert$임은 이미 잘 알려져 있는 사실입니다.

그러니, 답이 되는 $(x_1, \cdots, x_n)$의 개수는 대강

와 같다고 볼 수 있겠습니다. 이 값이 지나치게 크다면 다른 접근을 시도하는 것이 현명합니다.

$n \neq m$인 경우에도 비슷한 분석을 할 수 있을 것으로 보이나, 대부분의 경우 $n = m$이므로 생략합니다.

구현

SageMath 구현체는 다음과 같습니다. rbtree님의 LLL repository를 참고하였습니다.

from sage.modules.free_module_integer import IntegerLattice

# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
	M = IntegerLattice(mat, lll_reduce=True).reduced_basis
	G = M.gram_schmidt()[0]
	diff = target
	for i in reversed(range(G.nrows())):
		diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
	return target - diff


def solve(mat, lb, ub, weight = None):
	num_var  = mat.nrows()
	num_ineq = mat.ncols()

	max_element = 0 
	for i in range(num_var):
		for j in range(num_ineq):
			max_element = max(max_element, abs(mat[i, j]))

	if weight == None:
		weight = num_ineq * max_element

	# sanity checker
	if len(lb) != num_ineq:
		print("Fail: len(lb) != num_ineq")
		return

	if len(ub) != num_ineq:
		print("Fail: len(ub) != num_ineq")
		return

	for i in range(num_ineq):
		if lb[i] > ub[i]:
			print("Fail: lb[i] > ub[i] at index", i)
			return

	# heuristic for number of solutions
	DET = 0

	if num_var == num_ineq:
		DET = abs(mat.det())
		num_sol = 1
		for i in range(num_ineq):
			num_sol *= (ub[i] - lb[i])
		if DET == 0:
			print("Zero Determinant")
		else:
			num_sol //= DET
			# + 1 added in for the sake of not making it zero...
			print("Expected Number of Solutions : ", num_sol + 1)

	# scaling process begins
	max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
	applied_weights = []

	for i in range(num_ineq):
		ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
		applied_weights.append(ineq_weight)
		for j in range(num_var):
			mat[j, i] *= ineq_weight
		lb[i] *= ineq_weight
		ub[i] *= ineq_weight

	# Solve CVP
	target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
	result = Babai_CVP(mat, target)

	for i in range(num_ineq):
		if (lb[i] <= result[i] <= ub[i]) == False:
			print("Fail : inequality does not hold after solving")
			break
    
	# recover x
	fin = None

	if DET != 0:
		mat = mat.transpose()
		fin = mat.solve_right(result)
	
	# recover your result
	return result, applied_weights, fin

위 코드는 행렬 mat, 벡터 lb, ub와 자연수 weight를 받습니다.

• mat은 부등식의 $a_{ij}$에 해당하는 $n \times m$ 행렬입니다.
• lb, ub는 말 그대로 $lb, ub$에 해당하는 벡터입니다.
• weight는 필요한 경우에만 넘기면 되는 인자로, $lb_i = ub_i$일 때 줄 가중치의 값입니다.

sanity check를 통과하지 못한 경우, 그 이유를 말해줍니다.

• 전달받은 데이터의 차원이 맞지 않는다던가
• $lb \preceq ub$ 조차 성립하지 않는다던가

그 후, $n = m$이면 휴리스틱을 통해 예상되는 해의 개수를 출력합니다.

• 만약 determinant가 0이라면, 이를 알려줍니다.
• 아니라면, 휴리스틱의 공식을 통해서 예상되는 해의 개수를 알려줍니다.
• 이 예상되는 해의 개수가 지나치게 큰 경우, 다른 접근을 시도하는 게 현명합니다.

최종 출력 결과는 세 벡터 result, applied_weights, fin입니다.

• result는 CVP의 결과 벡터 $v_{result}$입니다.
• applied_weights는 말 그대로 적용된 가중치입니다.
• 특히, result는 가중치가 적용된 벡터이므로, 이에 주의하여 답을 복구해야 합니다.
• fin은 $x_i$들의 값을 갖고 있는 벡터로, $x_i$들을 복구하기 위해서 선형방정식을 푼 결과입니다.

답이 잘 나오지 않는다면, 가중치를 직접 바꾸어가며 다시 시도하는 것도 방법입니다.

예시 문제 - SECCON CTF 2020 sharsable

from Crypto.Util.number import getPrime, GCD
from flag import FLAG
import random
 
def egcd(a, b):
    r0, r1 = a, b
    s0, s1 = 1, 0
    t0, t1 = 0, 1
    while r1 > 0:
        q = r0 // r1
        r0, r1 = r1, r0 % r1
        s0, s1 = s1, s0 - q * s1
        t0, t1 = t1, t0 - q * t1
    return s0, t0
 
def generateKey():
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    phi = (p-1)*(q-1)
 
    while True:
        d1 = getPrime(int(n.bit_length()*0.16))
        e1 = random.randint(1, phi)
        ed1 = e1 * d1 % phi
 
        d2 = getPrime(int(n.bit_length()*0.16))
        e2, k = egcd(d2, phi)
        e2 = e2 * (phi + 1 - ed1) % phi
        ed2 = e2 * d2 % phi
 
        if GCD(e1, e2) > 10:
            break
 
    assert((ed1 + ed2) % phi == 1)
 
    return (n, (e1, d1), (e2, d2))
 
n, A, B = generateKey()
M = int.from_bytes(FLAG, 'big')
C1 = pow(M, A[0], n)
C2 = pow(M, B[0], n)
assert(pow(C1, A[1], n) * pow(C2, B[1], n) % n == M)
 
import json
print(json.dumps({
    "n": n,
    "A": (A[0], C1),
    "B": (B[0], C2),
    #"d": (A[1], B[1]), # for debug
    }))

문제를 해결한 당시의 writeup은 https://rkm0959.tistory.com/165 를 참고합시다.

문제에서 주어진 조건은

• $d_1, d_2$는 대략 $n^{0.16}$ 이하로 작은 편
• $e_1d_1 + e_2d_2 \equiv 1 \pmod{\phi(n)}$
• $gcd(e_1, e_2) > 10$이므로 common modulus attack 사용 불가능

문제에서 우리의 목표는 $d_1, d_2$를 복원하는 것입니다. 풀이를 위해서는 먼저

이 성립함을 확인합시다. 여기서 $k$는 정수이고, $e_1, e_2 < n$이므로 $d_1, d_2 < n^{0.16}$이므로 $k < 2 \cdot n^{0.16}$입니다.

또한, $p + q < 3\sqrt{n/2}$인 점을 이용하면, 대략

을 얻습니다. 이는 새로운 변수 $d_3$을 하나 잡으면,

으로 쓸 수 있습니다. 이 부등식과 이미 아는 부등식

을 합치면, 변수 3개, 부등식 3개를 얻습니다. 이제 위 도구를 사용하여 $d_1, d_2$를 복원하면 됩니다.

# Example Challenge 2 in https://github.com/rkm0959/Inequality_Solving_with_CVP

# find actual data in the repository :)
n  = 
e_1 = 
C_1 = 
e_2 = 
C_2 = 

# build matrix
M = matrix(ZZ, 3, 3)

# encode d_1
M[0, 0] = 1 

# encode d_2
M[1, 1] = 1 

# encode e_1d_1 + e_2d_2 + nd_3
M[0, 2] = e_1
M[1, 2] = e_2
M[2, 2] = n

# build lb/ub
lb = [0, 0, -int(n ** 0.66 * 3 * sqrt(2))]
ub = [int(n ** 0.16), int(n ** 0.16), 0]

# solve system
res, weights, fin = solve(M, lb, ub)

d_1 = int(fin[0])
d_2 = int(fin[1])

val = (pow(C_1, d_1, n) * pow(C_2, d_2, n)) % n
print(long_to_bytes(val))

특수 케이스

지금까지 우리는 linear inequality의 system을 CVP로 해결했습니다. 하지만 매우 특수한 경우에서는 더욱 효율적이고 강력한 알고리즘이 존재합니다. 이제부터 우리가 다룰 문제는

형태의 문제입니다. 이는 사실 조금만 생각해보면

과 동일한 문제임을 알 수 있습니다. 여기서 주의해야 할 점이 있습니다.

이라는 부등식의 의미가 생각하는 것과 다를 수 있습니다.

$0$부터 시작해서 $M-1$까지 갔다가 다시 $0$으로 돌아오는 시계 같은 원을 하나 생각을 합시다. 여기서 위 부등식의 의미는, $Ax \pmod{M}$이 $L$에서 시작해서 시계방향으로 $R$에서 끝나는 “원호” 위에 존재한다는 것입니다.

예를 들어, 충분히 큰 $M$에 대해서

의 의미는 $Ax \pmod{M} = M-2 ,M-1, 0, 1$이라는 뜻입니다.

이 문제의 특별한 점은,

을 만족하는 최소의 음이 아닌 정수 $x$를 찾는 것이 빠르게 된다는 점입니다.

그 원리를 여기에 설명하기에는 너무 길어지니, 제 PS 정수론 가이드 https://rkm0959.tistory.com/188 와 Codeforces Good Bye 2014의 G번, NWRRC 2019의 G번을 참고하시기 바랍니다.

이제 기존의 문제도 해결할 수 있습니다. 먼저

가 있으면, $L’ \equiv L - AS \pmod{M}$, $R’ \equiv R - AS \pmod{M}$을 생각하고

으로 식을 바꿀 수 있습니다. 이제

을 만족하는 최소의 음이 아닌 정수 $t$을 찾아줍시다. 이제 풀어야 하는 문제는

이므로, 다시 $L’’ = L’ - (t+1)S \pmod{M}$, $R’’ = R’ - (t+1)S \pmod{M}$이라 하고

을 만족하는 최소의 음이 아닌 정수를 찾고, 이를 $x$에 대한 허용 구간이 공집합이 될 때까지 반복하면 됩니다.

확률적으로 생각하면, 해의 개수는 대략

개 정도 있을 것이라고 생각할 수 있습니다. 이 값이 크면 다른 접근을 사용하는 것이 좋겠습니다.

구현

python3에서 구현을 했습니다.

from Crypto.Util.number import GCD

def ceil(n, m): # returns ceil(n/m)
	return (n + m - 1) // m

def is_inside(L, R, M, val): # is L <= val <= R in mod M context?
	if L <= R:
		return L <= val <= R
	else:
		R += M
		if L <= val <= R:
			return True
		if L <= val + M <= R:
			return True 
		return False

## some notes : it's good idea to check for gcd(A, M) = 1
def optf(A, M, L, R): # minimum nonnegative x s.t. L <= Ax mod M <= R
	if L == 0:
		return 0
	if 2 * A > M:
		L, R = R, L
		A, L, R = M - A, M - L, M - R
	cc_1 = ceil(L, A)
	if A * cc_1 <= R:
		return cc_1
	cc_2 = optf(A - M % A, A, L % A, R % A)
	return ceil(L + M * cc_2, A)

# check if L <= Ax (mod M) <= R has a solution
def sol_ex(A, M, L, R):
	if L == 0 or L > R:
		return True
	g = GCD(A, M)
	if (L - 1) // g == R // g:
		return False
	return True

## find all solutions for L <= Ax mod M <= R, S <= x <= E:
def solve(A, M, L, R, S, E):
	# this is for estimate only : if very large, might be a bad idea to run this
	print("Expected Number of Solutions : ", ((E - S + 1) * (R - L + 1)) // M + 1)
	if sol_ex(A, M, L, R) == False:
		return []
	cur = S - 1
	ans = []
	num_sol = 0
	while cur <= E:
		NL = (L - A * (cur + 1)) % M
		NR = (R - A * (cur + 1)) % M
		if NL > NR:
			cur += 1
		else:
			val = optf(A, M, NL, NR)
			cur += 1 + val
		if cur <= E:
			ans.append(cur)
			# remove assert for performance if needed
			assert is_inside(L, R, M, (A * cur) % M)
			num_sol += 1
	print("Actual Number of Solutions : ", num_sol)
	return ans

solve 함수를 호출하여 원하는 $x$의 list를 얻을 수 있습니다.

만약 예상되는 해의 개수가 지나치게 많다면, 다른 접근을 생각하는 것이 현명합니다.

예시 문제 - PBCTF 2020 Special Gift

from Crypto.Util.number import getStrongPrime, inverse, bytes_to_long, GCD as gcd
from Crypto.Random.random import randint
from flag import flag
 
p = getStrongPrime(512)
q = getStrongPrime(512)
N = p * q
phi = (p - 1) * (q - 1)
 
# Hehe, boi
while True:
    d = randint(int(N ** 0.399), int(N ** 0.4))
    if gcd(d, phi) == 1:
        break
 
e = inverse(d, phi)
 
# Here's a special gift. Big.
gift = d >> 120
 
enc = pow(bytes_to_long(flag), e, N)
 
print("N =", N)
print("e =", e)
print("gift =", gift)
print("enc =", enc)

첫 예시 문제와 동일한 식

를 생각합시다. 이번에는 $d < n^{0.4}$이므로 $k < n^{0.4}$이고, $p+q < 3 \sqrt{n/2}$를 이용하면 대략

를 얻습니다. 좌변의 상수 $3$은 매우 넉넉하게 잡은 것입니다.

그런데 $gift = \lfloor d / 2^{120} \rfloor$를 알고 있으니, $d = gift \cdot 2^{120} + c$라고 쓸 수 있습니다. 이제

를 얻고, 동시에 $0 \le c < 2^{120}$이니, 위 알고리즘을 적용할 환경이 준비가 됩니다.

휴리스틱을 적용하면 대략 $2^{120} \cdot 3 \cdot n^{-0.1} \approx 6 \cdot 10^5$개의 해가 나올 것을 예상할 수 있습니다.

이를 전부 구하고, 각 $c$에 대하여 decryption을 시도해보면 flag를 얻을 수 있습니다.

# find actual data in the repository! 
N = 
e = 
gift = 
enc = 
 
R = (-e * (gift << 120)) % N
L = (-e * (gift << 120) - 3 * (int)(N ** 0.9)) % N

val = solve(e, N, L, R, 0, 1 << 120)
num_sol = len(val)

for i in tqdm(range(num_sol)):
	d = (gift << 120) + val[i]
	s = long_to_bytes(pow(enc, d, N))
	if s[:5] == b"pbctf":
		print(s)

결론 및 후기

지금까지 제 repository “Inequality Solving with CVP”의 기본 원리를 알아보았고, 실제 CTF에서 출제된 문제들을 풀어보면서 사용법도 알아보았습니다. Lattice를 활용하는 많은 문제가 이 도구를 활용하여 해결될 수 있으니, 많이 사용해주시면 정말 기쁠 것 같습니다. RSA 관련 문제를 예시로 들었으나, Hidden Number Problem, Linear Congruential Generator 등 문제를 선형적인 방정식으로 나타낼 수 있다면 이 방법을 시도할 수 있습니다. repository에 예시 문제가 위에서 소개한 것을 포함해서 총 8문제가 있으니, 참고해주시기 바랍니다.

Lattice를 사용하는 대표적인 암호를 깨는 알고리즘에는

• Coppersmith’s Algorithm을 사용한 polynomial root 계산
• 이 글에서 다루는, Linear System of Inequality를 만들고 해결

이 있습니다. (정보를 더 원하신다면, https://eprint.iacr.org/2020/1506.pdf 를 참고해주세요)

첫 알고리즘의 경우에는 dicegang의 defund라는 분이 만든 repository인 “defund/coppersmith” 가 있습니다. 제 repository는 두 번째 알고리즘에 집중하는 것으로 볼 수 있는데, 제 구현체도 defund의 구현체처럼 많은 사람들이 사용해주었으면 좋겠습니다. 긴 글 읽어주셔서 감사합니다. 질문은 rkm0959.tistory.com에서 받습니다.