[picoCTF 2022] NSA Backdoor

1. Investigation

Hint#1 : Look for Mr. Wong's whitepaper... His work has helped so many cats!

---

2. Solution

오픈소스로 구현해놓은 디피-헬먼 알고리즘에 누군가 몰래 백도어를 설치했다고 합니다.

 

힌트를 보아하니 Wong 씨의 논문을 찾아보라고 하네요.

(How to Backdoor Diffie-Hellman : https://eprint.iacr.org/2016/644.pdf)

(아래에서 소개할 알고리즘에 대한 이론이 담겨있음)

 

일단 주어진 파일부터 살펴보겠습니다.

 

>> gen.py

#!/usr/bin/python

from binascii import hexlify
from gmpy2 import *
import math
import os
import sys

if sys.version_info < (3, 9):
    math.gcd = gcd
    math.lcm = lcm

_DEBUG = False

FLAG  = open('flag.txt').read().strip()
FLAG  = mpz(hexlify(FLAG.encode()), 16)
SEED  = mpz(hexlify(os.urandom(32)).decode(), 16)
STATE = random_state(SEED)

def get_prime(state, bits):
    return next_prime(mpz_urandomb(state, bits) | (1 << (bits - 1)))

def get_smooth_prime(state, bits, smoothness=16):
    p = mpz(2)
    p_factors = [p]
    while p.bit_length() < bits - 2 * smoothness:
        factor = get_prime(state, smoothness)
        p_factors.append(factor)
        p *= factor

    bitcnt = (bits - p.bit_length()) // 2

    while True:
        prime1 = get_prime(state, bitcnt)
        prime2 = get_prime(state, bitcnt)
        tmpp = p * prime1 * prime2
        if tmpp.bit_length() < bits:
            bitcnt += 1
            continue
        if tmpp.bit_length() > bits:
            bitcnt -= 1
            continue
        if is_prime(tmpp + 1):
            p_factors.append(prime1)
            p_factors.append(prime2)
            p = tmpp + 1
            break

    p_factors.sort()

    return (p, p_factors)

while True:
    p, p_factors = get_smooth_prime(STATE, 1024, 16)
    if len(p_factors) != len(set(p_factors)):
        continue
    # Smoothness should be different or some might encounter issues.
    q, q_factors = get_smooth_prime(STATE, 1024, 17)
    if len(q_factors) == len(set(q_factors)):
        factors = p_factors + q_factors
        break

if _DEBUG:
    import sys
    sys.stderr.write(f'p = {p.digits(16)}\\n\\n')
    sys.stderr.write(f'p_factors = [\\n')
    for factor in p_factors:
        sys.stderr.write(f'    {factor.digits(16)},\\n')
    sys.stderr.write(f']\\n\\n')

    sys.stderr.write(f'q = {q.digits(16)}\\n\\n')
    sys.stderr.write(f'q_factors = [\\n')
    for factor in q_factors:
        sys.stderr.write(f'    {factor.digits(16)},\\n')
    sys.stderr.write(f']\\n\\n')

n = p * q
c = pow(3, FLAG, n)

print(f'n = {n.digits(16)}')
print(f'c = {c.digits(16)}')

코드를 보아하니 Very Smooth 문제와 굉장히 유사해보이며 소수 p, q 가 모두 Smooth Integer 인 것을 확인할 수 있습니다.

 

Pollard’s p-1 method 를 사용하면 합성수 n 을 소인수분해(Factorize) 할 수 있을 것 같습니다.

 

그런데 특이하게도 암호문을 생성하는데 RSA 기법을 사용하는게 아니라 문제 설명에 나와있듯이 Diffie-Hellman 알고리즘을 사용하는 것을 확인할 수 있습니다.

 

>> output.txt

n = 5bf9961e4bcfc88017e1a9a40958af5eae3b3ee3dcf25bce02e5d04858ba1754e13e86b78a098ea0025222336df6b692e14533dad7f478005b421d3287676843f9f49ffd7ebec1e8e43b96cde7cd28bd6fdf5747a4a075b5afa7da7a4e9a2ccb26342799965f3fb6e65e0bb9557c6f3a67568ccbfaaa7e3d6c5cb79dd2f9928111c3183bf58bd91412a0742bbfb3c5cebfb0b82825da0875c5ee3df208ce563f896d67287c8b9aad9943dd76e5eae1fc8abd473ec9f9e4f2b49b7897954ca77b8f00ed51949c7e4f1f09bd54b830058bd7f4da04e5228250ba062ec0e1d19fb48a05333aada60ecdfc8c62c15773ed7e077edba71621f6a6c10302cc9ed26ec9
c = 2475123653f5a4b842e7ac76829e896450126f7175520929a35b6a4302788ceff1a605ed30f4d01c19226e09fc95d005c61320d3bbd55cfebbc775332067ac6056c1969282091856eaa44ccaf5738ac6409e865bbd1186d69f718abd2b3a1dd3dc933a07ca687f0af9385406fd9ee4fa5f701ad46f0852bf4370264c21f775f1e15283444b3bf45af29b84bb429ed5a17adc9af78aee8c5351434491d5daf9dd3ce3cf0cd44b307eb403f0e9f482dd001b25ed284c4e6c1ba2864e5a2c4b1afe4161426cc67203f30553c88d7132aef1337eca00622b47cb7a28195f0e3a2ab934e6163b2941a4631412e13b1a72fe34e6480fada9af4dae14f2608805d61ee

output 으로는 합성수 n 과 암호문 c 를 주고 있습니다.

 

 

Diffie-Hellman 알고리즘 (필요한 부분만)

1. 앨리스는 공개키인 A = g ^ a (mod p) 를 계산하여 외부에 알린다.
2. 이 때, 앨리스와 밥 이외의 인물은 각각의 개인키인 a, b 를 알 수 없으며, 소수 p, 정수 g, 앨리스의 공개키 A, 밥의 공개키 B 만을 알 수 있다.

위처럼 디피-헬먼 알고리즘의 강점은 충분히 크고 안전한 소수 p 를 선택했다면 개인키 a 를 알아내는 것은 공격자가 이산 로그 문제(Discrete Logarithm Problem)을 푸는 것과 같기 때문에 거의 불가능함에 있습니다.

 

* 이산 로그 문제 : A = g ^ a (mod p) 에서 g, a, p 를 이용해 A 를 구하기는 쉽지만 g, A, p 를 이용해 원래의 a 를 찾기는 어렵다는 것.

 

하지만 이산 로그 문제를 합리적인 시간 내에 풀 수 있는 방법이 있다면 어떨까요?

 

Pohlig-Hellman Algorithm

(https://en.wikipedia.org/wiki/Pohlig–Hellman_algorithm)

유한 아벨군(Finite Abelian Group)의 차수(order)가 Smooth Integer 일 때 이산 로그를 계산하는 효과적인 알고리즘.

* order : 군 G의 집합의 크기

1. y = g^x (mod p) 와 같은 식이 주어짐.

2. 오일러 피함수를 이용하여 소수 p 에 대한 차수(order)를 구하고 Smooth Integer 인 것을 확인.

3. 각 소인수로 x 에 대한 합동식을 만들 수 있음.

4. Chinese Remainder Theorem (CRT) 를 이용하여 x (mod ϕ(p)) 를 구할 수 있음.

 

(Reference : https://risencrypto.github.io/PohligHellman/)

 

→ 쉽게 말해, 풀기 어려운 큰 문제를 작은 문제들로 쪼갠 뒤에 작은 문제들을 해결해서 큰 문제를 해결하는 방식입니다.

 

그런데 잘 생각해보면 주어진 문제의 소스코드에서 암호문을 생성하는 방식은 약간 다른 점이 있었습니다.

 

위처럼 (mod p) 가 아니라 (mod n) 이라는 것 입니다.

 

하지만 걱정할 필요 없습니다. n = p * q 이기 때문에 n 에 대한 큰 문제를 해결하는게 아닌 p 와 q 에 대한 작은 문제로 쪼개 각 문제를 해결하면 됩니다.

 

각 (1), (2) 식에 대해 Pohlig-Hellman Algorithm 을 적용한 후 구한 FLAG_a (mod ϕ(p)) 와 FLAG_b (mod ϕ(q)) 에 대해 CRT 를 적용해 최종적인 FLAG 를 구하면 됩니다.

 

Summary

1. Very Smooth 문제와 같이 소수 p, q 모두 Smooth Integer 이기 때문에 n 을 합리적인 시간 내에 소인수분해하여 소수 p, q 를 알아낸다. (Pollard’s p-1 method)
2. 소수 p, q 를 알아냈기 때문에 디피-헬먼 알고리즘의 이산 로그 문제(DLP)를 각각의 소수 p, q 에 대한 작은 문제로 쪼개 합리적인 시간 내에 FLAG_a 와 FLAG_b 를 구한다. (Pohlig-Hellman Algorithm)
3. Chinese Remainder Theorem (CRT) 를 사용해 최종적인 FLAG 를 구한다.

 

아래는 위 세 단계의 과정을 구현한 코드입니다.

 

>> NSA_Backdoor-sol.py

# <http://www.secmem.org/blog/2019/10/20/Smooth-number-and-Factorization/>

import math

N = 0x5bf9961e4bcfc88017e1a9a40958af5eae3b3ee3dcf25bce02e5d04858ba1754e13e86b78a098ea0025222336df6b692e14533dad7f478005b421d3287676843f9f49ffd7ebec1e8e43b96cde7cd28bd6fdf5747a4a075b5afa7da7a4e9a2ccb26342799965f3fb6e65e0bb9557c6f3a67568ccbfaaa7e3d6c5cb79dd2f9928111c3183bf58bd91412a0742bbfb3c5cebfb0b82825da0875c5ee3df208ce563f896d67287c8b9aad9943dd76e5eae1fc8abd473ec9f9e4f2b49b7897954ca77b8f00ed51949c7e4f1f09bd54b830058bd7f4da04e5228250ba062ec0e1d19fb48a05333aada60ecdfc8c62c15773ed7e077edba71621f6a6c10302cc9ed26ec9
B = 70000   # This value should be modified.

# Prime
primes = []
for i in range(2, B + 1):
    flag = True
    for j in primes:
        if j * j > i:
            break
        if i % j == 0:
            flag = False
            break
    if flag:
        primes.append(i)

# Pollard's p-1 algorithm
a = 2
for p in primes:
    wow = pow(p, math.floor(math.log(B, p)))
    a = pow(a, wow, N)

print(math.gcd(a - 1, N))
# 112702077491326624035437448311528244416633038267184436467539953783623022543629307291975209668348933325006075339780165463077524233511267597550006727923822554354936896793276829740193900248027487979522143806746878229772394053610558597354876381637035909859704552979985236170415302488615161107293296362528480525723
# Modulus N is factorized!!!

p = 112702077491326624035437448311528244416633038267184436467539953783623022543629307291975209668348933325006075339780165463077524233511267597550006727923822554354936896793276829740193900248027487979522143806746878229772394053610558597354876381637035909859704552979985236170415302488615161107293296362528480525723
q = N // p
assert p*q == N

g = 3
ct = 0x2475123653f5a4b842e7ac76829e896450126f7175520929a35b6a4302788ceff1a605ed30f4d01c19226e09fc95d005c61320d3bbd55cfebbc775332067ac6056c1969282091856eaa44ccaf5738ac6409e865bbd1186d69f718abd2b3a1dd3dc933a07ca687f0af9385406fd9ee4fa5f701ad46f0852bf4370264c21f775f1e15283444b3bf45af29b84bb429ed5a17adc9af78aee8c5351434491d5daf9dd3ce3cf0cd44b307eb403f0e9f482dd001b25ed284c4e6c1ba2864e5a2c4b1afe4161426cc67203f30553c88d7132aef1337eca00622b47cb7a28195f0e3a2ab934e6163b2941a4631412e13b1a72fe34e6480fada9af4dae14f2608805d61ee

'''
# Implemented in SageMath
# Pohlig-Hellman with CRT
Rp = IntegerModRing(p)
Rq = IntegerModRing(q)

# Find xa, xb with discrete_log function.
# ct = g ^ xa (mod p)
# ct = g ^ xb (mod q)
xa = discrete_log(Rp(ct), Rp(g))
xb = discrete_log(Rq(ct), Rq(g))

# Then, get solution using CRT.
# x = xa (mod p - 1)
# x = xb (mod q - 1)
print(crt([xa, xb], [p-1, q-1]))
# 38251710328773353864596243890570950490237
'''

flag = 38251710328773353864596243890570950490237
flag = bytes.fromhex(format(flag, 'x'))
print(flag)
# b'picoCTF{cf****b8}'

 

🚩 FLAG : picoCTF{cf****b8}

---