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