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

...