Codegate2018 miro

By ccoma | February 18, 2018

Codegate2018 Boom 출제자 Write Up

안녕하세요. 이번 Codegate2018 예선에 boom과 miro를 출제한 ccoma입니다.
이번 글에서는 miro의 풀이에 대해 간단히 다루어보려고 합니다.

문제를 확인해 보면 Do you wanna play the game? :D 라는 설명과 함께 miro.pcap, client.py, 2개의 파일을 다운받을 수 있습니다.


client.py 파일을 실행시키면 서버와의 통신을 통해 아래와 같은 미로 게임을 수행할 수 있습니다.



그런데 client.py를 통해 오른쪽과 아래로는 이동할 수 있지만, 왼쪽과 위쪽으로 가기 위해 값을 입력하면 Sorry.. Not support function..를 출력하고 프로그램이 종료됩니다.



client.py의 코드를 확인해 보면 다음과 같습니다.


from socket import *
from ssl import *
import time

def recv_until(s, string):
    result = ''
    while string not in result:
        result += s.recv(1)
    return result

client_socket=socket(AF_INET, SOCK_STREAM)
tls_client = wrap_socket(client_socket, ssl_version=PROTOCOL_TLSv1_2, cert_reqs=CERT_NONE)

print "[+] Connecting with server.."

tls_client.connect(('ch41l3ng3s.codegate.kr',443))

print "[+] Connect OK"

while 1:
    data = recv_until(tls_client, "Input : ")
    print data
    #message
    user_input = raw_input()

    if user_input == "u":
        print "Sorry.. Not support function.."
        exit()
    elif user_input == "d":
        tls_client.send("6423e47152f145ee5bd1c014fc916e1746d66e8f5796606fd85b9b22ad333101\n")
    elif user_input == "r":
        tls_client.send("34660cfdd38bb91960d799d90e89abe49c1978bad73c16c6ce239bc6e3714796\n")
    elif user_input == "l":
        print "Sorry.. Not support function.."
        exit()
    else:
        print "Invalid input!"
        exit()    

client_socket.shutdown(SHUT_RDWR)
client_socket.close()


서버와 통신을 하는 클라이언트의 소스코드이지만, 단순 TCP 통신이 아니라 TLS 1.2로 통신하는 것을 알 수 있습니다.


또한 오른쪽과 아래로 이동하기 위한 값을 입력하면 특정 해쉬 값이 서버에 전송되지만, 위쪽과 아래쪽으로 이동하기 위한 값을 입력하면 Sorry.. Not support function.. 를 출력하고 프로그램을 종료합니다.

따라서 미로를 통과 해 [G]로 가기 위해선 주어진 pcap 파일을 사용해야 합니다.


pcap 파일을 열어 보면 서버와 클라이언트가 통신 한 패킷이 캡쳐되어 있으며, TLS 1.2로 암호화 되어 있는 것을 확인할 수 있습니다.


따라서 암호화 된 패킷을 복호화 한 후, 위쪽과 왼쪽으로 이동할 때 전송하는 값을 찾아야 합니다.


패킷을 복호화 하기 위해선 Private Key가 필요 합니다.

즉, 문제를 해결하기 위해 패킷에서 먼저 인증서를 추출한 후, 인증서에서 공개키를 추출, 이 후 이를 바탕으로 개인키를 만들어 패킷을 복호화 해야 합니다.



1. Certificate 추출

패킷 중 Certificate 패킷에서 통신 시 사용하는 Certificate을 추출할 수 있습니다.


Certificate 추출 방법은 다음과 같습니다.

  1. Certificate
  2. Handshake Protocol: Certificate
  3. Certificate (754 bytes)
  4. Certificate: 3082... 에서 마우스 오른쪽 버튼 > Export Packet Bytes 선택


추출 한 Certificate은 server.crt로 저장 합니다.


2. Public Key 추출

패킷에서 추출 한 인증서를 가지고 아래와 같은 명령어를 통해 공개키를 추출할 수 있습니다.


