The Accursed Lego Bin — UMass Cybersecurity CTF

Description

I dropped my message into the bin of Legos. It's all scrambled up now. Please help.

English summary: the challenge provided an RSA-derived seed value and a hex-encoded scrambled flag. The goal was to recover the hidden shuffle seed, undo the repeated bit permutations, and reconstruct the original flag.

Analysis

The core weakness is textbook RSA with a tiny public exponent. In encoder.py, the script encrypts the fixed plaintext I_LOVE_RNG with e = 7 and a fresh 4096-bit modulus:

n, seed = RSA_enc(text)

Because the plaintext integer for I_LOVE_RNG is extremely small compared to a 4096-bit modulus, m^7 < n. That means the modular reduction in pow(m, 7, n) never changes the value, so the published seed is actually just the exact integer 7th power of the message integer.

The script then raises that value to the 7th power again:

enc_seed = pow(seed, e, n)

For the same reason, seed^7 is still below n, so enc_seed in output.txt is also an exact integer 7th power. This gives a direct recovery path: take the integer 7th root of enc_seed to recover seed, then take another integer 7th root to recover the original plaintext integer and decode it back to I_LOVE_RNG.

The rest of the challenge is only a deterministic permutation. The flag is converted into a bit array, then shuffled 10 times with Python's random.shuffle, using seeds seed * (i + 1) for i = 0..9. Since the seed is recoverable and random.shuffle is reversible once the permutation is known, we can recreate each shuffle on an index array and apply the inverse permutations in reverse order.

Solution

...