[Kaist-Postech 2020] - Baby Bubmi

예전에 포스팅했던 카이스트 - 포스텍 해킹전 문제들 중에 Baby Bubmi 라는 문제가 있었다. RBTree 님의 블로그에서 따온 문제이다. 예전에는 RBTree 님의 블로그를 보고 풀이도 참고하면서 풀었던 문제이지만, 이번에는 풀이 없이 문제만 보고 풀어보자! 하고 다시 포스팅해보게 되었다. (여기서 못풀면 레전드)

🖲️ Code Analysis

자, 그럼 코드를 살펴보자. 이 문제는 Cryptohack.org 워게임 사이트의 Real Eisenstein 문제와 거의 유사한 문제인데, 관심있으면 풀어보고 오시길 ~ (맨 처음에 아인슈타인이라고 읽음 ㅋㅋ)

#!/usr/bin/env python3

from decimal import *
import math
import random
import struct

from flag import flag

primes = [2]
for i in range(3, 100):
    f = True
    for j in primes:
        if i * i < j:
            break
        if i % j == 0:
            f = False
            break
    if f:
        primes.append(i)

# Random shuffle the primes
# Now you cannot know the order
seed = struct.unpack('<i', flag[5:9])[0]
random.seed(seed)
random.shuffle(primes)

# Use ln function
# Now you cannot know the key itself
getcontext().prec = 100
keys = []
for i in range(len(flag)):
    keys.append(Decimal(primes[i]).ln())

# Sum values
# Now you cannot know the flag
sum_ = Decimal(0.0)
for i, c in enumerate(flag):
    sum_ += c * Decimal(keys[i])

ct = math.floor(sum_ * 2 ** 256)
print(ct)

먼저, 코드는 매우 짧다. 마지막에 sum_ 이라는 변수를 이용해서 c * key[i] 를 함으로써 KnapSack 암호화 알고리즘이라는 것이 드러났고, 이는 곧 LLL 로 해결할 수 있을 것이라는 생각까지 든다. 

 

그러면 각 알고리즘이 어떻게 되는지 알아보자.

처음에 2부터 100까지의 정수 중 소수만을 뽑아내고 flag[5:9] 까지의 값으로 이 소수들을 shuffle 한다. 그 후에 ln() 함수를 통해서 log 를 취해준다. (e 를 밑으로 하는..)

 

이렇게 만들어진 key 를 통해서 아까 말했던 Knapsack 암호화 알고리즘을 실행하는데, 간단하니 보고 오는 것도 낫배드한 선택일지도  >>>> Knapsack Algorithm

💡 Main Idea

자, 여기서 아까 말했던 LLL 알고리즘이 쓰인다. LLL 알고리즘에 대해서 자세하게 기술하는 것은 문제 하나에서 하기에는 너무 방대한 양이기 때문에 나중에 따로 Theory 부분을 만들어 포스팅하겠다..(하겠지)

 

여튼 간단하게 LLL 알고리즘에 대해서 말해보자면, 여러 벡터들이 주어졌을 때 그 벡터들로 좌표평면에 n차 공간을 만들어 격자를 표시할 수 있다. 주어진 벡터들을 같은 격자를 표현하는 다른 벡터들로 치환함으로써 가장 짧은 벡터들로 구성하는 것이다. 다시 말하면 원점에 가장 가까운 격자를 찾는 행위로도 표현할 수 있겠다. 

 

예를 들어 (3,4) 라는 벡터와 (5,6) 이라는 벡터가 주어져 이 벡터들로 격자를 구성했을 때, (1,1) 에도 격자가 존재함과 동시에, 둘 중 하나를 (1,1) 이라는 벡터로 치환해도 같은 격자가 나타나는 것을 이해할 수 있을 것이다. 

 

자, 그럼 이게 앞선 알고리즘과 무슨 상관이냐..?? 라는 생각이 들면 정상이다. 많은 설명보다는 간단한 수식이 더 이해가 잘 갈 것 같으니 다음 행렬을 살펴보자. 

$$\begin{bmatrix}
1 & 0 & \cdots & 0 & 0 & keys[0] \\
0 & 1 & 0 & 0 & 0 & keys[1] \\
\vdots & 0 & \ddots & 0 & \vdots & \vdots \\
0 & 0 & 0 & 1 & 0 & keys[n-1] \\
0 & 0 & \cdots & 0 & 1 & keys[n] \\
0 & 0 & 0 & 0 & 0 & ct \\
\end{bmatrix}$$

 

이런 행렬에서 가장 짧은 행렬을 만들기 위해서 LLL 알고리즘을 사용한다면 어떤 일이 벌어질까? 마지막 행에 있는 $ct$ 의 값은 다른 여러 행들의 값과 비교해서 매우 큰 수이기 때문에 이 수를 줄이도록 LLL 알고리즘이 움직일 것이다. 따라서 여러 행들을 더하고 빼며, $ct$ 의 값을 매우 작게 만들기 위해서 노력할 것이다. 

 

