HackTheBox Partial Tenacity Writeup

Explore the basics of cybersecurity in the Partial Tenacity Challenge on Hack The Box. This medium-level Challenge introduces encryption reversal and file handling concepts in a clear and accessible way, perfect for beginners.

https://app.hackthebox.com/challenges/660

Description

You find yourself in a labyrinthine expanse where movement is restricted to forward paths only. Each step presents both opportunity and uncertainty, as the correct route remains shrouded in mystery. Your mission is clear: navigate the labyrinth and reach the elusive endpoint. However, there’s a twist—you have just one chance to discern the correct path. Should you falter and choose incorrectly, you’re cast back to the beginning, forced to restart your journey anew. As you embark on this daunting quest, the labyrinth unfolds before you, its twisting passages and concealed pathways presenting a formidable challenge. With each stride, you must weigh your options carefully, considering every angle and possibility. Yet, despite the daunting odds, there’s a glimmer of hope amidst the uncertainty. Hidden throughout the labyrinth are cryptic clues and hints, waiting to be uncovered by the keen-eyed. These hints offer glimpses of the correct path, providing invaluable guidance to those who dare to seek them out. But beware, for time is of the essence, and every moment spent deliberating brings you closer to the brink of failure. With determination and wit as your allies, you must press onward, braving the twists and turns of the labyrinth, in pursuit of victory and escape from the labyrinth’s confounding embrace. Are you tenacious enough for that?

Exploitation

#!/usr/bin/env python3
from math import sqrt
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

def load_data():
    with open('output.txt') as f:
        n = int(f.readline().split(' = ')[1])
        ct = bytes.fromhex(f.readline().split(' = ')[1])
        hint_p = int(f.readline().split(' = ')[1])
        hint_q = int(f.readline().split(' = ')[1])
    return n, ct, hint_p, hint_q

def decrypt(p, q, n, ct):
    e = 0x10001
    d = pow(e, -1, (p-1)*(q-1))
    key = RSA.construct((n, e, d))
    flag = PKCS1_OAEP.new(key).decrypt(ct)
    return flag

def create_masks(primelen):
    pmask = ''.join(['1' if i % 2 == 0 else '0' for i in range(primelen)])
    qmask = ''.join(['1' if i % 2 == 1 else '0' for i in range(primelen)])
    return pmask, qmask

def bruteforce_digit(i, n, known_prime, prime_to_check, hint_prime):
    msk = 10**(i+1)
    known_prime = 10**i * (hint_prime % 10) + known_prime
    for d in range(10):
        test_prime = 10**i * d + prime_to_check
        if n % msk == known_prime * test_prime % msk:
            updated_prime_to_check = test_prime
            updated_hint_prime = hint_prime // 10
            return known_prime, updated_prime_to_check, updated_hint_prime

def factor(n, p, q, hp, hq, pmask, qmask, prime_len):
    for i in range(prime_len):
        if pmask[-(i+1)] == '1':
            p, q, hp = bruteforce_digit(i, n, p, q, hp)
        else:
            q, p, hq = bruteforce_digit(i, n, q, p, hq)
    assert n == p * q
    return p, q

def pwn():
    n, ct, hint_p, hint_q = load_data()
    prime_len = len(str(int(sqrt(n))))
    pmask, qmask = create_masks(prime_len)
    p, q = factor(n, 0, 0, hint_p, hint_q, pmask, qmask, prime_len)
    flag = decrypt(p, q, n, ct)
    print(flag.decode())

if __name__ == '__main__':
    pwn()

Summary

The Partial Tenacity Challenge on Hack The Box is a medium-level task focused on cryptographic exploitation and RSA factorization. The scenario involves navigating a labyrinthine challenge where participants must factorize an RSA modulus (n) using partial knowledge of its prime factors (hint_p and hint_q). The Python script automates the process by reconstructing the full prime factors through a digit-by-digit brute-force approach, leveraging the provided hints. Once the primes are recovered, the script decrypts the ciphertext using RSA-OAEP to reveal the flag. This challenge emphasizes the importance of understanding RSA vulnerabilities and demonstrates how partial information can be exploited to break encryption. It’s an excellent exercise for those interested in cryptography and factorization techniques.