Category: Cryptography

NSA Backdoor (500 points)

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

This challenge took me quite a bit to solve (as to be expected; it’s a 500 point challenge). However, having solved it, it actually wasn’t that hard of a challenge.

On first glance it…actually looks similar to Very Smooth. Infact, it’s the same script. However, the only difference is that when the ciphertext is computed, it is performed through e^flag rather than flag^e. Although a small alteration, this practically means that RSA will not work in this case. So, we’re going to need to find some way to figure out what exactly is going on here.

The hint listed (the only one) tells us to look up D. Wong, and that he is very friendly to cats, apparently. After some digging I then discovered this (written by a David Wong, so he’s probably our guy). The post mentioned is just a simple overview of the longer post listed here. Essentially, given the aspect of the hint referring to “cats”, it can be ascertained that it’s referring to the socat diffie hellman backdoor. This was a pretty big vulnerability essentially brought on by the fact that all diffie hellman exchanges were being carried out by a nonprime 1024 bit modulus (p).

More information about that backdoor can be found here: https://github.com/AllThing/socat_backdoor

Essentially, what we can do is, if we know the order of n (now p), we can do one of two things to recover c (now the Diffie-Hellman public key):

• Active Small Subgroup Attack
• Pohlig-Hellman Algorithm

Given how we don’t have access to a live server, we aren’t able to perform option 1. This leaves us with option 2: Pohlig-Hellman.

Pohlig-Hellman is essentially a way to solve the Discrete Logarithm Problem provided that we are able to factor the order of p into smaller prime factors, for which we can then compute the discrete logarithm of each of them. This vastly decreases the amount of time it takes compared to just straight up factoring p.

Afterwards, we can then use these results with the Chinese Remainder Theorem to construct the result of the discrete log of 3^x=public_key.

…ALTHOUGH…one small mention…

What I said was all good and whatnot, but when it actually came time to running the thing, I noticed that, well, firstly…I wasn’t able to code the algorithm myself. So I just resorted to sympy.ntheory.residue_ntheory._discrete_log_pohlig_hellman.

But I also noticed that, once pohlig hellman completed, our order returned a discrete logarithm result that was valid, but was not the flag. It took me a long while to fix this, however, eventually I did. All I needed to do was divide the order by a specific amount and constrain it enough so we know for certain that only the flag will be considered as a possible private key.

After that, I got the flag.

Script

#!/usr/bin/python3
#define the variables
g = 3
p = 0x5bf9961e4bcfc88017e1a9a40958af5eae3b3ee3dcf25bce02e5d04858ba1754e13e86b78a098ea0025222336df6b692e14533dad7f478005b421d3287676843f9f49ffd7ebec1e8e43b96cde7cd28bd6fdf5747a4a075b5afa7da7a4e9a2ccb26342799965f3fb6e65e0bb9557c6f3a67568ccbfaaa7e3d6c5cb79dd2f9928111c3183bf58bd91412a0742bbfb3c5cebfb0b82825da0875c5ee3df208ce563f896d67287c8b9aad9943dd76e5eae1fc8abd473ec9f9e4f2b49b7897954ca77b8f00ed51949c7e4f1f09bd54b830058bd7f4da04e5228250ba062ec0e1d19fb48a05333aada60ecdfc8c62c15773ed7e077edba71621f6a6c10302cc9ed26ec9
public_key = 0x2475123653f5a4b842e7ac76829e896450126f7175520929a35b6a4302788ceff1a605ed30f4d01c19226e09fc95d005c61320d3bbd55cfebbc775332067ac6056c1969282091856eaa44ccaf5738ac6409e865bbd1186d69f718abd2b3a1dd3dc933a07ca687f0af9385406fd9ee4fa5f701ad46f0852bf4370264c21f775f1e15283444b3bf45af29b84bb429ed5a17adc9af78aee8c5351434491d5daf9dd3ce3cf0cd44b307eb403f0e9f482dd001b25ed284c4e6c1ba2864e5a2c4b1afe4161426cc67203f30553c88d7132aef1337eca00622b47cb7a28195f0e3a2ab934e6163b2941a4631412e13b1a72fe34e6480fada9af4dae14f2608805d61ee

#create imports
from tqdm import trange
from Crypto.Util.number import long_to_bytes
from sympy.ntheory import pollard_pm1
from sympy.ntheory.residue_ntheory import _discrete_log_pohlig_hellman, _discrete_log_pollard_rho

#sympy already has an implementation of the Pollard p-1 algorithm
#i didn't need to code it from scratch with my Very_Smooth writeup. lol.
#so we first need to extract p_1 and p_2 from p to get the smooth factors
print("Gathering p_1 using Pollard p-1...")
p_1 = pollard_pm1(p, 0xffff, 2)
if p_1 == None:
    print("p_1 was none (Pollard p-1 failure?)")
    exit()

p_2 = p//p_1
if p_1*p_2 != p:
    print(f"{p_1*p_2} != {p}") #sanity check
    exit()

#phi(p) = order
order = (p_1-1)*(p_2-1)

#perform Pohlig-Hellman against the public key to obtain X, using the group order
#I used a for-loop to divide the order by larger amounts in order to decrease the possible private key size
#this was because in my original testing, pohlig hellman DID return a valid result, but it was too large to be the flag
#it was around the third iteration where the flag was returned to me.
#picoCTF{cf58a7b8}
print("Performing Pohlig-Hellman...")
for i in trange(10):
    try:
        x = _discrete_log_pohlig_hellman(p, public_key, g, order//(i+1))
    except KeyboardInterrupt:
        continue
    if pow(g, x, p) != public_key:
        print("Pohlig-Hellman failure") #another sanity check
        exit()

    print(long_to_bytes(x))