티스토리 뷰
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)
Fini
random.randrange()
가 32bit
단위로 시드마다 고정된 값이 나온다는것 알아간다.