[CONFidence CTF 2019 Teaser] Count me in! writeup

문제

---

분석

총 2개의 파일이 주어진다.

output.txt와 count.py

import multiprocessing

from Crypto.Cipher import AES

from secret import key, flag

counter = 0
aes = AES.new(key, AES.MODE_ECB)


def chunk(input_data, size):
    return [input_data[i:i + size] for i in range(0, len(input_data), size)]


def xor(*t):
    from functools import reduce
    from operator import xor
    return [reduce(xor, x, 0) for x in zip(*t)]


def xor_string(t1, t2):
    t1 = map(ord, t1)
    t2 = map(ord, t2)
    return "".join(map(chr, xor(t1, t2)))


def pad(data):
    pad_byte = 16 - len(data) % 16
    return data + (chr(pad_byte) * pad_byte)


def worker_function(block):
    global counter
    key_stream = aes.encrypt(pad(str(counter)))
    result = xor_string(block, key_stream)
    counter += 1
    return result


def distribute_work(worker, data_list, processes=8):
    pool = multiprocessing.Pool(processes=processes)
    result = pool.map(worker, data_list)
    pool.close()
    return result


def encrypt_parallel(plaintext, workers_number):
    chunks = chunk(pad(plaintext), 16)
    results = distribute_work(worker_function, chunks, workers_number)
    return "".join(results)


def main():
    plaintext = """The Song of the Count

You know that I am called the Count
Because I really love to count
I could sit and count all day
Sometimes I get carried away
I count slowly, slowly, slowly getting faster
Once I've started counting it's really hard to stop
Faster, faster. It is so exciting!
I could count forever, count until I drop
1! 2! 3! 4!
1-2-3-4, 1-2-3-4,
1-2, i love couning whatever the ammount haha!
1-2-3-4, heyyayayay heyayayay that's the sound of the count
I count the spiders on the wall...
I count the cobwebs in the hall...
I count the candles on the shelf...
When I'm alone, I count myself!
I count slowly, slowly, slowly getting faster
Once I've started counting it's really hard to stop
Faster, faster. It is so exciting!
I could count forever, count until I drop
1! 2! 3! 4!
1-2-3-4, 1-2-3-4, 1,
2 I love counting whatever the
ammount! 1-2-3-4 heyayayay heayayay 1-2-3-4
That's the song of the Count!
""" + flag
    encrypted = encrypt_parallel(plaintext, 32)
    print(encrypted.encode("hex"))


if __name__ == '__main__':
    multiprocessing.freeze_support()
    main()

여기서 multiprocessing 모듈은 멀티 스레딩 작업을 위한 모듈이고 distribute_work 함수 등은 이를 위해 설계된 것이다.

output.txt에는 위 python 코드의 실행결과로 보이는 암호문이 있었다.

대부분의 CTF 문제가 그렇듯이 멀티 스레딩 작업을 하는 부분에서 취약점이 발생하지 않을까 생각했다.

---

EXPLOIT

위 python code는 plain text를 16바이트씩 분할하여 AES-EBC 암호화 하는 프로그램이다.

또한 이를 면밀히 분석하면, 여러 스레드가 동시에 worker_function을 실행함을 알 수 있다.

그러면서 count를 증가시키고, 이를 key 값으로 사용하는 것이다.

하지만 멀티 스레딩, 즉 여러 스레드가 이를 동시에 실행하기 때문에 같은 count 값을 가지고 key를 형성하는 일이 필연적으로 생길 수 밖에 없다.

이를 확인하고자 plaintext를 'a' * 976으로 두고 위 python code를 실행해보았다.

그 결과는 아래와 같았다.

0번째 줄, 6번째 줄, 13번째 줄, 21번째 줄의 내용이 일치한다.

즉, 해당 block에 대해 같은 key 값이 사용되었음을 의미한다.

그렇다면 output.txt도 마찬가지일 것이다.

이 점을 이용해 i가 주어졌을때 plaintext[i]^ciphertext[i]와 plaintext[j]^ciphertext[j]가 같은 j를 찾아내는 코드를 만들었고

flag가 시작되는 지점은 plaintext[57]부터 이므로 i에 57을 대입해서 실행해보았다.

실행결과는, 54번 라인이 이와 같다고 나왔다!

---

FL4G

plaintext[54]^ciphertext[54]를 계산하여 54번 라인과 57번 라인에서 공통으로 사용된 키 스트림을 구해냈고

이 키와 ciphertext[57]을 xor 연산한 결과,

flag가 구해짐을 알 수 있었다.

마찬가지로 58번 라인, 59번 라인, 60번 라인도 구해냈다.

             

  FLAG : p4{at_the_end_of_the_day_you_can_only_count_on_yourself}