Description

Tears dripped from my face as I stood over the bathroom sink. Exposed again! The tears melted into thoughts, and an idea formed in my head. This will surely keep my secrets safe, once and for all. I crept back to my computer and began to type.

문제에서 RSA 파이썬 스크립트와 함께 암호화된 flag.enc파일과 공개키 key.sad.pub가 주어진다. key.sad.pub는 python의 pickle모듈을 통해 dump된 Key클래스 파일이다.

먼저 키 생성이 어떻게되는 것인지를 살펴보면 아래와 같습니다.

def genkey(bits):
	assert bits % 2 == 0
	while True:
		p = genprime(bits // 2)
		q = genprime(bits // 2)
		e = 65537
		d, _, g = egcd(e, (p-1) * (q-1))
		if g != 1: continue
		iQmP, iPmQ, _ = egcd(q, p)
		return Key(
			N=p*q, P=p, Q=q, E=e, D=d%((p-1)*(q-1)), DmP1=d%(p-1), DmQ1=d%(q-1),
			iQmP=iQmP%p, iPmQ=iPmQ%q, bits=bits,
		)

여기서 key.sad.pub은 N, iQmP, iPmQ, bits만이 남아있고, 나머지는 다 제거된 상태입니다.

iQmP, iPmQ, _ = egcd(q, p)

iQmP = a, iPmQ = b라고 나타내면 Bézout's identity에 의해서 a*q+b*p=1이 성립합니다.

$aq + bp = 1$

$A = a + px \\ B = b + qy$

이제 여기서 A*q + B*p를 계산해봅시다.

$Aq + Bp = (a+px)q + (b+qy)p \\ = aq + bp + pq(x+y)$

여기서 aq+bp=1이고 n=pq이므로 다시 정리하면 아래와 같습니다.

$Aq+Bp = N(x+y)+1$

그런데 이때 우리는 A와 B가 p와 q에 의해 나머지연산된 것이라는 것을 압니다. 그러므로

$(0 < A < p,　0<B<q,　N=pq)$
이고 결국 아래와 같습니다.

$0 < Aq+Bp = N(x+y)+1 < 2N$

$Aq+Bp = N+1$

이제 양옆에 p를 곱하게되면 아래와 같이 정리됩니다.

$Apq+Bpp = pN+p \\ AN+Bp^2 = pN+p$

$Bp^2-p(N+1)+AN = 0$

이제 우리가 잘아는 근의 공식을 사용하면 p를 구할 수 있습니다.

$\frac{(N+1) \pm \sqrt{(N+1)^2-4BAN}}{2B}$

BAN = ((N+1)**2) - 4*B*A*N
BAN, _ = gmpy.root(D, 2)

T = ((N+1)-(BAN))//(2*B)
P = T
Q = N/P
print(N==P*Q)
print("p : " + str(P))
print("q : " + str(Q))

myria@ctf:~/CTF/PlaidCTF/rusad$ python get_pq.py
p : 31659077809885706699482361830477717572837081779677626435829903374921581240849180063108552019274021826092781287218568613206006085334956822705610578514426596962412655157776833178744403034727698399320215892200440936975683502329350531806920697009386909154114556681774784614085691096050135180228131842452179315216957730905902673882170120973148157907231188547167482558383495097819905373068326760590890291412820411304614611983343203819383860434964843931325658872603238498210722446318497674396725811567139923114789843056157733621133155720503541819498078610854651245426825738313809229403279974283490718799392611854934535622307
q : 25004672227855409995386175663336188685177638541286666056441830847618100808198668167307814236224429885295241140194633625051478252429462828073782848889819460674774292004752724556602147320684206242726073358822655212944688523823150236245522627662371134165404316388528738697090763677910441487876514668914442018764569771021916503649822836288868439220382922721194436569302106969570041514638164319835688101248578648742016186666021527781591528560611986692317045407081396778512783312692838307769559661780971287324753785154074832628454871505400166651610503632212720604214996108967812794633118832616768643612648168060802523582631

이제 주어진 rusad.py를 이용해 key파일을 만들어준 후, decrypt하면됩니다.

myria@ctf:~/CTF/PlaidCTF/rusad$ python3 rusad.py decrypt -i flag.enc -o flag -k attack.priv

PCTF{Rub_your_hands_palm_to_palm_vigorously_for_at_least_20_seconds_to_remove_any_private_information}

Blind
Pull the flag...if you can.

nc blind.q.2019.volgactf.ru 7070

문제 설명은 위와 같고, server.py라는 파이썬 스크립트가 하나 주어집니다.
주어진 파이썬 스크립트는 아래와 같습니다.

#!/usr/bin/env python
from __future__ import print_function
import os
import sys
import shlex
import subprocess

from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes, bytes_to_long

privkey = RSA.generate(1024)
pubkey = privkey.publickey()


"""
    Utils
"""


def run_cmd(cmd):
    try:
        args = shlex.split(cmd)
        return subprocess.check_output(args)
    except Exception as ex:
        return str(ex)


"""
    Signature
"""

class RSA:
    def __init__(self, e, d, n):
        self.e = e
        self.d = d
        self.n = n

    def sign(self, message):
        message = int(message.encode('hex'), 16)
        return pow(message, self.d, self.n)

    def verify(self, message, signature):
        message = int(message.encode('hex'), 16)
        verify = pow(signature, self.e, self.n)
        return message == verify


"""
    Keys
"""


n = privkey.n
d = privkey.d
e = 65537
print("n : "+str(n))
print("d : "+str(d))
print("e : "+str(e))


"""
    Communication utils
"""

def read_message():
    return sys.stdin.readline()


def send_message(message):
    sys.stdout.write('{0}\r\n'.format(message))
    sys.stdout.flush()


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)


"""
    Main
"""

def check_cmd_signatures(signature):
    cmd1 = 'exit'
    cmd2 = 'leave'
    assert (signature.verify(cmd1, signature.sign(cmd1)))
    assert (signature.verify(cmd2, signature.sign(cmd2)))


class SignatureException(Exception):
    pass


if __name__ == '__main__':
    signature = RSA(e, d, n)
    check_cmd_signatures(signature)
    try:
        while True:
            send_message('Enter your command:')
            message = read_message().strip()
            (sgn, cmd_exp) = message.split(' ', 1)
            eprint('Accepting command {0}'.format(cmd_exp))
            eprint('Accepting command signature: {0}'.format(sgn))

            cmd_l = shlex.split(cmd_exp)
            cmd = cmd_l[0]
            if cmd == 'ls' or cmd == 'dir':
                ret_str = run_cmd(cmd_exp)
                send_message(ret_str)

            elif cmd == 'cd':
                try:
                    sgn = int(sgn)
                    if not signature.verify(cmd_exp, sgn):
                        raise SignatureException('Signature verification check failed')
                    os.chdir(cmd_l[1])
                    send_message('')
                except Exception as ex:
                    send_message(str(ex))

            elif cmd == 'cat':
                try:
                    sgn = int(sgn)
                    if not signature.verify(cmd_exp, sgn):
                        raise SignatureException('Signature verification check failed')
                    if len(cmd_l) == 1:
                        raise Exception('Nothing to cat')
                    ret_str = run_cmd(cmd_exp)
                    send_message(ret_str)
                except Exception as ex:
                    send_message(str(ex))

            elif cmd == 'sign':
                try:
                    send_message('Enter your command to sign:')
                    message = read_message().strip()
                    message = message.decode('base64')
                    cmd_l = shlex.split(message)
                    sign_cmd = cmd_l[0]
                    if sign_cmd not in ['cat', 'cd']:
                        sgn = signature.sign(sign_cmd)
                        send_message(str(sgn))
                    else:
                        send_message('Invalid command')
                except Exception as ex:
                    send_message(str(ex))

            elif cmd == 'exit' or cmd == 'leave':
                sgn = int(sgn)
                if not signature.verify(cmd_exp, sgn):
                    raise SignatureException('Signature verification check failed')
                break

            else:
                send_message('Unknown command {0}'.format(cmd))
                break

    except SignatureException as ex:
        send_message(str(ex))
        eprint(str(ex))

    except Exception as ex:
        send_message('Something must have gone very, very wrong...')
        eprint(str(ex))

    finally:
        pass

위 파이썬 스크립트는 서버에 sign값과 cmd값을 보내면 특정 명령어를 실행할 수 있습니다.
사용가능한 명령어는 ls, dir, cd, cat으로 여기서 ls, dir은 sign값 없이도 실행할 수 있지만 cd, cat은 sign값이 필요합니다.

def run_cmd(cmd):
    try:
        args = shlex.split(cmd)
        return subprocess.check_output(args)
    except Exception as ex:
        return str(ex)

while True:
    send_message('Enter your command:')
    message = read_message().strip()
    (sgn, cmd_exp) = message.split(' ', 1)
    eprint('Accepting command {0}'.format(cmd_exp))
    eprint('Accepting command signature: {0}'.format(sgn))

    cmd_l = shlex.split(cmd_exp)
    cmd = cmd_l[0]
    if cmd == 'ls' or cmd == 'dir':
        ret_str = run_cmd(cmd_exp)
        send_message(ret_str)

    elif cmd == 'cd':
        try:
            sgn = int(sgn)
            if not signature.verify(cmd_exp, sgn):
                raise SignatureException('Signature verification check failed')
            os.chdir(cmd_l[1])
            send_message('')
        except Exception as ex:
            send_message(str(ex))

    elif cmd == 'cat':
        try:
            sgn = int(sgn)
            if not signature.verify(cmd_exp, sgn):
                raise SignatureException('Signature verification check failed')
            if len(cmd_l) == 1:
                raise Exception('Nothing to cat')
            ret_str = run_cmd(cmd_exp)
            send_message(ret_str)
        except Exception as ex:
            send_message(str(ex))

그리고 cat, cd를 제외한 모든 문자열에 대해서 서버로 부터 sign값을 받아낼 수 있습니다.

elif cmd == 'sign':
    try:
        send_message('Enter your command to sign:')
        message = read_message().strip()
        message = message.decode('base64')
        cmd_l = shlex.split(message)
        sign_cmd = cmd_l[0]
        if sign_cmd not in ['cat', 'cd']:
            sgn = signature.sign(sign_cmd)
            send_message(str(sgn))
        else:
            send_message('Invalid command')
    except Exception as ex:
        send_message(str(ex))

먼저 ls 명령을 통해 파일 목록을 보면 flag가 있는 것을 볼 수 있습니다.

그러므로 cat flag의 sign값을 알아내기만 하면 flag를 얻을 수 있습니다.

공격법으로는 RSA 암호의 특징을 이해하고, mod 연산의 특성을 알면 쉽게 생각해낼 수 있는 방법이 있습니다. 이에 대한 증명은 위키피디아 등에 찾아보면 아주 자세히 증명해놓았기 때문에 여기서 설명하진 않겠습니다.

1. 먼저 서명할 메세지(m / "cat flag")를 정수로 변환하여 약수를 구합니다.
   m = 2 * 3 * ....
2. 구한 약수 중 하나(r)를 임의로 선택합니다.
   r = 2
3. m/r을 서명합니다.
   S1 = (m/r)^d mod N
4. r을 서명합니다.
   S2 = (r)^d mod N
5. S1과 S2를 곱합니다.
   S1 * S2 = (r)^d mod N * (m/r)^d mod N = (m)^d mod N = S'
6. S'를 서명으로 하여 m을 전송합니다.
   S'^e mod N = m^ed mod N = m

위와 같이 되어 sign 필터링을 우회하여 cat flag를 서명할 수 있습니다.
위를 바탕으로 exploit을 짜면 아래와 같습니다.

from pwn import *
from base64 import b64encode
import shlex

conn = remote("blind.q.2019.volgactf.ru", 7070)

conn.recvuntil("Enter your command:")

# sign1
payload = "1 sign"
conn.sendline(payload)

conn.recvuntil("Enter your command to sign:")
m = int("cat flag".encode('hex'), 16)
m_1 = m/408479
m_1 = ("0"+(hex(m_1)[2:])).decode("hex")

payload = b64encode(m_1)
conn.sendline(payload)
conn.recvline()

sign1 = int(conn.recvline().strip())
log.info("sign1 : " + str(sign1))

# sign2
conn.recvuntil("Enter your command:")
payload = "1 sign"
conn.sendline(payload)

conn.recvuntil("Enter your command to sign:")
payload = b64encode(p32(408479)[::-1][1:]) # 408479
conn.sendline(payload)
conn.recvline()

sign2 = int(conn.recvline().strip())
log.info("sign2 : " + str(sign2))

## mix!
sign = sign1*sign2
log.info("sign : " + str(sign))

conn.recvuntil("Enter your command:")
payload = str(sign) + " "
payload += "cat flag"
conn.sendline(payload)

conn.interactive()

대회가 끝나고 나서 알았는데, Blind RSA signatures Attack이라는게 있었습니다.
문제명도 Blind인 것을 보니... 제가 한 공격이 아니라 이 공격이 원래 의도한 문제풀이였나봅니다. Blind RSA attack도 간단해서 한번 정리해봅니다.

1. 먼저 임의의 수 r을 선택합니다. (이때 r은 n과 서로수),
   gcd(r, n)==1
2. 메세지(m)을 서명한 r과 곱합니다. 그리고 r은 r^-1를 구합니다.
   m' ≡ m*r^e (mod n), r^{-1} (mod n)
3. m'를 서명합니다.
   s' ≡ (m')^d (mod n)