$ openssl x509 -inform der -pubkey -noout -in server.crt > public_key.pem


명령어 실행 후, 아래와 같이 public_key.pem이 생성된 것을 확인할 수 있습니다.



-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQHCC9wBfjyqPFebQNQ54uzXDxLE
1/J2R4TJWj/dugCYG6nOWyJ63kewp6CorKukVBq5XFL2tt49+ewJDGw1ZEWyG+Q3
q+ECFNC0o5ipZ0O79wyGRof7Lskp8B1u2rLZh/4JeZrSIEonBPMwYdv5wuA7My8L
oaRGZEyGSgbNWG1ICwIDAQAB
-----END PUBLIC KEY-----


3. Private Key 생성

마지막으로 패킷을 복호화 하기 위해 private key를 생성해야 합니다.


private key를 생성하기 위해서는 public key에 있는 n 값을 바탕으로 p와 q 값을 구하고, e를 참고 해 d를 찾아야 합니다.


이를 찾기 위해 아래의 내용을 참고 해 Fermat Factoring Algorithm을 사용 해 p와 q를 인수분해 하고, 이를 바탕으로 d를 구할 수 있습니다.



public key를 바탕으로 private key를 생성하기 위한 소스코드는 아래와 같습니다.


#make private key from public key
from Crypto.PublicKey import RSA
import time

def xgcd(b, n):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while n != 0:
        q, b, n = b // n, n, b % n
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return  b, x0, y0

# An application of extended GCD algorithm to finding modular inverses:
def mulinv(b, n):
    g, x, _ = xgcd(b, n)
    if g == 1:
        return x % n
# https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm

def isqrt(n):
  x = n
  y = (x + n // x) // 2
  while y < x:
    x = y
    y = (x + n // x) // 2
  return x

def fermat(n, pub):
    a = isqrt(n) # int(ceil(n**0.5))
    b2 = a*a - n
    b = isqrt(n) # int(b2**0.5)
    count = 0
    while b*b != b2:
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2) # int(b2**0.5)
        count += 1
    p=a+b
    q=a-b
    assert n == p * q
    print('a=',a)
    print('b=',b)
    print('p=',p)
    print('q=',q)
    print('pq=',p*q)
    print('p-1*q-1=', (p-1)*(q-1))

    assert pub.n == p * q
    print (pub.e)
    d = mulinv(pub.e, (p - 1) * (q - 1))
    priv = RSA.construct((pub.n, pub.e, d))
    print(priv.exportKey('PEM'))

    return p, q

def main():
    pub = """-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQHCC9wBfjyqPFebQNQ54uzXDxLE
1/J2R4TJWj/dugCYG6nOWyJ63kewp6CorKukVBq5XFL2tt49+ewJDGw1ZEWyG+Q3
q+ECFNC0o5ipZ0O79wyGRof7Lskp8B1u2rLZh/4JeZrSIEonBPMwYdv5wuA7My8L
oaRGZEyGSgbNWG1ICwIDAQAB
-----END PUBLIC KEY-----
"""
    pub = RSA.importKey(pub)
    print(pub.e, pub.n)
    fermat(pub.n, pub)

main()


그 결과 아래와 같이 RSA Private Key를 구할 수 있습니다.


-----BEGIN RSA PRIVATE KEY-----
MIICXwIBAAKBgQHCC9wBfjyqPFebQNQ54uzXDxLE1/J2R4TJWj/dugCYG6nOWyJ6
3kewp6CorKukVBq5XFL2tt49+ewJDGw1ZEWyG+Q3q+ECFNC0o5ipZ0O79wyGRof7
Lskp8B1u2rLZh/4JeZrSIEonBPMwYdv5wuA7My8LoaRGZEyGSgbNWG1ICwIDAQAB
AoGBAaXJ06Iam+S4tSqusbim824DlIWkFnvAP7UuvliicNgeZSEfzMr29J2eHTa4
zg0vPfSnkKHldZkEWLGKUQghOCZfO5CccVXBc972huQ4e5ip/m7JF1UdgJV4OyHr
mHmP+xMklXttv5RM5ZHICZoeL0eHoogEyZWWTAWdAnSd/luBAkEBU23A7PvcdAsk
LHVXYPd/hsrJ/rNRkHIWh71wLxWcaoGE4/dcbzeGwIMtMBNyrTFl1gCt9jfNpO+8
ma22GFuvoQJBAVNtwOz73HQLJCx1V2D3f4bKyf6zUZByFoe9cC8VnF/g0U709WQB
GqJwzTJrXcxp+yvXZnM1ep+hOZWBq8IxyCsCQQEgzVfDzCCtE/W5ZjXsqWl2dQEd
l9Gkh44n/MWBKnAmJwG9PfEGKEadcn92UnXWaxts1LMvthdhaSId2DIB07FBAkEB
HW4zCVY2qWLhFX3Lb+BQ3kHToRqcIVK/PYCBQSb0K/A7MyFs5Z7EDgu7koWVCBur
Os/U+Fblei0y5lV34ULJpwJBAP1eOI1ilFJxmGfz6LRb18x0XR5+Jcvq0P5Nws8d
W127GnyEhQmLlHRU4S7Pew/WLunIsubNXq87d0aRfQ14gEI=
-----END RSA PRIVATE KEY-----


4. 패킷 복호화

해당 key를 private.key로 저장합니다.


Wireshark에서 Edit > Preferences > Protocols > SSL > RSA keys list > Edit을 선택 해
추출 한 private key를 아래와 같이 넣어 줍니다.



이 후, 패킷을 확인해 보면 아래와 같이 평문으로 복호화 된 내용을 확인할 수 있습니다.



패킷을 확인하며 미로에서 위로 이동할 때와 왼쪽으로 이동할 때 전송하는 해쉬 값을 찾습니다.

그 결과는 다음과 같습니다.


GO UP
9de133535f4a9fe7de66372047d49865d7cdea654909f63a193842f36038d362

GO DOWN
6423e47152f145ee5bd1c014fc916e1746d66e8f5796606fd85b9b22ad333101

GO RIGHT
34660cfdd38bb91960d799d90e89abe49c1978bad73c16c6ce239bc6e3714796

GO LEFT
27692894751dba96ab78121842b9c74b6191fd8c838669a395f65f3db45c03e2


이를 바탕으로 최종적으로 미로를 통과하기 위한 client.py를 구현합니다.


from socket import *
from ssl import *
import time

def recv_until(s, string):
    result = ''
    while string not in result:
        result += s.recv(1)
    return result

client_socket=socket(AF_INET, SOCK_STREAM)
tls_client = wrap_socket(client_socket, ssl_version=PROTOCOL_TLSv1_2, cert_reqs=CERT_NONE)

print "[+] Connecting with server.."

tls_client.connect(('ch41l3ng3s.codegate.kr',443))

print "[+] Connect OK"

while 1:
    data = recv_until(tls_client, "Input : ")
    print data
    #message
    user_input = raw_input()

    if user_input == "u":
        tls_client.send("9de133535f4a9fe7de66372047d49865d7cdea654909f63a193842f36038d362\n")
    elif user_input == "d":
        tls_client.send("6423e47152f145ee5bd1c014fc916e1746d66e8f5796606fd85b9b22ad333101\n")
    elif user_input == "r":
        tls_client.send("34660cfdd38bb91960d799d90e89abe49c1978bad73c16c6ce239bc6e3714796\n")
    elif user_input == "l":
        tls_client.send("27692894751dba96ab78121842b9c74b6191fd8c838669a395f65f3db45c03e2\n")
    else:
        print "Invalid input!"
        exit()    

client_socket.shutdown(SHUT_RDWR)
client_socket.close()


client.py를 실행시킨 후 미로를 통과해 [G]에 도달하면 FLAG를 얻을 수 있습니다.


문제 풀이 해 주신 모든 분들 수고하셨습니다 :)

comments powered by Disqus

Search

Categories

Tags