티스토리 뷰

카테고리 없음

Cyberoc 2020 finals - Counterfeit

mhibio 2020. 10. 21. 19:19

Cyberoc 2020 finals - Counterfeit

지난번 AI_HANDLER에 이어서 본선대회에 나온 crypto - counterfeit 문제이다.

대회에서 직접 크립토를 풀어본 것은 처음이다.

문제 흐름은 암호화된 python의 random.randrange(SIZE) 값을 250개 알 수 있고,
RandCrack모듈을 통해서 다음 난수값을 예측, 플래그를 복호화 해야하는 문제이다.

Chall.py

#!/usr/bin/env python3
import platform
import random
from typing import List
from secret import flag

SIZE = (1 << 96) - 1


def chunkify(data: int, length: int) -> List:
    MASK = (1 << length) - 1
    result = []
    while data > 0:
        result.append(data & MASK)
        data >>= length
    return result


def unchunkify(data: List, length: int) -> int:
    result = 0
    for i, d in enumerate(data):
        result += d << (i * length)
    return result


def gen_seqnum() -> List:
    init = random.randrange(SIZE)
    c = chunkify(init, 24)
    for i in range(4):
        c = [c[0] ^ c[1], c[1] ^ c[2], c[2] ^ c[3], c[0] ^ c[i] ^ c[2]]
    fini = unchunkify(c, 24)
    return fini


def encrypt(flag: int) -> int:
    flag_chunks = chunkify(flag, 96)
    flag_chunks = list(map(lambda c : c ^ gen_seqnum(), flag_chunks))
    enc_flag = unchunkify(flag_chunks, 96)
    return enc_flag


if __name__ == '__main__':
    print(f'version : {platform.python_version()}')
    for _ in range(250):
        print(f'Initial Seqnum : {gen_seqnum()}')
    flag = int.from_bytes(flag, byteorder='big')
    print(encrypt(flag))

=> 난수 생성
=> 난수 암호화
=> 난수 출력
=> 250번 반복
=> 다음 난수로 플래그 암호화

랜덤값을 예측해야 할 것 같다.

Mersenne Twister

메르센 트위스터란 유사난수생성기 ( pseudorandom number generator, **PRNG**) PRNG 이다.

즉, 암호학적으로 안전한 유사난수생성기 ( cryptographically secure, PRNG, deterministic random bit generator, DRBG ) CSPRNG 가 아니다.

python의 random은 CSPRNG를 사용하지 않고 메르센 트위스터(PRNG)를 사용하기 때문에 취약하다.

python - Rand Crack module

https://github.com/tna0y/Python-random-module-cracker

새로운 시드를 생성하고 다음 rand값 부터 624개의 32bit 난수를 가져와서 모듈에 넣어주면 다음 값부터 예측이 가능하다.

import random, time
from randcrack import RandCrack

random.seed(time.time())

rc = RandCrack()

for i in range(624):
    rc.submit(random.getrandbits(32))
    # Could be filled with random.randint(0,4294967294) or random.randrange(0,4294967294)

print("Random result: {}\nCracker result: {}"
    .format(random.randrange(0, 4294967295), rc.predict_randrange(0, 4294967295)))

gen_seqnum()

암호화를 할땐

    for i in range(4):
        c = [c[0] ^ c[1], c[1] ^ c[2], c[2] ^ c[3], c[0] ^ c[i] ^ c[2]]

해당 루틴을 거치는데,

A ^ A = 0
0 ^ A = A

이 두가지 성질을 이용하면 원본 랜덤값을 구할 수 있다.

rc.submit()

randcrack 모듈에다가 총 624개의 난수를 넣어줘야하는데 문제파일에서는 총 250개의 난수만 생성한다.

624개를 채우기에는 부족한 수. 하지만 python의 random.randrange()의 특징을 알면 쉽다.

import random

SIZE = (1 << 96) - 1

for i in range(2, -1, -1):
    random.seed(1)
    print(hex(random.randrange(((SIZE >> 32*i)))

output :

0x2265b1f5
0x91b7584a2265b1f5
0xd8f16adf91b7584a2265b1f5

range가 32bit단위로 커질때, 항상 일정한 random값이 나옴

즉 random.randrange(SIZE) 이 하나의 난수에서 3개의 32bit 난수값을 구할 수 있다.

3*250 = 750개.

이를 토대로 복호화 코드를 만들면 다음과같다.

Exploit Code

import platform
import random
from typing import List
from randcrack import RandCrack
from Crypto.Util.number import long_to_bytes

SIZE = (1 << 96) - 1

def chunkify(data: int, length: int) -> List:
    MASK = (1 << length) - 1
    result = []
    while data > 0:
        result.append(data & MASK)
        data >>= length
    return result

def unchunkify(data: List, length: int) -> int:
    result = 0
    for i, d in enumerate(data):
        result += d << (i * length)
    return result

def split_seqnum(data: int) -> int:
    c = []
    for i in range(3):
        c.append((data >> (32*i)) & 0xffffffff)
    return c

def make_seqnum(data: int) -> int:
    init = data
    c = chunkify(init, 24)
    for z in range(0, 4):
        c = [c[0] ^ c[1], c[1] ^ c[2], c[2] ^ c[3], c[0] ^ c[z] ^ c[2]]
    fini = unchunkify(c, 24)
    return fini

enc_flag = 2445367622995789784727362282389303874604173219621387781906754094753250264220521023165207602731464406603879744665435

rc = RandCrack()

f = list(map(int, open("output").read().split('\n')))
dec_seqnum = []

for i in range(len(f)):
    c = chunkify(f[i], 24)
    for j in range(3, 0, -1):
        new_c = [0, 0, 0, 0]
        if j == 2:
            new_c[0] = c[3]
        elif j == 1:
            new_c[0] = c[1] ^ c[3]
        elif j == 3:
            new_c[0] = c[2] ^ c[3]

        new_c[1] = new_c[0] ^ c[0]
        new_c[2] = new_c[1] ^ c[1]
        new_c[3] = new_c[2] ^ c[2]
        c = new_c

    new_c = [0, 0, 0, 0]
    new_c[2] = c[3]
    new_c[3] = new_c[2] ^ c[2]
    new_c[1] = new_c[2] ^ c[1]
    new_c[0] = new_c[1] ^ c[0]
    c = new_c

    dec_seqnum.append(unchunkify(c, 24))


enc_flag_chunkify = chunkify(enc_flag, 96)

predict_key = []

for i in range(int(624/3)):
    res = split_seqnum(dec_seqnum[i])
    predict_key += res

for i in predict_key:
    rc.submit(i)

for i in range(250 - 208):
    rc.predict_randrange(SIZE)

key = []
for i in range(4):
    key.append(make_seqnum(rc.predict_randrange(SIZE)))

flag = ''

for i in range(3, -1, -1):
    dec_flag = long_to_bytes(enc_flag_chunkify[i] ^ key[i])
    flag += dec_flag.decode("utf-8")

print(flag)