CTFZone 2018 Quals Write up

https://ctf.bi.zone/

CTFZone은 BI.ZONE이라는 러시아 보안 업체가 주최한 해킹 대회입니다. 5인 1팀으로 참여할 수 있고 상위 10개 팀은 러시아로 초청돼 11월에 Attack / Defense 형식의 본선을 치루게 됩니다. 예선은 Jeopardy 형식이었습니다. 저는 Crypto, Misc, Programming 카테고리의 문제를 맡았고 Crypto 2문제, Programming 2문제를 해결했습니다. 팀은 정확하게 기억은 안나지만 18-20 문제 정도를 해결했고 7위를 기록했습니다. 7월 21일에 치룬 대회인데 바빠서 이제야 write up을 쓰네요.

Crypto - Federation Workflow System (40 Solved)

서버와 클라이언트 소스는 각각 Server, Client 에서 확인할 수 있습니다. 주어진 서버와 클라이언트 파일의 코드를 잘 분석해보면, Client는 특정 파일의 AES-ECB mode encryption oracle을 들고 있음을 알 수 있습니다. 또한 server가 돌아가고있는 디렉토리에 totp.secret이라는 파일이 존재하고 하위 디렉토리로 files 와 top_secret가 있습니다. 원래 의도한 것은 files 내의 파일에 대한 encryption 결과만을 받는 것이지만 이는 경로를 "../"으로 둠으로서 쉽게 우회할 수 있습니다.

우리는 top_secret 내의 flag.txt를 읽는 것이 목표이고 이 목표를 달성하기 위해서는 totp.secret을 읽어 otp를 알아내서 admin token을 획득해 flag.txt를 읽거나, 아예 top_secret내의 flag.txt 파일을 바로 읽어들여야 합니다. 이것저것 시도를 하다보면 admin token 없이는 top_secret 디렉토리에 접근하는 것이 불가능함을 알 수 있습니다. 그러므로 totp.secret을 읽어들일 방법을 고안해야합니다.

서버에서 encryption은 아래와 같이 수행됩니다.

def send_file_data(self, file, client, address):
        content = self.read_file(file)
        response = '{0}: {1}'.format(file, content)
        encrypted_response = self.encrypt(response)
        self.send(client, encrypted_response)
        self.log('Sending file "{0}" to client {1}'.format(file, address[0]))

user의 input으로 넘겨받은 file과 그 파일의 내용(파일이 존재하지 않는다면 NOT_FOUND라는 문구)를 묶어 암호화를 진행하기 때문에, 저희는 특정 파일의 AES-ECB mode encryption oracle을 들고있는 것이 아니라 임의의 평문에 대한 encryption oracle을 들고 있는 상황입니다. 즉 Chosen Plaintext Attack 환경입니다.

그리고 file 이름의 길이를 잘 조정하면 totp.secret의 파일을 한 글자씩 떼오면서 공격을 수행할 수 있습니다. 예를 들어 totp.secret에 기록된 값이 01234 라고 해봅시다. 그러면 클라이언트에서 서버로 "..////////"를 보낼 경우, 서버는 "..////////: 12345" 를 암호화한 결과를 반환해주고 128bit = 16글자 단위로 독립적으로 암호화를 수행하기 때문에 "..////////: 12345" 으로 블록이 구분되어 우리는 마지막 글자에 대한 암호화 결과를 알 수 있습니다. CPA 환경이므로 모든 ascii 글자에 대해 암호화를 해보면 마지막 글자가 5임을 알아낼 수 있습니다. 마찬가지로 계속 진행하면 totp.secret을 복구할 수 있고, 이를 이용해 admin token을 획득하면 됩니다. 제 코드는 solver.py 에서 확인할 수 있습니다.

Crypto - Signature Server (28 Solved)

서버 소스는 Server 에서 확인할 수 있습니다. 확인해보면 내가 입력한 메시지에 대해 padding과 checksum을 붙여 sign을 돌려주는 oracle이 존재하고, 특정한 두 메시지(admin_command, show_flag_command)에 대한 checksum과 sign을 얻으면 flag를 획득할 수 있는 문제입니다. 단 oracle에 admin_command, show_flag_command를 입력할 수는 없습니다. show_flag_command에 대한 checksum과 sign은 쉽게 얻을 수 있습니다. padding이 메시지의 끝에 \xFF를 붙이는 padding이고, show_flag_command의 하위 23바이트가 전부 \xFF이기 때문에 그냥 show_flag_command의 마지막 한 바이트를 제외한 것을 보내면 바로 얻어낼 수 있습니다. 문제는 admin_command입니다. 마지막 24바이트가 \x00이기 때문에 show_flag_command처럼 간단하게 알아낼 수가 없습니다.

