[Kaist-Postech 2020] - fixed point revenge

 

 

이번 문제도 마찬가지로 카포전에 출제된 문제이다. 기존의 fixed point 문제 아이디어를 따와서 더욱 어렵게 만든(?) 것이라고 볼 수 있는데, 이 문제를 통해서 GF 가 크립토에 어떻게 적용되는지 등을 알 수 있었다. 개인적으로 매우 좋은 문제라고 생각하고,, 출제하신 rbtree 님께 박수를 👏👏

🖲️ Code Analysis

먼저 이 문제에서는 CRC64 라는 암호화 알고리즘이 등장한다. 사실 CRC64 알고리즘은 막 정의되어 있는 것이 아니긴 하지만, 대충 보고 오면 이해가 편하지 않을까..?

순환 중복 검사 - 위키백과, 우리 모두의 백과사전

사실 난 안보고 왔으니 안 보고 와도 되긴 하지 않을까? 죄송합니다.

 

그럼 바로 문제의 코드를 살펴보도록 하자.

#!/usr/bin/env python3
from binascii import unhexlify

def crc64(x):
    crc = 0

    x += b'\x00' * 8
    for c in x:
        crc ^= c
        for i in range(8):
            if crc & (1 << 63) == 0:
                crc = crc << 1
            else:
                crc = crc << 1
                crc = crc & 0xFFFFFFFFFFFFFFFF
                crc = crc ^ 0xd39d6612f6bcad3f

    ret = []
    for i in range(8):
        ret.append(crc & 255)
        crc >>= 8

    return bytes(ret[::-1])

inp_hex = input("> ")
inp = unhexlify(inp_hex)
assert len(inp) == 8, "Hey, check the length"

def f(s):
    ret = []
    for c in s:
        ret.append(inp[int(c)])
    return bytes(ret)

def g(t, s):
    return t + b"{" + f(s) + b"}"

def xor(a, b):
    return bytes([c1 ^ c2 for c1, c2 in zip(a, b)])

constraints = [
    [b"rbtree",   "01234567", "12345670", b'\x36\xb0\x16\xf7\x5f\x42\xa9\xf6'],
    [b"mathboy7", "12345670", "23456701", b'\x36\x94\xe4\xfc\x56\x1b\x9a\x5d'],
    [b"rubiya",   "23456701", "34567012", b'\xa8\xd8\x3a\xd2\x8d\x13\x4b\x16'],
    [b"bincat",   "34567012", "45670123", b'\xfc\x7f\xcc\xbe\xf9\xbc\x1b\xf6'],
    [b"5unkn0wn", "45670123", "56701234", b'\x08\xea\xb4\xc6\xc3\x3e\x12\x4f'],
    [b"saika",    "56701234", "67012345", b'\x68\x0c\xe0\x7e\x6f\xa7\xe4\x36'],
    [b"juno",     "67012345", "70123456", b'\x18\x7e\x80\xb9\x54\x7b\x35\xa7'],
    [b"wooeng",   "01234567", "76543210", b'\xc1\x5b\xe0\x2f\x1b\xf8\xb3\xaf']
]

for person, input_order, output_order, const in constraints:
    assert xor(crc64(g(person, input_order)), f(output_order)) == const, "WRONG :("

print("ERAI!")
print("Here's your flag")
print("flag{" + inp_hex + "}")

여기서 일단 f 함수나 g 함수에 대한 설명은 간단하니 생략하도록 하고, 대망의 CRC 함수를 살펴보도록 하자. CRC64 함수는 얼핏 보면 복잡하게 보일 수 있지만, 갈루아 필드를 곁들이면 그냥 수학 계산이 된다. 

 

GF 상에서는 XOR 연산은 단순한 더하기 연산이 되고, shift 연산 또한 x 를 곱하는 연산으로 변형되기 때문에 나와 있는 수식들을 사칙연산으로 단순화 시킬 수 있다. GF 에 대해서 알고 싶다면 아래 블로그를 참고..!!

[정보보호] 갈로아 체 GF(p), 아벨군

그럼 crc 함수만 따로 코드를 살펴보자.  

def crc64(x):
    crc = 0

    x += b'\x00' * 8
    for c in x:
        crc ^= c
        for i in range(8):
            if crc & (1 << 63) == 0:
                crc = crc << 1
            else:
                crc = crc << 1
                crc = crc & 0xFFFFFFFFFFFFFFFF
                crc = crc ^ 0xd39d6612f6bcad3f

    ret = []
    for i in range(8):
        ret.append(crc & 255)
        crc >>= 8

뒤에 8 개의 Null 바이트를 붙이고, 각 바이트마다 crc 와 xor 을 한다. 그 후에 계속 왼쪽으로 shift 하면서 범위를 벗어날 때 특정한 수와 xor 을 통해서 다시 줄이게 된다. 

 

여기서 "범위를 벗어나면 XOR" 이라는 말은 GF 에서의 계산을 의미한다. 0xdf~~ 의 숫자에 해당하는 polynomial 을 찾아서 그 다항식을 modulus 로 하는 GF 를 형성해주게 되면 GF 상에서의 계산으로 변경할 수 있다. 

 

그렇다면 그냥 GF 상에서 $x^8$ 을 해주는 작업이라고 생각할 수 있고, 모든 과정을 합쳐보면, $crc = c * x^8$ 인 계산이 된다. 그렇다면 이 식을 모든 c 에 대해서 실행해주면,  $x^8 *( input ) + \alpha$ 까지 변형시킬 수 있다. 여기서 $\alpha$ 라는 값은 우리가 입력한 값 이외의 모든 것을 의미한다. 