4. s'에 r^-1를 곱하게 되면 m^d mode N을 구할 수 있습니다.
   s ≡ s'r' ≡ m^d (mod n)

관련 사이트 :
위키피디 https://en.wikipedia.org/wiki/Blind_signature#Blind_RSA_signatures
Blinding Attack on RSA Digital Signatures https://masterpessimistaa.wordpress.com/2017/07/10/blinding-attack-on-rsa-digital-signatures/

Blind RSA attack을 이용한 exploit입니다.

from pwn import *
import gmpy
from gmpy2 import gcd

n = 26507591511689883990023896389022361811173033984051016489514421457013639621509962613332324662222154683066173937658495362448733162728817642341239457485221865493926211958117034923747221236176204216845182311004742474549095130306550623190917480615151093941494688906907516349433681015204941620716162038586590895058816430264415335805881575305773073358135217732591500750773744464142282514963376379623449776844046465746330691788777566563856886778143019387464133144867446731438967247646981498812182658347753229511846953659235528803754112114516623201792727787856347729085966824435377279429992530935232902223909659507613583396967
e = 65537

m = int('cat flag'.encode('hex'), 16)
r = 2
"""
while True:
    if gcd(r,n)!=1:
        r+=1
        continue
    m1 = (m*r**e)%n
    m1 = hex(m1)[2:-1] # cut leading '0x'
    if (len(m1)%2 == 1): m1 = '0' + m1 # adjust padding
    m1 = m1.decode('hex')
    print('r = ' + str(r))
    try:
        res = shlex.split(m1)[0]
    except:
        r+=1
        continue
    if (res == m1):
        print('r = ' + str(r))
        break
    r += 1
"""
r = 6631

