BSides CHS RSA Pcapng

A walkthrough of RSA.pcapng from BSCHS 2017.

November 13, 2017 - 8 minute read -
bschs crypto

This was one of the first challenges I attempted during the CTF. Pcap challenges are typically very easy if you know what to look for and are familiar with the common tools used to work with pcap files. The difference with this challenge and typical other pcap challenges is that this one has something to do with RSA.

Download the challenge here.

Flag 1

As with most beginner challenges, running the strings command is an excellent first step.

Strings Flag 1A

This gives us our first flag: Itcann0tbeSoe4sy!.

During the CTF, this flag had not yet been put into the scoreboard by the time I solved it, but it was quickly put in and we were rewarded with 100 points. I was also told that this might be a bait flag, but brushed it off seeing as the text literally said “the flag is”.

I had not realized that there was more to be had with this pcap until a teammate brought up that there was a public key captured in the pcap. This leads us to flag 2.

Flag 2

More in-depth analysis of pcap files can be done using an amazing tool called Wireshark. According to their website, “Wireshark is the world’s foremost and widely-used network protocol analyzer”. Their claim is true, it’s an amazing tool.

If we look through the pcap manually we can see that there are some DNS requests to ntp.ubuntu.com (time sync) and a very interesting set of data on tcp stream 1. You can filter by tcp streams in Wireshark by typing tcp.stream eq 1 in the Filter field. Right clicking on any packet and clicking Follow TCP Stream shows us the entire conversation.

Wireshark Flag 2A

We can see that two people are having a conversation about encrypting a message using RSA because the current channel of communication is insecure (well yeah it’s in plaintext and someone is actively sniffing your network!). One person then sends their public key to the other. The other person encrypts the message and sets up a python web server. Lastly, the owner of the public key performs a GET request on the web server to get the encrypted text. This can all be seen in different TCP streams. The following two pictures are tcp.stream eq 19 and an HTTP object found by navigating through Wireshark with File -> Export Objects -> HTTP.

Public key:

Wireshark Flag 2B

Ciphertext:

Wireshark Flag 2C

In order to understand why this next part works, we need to understand a little about the method used to encrypt the message. In public key cryptography, users generate a public and private keypair. The public key is used to encrypt a message and the private key is used to decrypt a message. The public key is meant to be shared with everyone that intends on encrypting a message and sending it to the owner of the public key. The private key is meant to be kept securely by whoever generated the public and private keypair.

Public Key Crypto

For example, Alice sends Bob her public key. Remember, this is not intended to be a secret. Bob then encrypts his message, “Hello Alice!”, with Alice’s public key. At this point, the ciphertext that Bob generated by encrypting his message with Alice’s public key is essentially invulnerable. The ciphertext is then sent to Alice. Alice is able to decrypt the ciphertext with the private key that corresponds with the public key Bob used.

Therefore, if you are able to retrieve a user’s private key, you’re able to decrypt any message that they have received if it was encrypted with their public key.

In order to understand how we can break RSA, we need to understand a little about the math behind it. The public key is made up of two variables, n and e. n is a very large number designed to be made public to everyone. e is almost always 65537. The private key is made up of five variables, n, e, d, p, and q. The n and e come from the public key. We know e is almost always 65537 to comply with the standard, but where does n come from? The variable n comes from the equation n = p * q. Both p and q are very large random prime numbers. RSA is based on the fact that multiplying p and q together is very computationally easy, but figuring out what two numbers make an integer n is very computationally difficult. Lastly, d is the exponent used to decrypt the ciphertext. d can be found with the equation d = modinv(e, ((p-1) * (q-1)) where modinv is the modular inverse function.

Let’s clarify our objectives now:

  1. Find n and e from the public key
  2. Factor n into p and q
  3. Calculate d with e, p, and q
  4. Generate a private key
  5. Decrypt the ciphertext with our new private key

Recall that n and e are meant to be shared with everyone and that in no way is this information supposed to be considered a secret. To recover n and e, we can use a simple Python program.

from Crypto.PublicKey import RSA

f = open("public.key", "r")
key = RSA.importKey(f.read())
print(key.n, key.e)

This prints the following:

n = 90187489204964341357580822098641855317607686795656773417285864916432620562501
e = 65537
  1. Find n and e from the public key
  2. Factor n into p and q
  3. Calculate d with e, p, and q
  4. Generate a private key
  5. Decrypt the ciphertext with our new private key

Recall that recovering the private key all hinges on being able to factor n. This means that we need a sufficiently small n that we can factor into p and q. A very good tool for doing this is Yafu or Yet Another Factoring Utility.

If we just launch yafu and run the factor command with our n, yafu will attempt to factor it and lucky for us, after only 114.6398 seconds or a little under 2 minutes we were able to recover p and q.

YAFU Cracked

p = 324388787784871038939401053607215918019
q = 278022831247715948169664169460326581079
  1. Find n and e from the public key
  2. Factor n into p and q
  3. Calculate d with e, p, and q
  4. Generate a private key
  5. Decrypt the ciphertext with our new private key

Now that we’ve recovered p and q, we can move on to calculating d. To do this, I wrote a simple python program that implements the formula for calculating d. I used the ECDSA module to import the inverse_mod function so that we don’t have to implement it ourselves. If you want to implement this function yourself you can take a look over at this math stackexchange post.

from ecdsa.numbertheory import inverse_mod

e = 65537
p = 324388787784871038939401053607215918019
q = 278022831247715948169664169460326581079
d = inverse_mod(e, ((p-1) * (q-1)))
print(d)
d = 34163825121724289157930657329766127532538458604069030506669045412324052489465
  1. Find n and e from the public key
  2. Factor n into p and q
  3. Calculate d with e, p, and q
  4. Generate a private key
  5. Decrypt the ciphertext with our new private key

To generate a private key, we can write some more python that turns out to be very simple.

from Crypto.PublicKey import RSA

n = 90187489204964341357580822098641855317607686795656773417285864916432620562501
e = 65537
d = 34163825121724289157930657329766127532538458604069030506669045412324052489465
p = 324388787784871038939401053607215918019
q = 278022831247715948169664169460326581079

key_params = (n, e, d, p, q)
key = RSA.construct(key_params)
print(key.exportKey().decode('utf-8'))

If we run the above python, it outputs our desired RSA private key.

Private Key Generated

  1. Find n and e from the public key
  2. Factor n into p and q
  3. Calculate d with e, p, and q
  4. Generate a private key
  5. Decrypt the ciphertext with our new private key

Lastly all we have to do is decrypt the ciphertext given the private key that we just generated. Fortunately for us, this is as easy as a single openssl command.

openssl rsautl -decrypt -inkey mykey.priv -in secret

Decrypted

This was worth an astounding 750 points! I hope you enjoyed the long explanation of how to solve this, but here is where I might make you a little mad. There is a tool on Github called RSACtfTool that does everything for you in just a couple seconds. No need to understand RSA or the attacks on it. No complicated math, just input and run.

All we have to do is supply RSACtfTool.py with the public key and ciphertext and it attempts to generate the private key and decipher the ciphertext.

RSA Solved

There isn’t a need to reinvent the wheel, but understanding how this magic tool works is beneficial.