PicoCTF is a Capture the Flag event focused on teaching skills, rather than being primarily a competition. This means that the challenges are written in a way to teach the person playing something and since there are different levels, many will learn something new during the CTF.

Here's the challenge:

"Daedalus Corp's spy in Thyrin Labs seems to sometimes use an encrypted drop box for their messages. We intercepted one of their messages, but we don't seem to be able to decrypt it. Fortunately, we have the source and the address of their key generation server: maybe there's a way to use that to decrypt their message? Unfortunately, we don't have their list of cached primes...

Their source, and our intercepted message, are here. The key generation service is running at vuln2014.picoctf.com:51818."

Let's take a look at what happens when we connect to the service:

$ nc vuln2014.picoctf.com 51818

Welcome to the Daedalus Corp Spies RSA Key Generation Service. The public modulus you should use to send your updates is below. Remember to use exponent 65537.

9088fd841834f273448691c2b81bffe38bd65613f0a6896651fefbf19bbc4b7a6991ab7b46f7d5a462ce7d85fea27354929568adcbe7be3a4215813d2a2e559759509bff8f080e8d90c79877095b73e9f2a98bae4add09df876efb61547f9434760203a633b8c19663822867028a816a29868d5e074704b62d67f3d930cf7cf3

OK. So we're getting information to use for a public key. Let's take a look at the files we were provided.

#!/usr/bin/env python

import os

import SocketServer

import threading

import random

import time

class threadedserver(SocketServer.ThreadingMixIn, SocketServer.TCPServer):

pass

id_dict = {}

prime_pool = set()

def make_pool():

global prime_pool

# pull our primes out of the cache

# we used to just generate new ones, but we were running out of randomness too fast.

# 30 should be plenty

f = open('primes.txt')

data = f.read()

data = data.split('\n')

data = [int(d) for d in data if d != '']

for d in data:

prime_pool.add(d)

assert len(prime_pool) == 30

make_pool()

generated_keys = set([])

class incoming(SocketServer.BaseRequestHandler):

def handle(self):

cur_thread = threading.current_thread()

self.request.send("Welcome to the Daedalus Corp Spies RSA Key Generation Service. The public modulus you should use to send your updates is below. Remember to use exponent 65537.\n")

p = random.choice(list(prime_pool))

q = random.choice(list(prime_pool - set([p])))

self.request.send(hex(p*q).strip('0x').strip('L') + '\n')

generated_keys.add(tuple(sorted((p, q))))

server = threadedserver(("0.0.0.0", 51818), incoming)

server.timeout = 4

server_thread = threading.Thread(target=server.serve_forever)

server_thread.daemon = True

server_thread.start()

server_thread.join()

If you're comfortable with python, this script isn't too complicated. Basically, make_pool() reads in a list of 30 prime numbers to use. Then when a client connects, this script picks two at random and uses that to generate the RSA PublicKey.

The other file is a pcap. For the sake of simplicity, I'll just copy out the relevant information from that pcap:

Welcome to the Thyrin drop box. Please send your public key and message.

Public key: c20a1d8b3903e1864d14a4d1f32ce57e4665fc5683960d2f7c0f30d5d247f5fa264fa66b49e801943ab68be3d9a4b393ae22963888bf145f07101616e62e0db2b04644524516c966d8923acf12af049a1d9d6fe3e786763613ee9b8f541291dcf8f0ac9dccc5d47565ef332d466bc80dc5763f1b1139f14d3c0bae072725815f

Message: 49f573321bdb3ad0a78f0e0c7cd4f4aa2a6d5911c90540ddbbaf067c6aabaccde78c8ff70c5a4abe7d4efa19074a5249b2e6525a0168c0c49535bc993efb7e2c221f4f349a014477d4134f03413fd7241303e634499313034dbb4ac96606faed5de01e784f2706e85bf3e814f5f88027b8aeccf18c928821c9d2d830b5050a1e

We now know the public key that was used, as well as the message that we are being asked to crack.

I'll note that we don't actually need knowledge of the public key to complete this problem, but it does make it a little simpler. As the name suggests, the problem has to do with not having enough entropy. Wikipedia has a nice article about RSA for those unfamiliar. I will assume some level of familiarity with the crypto system moving forward, but everything referenced is expanded on in that article.

In RSA, *n* is the letter used to describe a common modulus used in encrypting and decrypting. This is what is being generated by the server.py script. We are less interested in the *n* value itself as that is public, and more interested in the two relative primes *p* and *q* that were used to generate it. This is because, without knowledge of those two primes, we would have to fight the difficult problem of factorizing very large numbers. This is something that, so far as we know, nobody has a good way of doing.

Let's look at the *make_pool* function. Notice that the function is reading the primes from a static file. The assumption is obviously that the file itself will not be changing, and that those primes have been computed once. If that were not the case, we would again have a bigger problem. However, assuming that the file is static, we know that at most there are 30 primes being used. While we're not being provided the prime numbers themselves, we're being provided a composite of two of the prime numbers. Also, we're allowed to ask for a new composite as many times as we like. This means we can create a list of a bunch of different valid composites that are generated by those 30 primes.

The insight at this point is to understand what we're looking at. Each number we get is *n = p * q*. Because we have a bunch, and because the greatest common denominator for two numbers is a much easier problem, we can try mashing all of the different *n* values together and see if the greatest common denominator is something other than 1. If so, we've just recovered a prime that was in that file on the server.

The first step is to collect a sample of composite numbers. This can be done easily through a bash script:

while [ True ]; do nc vuln2014.picoctf.com 51818 | grep -v Welcome >> compositeList ; done

Just leave that running for a little bit. Now that we have a sample, we need to try checking gcd. For this, I utilized python and it's library for gcd and iterations:

from fractions import gcd

import itertools

f = open("primesList","r")

comp = f.readlines()

# Sanitize input

comp2 = [int(x[:-1],16) for x in comp]

print("Shaking primes free")

primes = set([])

numPrimes = 0

for pair in itertools.combinations(comp2,2):

# Don't care if they're the same

if pair[0] == pair[1]:

continue

d = gcd(pair[0],pair[1])

# Check for legit win

if d != 1:

primes = set(list(primes) + [d])

if len(primes) > numPrimes:

numPrimes = len(primes)

print("Recovered {0}/30 primes".format(numPrimes))

if numPrimes == 30:

print("Recovered All Primes")

break

Most of the script it just plumbing to make nice output. The key is the looping through combinations and checking *gcd(pair[0],pair[1])*. Also, I added a check to quit after finding 30 unique primes since we know that's all there should be. If you take that out, you can verify that indeed we're only seeing 30 primes.

Here's the output:

$ ./recoverPrimes.py

Shaking primes free

Recovered 1/30 primes

Recovered 2/30 primes

Recovered 3/30 primes

Recovered 4/30 primes

Recovered 5/30 primes

Recovered 6/30 primes

Recovered 7/30 primes

Recovered 8/30 primes

Recovered 9/30 primes

Recovered 10/30 primes

Recovered 11/30 primes

Recovered 12/30 primes

Recovered 13/30 primes

Recovered 14/30 primes

Recovered 15/30 primes

Recovered 16/30 primes

Recovered 17/30 primes

Recovered 18/30 primes

Recovered 19/30 primes

Recovered 20/30 primes

Recovered 21/30 primes

Recovered 22/30 primes

Recovered 23/30 primes

Recovered 24/30 primes

Recovered 25/30 primes

Recovered 26/30 primes

Recovered 27/30 primes

Recovered 28/30 primes

Recovered 29/30 primes

Recovered 30/30 primes

Recovered All Primes

Now that we know the primes, we can get back to the pcap. I noted earlier that we don't need the public key. Because we have it, we can now find exactly which primes were involved in the creation of that key. Again, going back to *n = p * q*, all we need to do is test each combination of our primes for a match with the value we're provided.

for p,q in itertools.combinations(primes,2):

# Check if we're working with the right primes

if p * q == pubKey:

print("Matched pubKey:\np = {0}\nq = {1}".format(p,q))

phi = (p-1) * (q-1)

break

The above code does that. While we're matching the *p* and *q* values, we might as well calculate the phi function that we'll need to decrypt.

Matched pubKey:

p = 12068007193924458934136437678747032125702047288192605563386647134926126290032925205587466786811951860570462107503408192389036293790565313661792631609456701

q = 11290942893206290336467162060839444758991526481896862143525109986063294905531141292368885863941910700698869187227122590028398079775349558555477255622057419

The rest is simply generating the corresponding private key and using it to decrypt the message. Note that in the initial output, there was a mention about *Remember to use exponent 65537.* We need to know that number for decryption.

# Calculate the private key

privKey = modinv(e,phi) # Decrypt it

decrypted = pow(encData,privKey,pubKey)

# Decode it

decoded = binascii.unhexlify(hex(decrypted)[2:])

The last part there was just taking the decrypted input, changing it to hex, then changing that hex into ASCII. It's a normal way of encoding/decoding messages.

Putting it all together into a script, we get:

$ ./recoverPrimes.py

Shaking primes free

Recovered 1/30 primes

Recovered 2/30 primes

Recovered 3/30 primes

Recovered 4/30 primes

Recovered 5/30 primes

Recovered 6/30 primes

Recovered 7/30 primes

Recovered 8/30 primes

Recovered 9/30 primes

Recovered 10/30 primes

Recovered 11/30 primes

Recovered 12/30 primes

Recovered 13/30 primes

Recovered 14/30 primes

Recovered 15/30 primes

Recovered 16/30 primes

Recovered 17/30 primes

Recovered 18/30 primes

Recovered 19/30 primes

Recovered 20/30 primes

Recovered 21/30 primes

Recovered 22/30 primes

Recovered 23/30 primes

Recovered 24/30 primes

Recovered 25/30 primes

Recovered 26/30 primes

Recovered 27/30 primes

Recovered 28/30 primes

Recovered 29/30 primes

Recovered 30/30 primes

Recovered All Primes

Recovering possible decryption keys

Matched pubKey:

p = 12068007193924458934136437678747032125702047288192605563386647134926126290032925205587466786811951860570462107503408192389036293790565313661792631609456701

q = 11290942893206290336467162060839444758991526481896862143525109986063294905531141292368885863941910700698869187227122590028398079775349558555477255622057419

Recovered private key: 70118266743531770742541821902419779511239599511770182985184154839839018008193467076473425663009520539545369270962530218486192141886710801892227602961998928213537654150767790772889562458972990736497832327701547730106443165511208494243221689127374975558908570745982766653293349491204750802344491680794276628473

Recovered message: b"Good thing no one can read this! I'd hate for them to know that the flag is make_sure_your_rng_generates_lotsa_primes."

Flag: make_sure_your_rng_generates_lotsa_primes

Source for the solver can be found on github: https://github.com/Owlz/CTF/blob/master/2014/PicoCTF/Low-Entropy/solve.py