# connect to ctf server
conn = remote('blind.q.2019.volgactf.ru', 7070)
conn.recvuntil('Enter your command')

# sign modified message m1
conn.sendline('1 sign')
conn.recvuntil('Enter your command to sign:')
conn.sendline(m1)

# receive signature s1
conn.recvline()
resp = conn.recvline()
s1 = int(resp)

# calculate signature s from s1 and r
s = s1*int(gmpy.invert(r,n))%n

# send command 'cat flag' with appropriate signature
conn.sendline(str(s) + ' cat flag')
conn.interactive()

몇 일전에 있었던 BSidesSF CTF 2019에 나왔던 문제를 풀어보겠다. mixxer라는 문제로 Web과 Crypto분야의 문제이다.

Log in as administrator!

(Check out the user cookie)

Location - https://mixer-f3834380.challenges.bsidessf.net/

주어진 url을 통해 웹사이트에 들어가게 되면 로그인을 할 수 있는 페이지가 나온다. 권한을 높여라!라고 크게 적혀있고, 로그인할 수 있는 폼이 있다.

일단 활성화되어있는 칸이 2개 있으므로, admin을 입력하면 아래와 같은 내용이 나온다.

is_admin의 값이 1로 설정되어야하는 것 같다. 하지만 is_admin은 칸은 비활성화되어있어 값을 수정할 수 없다. 그래서 제일 먼저 생각나는 크롬 개발자 도구를 이용해보았다.

