[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위 소스코드를 분석해보니 다음과 같았습니다:
- KL = round(1024 / 5 * 4) = 819, KR = round(1024 / 5 * 1) = 205 bits 만큼 분리해서 왼쪽 청크(chunk)의 RSA 암/복호화 따로, 오른쪽 청크의 RSA 암/복호화 따로 진행
- 키 생성
- 왼쪽 청크
- 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
- 왼쪽 청크
- 엔트로피 풀(Entropy Pool) 생성 (=랜덤값 리스트 생성)
- 고정된 SEED 사용
- 약 204 bits 크기의 랜덤 정수를 128개 생성
- 생성된 128개의 랜덤 정수를 무작위로 섞어 엔트로피 풀 생성
- 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 값이 됨.
- RSA-OOPS-1024 복호화
- 어차피 개인키 DL, DR 를 모르기 때문에 사용 불가.
서버 인스턴스에 접속 시 다음과 같은 정보를 알려줍니다:
- 엔트로피 풀에 남아있는 랜덤값 갯수
- 공개키 N 값 : 이것 또한 Lshift 연산을 통해 N = (NL << KR) + NR 의 16진수 값을 반환해줌
- [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 을 구할 수 있게 된다.
이제 해당 공격을 문제 풀이에 그대로 적용해봅시다.
공격 순서
- 문제 서버 인스턴스에 접속해 공개키 N 를 받아 왼쪽 청크, 오른쪽 청크로 분리.
- NL = N >> KR
- NR = N - (NL << KR)
- [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)
- 1st
- NR 을 소인수분해하여 개인키 DR 을 구함.
- XOR 연산의 교환법칙을 이용하여 엔트로피 풀에서 가져온 r_int 값을 계산. (2번 반복)
- r_int_0 = Y_0 ^^ (X_0 ^ DR (mod NR))
- r_int_1 = Y_1 ^^ (X_1 ^ DR (mod NR))
- 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_*********}