Created: 2014-11-07 21:04:24
Last modified: 2014-11-09 23:28:11
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
.
We're pretty sure that 30 total possible primes is low enough that we should be able to correlate different keys somehow...
Factor the given publickey since we have only 30 primes, then use the factors to compute the private key and decrypt the message.
For the purposes of this solution, I am going to assume you are familiar with the basics of the RSA encryption/decryption
In this problem we are given a server which generates RSA moduli and are told that there are only 30 possible primes that the server uses to generate them. First, we copy the given modulus 0xc20a1d8b3903e1864d14a4d1f32ce57e4665fc5683960d2f7c0f30d5d247f5fa264fa66b49e801943ab68be3d9a4b393ae22963888bf145f07101616e62e0db2b04644524516c966d8923acf12af049a1d9d6fe3e786763613ee9b8f541291dcf8f0ac9dccc5d47565ef332d466bc80dc5763f1b1139f14d3c0bae072725815f
and the cipher text
0x49f573321bdb3ad0a78f0e0c7cd4f4aa2a6d5911c90540ddbbaf067c6aabaccde78c8ff70c5a4abe7d4efa19074a5249b2e6525a0168c0c49535bc993efb7e2c221f4f349a014477d4134f03413fd7241303e634499313034dbb4ac96606faed5de01e784f2706e85bf3e814f5f88027b8aeccf18c928821c9d2d830b5050a1e
out of the intercepted_message.pcap
using Wireshark. We can glean two key observations from this:
If we repeatedly request moduli it wont be too long before one of the keys shares a prime with our modulus (See a python sample of this below). If this occurs, the GCD of the two moduli will be the p
component of the modulus and dividing the modulus, N
by p
will yeild the other prime q
. Now that we have the two primes and know the public exponent, e
equals 65537, we can easily compute the private exponent d
as 70118266743531770742541821902419779511239599511770182985184154839839018008193467076473425663009520539545369270962530218486192141886710801892227602961998928213537654150767790772889562458972990736497832327701547730106443165511208494243221689127374975558908570745982766653293349491204750802344491680794276628473
and the message as 41494331723717004087840363038436379137678883897083290482504777727264502253603851759718429929339251785330232810578894088434140357577326859552100822540305154760883449774383987636028167175968532867374560076986174085246917601557997651752239365247146390720857679075750704377311507373191982
Finally, converting the decrypted number to plaintext reveals the message:
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.
and the flag!
Python Sample Code for finding the gcd of the modulus:
from fractions import gcd
import socket
server = "vuln2014.picoctf.com"
c = int(0xc20a1d8b3903e1864d14a4d1f32ce57e4665fc5683960d2f7c0f30d5d247f5fa264fa66b49e801943ab68be3d9a4b393ae22963888bf145f07101616e62e0db2b04644524516c966d8923acf12af049a1d9d6fe3e786763613ee9b8f541291dcf8f0ac9dccc5d47565ef332d466bc80dc5763f1b1139f14d3c0bae072725815f)
test_num = 1
while gcd(c,test_num) == 1:
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect((server, 51818))
sock.recv(2048)
string = "0x" + sock.recv(2048)
test_num = int(string,16)
print gcd(test_num,c)
print c/gcd(test_num,c)
make_sure_your_rng_generates_lotsa_primes