값을 1로 바꾸는데 성공하였다. 그러나 저 상태로 아무리 로그인을 시도하여도 아래 메세지는 변함이 없었다...

Welcome back, admin admin!

It looks like you aren't admin, though!
Better work on that! Remember, is_admin must bet set to 1 (integer)!
And you can safely ignore the rack.session cookie. Like actually. But that other cookie, however....

웹페이지에 걸려있는 Note와 로그인 시도시 나오는 문구를 살펴보면 rack.session 쿠키는 무시하고, 다른 쿠키값이 문제를 풀기 위한 키포인트일 것 같다.

그래서 페이지의 쿠키를 살펴본 결과 user라고하는 수상한 쿠키값을 발견할 수 있었다.

그러나 아직 이 값이 무엇인지 모르겠다... 그래서 Burp suite를 사용하여 값이 어떻게 넘어가는지 살펴보았다.

! ? is_admin의 값은 넘어가지않고, action, first_name, last_name의 값만 파라미터로 넘어가는것을 알 수 있었다. 왠지 is_admin은 아무리 바꾸어도 user쿠키나 그 무엇에도 영향이 없더라 ...

그리고 소스코드를 살펴보면 is_admin은 name이 지정되어있지않은것을 알 수 있다.

뭐 아무튼 그렇다면 이제 남은것은 user라는 쿠키값이다. first_name과 last_name을 여러번 넣어보면 이 user라는 쿠키값이 어떻게 나오는지 유추할 수 있다.

Fisrt name : aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

 Last name : b user Cookie : f75f9acf55c0f1efbfedd5509e2cb55fbd3fc0da723d226f5d2dd82478531b24bd3fc0da723d226f5d2dd82478531b245c36e6b0b2e6ef806cad8c1dce32c2f4f72de03131106d5a3f8384d2aadf9d2c

Fisrt name : aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

 Last name : bb user Cookie : f75f9acf55c0f1efbfedd5509e2cb55fbd3fc0da723d226f5d2dd82478531b24bd3fc0da723d226f5d2dd82478531b245c36e6b0b2e6ef806cad8c1dce32c2f4543f1ee77054c119fdfa2343152015ece379f6cd6b130380dd363f9d48a409ea

위 입력을 인자로 주었을 때, 두 쿠키값이 비슷함을 볼 수 있다. 즉, 이 쿠키값은 적어도 해시값이 아닌 일정한 암호화과정이 있다는 것이다. 또한 Last name의 길이가 1늘어남에 따라 user의 길이는 32만큼 증가하였다.

즉, 블록크기만큼 끓어 암호화하는 블록암호일 가능성이 생겼다. 그러므로 user Cookie를 32문자씩 끓어비교하면 아래와 같다.

f75f9acf55c0f1efbfedd5509e2cb55f
bd3fc0da723d226f5d2dd82478531b24
bd3fc0da723d226f5d2dd82478531b24
5c36e6b0b2e6ef806cad8c1dce32c2f4
f72de03131106d5a3f8384d2aadf9d2c

2번째 블록과 3번째 블록이 같음을 알 수 있다. 이는 아마 aaaaaaaaaaaaaaaa가 암호화된 결과일 것이다.

자. 그렇다면 이제 위와 같은 결과들을 통해 조심스럽게 이 user라는 쿠키는 AES-ECB mode를 통해 암호화되었다고 유추해볼 수 있다.

그렇다면 이제 할 일은 간단한데, 이전에 필자가 올린 글 중 CSAW Quals 2017 BabyCrypt Writeup에서 사용했던던 Byte_at_a_time_ECB_decryption기법을 이용해 공격해보는 것이다.

import requests
import string

alpha = string.ascii_letters+string.digits

def encryption_oracle(plain):
	print(plain)
	url = "https://mixer-f3834380.challenges.bsidessf.net/"

	session = requests.Session()

	parameter = "?action=login&first_name="+plain+"&last_name="
	new_url = url + parameter
	cookies = {'rack.session': 'BAh7B0kiD3Nlc3Npb25faWQGOgZFVEkiRThmMTYzMzAwM2Q5NjgyNmUwN2Rh%0AOWU5MzY2MzFkNzBjMmI0OWY2ZjYxMzRkYTIyNzhlY2NlNWU2NmI5ODZlZmIG%0AOwBGSSIMYWVzX2tleQY7AEYiJVzOrjIKbvpJ9eq5eel4KQ4hCry4b4wQeVGT%0AZzmWrYHk%0A--97592bb99a0aea52091f7361fa4238deac2f4df3'}
	response = session.get(new_url, cookies=cookies)
	user = session.cookies.get_dict()['user']

	return user.decode("hex")



