[Christmas CTF_2016] StupidRSA(misc)

## Christmas CTF_2016(StupidRSA,misc,100pts)

[Summary]

1. 랜덤 문자열을 RSA암호화하여 던져주고 사용자 입력을 받은 후 인크립트하여 같은 문자열인지 검사.

2. N과 e가 주어진다.

3. p,q를 구해야 한다. => d를 구할 수 있음.

4. 랜덤이 랜덤이 아니다.

[Analysis] - server.py

from socket import *
import sys
from time import *
import threading
from gmpy2 import *
import random, string
 
#======================================================================================
# function "xgcd" tackes positive integers a, b as input
# and return a triple (g, x, y), such that ax + by = g = gcd(a, b).
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 GeneratePrime(Base, randomST):
    while True:
        k1 = mpz_urandomb(randomST, 1023)
        k2 = k1 + mpz_urandomb(randomST, 1023)
 
        #Add Random Number to Bignumber, then find next prime number
        p1 = next_prime(Base+k1)
        p2 = next_prime(Base+k2)
        #Prime Checking
        if is_prime(p1, 100) and is_prime(p2, 100):
            return [p1, p2]
 
def GenerateKeys(p, q):
    e = 65537
    n = p * q
    pin = (p-1)*(q-1)
    d = mulinv(e, pin)
    return [e, d, n]
 
 
def MakeRandomString():
    return ''.join(random.choice(string.lowercase+string.uppercase+string.digits) for i in xrange(32))
 
def PrintIntro(conn):
    conn.send("ggggg\n")
 
 
Flag = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
 
def ClinetHandle(conn):
    TimeLimit = 1
    randomST = random_state()
    #Make Big Number with 2048 bits
    BaseNumber = (mpz(2) ** mpz(2048)) + mpz_urandomb(randomST, 512)
    if True:
        PrintIntro(conn)
        conn.send("Generating Keys... Wait some seconds\n")
        sleep(1)
 
        p, q = GeneratePrime(BaseNumber, randomST)
        #sleep is for resting of server
        sleep(1)
 
        PublicKey, PrivateKey, N = GenerateKeys(p, q)
        #sleep is for resting of server
        sleep(1)
        
        Data = MakeRandomString()
        Data = int(Data.encode('hex'),16)
 
        EncryptedData = powmod(Data, PublicKey, N)
        conn.send("Key Generating is Ended\n")
        conn.send("Encrypted Data : %d\nPublic Key : %d\nN : %d\n" % (EncryptedData, PublicKey, N))
        
        s_time = time()
        Answer = conn.recv(1500)
        e_time = time()
 
        #Time Out
        if e_time - s_time > TimeLimit:
            conn.send("Time Out!!!!!\n")
            conn.close()
            return
 
        #Answer is OK
        if int(Answer) == Data:
            conn.send(Flag+"\n")
            conn.close()
            return
        conn.send("You are Wrong!!!!!!\n")
        conn.close() 
        return
    else:
        conn.close()
        print "SOCKET ERROR"
        return
 
PORT = 40002
serverSocket = socket()
 
try:
    serverSocket.setsockopt(SOL_SOCKET, SO_REUSEADDR, 1)
    serverSocket.bind(('', PORT))
except error as msg:
    print 'Bind failed. Error Code : ' + str(msg[0]) + ' Message ' + msg[1]
    sys.exit()
 
serverSocket.listen(30)
 
while 1:
    try:
        conn, addr = serverSocket.accept()
    except socket.error:
        break
    print 'Connected with ' + addr[0] + ':' + str(addr[1])
    t = threading.Thread(target = ClinetHandle, args=(conn,))
    t.start()        
 
serverSocket.close()

위 파이썬 서버 소스코드를 간단하게 분석해보면 gmpy2 모듈을 import한 후 random_state()함수를 이용하여 random state를 세팅한다.

그리고 line number 66에서 GeneratePrime(BaseNumber, randomST)함수를 이용하여 p와 q를 생성하는데 이 때 BaseNumber의 값이 

너무 커서 p와 q의 값이 항상 일정한 것을 확인할 수 있다.



 사실 대회때 풀때는 nc로 해당 IP에 접속하니까 N값이 아래 [그림 1]과 같이 항상 같은 것을 알 수 있었고 이를 통해 p,q의 값이 계속

계속 같은 값으로 세팅될것이라 생각하고 server.py를 돌린 후 조금 수정하여 line number 39에 GenerateKeys()함수에 p,q를 프린트하는

코드를 집어넣고 p, q가 어떤 값인지 확인하였다. 따라서 N의 p, q 값을 구할 수 있었고 아래 exploit코드를 통해 encrypted_data를

복호화하여 plain_data를 보내 flag를 획득할 수 있었다.

[그림 1] N값 동일

[Exploit Code] - stupidrsa_exploit.py

from gmpy2 import *
from pwn import *
 
p = 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521954285833276606292740174507176908054077273016103644389803261062635470374515595892199454891155463898488297024308700957247533881208055894474582694028535079545281620566442541400114261729854235365927395115457109476960042332821732358509197923144094801013581965651112146928918286923938064987973879624251895591220179
q = 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521990685772174514834944123086486002362345153147580453526134037171595087108668773961917317502849945855689432886442889958513294157709640362363734479327004391952407569596153273880472331909250263593691635107321048666489395316204775782962517724272901158130972610802371589601746375325078943967095960733617174538141999
N = 1044388881413152506691752710716624382579964249047383780384233483283953907971557456848826811934997558340890106714439262837987573438185793607263236087851365277945956976543709998340361590134383718314428070011855946226376318839397712745672334684344586617496807908705803704071284048740118609114467977783598029006690697600653450794402499073313655339553833700162307202013282630845566129486279002848586096254031476866169150792712561588286084912360489096086200722815030967777717184920678698120026611906420006892800629990673807045740381567965542428579442736758203240180858489936597121784161788543599325256723713897245258564131378894882215721032454483182663602447410406206605827169895576134734205640381165130412956991982982813624560781237251487840725883976219267677157563885355442227842754369664991260936611978646990570202470864911216177534982510459238429002261957146109354524074258091155400881651699324739110875426250103752411336489340207397621943251616715427383143672581025383482605402570803003488772623873903367163515172010706471506968810059433811270160224272718635182798462613003559659236641594639570465027376724958024431953464028003281075460976002320362078753623631924730508277339588386023508080515190999918781675629931130902752659976197821
phi = (p-1)*(q-1)
e = 65537
 
def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y
 
gcd, a, b = egcd(e, phi)
d = a
 
p = remote('52.175.158.46', 40002)
print p.recvline(); print p.recvline(); print p.recvline()
encrypted_data = p.recvline()[17:]; print encrypted_data
 
print p.recvline(); print p.recvline()
decrypted_data = powmod(int(encrypted_data), d, N)
decrypted_data_str = hex(decrypted_data)[2:].decode('hex')
print '[*] decrypted_data : ' + decrypted_data_str
 
p.send(str(decrypted_data)+'\n')
print p.recv(1024)
 
# ref1) http://crypto.stackexchange.com/questions/19444/rsa-given-q-p-and-e
# ref2) 

[Get Flag~~!!!!] 

[그림 2] flag

끝~!