[n00bzCTF2022] RSA-OOPS

1. Investigation

RSA-OAEP 가 너무 복잡해서 RSA-OOPS 라고 불리는 자신만의 RSA Original Optimal Padding Scheme 을 만들었다고 합니다.

접속 제공 정보 : nc 159.65.232.9 10333

이 CTF 에서는 특이하게 디스코드에서 운영진들이 각 문제에 대한 소스코드를 제공해주고 있어서 디스코드 서버에 접속해 별도로 받아와야 했습니다.

 

>> challenge.py

#!/usr/local/bin/python
#
# Polymero
#

# Imports
from Crypto.Util.number import getPrime, inverse
import os, random

# Local imports
with open('flag.txt', 'rb') as f:
    FLAG = f.read()
    f.close()


# Challenge class:
class RSAOOPS1024:

    def __init__(self):
        """ Generate RSA keys and entropy pool. """
        # Chunk sizes
        self.KL = round(1024 / 5 * 4)
        self.KR = round(1024 / 5 * 1)

        # RSA key for L chunk
        self.EL = 17
        while True:
            PL, QL = [getPrime(self.KL // 2) for _ in '01']
            self.DL = inverse(self.EL, (PL - 1)*(QL - 1))
            if self.DL != 1:
                self.NL = PL * QL
                break

        # RSA key for R chunk
        self.ER = 0x10001
        while True:
            PR, QR = [getPrime(self.KR // 2) for _ in '01']
            self.DR = inverse(self.ER, (PR - 1)*(QR - 1))
            if self.DR != 1:
                self.NR = PR * QR
                break

        # Entropy pool
        rng = random.Random(SERVER_SEED)
        self.pool = [rng.getrandbits(self.NR.bit_length() - 1) for _ in range(128)]
        random.shuffle(self.pool)

    def __repr__(self):
        """ Representation string. """
        pubkey = ((self.NL << self.KR) + self.NR).to_bytes(128, 'big').hex()
        return "RSA-OOPS-1024 ({} left) with public key N = {}".format(len(self.pool), pubkey)

    def encrypt(self, m):
        """ RSA-OOPS-1024 encryption. """
        m_int = int.from_bytes(m, 'big')
        r_int = self.pool.pop(0)
        X = pow(m_int + r_int, self.EL, self.NL)
        Y = pow(X, self.DR, self.NR) ^ r_int
        return (X << self.KR) + Y

    def decrypt(self, XY):
        """ RSA-OOPS-1024 decryption. """
        X = XY >> self.KR
        Y = XY & (2**self.KR - 1)
        r = Y ^ pow(X, self.DR, self.NR)
        m = pow(X, self.DL, self.NL) - r
        return m.to_bytes(128, 'big').lstrip(b"\x00")


# Server loop
HDR = r"""|
|
|    (    (                 )     )  (    (     
|    )\ ) )\ )   (       ( /(  ( /(  )\ ) )\ )  
|   (()/((()/(   )\      )\()) )\())(()/((()/(  
|    /(_))/(_)|(((_)(   ((_)\ ((_)\  /(_))/(_)) 
|   (_)) (_))  )\ _ )\   ((_)  ((_) (_)) (_))   
|   | _ \/ __| (_)_\(_)  / _ \ / _ \| _ \/ __|  
|   |   /\__ \  / _ \   | (_) | (_) |  _/\__ \  
|   |_|_\|___/ /_/ \_\   \___/ \___/|_|  |___/  
|"""

print(HDR)

SERVER_SEED = int.from_bytes(os.urandom(32), 'big')

oop = RSAOOPS1024()

while True:

    try:

        if not oop.pool:

            print('|\n|  You have exhausted the entroopsy pool.')
            print('|   [C]onstruct new instance\n|   [Q]uit')
            choice = input('|\n|  >> ').lower()

            if choice == 'c':
                oop = RSAOOPS1024()

            elif choice == 'q':
                raise KeyboardInterrupt

            else:
                continue

        print('|\n|  {}'.format(oop))
        print('|\n|   [E]ncrypt flag\n|   [Q]uit')
        choice = input('|\n|  >> ').lower()

        if choice == 'e':
            flag = oop.encrypt(FLAG).to_bytes(128, 'big').hex()
            print("|\n|  {}".format(flag))

        elif choice == 'q':
            raise KeyboardInterrupt

        else:
            continue

    except KeyboardInterrupt:
        print("|\n|\n|  Bye ~ !\n|")
        break

    except:
        print("|\n|  Something went wrong...")
        continue

위 소스코드를 분석해보니 다음과 같았습니다:

1. KL = round(1024 / 5 * 4) = 819, KR = round(1024 / 5 * 1) = 205 bits 만큼 분리해서 왼쪽 청크(chunk)의 RSA 암/복호화 따로, 오른쪽 청크의 RSA 암/복호화 따로 진행
2. 키 생성
   • 왼쪽 청크
     • Public Exponent : EL = 17
     • Prime P, Q : PL = getPrime(KL // 2), QL = getPrime(KL // 2)
     • Private Key : DL = EL ^ (-1) (mod (PL - 1)*(QL - 1))
     • Public Modulus : NL = PL * QL
   • 오른쪽 청크
     • Public Exponent : ER = 0x10001 = 65537
     • Prime P, Q : PR = getPrime(KR // 2), QR = getPrime(KR // 2)
     • Private Key : DR = ER ^ (-1) (mod (PR - 1)*(QR - 1))
     • Public Modulus : NR = PR * QR
3. 엔트로피 풀(Entropy Pool) 생성 (=랜덤값 리스트 생성)
   • 고정된 SEED 사용
   • 약 204 bits 크기의 랜덤 정수를 128개 생성
   • 생성된 128개의 랜덤 정수를 무작위로 섞어 엔트로피 풀 생성
4. RSA-OOPS-1024 암호화
   • 메시지 m 을 정수로 변환 : m_int
   • 엔트로피 풀에서 첫번째 값 pop : r_int
   • X = (m_int + r_int) ^ EL (mod NL) 계산
   • Y = X ^ DR (mod NR) ^^ r_int 계산 (^^ 는 XOR 연산을 의미)
   • return (X << KR) + Y : X 를 KR(205 bits) 만큼 Lshift 한 뒤 Y 를 더한 값을 반환. 이렇게 하면 좌측 KL(819 bits) 만큼은 X 값이 되고, 우측 KR(205 bits) 만큼은 Y 값이 됨.
5. RSA-OOPS-1024 복호화
   • 어차피 개인키 DL, DR 를 모르기 때문에 사용 불가.

 

서버 인스턴스에 접속 시 다음과 같은 정보를 알려줍니다:

1. 엔트로피 풀에 남아있는 랜덤값 갯수
2. 공개키 N 값 : 이것 또한 Lshift 연산을 통해 N = (NL << KR) + NR 의 16진수 값을 반환해줌
3. [E]ncrypt 옵션 선택 시 암호화된 FLAG 를 반환해줌.

 

이로써 우리가 알 수 있는 정보는 좌, 우 청크 RSA 암호화에 사용된 공개키 쌍 (NL, EL), (NR, ER) 과 FLAG 에 대한 암호문입니다. 이걸 가지고 어떻게 문제를 풀 수 있을까요?

---

2. Solution

문제 해결의 실마리는 공개키 값 중 NR 에 있습니다. NR 은 약 205 bits 길이의 정수인데 이 길이가 어느정도 짧기 때문에 합리적인 시간 내에 소인수분해를 할 수 있습니다.

REF#1 : https://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity

REF#2 : https://stackoverflow.com/questions/44045098/calculation-time-of-nfs-algorithm

현재 이론적으로 가장 빠르다고 알려진 소인수분해 알고리즘인 general number field sieve (GNFS) 의 시간 복잡도는 다음과 같다:

n = 10738166023052890527259645462663212212392996152993945000850289 이고, 현재 CPU 의 클럭이 2.5Ghz 라고 한다면 소인수분해에 걸리는 대략적인 시간은 다음과 같다:

# Implemented in SageMath
a = 64/9
b = a.n()
n = 10738166023052890527259645462663212212392996152993945000850289
res = exp((b.nth_root(3) + 1) * (ln(n))^(1/3) * (ln(ln(n)))^(2/3))
print(round(res))   # 14368254681099097659
print(round(res) / 2500000000.0)   # 5.74730187243964e9

(약 5 ~ 6초)

 

소인수분해가 가능하다는 것은 PR, QR 값을 알아냈다는 것과도 같기 때문에 이를 이용하여 개인키 DR 을 구할 수 있습니다.

 

위 소스코드에서 암호문을 만들 때 사용했던 식인 Y = X ^ DR (mod NR) ^^ r_int 식에서  Y, X, DR, NR 값을 모두 알고 있기 때문에 교환법칙을 이용하면 쉽게 r_int 의 값을 알아낼 수 있습니다. (r_int = Y ^^ (X ^ DR (mod NR)))

 

그런데 r_int 값을 알아냈다고 해도 m_int 값도 모르고 개인키 DL 값도 모르기 때문에 또 하나의 식인 X = (m_int + r_int) ^ EL (mod NL) 를 풀어낼 수는 없어 보입니다.

 

여기서 약간의 사전 지식이 필요한데, 기존에 다른 RSA 문제들을 여럿 풀어보셨더라면 Franklin-Reiter Related Message Attack 에 대해서 들어보신 적이 있을 겁니다.

 

해당 공격의 원리는 다음과 같다:

공개키에서 e 값이 3 이고, c1 = m ^ e (mod n) 과 c2 = (m + r) ^ e (mod n) 과 같은 형태로 암호화된 메시지 c1, c2 와 r 값을 알고 있을 때 f_1(x) = x ^ e - c1 (mod n), f_2(x) = (x + r) ^ e - c2 (mod n) 과 같은 형태의 선형 방정식을 만들면 f_1(x) = x ^ e - m ^ e(=c1) (mod n), f_2(x) = (x + r) ^ e - (m + r) ^ e(=c2) (mod n) 이고, 두 함수 f_1(x), f_2(x) 는 x 에 m 을 대입했을 때 f_1(m) = 0, f_2(m) = 0 으로 m 이라는 공통근을 가진다는 뜻이 된다.

 

이 때, 공통근 m 을 가지는 두 함수 f_1(x), f_2(x) 는 다음과 같이 표현이 가능하다:

f_1(x) = (x - m)g_1(x)

f_2(x) = (x - m)g_2(x)

(g_1(x), g_2(x) 는 각 f_1(x), f_2(x) 함수의 또다른 근들을 모르기 때문에 함수 형태로 축약하여 표현한 것)

 

다음으로 두 선형방정식 f_1(x), f_2(x) 의 최대공약수(GCD)를 구하면 f_3(x) = (x - m) (mod n) 이라는 새로운 1차 방정식이 나오게 되며 해당 방정식에서 0차항의 계수인 -m 을 통해 쉽게 원본 메시지인 m 을 구할 수 있게 된다.

 

이제 해당 공격을 문제 풀이에 그대로 적용해봅시다.

 

공격 순서

1. 문제 서버 인스턴스에 접속해 공개키 N 를 받아 왼쪽 청크, 오른쪽 청크로 분리.
   • NL = N >> KR
   • NR = N - (NL << KR)
2. [E]ncrypt 옵션을 통해 암호화된 FLAG 인 XY 를 받아 왼쪽 청크, 오른쪽 청크로 분리. (2번 반복) 
   • 1st
     • X_0 = XY_0 >> KR
     • Y_0 = XY_0 - (X_0 << KR)
   • 2nd
     • X_1 = XY_1 >> KR
     • Y_1 = XY_1 - (X_1 << KR)
3. NR 을 소인수분해하여 개인키 DR 을 구함.
4. XOR 연산의 교환법칙을 이용하여 엔트로피 풀에서 가져온 r_int 값을 계산. (2번 반복)
   • r_int_0 = Y_0 ^^ (X_0 ^ DR (mod NR))
   • r_int_1 = Y_1 ^^ (X_1 ^ DR (mod NR))
5. Franklin-Reiter Related Message Attack 을 통해 원본 메시지 m 복구
   • f_1 = (x + r_int_0) ^ EL - X_0 (mod n)
   • f_2 = (x + r_int_1) ^ EL - X_1 (mod n)
   • f_3 = GCD(f_1, f_2) = (x - m) (mod n)
   • f_3 에서 0차항의 계수를 취해 -m 으로 부터 원본 메시지 m 복구

 

아래는 위 순서대로 구현한 코드입니다.

from pwn import *

url = '159.65.232.9'
port = 10333

nc = remote(url, port)

# Getting Public Modulus N from server.
res = nc.recvuntil(b'public key N = ')
print(res)

N = nc.recvline().strip().decode()
N = int(N, 16)
print("N: ", N)
# 27418213725902686978952989060103516357079827146921199353623916293081581191262631309773231217734884479255678834348338137921143955597358628536827390353193522746371669007294592864301104311938191931509962017656744294867675092079659663906103487865663331754706173277583377591238193736276151964246630586345823646577

KL = round(1024 / 5 * 4)
KR = round(1024 / 5 * 1)

# Splitting N into two chunks NL, NR.
NL = N >> KR
NR = N - (NL << KR)
assert ((NL << KR) + NR) == N
print("NL: ", NL)
print("NR: ", NR)

EL = 17
ER = 65537

print('='*64)

# m = FLAG
# X = (m + r) ^ EL (mod NL)
# Y = X ^ DR (mod NR) ^^ r
# XY = (X << KR) + Y

# Getting two ciphertexts to use Franklin-Reiter Attack.
# Since we can form below linear equations:
# X_0 = (m + r_0) ^ EL (mod NL)
# X_1 = (m + r_1) ^ EL (mod NL)
X_list = []
Y_list = []
for i in range(2):
    nc.sendlineafter(b'|\n|  >> ', b'E')
    nc.recvuntil(b'|\n|  ')
    XY = nc.recvline().strip().decode()
    XY = int(XY, 16)
    print("XY: ", XY)

    X = XY >> KR
    Y = XY - (X << KR)
    assert ((X << KR) + Y) == XY
    print("X: ", X)
    print("Y: ", Y)
    X_list.append(X)
    Y_list.append(Y)


'''
# Since NR is about 205 bits long, we can factor it in reasonable time.
PR, QR = prime_factors(NR)
assert PR*QR == NR
print("PR: ", PR)
print("QR: ", QR)

DR = pow(ER, -1, (PR-1)*(QR-1))
print("DR: ", DR)

# Recall the ciphertext Y formula, Y = X ^ DR (mod NR) ^^ r
# We can calculate r since we know all of the variables Y, X, DR, NR.
# r = Y ^^ (X ^ DR mod NR)
# Note that ^^ is XOR in SageMath not ^.
r_list = []
for i in range(2):
    r = Y_list[i] ^^ int(pow(X_list[i], DR, NR))
    r_list.append(r)
    print(f"[{i}] r: ", r)
    # [0] r:  5550274212742870043820281375134617899012942474741656740037597
    # [1] r:  1522778945158105280735700670310796696899299216875498353933050

# Franklin-Reiter Related Message Attack
# https://crypto.stackexchange.com/questions/30884/help-understanding-basic-franklin-reiter-related-message-attack
R.<x> = Zmod(NL)[]
f1 = (x + r_list[0]) ^ EL - X_list[0]
f2 = (x + r_list[1]) ^ EL - X_list[1]

def my_gcd(a, b): 
    return a.monic() if b == 0 else my_gcd(b, a % b)

m = -my_gcd(f1, f2).coefficients()[0]   # coefficient 0 = -m
m = bytes.fromhex(format(m, 'x'))
print("FLAG: ", m)
# b'n00bz{turns_0ut_***********_1snt_4lw4ys_*******_s0_st1ck_t0_th3_*********}'
'''

🚩 FLAG : n00bz{turns_0ut_***********_1snt_4lw4ys_*******_s0_st1ck_t0_th3_*********}