💡 Main Idea

그렇다면 이 문제를 풀기 위해서는 어떻게 해야 할까? 주어진 constraint 의 값을 모두 만족하는 $input$ 값을 설정해야 하고, 그 값이 곧 flag 가 될 것이다. 그렇다면 전체적인 식을 작성해보도록 하자. 

 

$ a_0 \cdots a_7, b_0 \cdots b_7$ 이 주어졌을 때 (여기서 fix 는 고정된 string 을 의미한다.)

$CRC64( fix + input_{a_0} input_{a_1} \cdots input_{a_7} ) = input_{b_0} input_{b_1} \cdots input_{b_7} \bigoplus const$

로 표현할 수 있고, 아까 말했던 CRC64 의 계산 방식까지 추가하게 되면, 

$\alpha + input_{a_0} input_{a_1} \cdots input_{a_7} * x^{80} = input_{b_0} input_{b_1} \cdots input_{b_7} \bigoplus const$ 가 된다. 

 

마지막으로 GF 상에서는 빼는 것과 더하는 것이 동일한 계산이고, XOR 또한 더하기이기 때문에 우변을 이항해주면, 

$\alpha + input_{a_0} input_{a_1} \cdots input_{a_7} * x^{80} + input_{b_0} input_{b_1} \cdots input_{b_7} = const$ 으로 최종적으로 변할 수 있게 된다 😊

 

결국, 하나의 8 개의 변수를 가진 방정식이 생기게 되었고, constraints 가 총 8 개가 있기 때문에 이 문제는 8 개의 변수를 가진 8차 연립 방정식을 푸는 과정으로 변환이 가능하다 !!

 

여기까지 조금 어렵다면 아래 블로그에서 CRC 에 대해서 조금 더 살펴보고 오면 좋을 듯 하다!!

Understanding CRC

아마 선형대수학이나 정수론 등을 배우면 많이 접했겠지만, 행렬을 이용해서 연립방정식을 해결할 수 있다. 이 8개의 연립방정식을 행렬로 구성하여 풀어보도록 하자. 

# from rbtree's code.. I'm poor...
a = [ x^(8*i + 80) for i in reversed(range(8)) ]
b = [ x^(8*i) for i in reversed(range(8)) ]

row = [ a[i] + b[(i - 1) % 8] for i in range(8) ]
mat = [ row[-i:] + row[:-i] for i in range(7) ]

# Last row is different
b = [ x^(8*i) for i in range(8) ]
row = [ a[i] + b[i % 8] for i in range(8) ]
mat += [ row ] # 8x8 matrix!

위는 RBTree 님의 블로그에 나와 있는 코드이다. 솔직히 행렬을 스스로 구성하려고 했지만, 뭔가 코드 짜는 능력이 딸려서 이렇게 긁어오게 되었다. 사실 노가다로도 구성할 수 있긴 하지만, 자동화하는 게 좋잖습니까 ㅎㅎ

 

여튼 이렇게 행렬을 구성하게 되면, 역행렬에 상수 행렬을 곱해줌으로써 문제를 해결할 수 있다. 여기서 상수 행렬이란 $\alpha$ 와 const 값을 모두 계산한 것으로, 예를 들어 $rbtree\text{{\x00\x00\x00\x00\x00\x00\x00\x00}}$ 을 대입하면 상수를 쉽게 구할 수 있다. 

 

따라서 이 행렬에 상수 행렬을 곱하면, 각 input 의 값들을 구해낼 수 있다. 

$$ Mat \times Input = Const$$

$$ Mat^{-1} \times Mat \times Input = Mat^{-1} \times Const$$

$$ Input = Mat^{-1} \times Const$$

📖 Exploit Code

def int_to_poly_gf(integer, base=2):
    F = GF(base)
    R = PolynomialRing(F, 'x')
    binary_repr = bin(integer)[2:]
    polynomial = sum(int(bit) * R.gen()**index for index, bit in enumerate(reversed(binary_repr)))
    polynomial += R.gen()**64
    return polynomial

GF_poly = int_to_poly_gf(0xd39d6612f6bcad3f)
F.<x> = GF(2^64, modulus = GF_poly)

# from rbtree's code.. I'm poor...
a = [ x^(8*i + 80) for i in reversed(range(8)) ]
b = [ x^(8*i) for i in reversed(range(8)) ]

row = [ a[i] + b[(i - 1) % 8] for i in range(8) ]
mat = [ row[-i:] + row[:-i] for i in range(7) ]

# Last row is different
b = [ x^(8*i) for i in range(8) ]
row = [ a[i] + b[i % 8] for i in range(8) ]
mat += [ row ] # 8x8 matrix!

rev = matrix(mat).inverse()

consts = [
    [F.from_integer(0x1b043df67c053eeb)],
    [F.from_integer(0x6e68dc437c0b2a99)],
    [F.from_integer(0x8eabbe5ab86018bb)],
    [F.from_integer(0x7c3b54bc0b18bd3f)],
    [F.from_integer(0xf85907527add29da)],
    [F.from_integer(0x83c3e3323f2de05a)],
    [F.from_integer(0x05e50a9f33ce91eb)],
    [F.from_integer(0x1e7c73f6327d3beb)]
]

consts = matrix(consts)
res = rev * consts

flag = ''
for poly in res:
    flag += hex(F(str(poly)).to_integer())[2:]

print(flag)

Flag : flag{8bb7cb9b53d5b3b2}