Intro

Over this past summer with the virus and all, I’ve been able to explore a variety of interests ranging from neuroscience research, self-study classes, and reading. One of the perhaps more interesting things I’ve done however was participate in Capture the Flag events or competitions (CTFs). In essence, CTFs are cybersecurity competitions designed to use various skills in hacking and other areas practically to complete a task or challenge.

There are two main types of CTFs: classic “jeopardy”-style CTFs and attack and defense CTFs. Attack-defense CTFs involve every team having its own machine or server with several built-in vulnerabilities. The goal of this CTF is then to attack other teams’ machines, exploiting their vulnerabilities to find hidden flags within the machine. What makes this interesting however is that you have the freedom to patch these vulnerabilities through various tactics. What makes this even more interesting is the concept of game-time or a tick. Every tick, a team can employ its exploit against other teams (presuming it works) and retrieve a flag to then submit to the game server. This creates a time pressure element on other teams to patch vulnerabilities as well as an interesting strategic factor, where a team can spread a successful patch to other teams if you wouldn’t want a team to get too far in the lead. One can even analyze the traffic analysis to a game server to perhaps steal flags or exploits from other teams. Overall, this style of CTF is really interesting but it wasn’t the main one I participated in (these are especially hard and require more in-depth skills). This video at the start explains what I talked about here well.

Instead of attack and defense CTFs, I focused more on the classic “jeopardy”-style CTFs this summer. These types of CTFs feature completing various challenges from different categories to earn points. These categories often include binary exploitation, web exploitation, steganography, cryptography, open-source intelligence and many more. Whoever scores the most points then wins the CTFs – fairly simple. Just through participating in these, I’ve learned various coding skills, steganography techniques, and cryptography methods. In this article, I’ll talk about the importance of prime numbers through one concept I’ve learned through these CTFs: Rivest-Shamir-Adleman (RSA) encryption, a modern encryption technique that is still widely used today.

General Encryption Information

The best way to think of encryption and decryption techniques would be a function; you plug a plaintext in and you get some ciphertext out. However, if we encrypted everything with this same encryption function, it would only be a matter of time until that function is cracked, effectively exposing the rest of the information using the same encryption function. This is where keys come in. In general, these keys change the function somehow, altering the output given the same plaintext. This solves our previous problem as even though one may know the encryption algorithm, they would still need to know the key to decrypt a certain ciphertext. Knowing what function to use and key generation is a complex topic and I’ll touch on it a bit in a later section.  There are two types of key algorithms: symmetric key algorithms which use the same key for both encryption and decryption as well as asymmetric key algorithms which use different keys for encryption and decryption. Asymmetric key algorithms are much slower than symmetric key algorithms but also boast the fact that they are more convenient as one public key can be distributed to encrypt messages that would then be decrypted by a users’ private key or decrypt messages encrypted by a users’ private key. In other words, asymmetric algorithms do not require all parties to distribute a key beforehand like in symmetric key algorithms. Further asymmetric encryption possesses increased security as one user can no longer exploit the algorithm with only one key. Asymmetric encryption is the most widely used key algorithm on the internet due to its convenience and security.

RSA Encryption

RSA encryption is one of the more popular asymmetric encryption techniques. The best way to explain it in my opinion is to just explain the steps to go through key generation, encryption, and decryption. Key generation is where the importance of primes really shines in the RSA cryptosystem (fancy word for the set of algorithms/functions for encryption, decryption and key generation). Key generation works through these general steps:

1. Pick two prime numbers p and q.
2. The product of these two numbers N is one part of the public key.
3. Calculate Euler’s totient function for N, ϕ(N). Intuitively, this gives the number of numbers that are co-prime with N. A number co-prime with N means that it shares no common factors with N. Euler’s totient function for N evaluates to ϕ(N)=(p-1)(q-1). A proof of this can be found here.
4. Choose a number e that is greater than 1 but less than ϕ(N) and is co-prime to both ϕ(N) and N. This will constitute the second part of the public key.
5. Solve the equation de (mod ϕ(N))=1. This is equivalent to finding the modular inverse d of e mod ϕ(N). d is the private key.
6. To summarize, the public key is (e, N) and the private key is d.

