[SECCON CTF 2021] oOoOoO

 

import signal
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random
from flag import flag

message = b""
for _ in range(128):
    message += b"o" if random.getrandbits(1) == 1 else b"O"

M = getPrime(len(message) * 5)
S = bytes_to_long(message) % M
print("message :",message)

print("M =", M)
print('S =', S)
print('MESSAGE =', message.upper().decode("utf-8"))

signal.alarm(600)
ans = input('message =').strip().encode()

if ans == message:
    print(flag)
else:
    print("🧙")

 

문제를 보면, 상당히 간단하지만 이상한 작업이 일어나고 있다.

1. o 혹은 O를 random하게 128개 선정

2. M (640 bit prime)을 생성하고 위에서 선정한 값 % M 과, M을 제공

3. 600초 내에 1에서 생성한 message를 복구하면 FLAG 획득

 

처음엔 단순히 알고리즘(dp)로 풀 수 있지 않을까라고 생각했는데 무리였다. 여기서 문제를 계속 보다가 message를 hex로 출력했을 때 아이디어가 떠올랐다.

 

message 예시 : 0x4f4f6f6f .... 0x4f6f4f

o는 0x6f, O는 0x4f인데,이 문제를 knapsack problem으로 변환할 수 있지 않을까라는 생각이 들었다.

 

예를 들어 message를 oOoO(0x6f4f6f4f) 인 상황으로 knapsack problem으로 변환하면 아래와 같다.

 

$$ m = [0,1,0,1] $$

$$ a = [\text{0x20, 0x2000, 0x200000, 0x20000000}]$$

 

$$C = \sum_{k=1}^{len(m)}a[i]*m[i]$$

$$message = C + 0\text{x4f4f4f4f}$$

 

위처럼 문제와 knapsack problem이 동일하다는 것을 깨닫고, knapsack과 동일하게 Lattice를 만들어서 해결할 수 있었다.

 

ans.sage

from Crypto.Util.number import *

M = 3358865267993523418646298427749210334190739093746169917905801902106704531466533019207168510725428625000745906615006168163760426165634422537200238665920036431174804069999894010449513018581107517
S = 81434408737825149523977840344877896815489474895176166647180625948548142497095545946587402230454660730614468241879031803665608158734074041583328238860751009218487635903923432583228418360634668
p = M

n = 128
N = ceil(sqrt(n) / 2)

base = b'\x4f' * 128
base = bytes_to_long(base) % p
s = S-base

a = []
for i in range(128):
    tmp = 0x20 << (i * 8)
    a.append(tmp % p)

b = []
for i in range(n):
    vec = [0 for _ in range(n + 1)]
    vec[i] = 1
    vec[-1] = N * a[i]
    b.append(vec)
    b.append([1 / 2 for _ in range(n)] + [N * s])

for k in range(128):
    print('time :',k)
    tmp = [1 / 2 for _ in range(n)] + [N * (s + p * k)]
    b[-1] = tmp

    BB = matrix(QQ, b)
    l_sol = BB.LLL()

    for e in l_sol:
        if e[-1] == 0:
            msg = 0
            isValidMsg = True
            for i in range(len(e) - 1):
                ei = 1 - (e[i] + (1 / 2))
                if ei != 1 and ei != 0:
                    isValidMsg = False
                    break

                msg |= int(ei) << i

            if isValidMsg:
                print('[*] Got flag:', long_to_bytes(msg))
                break
    if isValidMsg:
        break

a = bin(msg)[2:].rjust(128,'0')
print(a)
flag = b''

for i in range(len(a)):
    if a[i] == '0':
        flag += b'O'
    else:
        flag += b'o'
print(flag)

flag = bytes_to_long(flag)
if tmp % M == S:
    print((long_to_bytes(flag)))