The Perils of Inadequate Key Size in Public Cryptosystems

A public-key cryptosystem is an asymmetric cryptosystem where the public key and the private key form a mathematically related key pair. The public key acts as an encryption key whereas the private key is used for decryption. It is understood that the decryption key needs to be kept confidential to ensure secrecy of the communications that are encrypted with the corresponding public key. The Rivest Shamir Adleman (RSA) algorithm is an implementation of one such public key cryptosystem. The following capture the flag (CTF) challenge is a good instrument to learn the intricacies of practical and secure implementation of the RSA cryptosystem.

About NetForce 'Private Parts' Cryptography Challenge

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

In order to solve this challenge, you are required to locate the correct password that is revealed to you after exploiting a cryptographic vulnerability in this implementation of the RSA public key algorithm. You must be logged in to try potential passwords. The challenge requires prior knowledge of public key cryptosystems, and RSA encryption and decryption equations. Moreover, you will need to use tools for hexadecimal editing, reading public keys and certificates, and tedious mathematical calculations. You will also need to have basic programming skills to code the decryption algorithm from scratch.

Spoiler Alert!

Please be advised that the following content provides a solution to the intriguing cryptographic challenge 'Private Parts' on Net-Force. I advise against reading further without having tried your absolute best at this challenge first.

Solution to Cryptography Challenge 15, Level 316: "Private Parts"

This challenge presents us with three files [Figure 1]. One of these is the encrypted file (netforce.enc) that we need to decrypt in order to solve the challenge. The next file is obviously a public key. This Privacy Enhanced Mail (PEM) format likely contains the public key certificate that was used to encrypt the 'netforce.enc' file. The third file, GHMS.uyu, seems to baffling and needs analysis since '.uyu' is an 'unassigned' file extension.

Figure 1

What we are missing is the '.key' file that would contain the private key that could decrypt this file. Hence, the challenge lies in decrypting the encrypted file without access to the private key.

We commence our cryptanalysis with the unknown file type since this file most likely contains a clue to solve the challenge. Because we are completely unfamiliar this file type, we use the UNIX 'file' utility to determine the actual file type. This utility reads magic numbers or file signatures to specify the file type. However, in this case, it failed to shed any light on the matter [Figure 2].

Figure 2

Our only option now is to look at raw hexadecimal data stored in the file and attempt to make sense of it. We use the 'hexeditor' utility to view the file in hex mode [Figure 3]. We learn that the file contains a few seemingly random bytes and we notice the corresponding ASCII text.

Figure 3

It seems that this ASCII text is a simple encryption of some sort. After experimenting with the text, we discover that it is a shift cipher that decremented the corresponding decimal value of every character in the original message and then replaced the original character with the character corresponding to this decremented decimal value. Hence, we just need to reverse this process to obtain the original text message. For instance, the first character 'B' has decimal value '66', increment this by 1 and we get '67', and the corresponding ASCII character is 'C'. After repeating this procedure for all of the characters, we have the following decrypted message:

"Challenge notes: The file 'netforce.enc' can be decrypted with a private key. Every 64 bits chunk was encrypted at a time using the raw algorithm, the same can be done to decrypt by Rivest, Shamir, & Adleman"

Note: To speed things up, we used a Python code to decrypt this initial hint [Figure 4]. The code is available on Github here.

Figure 4

Now we understand that the RSA public key cryptosystem was used to encrypt the file, using the given public key. The hint suggests that we can decrypt the file using the private key. However, this key is not provided to us as one of the challenge files. Therefore, we need to extract it somehow from the given information.

Doing the Math

We are aware that RSA is only safe as long as the public key size is large enough. If it can be factored, then an attacker can obtain the corresponding private key. We need to determine if we can factor the public key stored in the '.pem' file. For this purpose, we use the 'openssl' utility in Linux to study the details of the given '.pem' public key [Figure 5]:

openssl rsa -inform PEM -text -pubin -noout < public_key.pem

Figure 5

We notice that the modulus of this public key is small enough to be factored, that is, it is possible for us to obtain the two prime numbers from this public key. This is a tedious calculation, so we used the Wolfram Alpha calculator online. After factorization, we notice that there are only two other divisors to this number (besides '1' and the number itself) and these are prime factors that we were looking for [Figure 6].

Figure 6

Since we are familiar with the intricacies of RSA algorithm, we know that the private exponent ('d') is formulated from these two prime numbers ('p' and 'q'). We need to calculate:

Here 'e' is the public key exponent, 'φ(n)' is Euler's totient function calculated as '(p-1) * (q-1)', and 'n' is 'p * q'.

As per the given challenge, we have 'e' = 65537 [Figure 5] and 'φ(n)' = 3917781346 * 4215069448. Substituting these values in the equation above, we need to calculate:

Once again, this is a tedious calculation and we need to use Wolfram Alpha. The resulting number, 9440767265896423601, is our private exponent [Figure 7].

Figure 7

Now that we have the private exponent, we can decrypt the encrypted file according to this RSA equation:

Here 'm' is the decrypted message and 'c' is the cipher text.

According to the challenge, we need to calculate:

We need to write a small program that will take 64 bits at a time (according to the hint we decrypted above) and raise them to the power '9440767265896423601', mod '16513720463601767803'.

Note: If you are not acquainted with the RSA encryption or decryption algorithms and the relevant equations discussed above, please refer to this text.

Coding the Decryption Program

We will commence by extracting hexadecimal data from the netforce.enc file and then perform the required operations for decryption over 16 hex bytes at a time (equivalent to performing these operations over 64 bit blocks). We use the 'xxd' utility in Linux for extraction of plain hex data from the encrypted file [Figure 8]:

xxd -p netforce.enc > netforce.hex

Figure 8

We now write a Python script that will perform the following required operation for decryption [Figure 9]:

Figure 9

This script reads the hex data of the encrypted file and then removes all newline characters from it. The calculations, that are required according to the decryption equation, are performed in line 15 of this code, and the result is stored in 'm'. After removing the unnecessary '0x' characters from the result, the final decrypted hex data is stored in a new file (decrypted.hex).

Note: This Python script is available at Github here. If you have questions regarding any part of this script, please let us know in comments below.

Close examination of this decrypted hex data revealed that it is not the final hex data that we are looking for. The hex bytes '2F 2F' at the start of this data do not indicate a valid magic number and file type, and we are still unsure of how to obtain the password from this [Figure 10].

Figure 10

After further analysis, we realize that this is base64-encoded data and we need to base64 decode it before we arrive at the final decrypted version. However, notice that some extra padding bytes have been added at the end of this base64 encoded hex (41414141x0). We need to remove these padding bytes since the base64 encoded hex probably ended at 3D3D (or '= ='). After removing the padding bytes, we copy the entire base64 encoded hex data and create a file using this data [Figure 11]. For this purpose, we can use the online hex utility here.

Figure 1

As a final step, we need to base64 decode this file. We use the online base64 decoder here and obtain the base64 decoded file as the final step [Figure 12].

Figure 12

This file is immediately recognized by our system to be an MP3 file [Figure 13].

Figure 13

Furthermore, when we inspect the hex data in the file, we notice the file header 'FF FB' that indicates that this is an MP3 file [Figure 14].

Figure 14

The 'file' utility also recognizes this to be an MP3 [Figure 15].

Figure 15

This 256 KBPS MP3 file contains a 29-second audio recording that contains a synthetic voice saying the following:

"As you can see a 64 bit key isn't enough. The asymmetric algorithm is only secure if you cannot find the key's prime factors. That's why you need larger keys. And now, the password for this NetForce challenge: A L L H A I L A L I C E A N D B O B"

Password: allhailaliceandbob

End Remarks

As demonstrated by this challenge, the effectiveness of RSA cryptosystem depends heavily on the difficulty of factoring a mathematical product of two sizable prime numbers. The public key and the RSA algorithm are never assumed to be a secret. According to Kerckhoffs's principle, a cryptosystem should protect against eavesdroppers even if the adversaries know every detail about it – except the private key. Accordingly, since the RSA public key is not confidential, choosing a small key size would mean that your adversary is able to factor this public key and discover the two prime numbers. After that, it's a simple matter of performing mathematical calculations in accordance with the RSA decryption algorithm and relevant equations. This enables the attackers to decrypt your sensitive communications easily, and the need for a large key size becomes apparent.

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

If you enjoyed this cryptography challenge, consider attempting more captivating challenges at Net-Force to test or build your skills in security. If you have spent a substantial amount of time on a specific challenge – and the solution has evaded you for long – then you can always come here to seek solutions. The solutions that we provide discuss only successful attempts for the sake of brevity.