def find_block_size(encryption_oracle):
	pre_cp = encryption_oracle("")
	p = "A"
	while(True):
		cp = encryption_oracle(p)
		size = len(cp)-len(pre_cp)
		if size != 0:
			return size
		p+="A"

def get_next_byte(encryption_oracle, known_suffix, block_size, prefix_size):
	dic = {}
	feed = "A"*(block_size-(prefix_size%block_size))
	feed += "A"*(block_size-1-(len(known_suffix)%block_size))

	for i in range(0x00,0x7F):
		pt = feed + known_suffix + "%"+hex(i)[2:].rjust(2, "0")
		ct = encryption_oracle(pt)[:len(pt)+prefix_size]
		dic[ct]=chr(i)
	ct = encryption_oracle(feed)[:len(feed + known_suffix)+1+prefix_size]

	if ct in dic:
		return dic[ct]
	else:
		return ""

BLOCK_SIZE = 16
PREFIX_SIZE = 15
print("BLOCK_SIZE  : %d" % BLOCK_SIZE)
print("PREFIX_SIZE : %d" % PREFIX_SIZE)
secret = ""

while(True):
	one_byte = get_next_byte(encryption_oracle, secret, BLOCK_SIZE, PREFIX_SIZE)
	if one_byte == "":
		break
	secret += one_byte
	print(secret)
print("result : "+secret)

이제 위 코드를 돌리면 user라는 쿠키값의 원래 값을 알아낼 수 있을 것으로 예상되었으나... 실패하였다;;

대신 다른 재미있는 결과를 얻을 수 있었는데, \x80인 아스키범위를 넘어가는 값이 들어갔을 경우이다.

JSON::GeneratorError를 볼 수 있는데, 파라미터가 json 형식으로 전달되어 user값으로 암호화되는 것을 알 수 있다.

그렇다면 user 쿠키값의 뒷 부분만 조금 변경하면 is_admin값에 영향을 줄 수 있을것이라 생각되어 조금 변경해보았다.

와우.. 새로운 오류메세지를 발견함과 동시에 암호화되기전의 user값을 유추할 수 있다.

{"first_name":"admin","last_name":"bb","is_admin":0}

그렇다면 이제 간단해진다. 우리는 First_name과 Last_name을 마음대로 쓸 수 있으므로 원하는 평문값을 AES-ECB로 암호화하여 바꿔쓰기할 수 있다. AES-ECB의 블록크기는 16bytes이므로 아래와 같이 payload를 구성하여 암호화된 user쿠키값에서 2번째 블록의 내용을 5번째 블록에 바꿔넣어준다면, is_amdin값은 1로 설정될 것이다.

Fisrt name : X1.0000000000000} Last name : XXXX user Cookie : 97333dd079886bf10452d25f119e24ec316eefd0b1d1734f116488a927fca3f7ccad1e8a1ed41ef310a377abe5c651d903c772d4cd5279ec078ead4300c3f294006c43bbbb599339783cac770c7371b7

Plain(json) : {"first_name":"X 1.0000000000000} ","last_name":"X XXX","is_admin": 0}

Cipher(user Cookie) : 97333dd079886bf10452d25f119e24ec 316eefd0b1d1734f116488a927fca3f7ccad1e8a1ed41ef310a377abe5c651d9 03c772d4cd5279ec078ead4300c3f294 006c43bbbb599339783cac770c7371b7

이제 쿠키값의 5번째 블록을 2번째 블록과 같은 값으로 바꿔주면 아래와 같이 될 것이다.

Plain(json) : {"first_name":"X 1.0000000000000} ","last_name":"X XXX","is_admin": 1}

Cipher(user Cookie) : 97333dd079886bf10452d25f119e24ec 316eefd0b1d1734f116488a927fca3f7ccad1e8a1ed41ef310a377abe5c651d9 03c772d4cd5279ec078ead4300c3f294 316eefd0b1d1734f116488a927fca3f7

user Cookie : 97333dd079886bf10452d25f119e24ec316eefd0b1d1734f116488a927fca3f7ccad1e8a1ed41ef310a377abe5c651d903c772d4cd5279ec078ead4300c3f294316eefd0b1d1734f116488a927fca3f7

이제 웹페이지에 user쿠키값을 위의 변조된 쿠키값으로 바꾸고 새로고침을 누르면 is_admin의 값이 1로 되어 flag를 얻을 수 있다.

*후기

왜 처음에 시도한 Byte_at_a_time_ECB_decryption이 성공하지 못했는지 생각해보니 "라는 값을 넣게되면 \"로 자동으로 바뀌기때문에... 성공할 수 없었던 것이였다. 덕분에 아쉽게 대회중에는 풀지 못했지만, 그래도 Web과 Crypto를 같이 붙여놓은 문제를 풀어볼 수 있는 좋은 기회였던 것 같다.

X-MAS CTF에 나온 암호문제중 하나입니다. CTF는 12.14 ~ 12.21에 진행된 CTF로 크리스마스 분위기가 물씬 풍기는 CTF였습니다. (Christmas 당일까지 진행하지않은게 정말 다행이네요 ㅎㅎ;; )

