[CodeGate 2022] - Hidden Command Service

☢️ Unintended Solution.. zzlol

이 문제는 코드가 좀 긴 대신 Unintended 풀이가 존재한다. 나도 이 문제를 인텐 풀이로 풀 자신이 없어서 언인텐 풀이로 풀긴 했는데, 이마저도 솔직히 혼자 다 하진 못했다 ^^ 멍청한 나 자신

🖲️ Code Analysis

from os import urandom as random
from hashlib import sha256
from time import time, sleep
from subprocess import check_output, DEVNULL

def gf_mul(a, b):
    res = 0
    for i in range(16):
        res <<= 1
        if res & 0x10000:
            res ^= 0x15A55
        if b & (1 << (15 - i)):
            res ^= a
    return res

def gf_pow(v, i):
    if i == 1:
        return v
    return gf_mul(gf_pow(v, i - 1), v)


class BlockCipher:
    # There are various ways to block differential cryptanalysis.
    # Kaisa Nyberg and Lars Knudsen proved this s-box structure is
    # safe from differential cryptanalysis attacks.
    SBOX = [gf_pow(v, 3) ^ 3 for v in range(2**16)]
    BLOCK_SIZE = 8
    KEY_SIZE = 32
    NUM_ROUND = 4

    def __init__(self, key):
        assert type(key) == bytes
        assert len(key) == self.KEY_SIZE
        self.rkey = []
        for i in range(0, self.KEY_SIZE, 2):
            self.rkey.append(int.from_bytes(key[i : i + 2], "little"))

    def encrypt_block(self, block):
        block = [
            int.from_bytes(block[i : i + 2], "little")
            for i in range(0, self.BLOCK_SIZE, 2)
        ]

        for rnd in range(self.NUM_ROUND):
            for idx in range(self.BLOCK_SIZE // 2):
                block[idx] ^= self.SBOX[
                    block[(idx + 1) % (self.BLOCK_SIZE // 2)]
                    ^ self.rkey[(self.BLOCK_SIZE // 2) * rnd + idx]
                ]

        return b"".join(v.to_bytes(2, "little") for v in block)

    def decrypt_block(self, block):
        block = [
            int.from_bytes(block[i : i + 2], "little")
            for i in range(0, self.BLOCK_SIZE, 2)
        ]
        for rnd in reversed(range(self.NUM_ROUND)):
            for idx in reversed(range(self.BLOCK_SIZE // 2)):
                block[idx] ^= self.SBOX[
                    block[(idx + 1) % (self.BLOCK_SIZE // 2)]
                    ^ self.rkey[(self.BLOCK_SIZE // 2) * rnd + idx]
                ]
        return b"".join(v.to_bytes(2, "little") for v in block)

    @classmethod
    def _pad(cls, b):
        v = cls.BLOCK_SIZE - len(b) % cls.BLOCK_SIZE
        return b + bytes([v] * v)

    @classmethod
    def _unpad(cls, b):
        if not b:
            # TODO: Define an exception and raise here
            return b""
        if not (1 <= b[-1] <= cls.BLOCK_SIZE):
            # TODO: Define an exception and raise here
            return b""
        return b[: -b[-1]]

    @staticmethod
    def _xor(a, b):
        return bytes(x ^ y for x, y in zip(a, b))

    def encrypt(self, pt):
        mac = sha256(pt).digest()[: self.BLOCK_SIZE]
        pt = self._pad(pt) + mac
        print(f'mac : {mac.hex()}')
        print(f'pt : {pt.hex()}')
        ct = random(self.BLOCK_SIZE) #iv vec
        print(ct.hex())
        for idx in range(0, len(pt), self.BLOCK_SIZE):
            print(f'idx : {idx}')
            block = pt[idx : idx + self.BLOCK_SIZE]
            ct += self.encrypt_block(self._xor(block, ct[-self.BLOCK_SIZE :]))
        return ct

    def decrypt(self, ct):
        pt = b""
        for idx in range(self.BLOCK_SIZE, len(ct), self.BLOCK_SIZE):
            iv, block = ct[idx - self.BLOCK_SIZE : idx], ct[idx : idx + self.BLOCK_SIZE]
            pt += self._xor(iv, self.decrypt_block(block))
        if len(pt) < 2 * self.BLOCK_SIZE:
            return b""
        padded, mac = pt[: -self.BLOCK_SIZE], pt[-self.BLOCK_SIZE :]
        padded = padded[:-1] + b'\x08'
        pt = self._unpad(padded)
        if (not pt) or sha256(pt).digest()[: self.BLOCK_SIZE] != mac:
            return b""
        return pt

def run_command(cmd):
    try:
        print(check_output(cmd, stdin=DEVNULL, shell=True).decode())
    except:
        pass


def main():
    seed = random(16)

    with open("./password", "rb") as f:
        password = f.read()

    key = sha256(seed + password).digest()
    cipher = BlockCipher(key)

    for _ in range(500):
        inp = input("> ")
        if inp == "emergency":
            print("[EMERGENCY MODE]")
            print("0. Get the server time (Testing purpose!)")
            print("1. Get the target info")

            inp = input("> ")
            if inp == "0":
                cmd = "date"
            elif inp == "1":
                cmd = "cat target_info"
            else:
                print("Wrong input :(")
                continue

            run_command(cmd)
            enc_cmd = cipher.encrypt(cmd.encode())
            print(f"Don't forget the encrypted command: {enc_cmd.hex()}")
            continue

        elif inp == "exit":
            print("Bye!")
            return

        try:
            enc_cmd = bytes.fromhex(inp.strip())
        except ValueError:
            print("Wrong input :(")
            continue

        if len(enc_cmd) % cipher.BLOCK_SIZE:
            print("Wrong input size :(")
            continue

        cmd = cipher.decrypt(enc_cmd)
        try:
            cmd = cmd.decode()
        except:
            cmd = ""

        run_command(cmd)

    print("There's a trial limit on each seed.")
    print("Please connect again. Bye!")


if __name__ == "__main__":
    main()

코드는 길지만 의외로 문제의 기능은 별로 없다. 먼저 기능들을 소개해보도록 하자.

1. emergency mode - date, cat target_info 두 명령어를 암호화.
2. 다른 문자를 입력하면, 이를 복호화해서 command 를 실행시킨다.

이렇게 두 단계로 분류할 수 있다. 하지만, emergency mode 로 date 를 암호화한 값을 다시 넣어주게 되면, 아무것도 출력되지 않음을 확인할 수 있다. 그 이유는 바로

💡 padded = padded[:-1] + b'\x08' pt = self._unpad(padded)

 

이 부분 때문이다. 이 부분으로 인해서 복호화된 마지막 바이트가 \x08 바이트로 바뀌게 되고, 이를 직접 구현한 unpad 함수를 적용시키게 되면, 한 블럭 자체가 없어지게 된다. ( unpad error )

 

< 그 이유는 return b[: -b[-1]] 을 함으로써 마지막 바이트에 해당하는 만큼 블럭을 제거한다. >

 

따라서, 아무리 복호화를 한다고 해도, 마지막 블럭이 사라지기 때문에 date 는 아예 삭제되고, cat target_info 명령어는 cat targ 만 보존되게 된다. -> 제대로 된 Unpad 가 이루어지지 않아 command 그대로 들어가지 않는다.

💡 Main Idea

여기서 나오는 아이디어는 바로 padding 을 제외하더라도 flag 를 읽을 수 있게 해주는 것이다. 일단 flag 가 어느 파일인지 명확하지 않으니 모든 파일을 읽을 수 있는 명령어를 생각해보자.

 

바로 cat **** 명령어를 쓰면, 모든 파일을 읽을 수 있음과 동시에 정확히 8 글자로 padding 오류를 피할 수 있겠다.

 

그럼 암,복호화 과정을 자세히 살펴보도록 하자.

def encrypt(self, pt):
    mac = sha256(pt).digest()[: self.BLOCK_SIZE]
    pt = self._pad(pt) + mac
    print(f'mac : {mac.hex()}')
    print(f'pt : {pt.hex()}')
    ct = random(self.BLOCK_SIZE) #iv vec
    print(ct.hex())
    for idx in range(0, len(pt), self.BLOCK_SIZE):
        print(f'idx : {idx}')
        block = pt[idx : idx + self.BLOCK_SIZE]
        ct += self.encrypt_block(self._xor(block, ct[-self.BLOCK_SIZE :]))
    return ct

def decrypt(self, ct):
    pt = b""
    for idx in range(self.BLOCK_SIZE, len(ct), self.BLOCK_SIZE):
        iv, block = ct[idx - self.BLOCK_SIZE : idx], ct[idx : idx + self.BLOCK_SIZE]
        pt += self._xor(iv, self.decrypt_block(block))
    if len(pt) < 2 * self.BLOCK_SIZE:
        return b""
    padded, mac = pt[: -self.BLOCK_SIZE], pt[-self.BLOCK_SIZE :]
    padded = padded[:-1] + b'\x08'
    pt = self._unpad(padded)
    if (not pt) or sha256(pt).digest()[: self.BLOCK_SIZE] != mac:
        return b""
    return pt

암,복호화 과정은 다음과 같다. 자세히 살펴보면, plaintext 에 해당하는 hash value 를 mac 값으로 정의한 후에, plaintext 를 padding 한 후에 mac 을 뒤에 이어붙이게 된다.

 

그 후에, 임의의 ct 값을 설정하고, 이 ct 값을 일종의 Initial Value, 즉 IV 로 설정하여 CBC 모드와 매우 유사하게 암호화를 진행하게 된다. ( 여기서 encrypt_block 은 문제 해결을 위한 주요 논점이 아니기에 배제하도록 하겠다. 물론 인텐 풀이에는 배제하면 큰일난다.. ㅎㅎ ) 

 

우리는 여기서 CBC 모드의 허점을 사용해야 한다. CBC 모드는 ciphertext 의 전 블럭을 IV 값으로 취급하기 때문에 이를 조작해준다면 손쉽게 plaintext 또한 조작할 수 있게 된다.

CBC mode

복화화 과정에서, 우리는 XOR 연산만으로 원하는 값을 조작할 수 있게 된다.

예를 들어서, P1, P2 블럭이 있다고 가정하자.

이 블럭들은 암호화되어 C1 = F( IV ^ P1 ), C2 = F( C1 ^ P2 ) 로 바뀐다.

하지만, 이를 다시 복호화할 때면, P1 = G(C1) ^ IV 라는 연산을 하게 된다. 그렇다면 여기서 IV 값을 변조하면 어떻게 될까??

 

우리가 원하는 값 P1* 으로 바꾸기 위해서는 P1* = G(C1) ^ IV* 라는 식을 만족시켜야 한다.

그런데 여기서 G(C1) 은 위의 식을 보면 P1 ^ IV 값으로 나타낼 수 있다. 따라서 IV* 의 값을 P1 ^ IV ^ P1* 값으로 변경시켜준다면, P1 을 우리 마음대로 조작할 수 있다.

📖 Exploit Code

조금 설명이 난잡했는데, 바로 문제를 해결해보도록 하자. 여기서 우리는 emergency 의 2번째 값인 cat target_info 라는 명령어를 활용해야 한다.

 

만약 date 라는 명령어를 사용하게 되면, [date + padding ] + [mac] 으로 2블럭의 plaintext 가 만들어지고, 암호화되면 총 3블럭이 만들어진다. 문제를 직접 해결해보면 깨닫겠지만, 블럭과 mac 값까지 조작하기 위해서는 최소 4 블럭이 필요하다.

 

먼저, cat target_info 는 암호화 시에 다음과 같은 구조를 띈다.

[ IV ] + f[ cat targ ] + f[ et_info + padding ] + f[ mac ] ( 앞의 f 는 암호화된 것을 의미한다. ) 이 구조가 복호화 과정을 거치면, [ cat targ ] + [ et_info + padding ] + [ mac ] 이 된다. 2번쨰 블럭에서 마지막 부분이 \x08 로 바뀌면서 어차피 2번째 블럭은 삭제될 예정이기 때문에, 첫번쨰 블럭을 아까 말했던 cat **** 으로 바꿔주면 문제를 해결할 수 있을 것이다.

 

추가로, mac 또한 sha256(plaintext) 를 만족하도록 해야 하기 때문에, mac 또한 조작해주자.

from hashlib import sha256
want = b'cat ****'
prev = b'cat target_info'
sha_want = sha256(b'cat ****').digest()[:8]

def xor(a, b):
   return bytes(x ^ y for x, y in zip(a, b))

prev_cmd = bytes.fromhex('0a94ecdeedbf42e2771d383ede759aa832f2689faf1973a89b2b5b01775e4693')
mac = bytes.fromhex('527b8c5dd3b5a57c')

flag = xor(xor(want,prev_cmd),prev).hex()[:16]+prev_cmd.hex()[16:-32]+
				xor(xor(prev_cmd[16:24],sha_want),mac).hex()+prev_cmd.hex()[-16:]
print(flag)

정리해보면 다음과 같은 코드가 만들어진다. 아까 설명했던 P1 ^ IV ^ P1 값이 새로운 IV 의 값이 되기 때문에 각각 3개를 XOR 한 값으로 정의했고, 나머지는 그대로 입력하면 되겠다.

 

다음과 같이 모든 파일이 출력되는 것을 확인할 수 있다.

 

Flag : CyKor{Crypto-1s-ha4d}

 

** 여기서 Flag 형식이 CodeGate 가 아닌 이유는, 감사하게도 어떤 선배님께서 대회가 끝난 후에 따로 서버를 열어주셔서 그 서버를 통해 문제를 해결할 수 있었다. 그래서 Flag 형식이 다른 것,,