Now to encrypt a plaintext message M to get the ciphertext C, we use our public key to obtain: C=Me (mod N). To decrypt the ciphertext C to get the plaintext message M, we use the private key to obtain: M=Cd (mod N). The people who came up with RSA were indeed very smart, but I encourage you to try and find out why this specific set of functions and algorithms work.

Large Prime Numbers

Finding p and q allows one to solve for every other parameter in the RSA cryptosystem, including the private key, allowing one to decrypt and encrypt any message they want. This is why having large prime numbers p and q is important due to the fact that the number N is public. If one were able to find a prime factorization of N (which gets harder with larger prime numbers intuitively), then they would be able to retrieve p and q, allowing them to effectively steal the private key and decrypt any message they want. This is why finding prime numbers and even finding a pattern for these numbers have become such a major application topic in the field of pure math. 

RSA Problems in CTFs

Many jeopardy-style CTFs will involve the category of cryptography. This cryptography category will feature a variety of traditional ciphers such as columnar ciphers, autokey ciphers, and Bifid ciphers as well as modern cryptography techniques including RSA, Blowfish, AES, and elliptic curve techniques (may talk about this in a later article). Just in this article, I’ll expand on a couple of the RSA problems I’ve encountered while participating in a variety of CTFs.

The easiest way to exploit RSA is to simply just brute-force the private key d. The issue with this is that it’s really slow, especially if one is using large prime numbers as they should. A more common challenge includes finding a vulnerability in RSA through brute-forcing the prime factorization for N using various methods. Once someone obtains p and q from the problem, they can then decrypt the encrypted message and find the flag. However, this is again really slow if large prime numbers are used. 

The rest of these problems require outside factors. A more complex problem could include some sort of faulty encryption. Suppose person A uses the wrong public key (e2, N) to encrypt a message. However, person B receives the message and is not able to decrypt it as he is given a private key that does not correspond to the public key person A used. Person B tells this to person A and person A uses the right public key (e1, N) to resend the message to person B. Now, suppose person C intercepted the ciphertext person A was sending as well as both public keys person A used. Person C can then exploit this using the Extended Euclidean Algorithm if the greatest common denominator of e1 and e2 is 1. The process of this as well as relevant code can be found here. This is often referred to as the Common Modulus Attack. 

The next attack involves encrypting multiple messages with a low public exponent e. Sometimes, it’s useful to use a low number for e as it makes the calculations significantly easier (e=3 is a common value). However, if an attacker can retrieve e number of ciphertexts that encrypt the same message but have different N values, they can use the Coppersmith method to obtain the plaintext M. The Coppersmith method requires heavy math that is pretty complex so if you’re looking to understand it more, view this source.

Through this section, I’ve listed a variety of RSA attacks that I’ve encountered through participating in various CTFs. However, the category of cryptography in CTFs encompass even more than just RSA attacks though, including other traditional and modern cryptography techniques as I’ve explained before.

Personal Commentary on CTFs

Cryptography and the RSA cryptosystem in particular, is just one small thing I’ve learned through various CTF competitions. I’ve also learned basic exploitation of web servers (SQL Injections, XSS), steganography (LSB, audio waveform analysis), exploitation of file binaries, and cyber forensics (PCAP analysis). Generally, doing these CTFs provides a fun medium for practical cybersecurity experience. Even though I don’t personally plan on going into the cybersecurity field, I found a ton of other benefits as well:

1. Sharpening logic and problem-solving skills
2. Networking with other fellow CTF players and taking a part in a small and unique community
3. Experience with various tools and UNIX systems (learning to work in GNU/Linux and the command terminal)
4. Improves familiarity with new coding languages (C++, Java, Python, Javascript, PHP, SQL, assembly)
5. Strengthen existing coding skills to solve various scripting problems
6. Adds a whole new dimension to your resume
7. Finding unique solutions to hard problems and competing in competitions is just fun

If you’re looking to get into the CTF space as well, I recommend visiting CTFTime which is the primary website for organizing CTF competitions and finding a CTF team. Being completely honest, it does take a large learning curve to get into it, but once you get the answer, it can feel so rewarding.