Special Christmas Wishlist (50 pts)

Description

While Santa was looking through the wishlists of the childern all around the world he came across a very strange looking one. Help Santa decode the letter in order to fulfill the wishes of this child.

(Flag is Non-Standard)

UPDATE: flag is lowercase!

Author: Gabies

Files: 

wishlist.zip

문제는 조금 어렵게 나왔다고 생각했는데... 대회가 종료될때에 Solver가 124팀으로 점수는 50점까지 낮아졌습니다.

먼저 문제설명을 살펴보면 "산타가 전 세계 어린이들이 보내온 Wishlist를 보고있는데 이~상한 Wishlist를 발견했다고 합니다. 그 희망목록은 산타가 읽을 수 없는 문자들로 가득했는데...! 산타가 문자를 읽을 수 있게 도와 아이의 소원을 이루어주세요!" 같은 내용입니다.

그래서 주어진 첨부파일인 wishlist.png를 살펴보면 정말 알 수 없는 문자들로 가득 채워진 그림을 볼 수 있습니다. 이미지파일이 세로로 정말 길기 때문에 일부만 가져와보겠습니다.

이야... 진짜 무엇 하나도 키보드로 표현할 수 없는 문자들뿐입니다. 대체 이걸 어떻게 124팀이나 푼지 모르겠습니다 :(. 스코어에 등록된게 1378팀인데... 뭐 아무튼 이런 류의 문제들이 가끔식 CTF에서 나오는데요. 계속해서 못 풀다가 이번 기회에 그러면 아예 제대로 공부해놓자! 해서 이 문제를 가지고 Writeup을 작성하게되었습니다.

문제로 돌아와서 주어진 wishlist.png파일은 비아스키문자들과 공백으로 이루어진 문자가 73줄 나열되어있습니다. 또한 문자와 공백들의 나열을 보고 유추하건데, 이 문제는 단순치환암호(Simple Substitution Cipher)일 것으로 보입니다.

그렇다면 이제 저 이미지의 모든 문자를 알파벳으로 치환한 후, 빈도수 분석을 이용하여 문제를 풀 수 있을 것으로 보입니다. 그런데 이미지의 문자 하나하나를 손으로 직접 바꾸는 것은 정말 어려운 문제입니다 ㅡㅡ;

저번에 있었던 RITSEC CTF 2018의 Nobody uses the eggplant emoji 에서는 위 문제와 마찬가지로 비아스키문자들로 이루어진 단순치환암호였지만 텍스트파일로 주어져 쉽게 알파벳으로 치환할 수 있었습니다.

chal.txt 🤞👿🤓🥇🐼💩🤓🚫💪🤞🗣🙄🤓🥇🐼💩🤓😀✅😟🤓🍞🐼✅🚫💪🥇🤓🐼👿🤓🚫💪😟🤓👿😾😀😯🤓👿🤞✅🔥🚫🤓🥇🐼💩🤓👻💩🔥🚫🤓😀🗣🔥🍞😟✅🤓🚫💪😟🔥😟🤓🚫💪✅😟😟🤓💔💩😟🔥🚫🤞🐼🗣🔥😭🤓🍞💪😀🚫🤓🤞🔥🤓🥇🐼💩🤓🗣😀👻😟🤢🤓🍞💪😀🚫🤓🤞🔥🤓🥇🐼💩✅🤓💔💩😟🔥🚫🤢🤓🍞💪😀🚫🤓🤞🔥🤓🚫💪😟🤓😀🤞✅🤓🔥🐙😟😟😎🤓👀😟😾🐼🤬🤞🚫🥇🤓🐼👿🤓😀🗣🤓💩🗣😾😀😎😟🗣🤓🔥🍞😀😾😾🐼🍞😭🤓🥇🐼💩✅🤓👿😾😀😯🤓🤞🔥🤡🤓😀👿✅🤞🤬😀🗣_🐼✅_😟💩✅🐼🐙😟😀🗣_🔥🍞😀😾😾🐼🍞_🍞🐼🍞_🚫💪😟✅😟🔥_😀_😎🤞👿👿😟✅😟🗣🤬😟🤓 __

하지만 이번에 주어진 문제는 텍스트파일이 아닌 이미지파일로 주어졌기 때문에, 이미지파일에서 각 문자를 추출하여 아스키문자로 표현해줄 필요가 있습니다.

위와 같이 각 문자당 하나의 알파벳을 할당하는 것이 목표입니다. 이를 위해 파이썬 라이브러리인 Pillow를 사용하는데, Pillow는 PIL(Python Image Library)를 계승한 라이브러리입니다. 더이상 업데이트가 되지 않는 PIL 대신 사용하는 파이썬 라이브러리로 이를 통해 손쉽게 파이썬을 이용해서 이미지 파일을 다룰 수 있습니다.

from PIL import Image
from string import ascii_lowercase

img = Image.open('wishlist.png').convert('1', dither=False)
lines = scan(img)
print(translate(lines))

먼저 PIL을 통해 Image를 불러옵니다. 옵션과 모드로 1-bit-pixel mode 와 dither=False를 선택하는데, 1-bit-pixel mode는 black인지 white인지만 판별하는 모드로 위 이미지의 문자는 흑백의 두 색으로만 이루어져있으므로 1bit모드로 충분합니다. 또 dither를 False로 설정하였는데 이는 이미지 프로세싱에서 많이 쓰이는 디더링(Dithering)이라는 것으로, 제한된 색을 이용하여 음영이나 색을 나타내는 것이며, 여러 컬러의 색을 최대한 맞추는 과정입니다.

이 디더(dither)를 False로 설정하면 음영을 구분하지않아 흑백으로만 그림이 나타날 것이므로 좀 더 편하게 문자열을 구분할 수 있습니다.

def scan(img):
	lines = []
	line_x, line_y = 30, 0
	while True:
		x, y = search(img, line_x, line_y, True, fix_x=True)
		if (x, y)==(None, None): break
		line = []
		while True:
			x, y = search(img, x, y, True, fix_y=True)
			if (x, y)==(None, None): break
			letter = bfs(img, x, y)
			line.append(normalize(letter))
			(min_x, min_y), (max_x, max_y) = bounds(letter)
			x = max_x + 1
			y = (max_y + min_y) // 2
		lines.append(line)
		line_y = max_y + 30
	return lines

이제 맨 윗줄부터 왼쪽에서 오른쪽으로 이동하면서 이미지 위의 문자를 찾습니다. 여기서 중요한 점은 이미지 위에 나타난 모든 문자들이 끓어지지않고 연속된 선으로 이루어져있다는 것입니다. 그러므로 이를 너비우선탐색(BFS)를 통해 각 문자에 대해 트리를 만들수 있습니다.

def bfs(img, start_x, start_y):
	queue = [(start_x, start_y)]
	visited = set(queue)
	for x, y in queue:
		for dx, dy in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]:
			xx, yy = x + dx, y + dy
			if img.getpixel((xx, yy)) > 0:
				continue
			if (xx, yy) not in visited:
				queue.append((xx, yy))
				visited.add((xx, yy))
	return visited

