[2022 Fall GoN Open Qual CTF] Checkers writeup

#!/usr/bin/python3
import random

CHARSET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ_/"

def key_gen():
    tmp = list(CHARSET)
    random.shuffle(tmp)
    p = "".join(tmp)
    k1, k2 = random.sample(range(1, 10), 2)
    k3_len = random.randint(5, 10)
    k3 = tuple(random.randrange(1, 10) for _ in range(k3_len))

    p_li = list(p)
    p_li.append(p_li[k1])
    p_li.append(p_li[k2])
    p_li[k1] = " "
    p_li[k2] = " "
    p = "".join(p_li)

    return (p, k1, k2, k3)

def read_flag():
    flag = ""
    try:
        with open("flag", "r") as f:
            flag = f.read().strip()
    except FileNotFoundError:
        print("fatal error: contact to admin")
        exit(1)
        
    assert(valid_msg(flag))
    return flag

def valid_msg(m):
    return all(c in CHARSET for c in m)

def straddling_checkerboard(pt, perm, k1, k2):
    assert(set(CHARSET + " ") == set(perm))
    assert(len(CHARSET) == len(perm) - 2)
    assert(k1 in range(1, 10))
    assert(k2 in range(1, 10))

    idx = perm.index(pt)
    if idx < 10:
        return (idx,)
    else:
        return  ((0, k1, k2)[idx // 10], idx % 10)

def straddling_checkerboard_inv(ct, perm, k1, k2):
    assert(set(CHARSET + " ") == set(perm))
    assert(len(CHARSET) == len(perm) - 2)
    assert(k1 in range(1, 10))
    assert(k2 in range(1, 10))

    res = ""

    while ct:
        if ct[0] == k1 and len(ct) > 1:
            res += perm[10 + ct[1]]
            ct = ct[2:]
        elif ct[0] == k2 and len(ct) > 1:
            res += perm[20 + ct[1]]
            ct = ct[2:]
        else:
            res += perm[ct[0]]
            ct = ct[1:]
    return res

def non_carry_add(n1, n2):
    res = 0
    cnt = 1

    while n1 != 0 or n2 != 0:
        res += (((n1 % 10) + (n2 % 10)) % 10) * cnt
        n1 //= 10
        n2 //= 10
        cnt *= 10

    return res

def substitute(pt, k3):
    assert(all(k in range(1, 10) for k in k3))
    
    res = []
    for i, c in enumerate(pt):
        res.append(non_carry_add(c, k3[i % len(k3)]))

    return res

def encrypt(pt, perm, k1, k2, k3):
    pt_checked = []
    for c in pt:
        pt_checked.extend(straddling_checkerboard(c, perm, k1, k2))

    pt_subed = substitute(pt_checked, k3)

    return straddling_checkerboard_inv(pt_subed, perm, k1, k2)

if __name__ == "__main__":
    PERM, K1, K2, K3 = key_gen()
    FLAG = read_flag()
    
    while True:
        print("--------------------")
        print("1. Encrypt Message")
        print("2. Decrypt Message")   
        print("3. Encrypt Flag") 
        print("4. Exit")
        try:
            op = int(input())
        except ValueError:
            print("[-] Unexpected input...")
            continue
        if op == 1:
            print("[*] Please give me the plaintext message")
            msg = input()
            if valid_msg(msg):
                print("[+] Encrypted message :%s" % encrypt(msg, PERM, K1, K2 ,K3))
            else:
                print("[-] Message format is invalid...")
        elif op == 2:
            print("[!] Ask Decryption oracle for ancient cipher??? HOW DARE YOU")
            break
        elif op == 3:
            print("[+] Encrypted Flag :GoN{%s}" % encrypt(FLAG, PERM, K1, K2, K3))
        elif op == 4:
            break
        else:
            print("[-] Unexpected input...")

 

제공된 chal.py 파일의 소스코드이다.

encrypt 된 flag 를 주는 것을 보아, decrypt 를 직접 해야하는 문제인듯 보인다.

 

근데 encrypt 하는 과정을 살펴보니 머리가 어지러워지기 시작한다.

그래서 일단 1번 기능을 이용하여, charset 의 문자 하나하나를 encrypt 해보았다.

 

A -> LK

B -> ZN

AB -> LK__

AC -> LK_Z

 

일단 첫번째 글자일 때의 암호화된 값은 두번째 글자일 때와 다르다.

그리고 그 전 글자를 암호화한 값이 그대로 남아 있는 것을 볼 수 있다.

 

그렇다면

1. CHARSET 의 문자 모두 암호화한 값을 추출

2. 암호화된 flag 값의 처음 부분과 같은 값으로 암호화되는 문자를 찾고

3. 찾은 문자와 다시 CHARSET 문자를 합친 후, 합친 문자열을 다시 암호화한 값을 추출

4. 2로 돌아가 반복

 

하면 flag 를 찾을 수 있을 것 같아보인다.

 

DFS 를 이용하여 서치해주면, flag 의 원본 값을 알아낼 수 있다.

 

from pwn import *

CHARSET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ_/"

while(True):
    p = remote('host3.dreamhack.games', 9660)

    def Encrypt(msg):
        p.recvuntil(b'4. Exit\n')
        p.send_raw(b'1\n')
        p.recvline()
        p.send_raw(msg.encode() + b'\n')
        p.recvuntil(b':')
        return p.recvline()[:-1]
        
    def EncryptFlag():
        p.recvuntil(b'4. Exit\n')
        p.send_raw(b'3\n')
        p.recvuntil(b':')
        return p.recvline()[:-1]


    def DFS_find_flag(depth, prev_flag_encrypted, flag_encrypted, flag):
        print('depth : {0}\nprev_flag_encrypted : {1}, flag_encrypted : {2}, flag : {3}'.format(depth, prev_flag_encrypted, flag_encrypted, flag))
        CHARSET_ENCRYPTED = list()
        for i in range(len(CHARSET)):
            CHARSET_ENCRYPTED.append(Encrypt(flag + CHARSET[i]).decode().strip().replace(prev_flag_encrypted, ''))
            #print('{0} : {1}({2})'.format(CHARSET[i], CHARSET_ENCRYPTED[i], len(CHARSET_ENCRYPTED[i])))
        POSSIBLE_CHARSET_ENCRYPTED_INDEX = list()
        for i in range(len(CHARSET_ENCRYPTED)):
            if(CHARSET_ENCRYPTED[i] == ' '):
                POSSIBLE_CHARSET_ENCRYPTED_INDEX.append(i)
            elif(len(CHARSET_ENCRYPTED[i]) == 1):
                if(flag_encrypted[0] == CHARSET_ENCRYPTED[i]):
                    POSSIBLE_CHARSET_ENCRYPTED_INDEX.append(i)
            else:
                if(flag_encrypted[:len(CHARSET_ENCRYPTED[i])] == CHARSET_ENCRYPTED[i]):
                    POSSIBLE_CHARSET_ENCRYPTED_INDEX.append(i)
        print('possible encrypted charset len : ' + str(len(POSSIBLE_CHARSET_ENCRYPTED_INDEX)))
        if(len(POSSIBLE_CHARSET_ENCRYPTED_INDEX) == 0):
            print("fuckedup")
            return "fuckedup"
        for i in range(len(POSSIBLE_CHARSET_ENCRYPTED_INDEX)):
            print('{0} -> {1}({2}) going deeper..'.format(i, CHARSET_ENCRYPTED[POSSIBLE_CHARSET_ENCRYPTED_INDEX[i]], 
                                        CHARSET[POSSIBLE_CHARSET_ENCRYPTED_INDEX[i]]))
            if(len(flag_encrypted) == len(CHARSET_ENCRYPTED[POSSIBLE_CHARSET_ENCRYPTED_INDEX[i]])):
                return flag + CHARSET[POSSIBLE_CHARSET_ENCRYPTED_INDEX[i]]
            result = DFS_find_flag(depth + 1, prev_flag_encrypted + CHARSET_ENCRYPTED[POSSIBLE_CHARSET_ENCRYPTED_INDEX[i]]
                                   , flag_encrypted[len(CHARSET_ENCRYPTED[POSSIBLE_CHARSET_ENCRYPTED_INDEX[i]]):], flag + CHARSET[POSSIBLE_CHARSET_ENCRYPTED_INDEX[i]])
            if(result == "fuckedup"):
                continue
            else:
                return result
        return "fuckedup"
        

    flag_encrypted = EncryptFlag().decode()
    print('flag encrypted : ' + flag_encrypted)
    flag_encrypted = flag_encrypted[4:-1]

    print('-- start --')
    print(flag_encrypted)
    if(flag_encrypted.find(' ') != -1):
        p.close()
        continue
    """CHARSET_ENCRYPTED = list()
    for i in range(len(CHARSET)):
        CHARSET_ENCRYPTED.append(Encrypt(flag + CHARSET[i]).decode())
        print('{0} : {1}'.format(CHARSET[i], CHARSET_ENCRYPTED[i]))"""
    flag = ''
    print('GoN{' + DFS_find_flag(0, '', flag_encrypted, flag) + '}')
    break


p.interactive()

 

스크립트를 만들 때 유의할 점은 암호화된 값 중에 ' ' 공백 문자가 나오는 경우가 있다.

직접 다음 단계에서 문자를 합치고 encrypt 해보면 ' ' 공백 문자가 사라지는 것을 보았기에

그냥 flag 에 ' ' 공백 문자가 포함되면 다시 연결하고,

암호화하면서 depth 가 깊어지는 과정에서 ' ' 공백 문자를 strip 함수로 없애주었다.

 

잠깐 배워놓았던 알고리즘이 여기서 쓰일줄이야..