BabyEncryption Technical Analysis — Hack The Box (Cryptography)

Photo by Mika Baumeister on Unsplash

“Hack the Box” is a really great platform for learning and gaining real-world experience within cybersecurity. Platforms like “Hack the Box” are an essential tool that future cyber-professionals can utilize in order to gain experience in an industry in a safe way. Without these types of platforms, it would be almost impossible, or illegal to gain the same experience in the cybersecurity industry. In this article, I will explore concepts in software engineering and cybersecurity in order to decipher an encrypted message from an organized crime group (as the challenge states). I will be using Python 3.9.2 for completing this challenge.

Challenge:

You are after an organized crime group which is responsible for the illegal weapon market in your country. As a secret agent, you have infiltrated the group enough to be included in meetings with clients. During the last negotiation, you found one of the confidential messages for the customer. It contains crucial information about the delivery. Do you think you can decrypt it?

Below is the original challenge file that is downloadable in this challenge. Once you unzip the original files provided by Hack the Box, then you will see that the “magic” happens in a chall.py file.

import string
from secret import MSG
def encryption(msg):
    ct = []
    for char in msg:
        ct.append((123 * char + 18) % 256)
    return bytes(ct)
ct = encryption(MSG)
f = open('./msg.enc','w')
f.write(ct.hex())
f.close()

Here we can see that the encryption function receives a “msg” parameter and iterates through each character, performing a mathematical calculation to alter the data, and ultimately returns the result in bytes. Next, the script will take this result and use the built-in hex function to convert the bytes into the corresponding hexidecimal form. All of this is written to a file called “msg.enc”. This file is also provided in the challenge and is a plain-text file. Here are the contents:

6e0a9372ec49a3f6930ed8723f9df6f6720ed8d89dc4937222ec7214d89d1e0e352ce0aa6ec82bf622227bb70e7fb7352249b7d893c493d8539dec8fb7935d490e7f9d22ec89b7a322ec8fd80e7f8921

It is clear to see that whatever the original message once was, it is clearly encrypted and cannot be deciphered at first inspection. There is a basic principle in cryptography known as “Kerckhoffs’s principle”. “It was formulated in the end of the nineteenth century by Dutch cryptographer named, Auguste Kerckhoffs. The principle goes as follows: A cryptographic system should be secure even if everything about the system, except the key, is public knowledge” (Crypto-IT). In this challenge we will see that this “cyptographic system” does not follow Kerckhoffs’s principle and once we know how it works under the hood, the encryption is quite trivial to decipher. Not only will we see how to reverse engineer and decipher the message, but we will discuss two possible solutions and the engineering principles behind each one.

First, when starting our reverse engineer efforts, we need to examine the original encryption function a bit more. We can extract the meat of the function, which is the mathematical equation:

(123 * char + 18) % 256)

In this case, the equation used to create the encryption uses the modulus operator, which is unfortunately not possible to reverse. This is because a modulus is the remainder or signed remainder of a division. Because of this, reversing the calculation would be out of the question, but we can still fall back to a brute force approach.

To do this, we write a function that accepts a character and performs the same mathematical function as the original encryption function. This will be used during the actual brute force algorithm.

import binascii
import time # used for timing only
''' --- Original ---
def encryption(msg):
    ct = []
    for char in msg:
        ct.append((123 * char + 18) % 256)
    return bytes(ct)
'''
def encrypt(char):
    return (123 * char + 18) % 256

Next, let’s look at how the main script will work. Remember, we will discuss two approaches:

with open("msg.enc") as f:
    msg = binascii.unhexlify(f.read())
    start = time.perf_counter()
    deciphered_w_loops = decipher_w_loops(msg)
    stop = time.perf_counter()
    loop_time = (stop - start) * 1000
    
    start = time.perf_counter()
    deciphered_w_hashmap = decipher_w_hashmap(msg)
    stop = time.perf_counter()
    hashmap_time = (stop - start) * 1000

We start by reading the encrypted message, but we have to covert it back to bytes from hexidecimal. Here we use the “unhexlify” function from the “binascii” library. I also have used the time library to capture the running time of both approaches which will be discussed at the end.

In the first approach, we will use nested loops in order to brute force the encryption.

def decipher_w_loops(msg):
    og_msg = []
    for byte in msg:
        for i in range(1, 129):
            encrypted = encrypt(i)
            if encrypted == byte:
                og_msg.append(chr(i))
    return ''.join(og_msg)

We start with an empty list for storing each deciphered character. Next, we iterate through each byte within the encrypted message. Then, while we are working on decrypting that byte, we iterate through all the possible printable characters. To do this, you can iterate through all numbers 1–128, where each number represents a different printable character. With each iteration here, we use the encrypt function to encrypt that character and check if it matches the current character from the provided message. If this result matches, then we will append the resulting character to the storage list. Finally, we join all the elements in the storage list and return that from the function. If we print out the result, then we can get the deciphered message and win the challenge!

print(f'Brute force: {brute_forced}')
Brute force: [flag redacted]

Now this is great and all, but its pretty plain and not very elegant as far as the solution goes. Not to mention its performing the decryption in O(n^2) time, which is terrible. So lets apply some good engineering practices to create a more elegant solution.

Instead of using nested loops, we can create a hashmap data structure that we can use to look up the decrypted values, in O(1) time, by providing the encrypted value. This will not only drastically reduce the decryption time for longer messages, but the hashmap could be saved to storage and used for decrypting future messages in O(1) time, instead of running through an entire algorithm for each message.

To do this in python is quite simple. For those who are not aware, the standard ‘dictionary’ object in python is actually a ‘hashmap’, which allows you to look up values, using keys. To create this hashmap, or dictionary, we can use a technique similar to list comprehension in python, but instead it is dictionary comprehension. The code below will create a dictionary where the keys are the encrypted values for all printable characters (1–128) and the values are the actual, deciphered characters.

def decipher_w_hashmap(msg):
    map = {encrypt(i): i for i in range(1, 129)}
    msg = [chr(map[char]) for char in msg]
    return ''.join(msg)

Once the dictionary is created, we can use list comprehension to create a list of the deciphered characters by iterating through every byte in the message and looking up its value in the dictionary. Finally, we join the list back into a string, and return its value. This is a much more efficient algorithm with a one-time max runtime of O(n+m), where m is the number of printable characters, and a future minimum runtime of O(n). Now with this improved algorithm, should we come across an encrypted message as long as this article, it shouldn’t be too painless to decipher :)

For additional reference, if you would like to see exactly how much time savings we are experiencing, see the output results below:

Loop duration: 0.7745 ms
Hashmap duration: 0.0174 ms

All that to shave off ~.75 milliseconds…

Citations

Crypto-IT. (n.d.). Kerckhoffs’s principle. http://www.crypto-it.net/eng/theory/kerckhoffs.html