이제 각 줄의 문자마다 만들어진 트리들을 가지고 같은 트리에는 같은 문자를 할당하여 나타내면 됩니다.

def translate(lines):
	alpha = dict()
	index = 0
	text = ''
	for line in lines:
		for letter in line:
			if letter not in alpha:
				alpha[letter] = ascii_lowercase[index]
				index += 1
			text += alpha[letter]
		text += '\n'
	return text

이제 이 소스코드를 실행하면 아래와 같은 결과를 얻을 수 있습니다.

abcdcefgahijdcefgkhelgldji
jdmbnngnbodapqhhrgifl
kcoaqggmjabllgllgchncsh
qbffhjsdlfhoceoqagml
bftgicemgmoeacdchhauadvsbcuk
csdjobmlkobaahslrgsgm
iglcdijlchmbjguhicbdigml
lodadijwdxhjbmfgilueavcemg
ahijfdlcbiugcheukabov
oeacduhahmhoqmglcgoagllsdigjablllgc
vgfglcbawgsgampkhafgm
bmcdlbibaqboqhhlbacukglc
bemhmblobmcadjkcdijvbigal
ckglgblgmvgicjbmfgilueavcemg
ckgyedcgbobxdijyeglcnhmyegmdgl
mgupuagfjabllcmggjahqglmgabcdhilkdvl
igsphmrcdogluelchonmhicvbjgvexxag
ckgqglcladijqgtgmbjguhhagm
cmdhodzgfogcbalgbmmdijl
qdmckohicknahsgmigurabug
bohckgmlahtgdlqgphifogblemglvhhilgc
sgffdijsbacxvgmlhibadxgfbmc
vgmlhibadxgfjhhfidjkcadccagogqhhr
uelchovgcihlgvmdicigurabugl
uelchovgcvdaahsl
ysgmcprgpqhbmf
aabobmbobabmjgxdvvgmvheuk
odohlbfdbjmbojabllsbmglgchnckmgg
ckbirphenhmphemvbmcdiopwhemigpigurabug
phjbvhlgkbijdijlueavcemgl
ckgqdrgukbdiqhsa
umdolhikgbmceoqmgaab
ckgyedxdildfgckgobxg
ogilkgmqbasbmodijladvvgml
phemlodigbifhemlgijmbtgffgubicgmlgc
ckgbiidtgmlbmpwhemiba
ohoobqdmfuenn
sdigqbmmgajedcbmmbur
ckgvaelkhmjbil
jbmadujmbcgmbifhdafdvvdijfdlk
hrchqgmnglcbagqggmqmgsdijrdc
obcglnhmadng
qhhrahtgmladjkcsgdjkclubmtgl
uhilcdcecdhihneidcgflcbcglhnbogmdubjabll
jhanjabllglvgscgmbijgauhdillgchncsgatg
qeiipngacqbqpladvvgml
vgmlhibadxgfcmggcmeirjabllsbmgfeh
gzvgucdijphebrggvlbrgvmgjibiupwhemiba
ckgqgmmpqeffp
ckgqdmfdgpbmiqhsa
rbickbukbifgadgmlgbmmdijl
vgmlhibadxgfoptgmphsiibogqhhr
eiduhmibifmbdiqhsodlobcukgfgbmmdijl
lahckvbalohqdag
qbchibqmbiuk
vgmlhibadxgfueccdijqhbmf
lohrgfgcguchmfgbucdtbcdhichsga
ckgaeigadjkc
vgmlhibadxgfbiidtgmlbmpvelkvdielbobv
ogilcbuhlhurl
gashhfckgeiduhmiugmgbaqhsa
ckgadccagvbcdgic
udmuaghnnbodapbifnmdgifllgmtdijqhsa
jabllnahsgmjbmfgiugicgmvdgug
qdmcklchigodigmbalhbvl
lgchnnhemjhanjabllgl
ckgugfbmckeoqvdbihl
uelchoobvuhblcgmlgc
qdjvgmlhibadcpfglrldjil
lgblchiglvablklvhijgkhafgm
phemohlcfgldmgfhqwgucckdlukmdlobl
ckgnabjdl
zoblphebmglhjhhfbcleqlcdcecdhiudvkgml