이 결과로써 우리는 $ct$ 와 같은 열에 존재하는 여러 $keys[i]$ 들이 더하고 빼지면서 $ct$ 의 값이 0 에 수렴하게 되고, 우리는 이를 가시적으로 나타내기 위해 1 이라는 값을 각 열마다 삽입함으로써 눈으로 확인할 수 있다. 

 

사실 이 방식은 모든 Knapsack 에서는 사용할 수는 없는 방식이기에, 특정한 경우 (Low Density) 의 경우에만 사용할 수 있다. 조건이나 수학적 증명에 관심있는 분들은 참고하길 바란다. Knapsack - Low Density Attack

추가로, 원래 Low Density Attack 에서는 마지막 행들을 1/2 로 정의함으로써 더 작은 벡터를 만들도록 유도한다. ( 기존의 Knapsack 은 0 아니면 1 이니까 중간값인 1/2 로 정의) 

하지만, 이 문제에서는 0 부터 128 (Ascii Code) 만큼 움직이기 때문에 그 중간값인 64 로 정의하면 문제를 더 빨리 풀 수 있을 것이다. (필수인지는 모르겠다..)

📖 Exploit Code

하지만 원래 코드에서는 math.floor 이라는 함수를 통해서 sum 의 값을 대충 연산시킨다. 따라서 바로 LLL 을 사용하면 오차가 있을 수 있기 때문에, 각 수에 n 을 곱해가면서 LLL 을 사용해보도록 하자. 

from decimal import *
import math
from random import *
import struct
from sage.all import *
from tqdm import tqdm
from itertools import *

ct = 737384863737803670841307970259513146291422299366557325168325233349136771464845311

getcontext().prec = int(100)

primes = [2]
for i in range(3, 100):
    f = True
    for j in primes:
        if i * i < j:
            break
        if i % j == 0:
            f = False
            break
    if f:
        primes.append(i)

keys = []
for i in range(len(primes)):
    keys.append(Decimal(int(primes[i])).ln())

def check(row):
    _sum = Decimal(0.0)
    for i in range(len(keys)):
        _sum += int(row[i]) * Decimal(keys[i])
    if math.floor(_sum * 2 ** 256) == ct:
        return True
    else:
        return False

def find(n):
    Matrix = list()
    for i in range(len(keys)):
        row = [0 for _ in range(len(keys)+1)]
        row[i] = 1
        row[-1] = int(keys[i] * pow(2,256)) * n
        Matrix.append(row)

    row = [64 for _ in range(len(keys))]
    row.append(ct * n)
    Matrix.append(row)

    Mat = matrix(Matrix)
    Mat = Mat.LLL()
    return Mat

shuffled_flag = None

for num in range(10000):
    res = find(num)
    num += 1
    finish = False
    for rows in res:
        valid = True
        for c in rows[:-1]:
            if c > 64 or c < -64:
                valid = False
                break
        if valid:
            ans = [int(c+64) for c in rows[:-1]]
            if check(ans):
                shuffled_flag = bytes(ans)
                finish = True
    if finish:
        break
print(shuffled_flag)

이렇게 N 을 곱해서 LLL 을 사용하는 함수를 만들어주고, 계속해서 1 씩 늘려나가며 제대로 된 rows 가 있는지 확인한다. 절댓값이 64 보다 작아야 ascii code 의 범위를 만족하기에 1차로 필터링해주고, 2차적으로 sum 을 생성하는 동일한 알고리즘을 사용하여 검산작업을 마친다.  

 

따라서 이를 실행해보면 다음과 같은 값이 나오게 된다. 

 

음,, 왜 NULL 값이 껴져 있는지는 자세히 모르겠지만 이 값이 flag 를 shuffle 한 값이라는 것은 확신할 수 있다. 

따라서 seed 를 flag[5:9] 를 이용해서 정의했기 때문에, 모든 seed 를 브루트포싱하여 flag 형식에 맞는 것을 찾아주도록 하자. 

import random
from itertools import *
from tqdm import tqdm
import struct

shuffled = b's31\x00a1r1tge4ns3nf\x00_{\x00l3\x00}'
char = [c for c in shuffled if c > 0]
length = len(shuffled)

for secret in tqdm(permutations(char,4)):
    seed = struct.unpack('<i', bytes(secret))[0]
    random.seed(seed)

    idx = [i for i in range(length)]
    random.shuffle(idx)

    flag = [shuffled[i] for i in idx]

    if b"flag{" in bytes(flag):
        print(bytes(flag))

이렇게 itertools 라이브러리를 사용하면 쉽게 문제를 해결할 수 있다. 이렇게 flag 를 출력시켜보자. 

 

Flag : flag{r341_e1s3nst13n}