picoCTF 2022 ~NSA Backdoor writeup~

Description

I heard someone has been sneakily installing backdoors in open-source implementations of Diffie-Hellman... I wonder who it could be... ;)

• gen.py
• output.txt

Solution

First, let's open gen.py. Various functions are written in this file, but the variable c is the most noteworthy part.

#!/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)

e = 0x10001

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)):
        continue
    factors = p_factors + q_factors
    if e not in 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

m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)

c = pow(FLAG, e, n)

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

Looking at the code, we can see that it is very similar to the VerySmooth problem, with the numbers p and q all being SmoothInteger.
It seems that the Pollard'sp-1method can be used to prime factorize (Factorize) the composite number n.
However, we can also confirm that singularly this challenge did not use the RSA technique to generate the ciphertext, but rather the Diffie-Hellman algorithm, as shown in the problem description.

It seems that we can get the flag by solving this discrete logarithm problem.

$$c = 3^{\text{flag}} \mod n$$

First, let's look at the contents of output.txt. The contents are given n and c.

→ cat output.txt
n = 5837ab2dd26ff8ab827a4885c72229e2e908af1de303c35e1190659fb120acd3b256cd71d91cc25a96ed4261259c8928720217b1fb8fcc1002375f779ff64fc4f181715d882f304678bed6f376cb0497cb599d88dc4bb4563e33709bd8b8c8e41da4b61ab01eb50d188f532690520a6b69b6c4790d2076eebc32e01d59945b5c3d8af79d0b7eb271527f8c6eb6cf70bdd141a5278d6f9f557513ec56b94da27d7cb85117074d318154967e645f42b4b42231ad8e29f0a3ccd2596444f6cc1de903ec3cb27c28792e9437b6bc1cd57a61f15b96f1690027119cb87c07d96760230afff7f8c9287d0573c34830359694918a721d87213d0baba7ee2f519d839581
c = 40c4c7f7a326558762ac0f64a8abb6f6496851c45a2763791132ecc4c8e029cc0a8c9d6ddb62dbdedf1e4f2f8ba8cb8a965aa9eb8c88cd582274b6ba9402fa84e63a6847c925b3fc34c6d5e9b925f03c656b2a6c2691a15196e4a246c5e3cb46b41f5090bf588911fbd8459ca9da19c1a8f3cd61af905790dd049d16544a2c4fd38f99af62d8080d49b5760c86a0cdb94ddadc785415e4e3e5ddf413a0a10e919c3ddda9c571f26498312718b4da3063a294394dc01fbb2f2c514d2b70dd999980cf5743ecf843450d71a613d74a3ab5d201bf864a617c3a25fecb9191e0ebe9bf678abed2384deb5ce91f753e9f20036fe61edfada631a4876a5cca790bc46

Unfortunately, I couldn't figure out anything from this information alone. So I looked at the hints.

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

• How to Backdoor Diffie-Hellman

This is a paper presented at DEFCON24. I am not an expert in cryptography, so I don't understand everything, but this gives me a hint to solve the problem.

$$y = g^x \mod n(=pq)$$

This figure shows that the difficult problem of finding x from the above equation can be decomposed into a simple problem of finding x from mod p and mod q instead of n.
Finally we can derive the answer to the original question using the Chinese Reminder Theorem (CRT).

In summary, we can get the flags by the following steps:

1. As in the VerySmooth problem, both the small numbers p and q are SmoothInteger, so the first step is to find out the prime numbers p and q by prime factorizing n in a reasonable amount of time. (Pollard's　p-1　method)

2. Having found out the prime numbers p and q, the discrete logarithm problem (DLP) of the DP-Hellman algorithm is divided into smaller problems for each prime number p and q, and FLAG_p and FLAG_q are obtained in a reasonable time. (Pohlig-Hellman Algorithm)

3. Find the final FLAG using ChineseRemainderTheorem(CRT).
   

import math
from sage import *

N = 0x5bf9961e4bcfc88017e1a9a40958af5eae3b3ee3dcf25bce02e5d04858ba1754e13e86b78a098ea0025222336df6b692e14533dad7f478005b421d3287676843f9f49ffd7ebec1e8e43b96cde7cd28bd6fdf5747a4a075b5afa7da7a4e9a2ccb26342799965f3fb6e65e0bb9557c6f3a67568ccbfaaa7e3d6c5cb79dd2f9928111c3183bf58bd91412a0742bbfb3c5cebfb0b82825da0875c5ee3df208ce563f896d67287c8b9aad9943dd76e5eae1fc8abd473ec9f9e4f2b49b7897954ca77b8f00ed51949c7e4f1f09bd54b830058bd7f4da04e5228250ba062ec0e1d19fb48a05333aada60ecdfc8c62c15773ed7e077edba71621f6a6c10302cc9ed26ec9
B = 100000  

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)

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))

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

g = 3
ct = 0x2475123653f5a4b842e7ac76829e896450126f7175520929a35b6a4302788ceff1a605ed30f4d01c19226e09fc95d005c61320d3bbd55cfebbc775332067ac6056c1969282091856eaa44ccaf5738ac6409e865bbd1186d69f718abd2b3a1dd3dc933a07ca687f0af9385406fd9ee4fa5f701ad46f0852bf4370264c21f775f1e15283444b3bf45af29b84bb429ed5a17adc9af78aee8c5351434491d5daf9dd3ce3cf0cd44b307eb403f0e9f482dd001b25ed284c4e6c1ba2864e5a2c4b1afe4161426cc67203f30553c88d7132aef1337eca00622b47cb7a28195f0e3a2ab934e6163b2941a4631412e13b1a72fe34e6480fada9af4dae14f2608805d61ee

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