picoCTF 2022 ~NSA Backdoor writeup~
Tags: security, ctf, python
Published: 2022-07-09 05:03:28

# 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.
<!--まずはgen.pyを開いてみましょう．いろいろな関数が書いてありますが，注目すべきところは変数cの部分です．-->

```python
#!/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.
<!--コードを見ると、VerySmooth問題と非常に似ていて、少数p、qがすべてSmoothIntegerであることが確認できます。Pollard'sp-1methodを使えば合成数nを素因数分解(Factorize)できるようです。しかし、特異にも暗号文を生成するのにRSA技法を使用するのではなく、問題説明に出ているようにDiffie-Hellmanアルゴリズムを使用することが確認できます。-->

It seems that we can get the flag by solving this  [discrete logarithm problem](https://en.wikipedia.org/wiki/Discrete_logarithm).
<!--よってこの離散対数問題を解くことで，flagを求められるようだ．-->

{% katex %}  c = 3^{\text{flag}} \mod n {% endkatex %}

First, let's look at the contents of `output.txt`. The contents are given `n` and `c`.
<!--まずはoutput.txtの中身を見てみよう．中身にはnと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](https://eprint.iacr.org/2016/644.pdf)

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.

<!--こちらはDEFCON24で発表された論文のようだ．私は暗号の専門家ではないため，すべてを理解できているわけではないが，ここから問題を解くヒントは得られた．-->

<!--こちらはDEFCON24で発表された論文のようだ．私は暗号の専門家ではないため，すべてを理解できているわけではないが，ここから問題を解くヒントは得られた．-->

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/p07zihq9nctlxge7egrq.png)

{% katex %}  y = g^x \mod n(=pq) {% endkatex %}

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).
<!--この図は，上の式からxを求めるという難しい問題をnではなくmod pとmod qからxを求める簡単な問題へと分解可能なことを示している．Finally, we can use the Chinese Reminder Theorem (CRT) to derive the answer to the original question.-->

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


```python
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}'
```