Hack The Box Cyber Santa CTF - Crypto Day 2 - XMAS Spirit Crypto Writeup

Challenge Files:  crypto_xmas_spirit.zip

Contained the following contents:

• challenge.py
• encrypted.bin

As expected, "encrypted.bin" contained 776,746 bytes worth of gibberish:

"challenge.py" contained the following code:

#!/usr/bin/python3

import random

from math import gcd

def encrypt(dt):

        mod = 256

        while True:

                a = random.randint(1,mod)

                if gcd(a, mod) == 1: break

        b = random.randint(1,mod)

        res = b''

        for byte in dt:

                enc = (a*byte + b) % mod

                res += bytes([enc])

        return res

dt = open('letter.pdf', 'rb').read()

res = encrypt(dt)

f = open('encrypted.bin', 'wb')

f.write(res)

f.close()

The first thing I noticed is that it opened a file called "letter.pdf", and I didn't see that in the challenge zip file.  Re-reading the challenge description, it says, "Santa has no idea about cryptography. Can you help him read the letter?"  Therefore, we need to decrypt the "encrypted.bin" into a "letter.pdf" file.  This script took in the original "letter.pdf" and encrypted it into "encrypted.bin", and now it's our job to reverse the process.

I started by trying to manually reverse the encrypt() function into a decrypt() function, but quickly got stuck trying to reverse the modulus on this line:  enc = (a*byte + b) % mod

After rigorous Googling on how to perform the inverse of a modulus operator, I took a break from that strategy after realizing how hard it is to do so, since reversing a "mod" operator yields many answers.  For example, since modulus captures the remainder of two numbers divided against each other, all odd numbers divided by 2 always has remainder 1.  So a zillion things can be the answer to "x % 2 = 1".

Changing gears, I spawned a "test.py" file to figure out how the encrypt() function works by observing how it handles simple input.  In my case, I fed it "AAAABBBB" with some debug print statements to see what the encrypted contents look like.

I ran it a few times and noticed the "a" and "b" values changed each time, but the "Byte" value stayed the same.  "Byte" is the variable representing each individual character from the input string, so that makes sense that it stayed static.  Since "a" and "b" changed each time, the math produced different encrypted strings each time as well.  I got curious if it would ever randomly produce the original input string if I ran it enough times.  Let's see why "a" and "b" keeps changing with each run:

mod = 256

a = random.randint(1,mod)

b = random.randint(1,mod)

So "a" and "b" is given a random number between 1 and 256 each run.  This means there is only a finite amount of ciphertext the encrypt() function can create; therefore, ONE of these random "a's" and ONE of these random "b's" combinations HAS to decrypt the message!  So for my small scale test, I did an infinite while loop that only stops if it finds the original input string of "AAAABBBB".  Essentially, my goal was to feed in "AAAABBBB" and obtain "AAAABBBB" as the "encrypted text" using the same challenge algorithm.  I also printed out which "a" and which "b" was responsible for this as well:

while True:

        encrypted, a, b = encrypt(message)

        if b"AAAABBBB" in encrypted:

                print("\nEncrypted Message: %s, a: %s, b: %s" % (encrypted, a, b))

                break

And I found it with "a = 1" and "b = 256", yielding this same output repeatedly:

Of course for the real thing, we wouldn't use a=1 and b=256 because that would just take in the original "encrypted.bin" and give us the same gibberish as output, but alas, we have proof of concept.  Now for the real thing, I modified the code to loop through 1-256 for "a" and 1-256 for "b" in a double for loop.  

Also, I only read in one line of gibberish from the "encrypted.bin" file because if I tried to decrypt all the data through my double for loop, it would take an eternity for a ~0.75MB text file.

More importantly, I opted to try decrypting only the first line from "encrypted.bin" because I assumed this would spit out a legitimate PDF file, and if so, the file header with the "PDF" magic number would appear if decrypted successfully.  As I decrypted each with a different "a" and "b" value, I wrote it to a file in the file name format, "output_a_b.pdf" where "a" and "b" is replaced with their current respective values in the for loop.  Here's my code to do so:

with open("encrypted.bin", "rb") as f:

        data = f.read()

for A in range(1, 256):0

        for B in range(1, 256):

                file = open("PDFs/output_%s_%s.pdf" % (A, B), "wb")

                #print(encrypt(data, A, B))

                file.write(encrypt(data, A, B))

                file.close()

2 Important things to note:  

• When reading and writing binary data, you must read it in with "rb" and write it out with "wb" instead of just 'r' and 'w'.
• Notice I commented out the print statement.  Here's why.  Brute forcing tactics take a long time, and printing debug messages to the screen makes it take HOURS longer, so I commented out that line after I had a warm fuzzy that my code worked properly.  
• I created a password brute forcer in C some time ago and it took 18 hours to crack a five character password when I printed out "Password not found" over and over.
• I commented out that line, and it took half a millisecond...

In another terminal on my Kali machine, I ran "file *.pdf | grep PDF" when it finished.  LO AND BEHOLD, ONE FILE HAS A PDF HEADER!

At this point, I could taste the flag in my mouth, AND I thought how ridiculous it would've been to try to reverse the modulus math.

I modified my code for the final time with "a=153" and "b=96" hardcoded in (it actually took a few tries with my typos because my hands were shaking from excitement).  I also changed "readline()" to "read()" since we want to process the entirety of "encrypted.bin" now.  Not required, but for satisfaction, I also made the output file "letter.pdf" as intended by the challenge story.

with open("encrypted.bin", "rb") as f:

        data = f.read()

file = open("letter.pdf", "wb")

file.write(encrypt(data, 153, 96))    # I changed the function to "def encrypt(dt, a, b)"

file.close()

And... VOILA!!!  The letter to Santa and the flag!  I've never seen something so exciting!

HTB{4ff1n3_c1ph3r_15_51mpl3_m47h5}