(This is a continuation from Part 1 of the walkthrough.)

And we’re back! In my last walk-through, I gained access to the user account of Orestis and nabbed the user.txt flag for the Brainfuck system on HackTheBox. After a much-needed break, I returned to the system to see if I could gain access to the root account and nab the root.txt flag.


My first task was to enumerate my environment and see what I could find. The most obvious place to look would be in Orestis’ home directory:

orestis@brainfuck:~$ ls -l
total 20
-rw------- 1 orestis orestis  619 Apr 29  2017 debug.txt
-rw-rw-r-- 1 orestis orestis  580 Apr 29  2017 encrypt.sage
drwx------ 3 orestis orestis 4096 Apr 29  2017 mail
-rw------- 1 orestis orestis  329 Apr 29  2017 output.txt
-r-------- 1 orestis orestis   33 Apr 29  2017 user.txt

Besides the user.txt, which contained the user-flag, there were three files that stood out. The most interesting was output.txt, which claimed to contain an “encrypted password” in the form of a very large number. This number, along with the debug.txt file (which contained additional numbers), was created by the encrypt.sage program:

nbits = 1024

password = open("/root/root.txt").read().strip()
enc_pass = open("output.txt","w")
debug = open("debug.txt","w")
m = Integer(int(password.encode('hex'),16))

p = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False)
q = random_prime(2^floor(nbits/2)-1, lbound=2^floor(nbits/2-1), proof=False)
n = p*q
phi = (p-1)*(q-1)
e = ZZ.random_element(phi)
while gcd(e, phi) != 1:
    e = ZZ.random_element(phi)

c = pow(m, e, n)
enc_pass.write('Encrypted Password: '+str(c)+'\n')

This program was written in Python, using the sage programming library, and it took the /root/root.txt file as input… the very file which contained the flag I sought to obtain! I wondered whether this was a diversion intended to slow me down and waste my time… I could waste precious time analyzing the code only to discover that this so-called “encryption” scheme was really a one-way, irreversible hash function. What if the true path to root was via privilege escalation attacks or exploiting some local service? But as an avid programmer fascinated with encryption, my curiosity got the best of me, and I dove in.

Sage Wisdom

I copied the three files onto my local system so that I could work on the code without spoiling the challenge for anyone else who happened to be hacking the box. I was able to figure out more about how the script worked, and began to piece together a means of working the script in reverse. Stated simply, here’s how the script works:

  1. Convert the flag stored in /root/root.txt into an integer, m.
  2. Calculate two large, random prime numbers, p and q.
  3. Calculate the product of p and q, stored in n.
  4. Calculate the product of p-1 and q-1, stored in phi.
  5. Find a random number e between 0 and phi-1 where the Greatest Common Denominator of e and phi is 1.
  6. Calculate the encrypted password with (m ** e) % n (via the pow function) and store it in the output.txt file.
  7. Store p, q and e in the debug.txt file.

It appeared that I would have to write some custom code to crack the password. Fortunately, I had some solid leads. Thanks to the debug.txt file, I knew the values used for p, q, and e, and I had the encrypted flag as well. Without knowing a way of reversing the pow function, I would have to brute-force all of the possible matching values for m, which I would then re-encode from integers back into text. From there, I could check each value of m to see whether it could be the flag.

Simple, right?

Not really. There were constraints on what the values of m could be – each HTB flag is a 32-character string comprising only letters and numbers. Still, that left a tremendous number of possibilities, and brute-forcing would take ages. I needed to find a better way to approach the problem – preferably, a more accurate mathematical method for calculating the reverse of pow(m, e, n).

Fortunately, I found a Stack Overflow post where a discussion of this process had already taken place, and I took some time to learn as much as I could from their discussion.

Reversing the Flow

With the help of the aforementioned Stack Overflow post, as well as another post which helped me to convert a large integer back into a string, I managed to write the following Python 3 code:

#!/usr/bin/env python3

import functools
import math

# -----[ The following functions were taken from James K Polk's reply  ]-----#
# -----[ to the following Stack Overflow query: https://bit.ly/2Pun615 ]-----#

def egcd(a, b):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def inverse(a, n):
    d, a_inv, n_inv = egcd(a, n)
    if d != 1:
        raise ZeroDivisionError("{} is not coprime to {}".format(a, n))
        return a_inv % n

def lcm(*x):
    if not x or len(x) < 2:
        raise ValueError("at least two arguments must be supplied to lcm")
    lcm_of_2 = lambda x, y: (x * y) // math.gcd(x, y)
    return functools.reduce(lcm_of_2, x)

def carmichael_pp(p, e):
    phi = pow(p, e - 1) * (p - 1)
    if (p % 2 == 1) or (e >= 2):
        return phi
        return phi // 2

def carmichael_lambda(pp):
    return lcm(*[carmichael_pp(p, e) for p, e in pp])

# -----[ The following code takes the resultant text files from Orestis' ]-----#
# -----[ encrypt.sage code and uses the above functions to calculate the ]-----#
# -----[ original plaintext of /root/root.txt.                           ]-----#

with open("output.txt", "r") as f:
    y = int(f.read().strip().split()[2])

with open("debug.txt", "r") as f:
    lines = [int(line.strip()) for line in f.readlines()]

p, q, b = lines

c = p * q

# Now we have y, b, and c. We need to calculate x, which is the original root
# flag in integer format.
lam = carmichael_lambda([(p, 1), (q, 1)])
z = inverse(b, lam)
x = pow(y, z, c)

# Now that we have x, we need to transform it back into plaintext. The
# following line was provided by Erik Aronesty in the following Stack Overflow
# conversation: https://bit.ly/2PsZpGl

root_flag = x.to_bytes(((x.bit_length() + 7) // 8), "big").decode()

print(f"Root flag: {root_flag}")

Once I had completed my code, all that was left was to execute it and hope for the best. Sure enough, thanks to the amazing mathematical genius of people who are much, much smarter than me, the code decrypted the root flag instantly:

root@kali:~/reverse# ./reverse.py
Root flag: 6efc1a5dbb8904751ce6566a305bb8ef

I took the flag, returned to the Brainfuck HTB page, and claimed my ownership of root.


I was a little disappointed that I never truly got root-level access to the system itself. Solving the programming problem was satisfying, and I felt proud of myself for being able to piece together the various parts of the puzzle, but I had still hoped to practice some privilege-escalation attack, or to exploit some misconfigured software to obtain root-level access to the machine. All the same, this was a very challenging box, with a number of creative steps required to capture the flags.

I’m willing to bet that the creator included more than one way to claim the root flag, so I’ll definitely be watching whatever walkthrough videos are available on YouTube to see if anyone else found methods that I had missed. It never hurts to learn from the hard work of others!

I look forward to my next challenge, and to the write-up that follows. Until then, stay safe, and stay tuned!