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

Partial Tenacity: exploit the RSA structure, recover the missing secret, and decrypt the flag.