첫 번째로 checksum을 알아내기 위해서는 checksum을 생성할 때 하위 byte의 작은 변화는 checksum의 상위 1byte에만 영향을 끼친다는 사실을 이용해야합니다. 사실 Winterniz Checksum의 동작 원리를 정확하게 파악하지 못해서 왜 그런건지는 잘 모르겠지만 그냥 그렇더라구요. 이를 이용해 admin_command에서 끝 1 byte만 \x00에서 \x01로 만든 forge_admin_command에 대한 checksum, sign을 먼저 얻은 후, checksum의 상위 1 byte를 바꿔가며 서버에 질의를 날리면 admin_command에 대한 올바른 checksum을 찾아낼 수 있습니다.

두 번째로 sign을 복원하기 위해서는 data+padding+checksum(=36byte)에 대한 sign을 만드는 과정 상에서 마치 ECB 모드와 같이 각 36개의 byte에 대해 독립적으로 32 byte씩 생성해 이를 합쳐서 sign을 만든다는 사실을 코드를 통해 알아내야 합니다.

그렇기에 forge_admin_command의 sign의 첫 31*32 byte + 하위 byte만 0x00으로 만든 임의의 메시지의 sign의 하위 byte에 대응되는 sign 32 byte를 하면 data+padding에 대한 sign은 알아낼 수 있습니다. 그 다음으로 checksum에 대한 sign을 알아내야 하는데, 이것 또한 마찬가지로 동일한 checksum을 가지는 다른 data를 찾아내서 추출이 가능합니다.

이후 복원한 data+sign을 전송하면 flag를 얻을 수 있습니다. 제 코드는 solver.py 에서 확인할 수 있습니다.

Programming - PlusMinus (?? Solved)

가장 많은 팀이 해결한 문제였던걸로 기억합니다.

문제는 굉장히 단순합니다. 1 2 5.77636 2 6 8 8.77636 이라고 수가 주어지면, 맨 마지막수를 제외한 나머지 수들로 연산을 해서 맨 마지막 수를 만들어내야 합니다. 이 때 수들 사이의 순서가 바뀌어서는 안되고 괄호와 사칙연산을 활용할 수 있습니다. (ex : 1+2+5.77637-2-6=8.77636) 항은 최대 9개까지 등장하고 10단계를 클리어하면 flag를 얻을 수 있습니다.

저는 python의 eval 함수를 이용해 식을 재구성하고 적당히 때려맞췄습니다. eval함수가 굉장히 느리게 동작하기 때문에 최적화를 다른 방식으로 시켰어야했을텐데, 이렇게 짜도 금방 답이 나오겠거니 싶어서 했습니다. 그런데 답이 잘 나오지 않아 거의 200번 가까이 시도를 계속 한 끝에 10단계를 통과했던 것 같네요. 코드는 solver.py 에서 확인할 수 있습니다.

Programming - Help Mars! (?? Solved)

대략 30~35개 팀 정도가 해결한 문제일겁니다. sample이 여러개 주어지고, sample을 이어붙여 vaccine을 만들 수 있는 레시피를 출력하는 문제입니다. 예를 들어 vaccine이 ACCCGGTTCAA이고

sample1 : ACC

sample2 : TTCAA

sample3 : GGTT

sample4 : CGG이면

1-4-2를 찾아내야 합니다.

유전자는 대략 20만개, vaccine의 길이가 1707입니다.

저는 $D1_{i,j} : Vaccine_{i,j}$와 일치하는 sample의 index, $D2_{i} : Vaccine_{0,i}$와 일치하는 recipe로 두어 D 테이블을 채워나가서 해결했습니다. 알고리즘에 익숙하다면 그럭저럭 쉽게 풀어낼 수 있는 문제였습니다. 제 코드는 solver.py 에서 확인할 수 있습니다.

팀이 7위를 기록한 덕분에 이 기회에 러시아를 한 번 가보나 싶었는데 ACM ICPC를 준비하느라 해킹에 집중할 수 있는 상황이 아니기도 하고, 또 본선이 Attack / Defense 방식이라길래 가봤자 제가 할 수 있는게 아무것도 없겠다 싶어서 눈물을 머금고 양보했습니다. 쥬륵.. 어찌됐든 문제가 그럭저럭 잘 풀려서 기분이 좋았습니다.