YALM — HackTheBox

Description

"I created an encryption server with RSA, but I forgot to show the modulus. Can you help me recover it yet another time?"

Server at 154.57.164.75:30995

RSA encryption server with e=3 and hidden modulus N. Option 1 encrypts a flag with known prefix. Option 2 provides a binary oracle that reveals whether input m < N or m >= N. Goal: recover N via binary search, then use Coppersmith's method to find the flag.

Analysis

The server implements RSA with:

• e = 3 (very small public exponent)
• Unknown modulus N (2048-bit)
• Two options:
  • Option 1 (Get secret): Encrypts a message with known prefix 'Hey! This is my secret... it is secure because RSA is extremely strong and very hard to break... Here you go: ' (110 bytes) concatenated with the FLAG, and returns the ciphertext.
  • Option 2 (Test encryption): Takes a hex plaintext m, encrypts it in a loop dividing by N each iteration. If m >= N, the loop runs more than once and returns "Too many messages!". If m < N, the loop runs once and returns "Thanks for the message!".

The key vulnerability is the combination of:

1. Binary oracle in option 2 allows recovering N exactly via binary search
2. e = 3 with known message prefix enables Coppersmith's stereotyped message attack

For Coppersmith's method to work, the unknown portion must be smaller than N^(1/e). With e=3 and N being 2048-bit, we can recover up to ~682 bits of unknown data. The flag is ~25 bytes = 200 bits, well within bounds.

Solution

Step 1: Recover N via Binary Search

The test_encryption oracle tells us whether any given integer m is less than N or not. We binary search between 2^2047 and 2^2048 to find the exact value of N. This requires ~2047 network queries.

from pwn import *

HOST = "154.57.164.75"
PORT = 30995

def connect():
    r = remote(HOST, PORT)
    r.recvuntil(b"Option: ")
    return r

def get_secret(r):
    r.sendline(b"1")
    line = r.recvuntil(b"Option: ").decode()
    for l in line.split('\n'):
        if 'Ciphertext:' in l:
            ct = l.split('Ciphertext: ')[1].strip()
            return int(ct, 16)
    return None

def test_encryption(r, m_int):
    m_hex = hex(m_int)[2:]
    r.sendline(b"2")
    r.recvuntil(b"Plaintext: ")
    r.sendline(m_hex.encode())
    resp = r.recvuntil(b"Option: ").decode()
    if "Thanks" in resp:
        return True   # m < N
    elif "Too many" in resp:
        return False  # m >= N
    return None

def binary_search_n(r):
    low = 1 << 2047
    high = 1 << 2048
    iterations = 0
    while high - low > 1:
        mid = (high + low) // 2
        result = test_encryption(r, mid)
        if result:
            low = mid
        else:
            high = mid
        iterations += 1
        if iterations % 200 == 0:
            log.info(f"Iteration {iterations}, remaining: {(high-low).bit_length()} bits")
    return high

r = connect()
ct = get_secret(r)
log.info(f"Got ciphertext: {hex(ct)[:50]}...")

N = binary_search_n(r)
log.info(f"Recovered N: {hex(N)[:50]}...")
r.close()

Step 2: Coppersmith's Stereotyped Message Attack

With e = 3 and known N, we apply Coppersmith's method:

• The message format is: prefix || FLAG where the prefix is 110 bytes of known text.
• The unknown FLAG is ~25 bytes ≈ 200 bits.
• Coppersmith's bound for e=3 is N^(1/e) = N^(1/3) ≈ 2^682 bits.
• Since 200 < 682, the unknown part is small enough for Coppersmith to recover.

# SageMath script for Coppersmith attack
from Crypto.Util.number import long_to_bytes, bytes_to_long

# Values from binary search
N = <recovered_N>
ct = <ciphertext>
e = 3

prefix = b'Hey! This is my secret... it is secure because RSA is extremely strong and very hard to break... Here you go: '

def coppersmith_attack(N, e, ct, prefix, flag_len):
    """Coppersmith's stereotyped message attack using SageMath"""
    prefix_int = bytes_to_long(prefix)
    
    # Message = prefix * 256^flag_len + x where x is the unknown flag
    # c = (prefix * 256^flag_len + x)^e mod N
    
    P.<x> = PolynomialRing(Zmod(N))
    shift = 256^flag_len
    f = (prefix_int * shift + x)^e - ct
    
    # Make monic
    f = f.monic()
    
    # Find small roots using Coppersmith's method
    # X is the upper bound on the root
    X = 256^flag_len
    roots = f.small_roots(X=X, beta=1.0, epsilon=0.05)
    
    return roots

# Try different flag lengths
for flag_len in range(20, 60):
    roots = coppersmith_attack(N, e, ct, prefix, flag_len)
    for root in roots:
        flag_bytes = long_to_bytes(int(root))
        if b'HTB{' in flag_bytes:
            print(f"FLAG: {flag_bytes.decode()}")
            break

Full Solve Script

#!/usr/bin/env python3
from pwn import *
from Crypto.Util.number import long_to_bytes, bytes_to_long

HOST = "154.57.164.75"
PORT = 30995

def connect():
    r = remote(HOST, PORT)
    r.recvuntil(b"Option: ")
    return r

def get_secret(r):
    r.sendline(b"1")
    line = r.recvuntil(b"Option: ").decode()
    for l in line.split('\n'):
        if 'Ciphertext:' in l:
            ct = l.split('Ciphertext: ')[1].strip()
            return int(ct, 16)
    return None

def test_encryption(r, m_int):
    m_hex = hex(m_int)[2:]
    r.sendline(b"2")
    r.recvuntil(b"Plaintext: ")
    r.sendline(m_hex.encode())
    resp = r.recvuntil(b"Option: ").decode()
    if "Thanks" in resp:
        return True
    elif "Too many" in resp:
        return False
    return None

def binary_search_n(r):
    low = 1 << 2047
    high = 1 << 2048
    while high - low > 1:
        mid = (high + low) // 2
        if test_encryption(r, mid):
            low = mid
        else:
            high = mid
    return high

# Phase 1: Recover N
r = connect()
ct = get_secret(r)
N = binary_search_n(r)
r.close()

print(f"N = {N}")
print(f"ct = {ct}")

# Phase 2: Coppersmith (run in SageMath)
# Save N and ct, then run the SageMath script above