자 그럼 이제 분도수 분석을 통해, 단순치환암호를 풀면 됩니다. quipquip를 이용하면 쉽게 단순치환암호문제를 풀 수 있습니다.

latitude longitude house sign giraffe family book ends html beer glasses set of two bad dog wisdom tumblers adventurer multi tool clip watch twig marsh mallow skewer nesting storage containers smiling jizo garden sculpture long distance touch lamp multi color ombre stem less wine glass set pedestal jewelry holder artisan al bamboo salt chest aurora smart lighting panels the sea serpent garden sculpture the quite amazing quest for queries recycled glass tree globes relationships new york times custom front page puzzle the best sling beverage cooler trio mixed metals earrings birth month flower necklace a mothers love is beyond measure spoon set wedding waltz personalized art personalized good night little me book custom pet nose print necklaces custom pet pillows qwerty keyboard llama rama large zipper pouch mimosa diagram glass ware set of three thank you for your part in my journey necklace yoga pose hanging sculptures the bike chain bowl crimson heart umbrella the quiz inside the maze mens herbal warming slippers yours mine and ours engraved decanter set the anniversary journal momma bird cuff wine barrel guitar rack the plush organs garlic grater and oil dipping dish oktober festale beer brewing kit mates for life book lovers lightweights carves constitution of united states of america glass golf glasses pewter angel coins set of twelve bunny felt baby slippers personalized tree trunk glass ware duo expecting you a keepsake pregnancy journal the berry buddy the birdie yarn bowl kantha chandeliers earrings personalized my very own name book unicorn and rainbow mismatched earrings sloth pals mobile baton a branch personalized cutting board smoke detector deactivation towel the lune light personalized anniversary push pinus a map mens taco socks elwood the unicorn cereal bowl the little patient circle of family and friends serving bowl glass flower garden centerpiece birth stone mineral soaps set of four golf glasses the cedar thumb pianos custom map coaster set big personality desk signs sea stone splash sponge holder your most desired object this chrism as the flag is xmas you are so good at substitution ciphers

FLAG는 마지막 줄에 있습니다. flag is xmas you are so good at substitution ciphers

전체소스

#!/usr/bin/python3

from PIL import Image
from string import ascii_lowercase


def search(img, start_x, start_y, need_color, fix_x = False, fix_y = False):
	found = False
	for y in range(start_y, img.height) if not fix_y else [start_y]:
		for x in range(start_x, img.width) if not fix_x else [start_x]:
			color = (img.getpixel((x, y)) == 0)
			if (color and need_color) or (not color and not need_color):
				found = True
				break
		if found:
			break

	if found:
		return (x,y)
	else:
		return (None, None)


def bfs(img, start_x, start_y):
	queue = [(start_x, start_y)]
	visited = set(queue)
	for x, y in queue:
		for dx, dy in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]:
			xx, yy = x + dx, y + dy
			if img.getpixel((xx, yy)) > 0:
				continue
			if (xx, yy) not in visited:
				queue.append((xx, yy))
				visited.add((xx, yy))
	return visited


# search google : python zip(*list)
def bounds(letter):
	x, y = zip(*list(letter))
	min_x, min_y = min(x), min(y)
	max_x, max_y = max(x), max(y)
	return (min_x, min_y), (max_x, max_y)


def normalize(letter):
	(min_x, min_y), (max_x, max_y) = bounds(letter)
	normal = set()
	for x, y in letter:
		xx, yy = x - min_x, y - min_y
		normal.add((xx, yy))
	return frozenset(normal)

def scan(img):
	lines = []
	line_x, line_y = 30, 0
	while True:
		x, y = search(img, line_x, line_y, True, fix_x=True)
		if (x, y)==(None, None): break
		line = []
		while True:
			x, y = search(img, x, y, True, fix_y=True)
			if (x, y)==(None, None): break
			letter = bfs(img, x, y)
			line.append(normalize(letter))
			(min_x, min_y), (max_x, max_y) = bounds(letter)
			x = max_x + 1
			y = (max_y + min_y) // 2
		lines.append(line)
		line_y = max_y + 30
	return lines


def translate(lines):
	alpha = dict()
	index = 0
	text = ''
	for line in lines:
		for letter in line:
			if letter not in alpha:
				alpha[letter] = ascii_lowercase[index]
				index += 1
			text += alpha[letter]
		text += '\n'
	return text


def main():
	img = Image.open('wishlist.png').convert('1', dither=False)
	lines = scan(img)
	print(translate(lines))

if __name__ == '__main__':
	main()