The Accursed Lego Bin

Platform: Umasscybersec | Category: Cryptography | Type: Challenge | Difficulty: Medium | OS: NA | Author: D3v0o0Nu11 | Date: 2026-04-11 | Status: Solved Techniques: integer_nth_root, permutation_inversion, textbook_rsa_exact_root

Summary

Task: a flag bitstream was scrambled with repeated Python shuffles, and the shuffle seed came from textbook RSA with e = 7. Solution: take two exact integer 7th roots to recover the seed source text, then invert the 10 deterministic shuffles in reverse order to restore the flag bits.

Recon

Port scan

 bash read-only • copy allowed Copy
nmap -p- -sV -sC <TARGET> --min-rate 1000 -Pn

Enumeration highlights

• Event: umasscybersec | ID: 20260411_umasscybersec_the_accursed_lego_bin
• Tags: rsa, textbook_rsa, low_exponent, random_shuffle, bit_permutation
• Indicators: textbook RSA uses a very small exponent such as e = 7, the plaintext is tiny compared to a 4096-bit modulus, ciphertext is actually an exact integer power with no modular wraparound, Python random.shuffle is applied repeatedly with deterministic seeds
• Source: 20260411_umasscybersec_the_accursed_lego_bin.md

Foothold

Vulnerability / Misconfiguration

1. integer_nth_root
2. permutation_inversion
3. textbook_rsa_exact_root

 bash read-only • copy allowed Copy
<command>

Exploitation

• See original writeup content for detailed exploitation.

Privilege Escalation

Enumeration

 bash read-only • copy allowed Copy
sudo -l
find / -perm -4000 2>/dev/null
getcap -r / 2>/dev/null
cat /etc/crontab
ps aux

Exploitation

1. N/A for challenge-type writeup; see exploitation above.
2. Flag obtained via challenge solve.

 bash read-only • copy allowed Copy
<command>

Flags

Key Takeaways / Lessons

• integer_nth_root
• permutation_inversion
• textbook_rsa_exact_root
• Tags: rsa, textbook_rsa, low_exponent, random_shuffle, bit_permutation

Original Writeup

<details><summary>Click to expand original content</summary>

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:

 python read-only • copy allowed Copy
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:

 python read-only • copy allowed Copy
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

1. Read encoder.py and note that it uses textbook RSA with e = 7.
2. Observe that the plaintext I_LOVE_RNG is tiny, so m^7 < n and the first RSA output is an exact integer 7th power.
3. Observe that the published enc_seed is seed^7 mod n, and this also stays below n, so it is another exact integer 7th power.
4. Take the integer 7th root of the published enc_seed to recover seed.
5. Take the integer 7th root of seed to recover the original message, confirming it is I_LOVE_RNG.
6. Convert the published hex flag into a bit array.
7. For each round from i = 9 down to 0, reseed Python's PRNG with seed * (i + 1), reproduce the shuffle on an index array, and invert that permutation.
8. Reassemble the recovered bits into bytes to obtain the original flag.

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import random

ENC_SEED = 27853968878118202600616227164274184566757028924504378904793832254042520819991144639702067205911203237440164930417495337197532501173607130020895075421529488925453640401673956438276491981209692168887241600331323119747563338336714474549971016558306628074198388772585672217715120627041791075104601103026751194857235765309608359123653353317678322176850235969280946203083455072140605141795053378439195293814791874092411691470992665912679118059266672118104677436338717139016415491690881114160151442145485980845723522027034166250144387200630948484934412980402141190370298072772878692178174395473352346736568834853932546775351591579301264010616662074516876263415244325179769805404580595987957830206775099221681479552297343673953519347816803686755315058241114932909715588571465125584675910868587612361307253375806962785674201551995414052898626175776112925401104907258409223265509906782478388392655489350014728299523474441953620142576405825798349964376116586305354010422094308152856531053593521850744465605649669069637606613192817098670399196448110611736116364403445860585755736974514672765253945103150765043635481842335038685418842068710568699703147745504514090439
ENC_FLAG_HEX = "a9fa3c5e51d4cea498554399848ad14aa0764e15a6a2110b6613f5dc87fa70f17fafbba7eb5a2a5179"
E = 7

def int_nth_root(value: int, n: int) -> int:
    lo, hi = 0, 1
    while hi ** n <= value:
        hi *= 2
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if mid ** n <= value:
            lo = mid
        else:
            hi = mid
    if lo ** n != value:
        raise ValueError(f"value is not a perfect {n}th power")
    return lo

def bits_from_hex(hex_str: str):
    return list(bin(int(hex_str, 16))[2:].zfill(len(hex_str) * 4))

def bits_to_bytes(bit_arr):
    return bytes(int("".join(bit_arr[i:i + 8]), 2) for i in range(0, len(bit_arr), 8))

def invert_shuffle(bit_arr, seed_value: int):
    positions = list(range(len(bit_arr)))
    random.seed(seed_value)
    random.shuffle(positions)

    original = [None] * len(bit_arr)
    for shuffled_index, original_index in enumerate(positions):
        original[original_index] = bit_arr[shuffled_index]
    return original

def main():
    seed = int_nth_root(ENC_SEED, E)
    plain_num = int_nth_root(seed, E)
    plain_text = plain_num.to_bytes((plain_num.bit_length() + 7) // 8, "big").decode()
    print(f"[+] Recovered message: {plain_text}")

    flag_bits = bits_from_hex(ENC_FLAG_HEX)
    for i in range(9, -1, -1):
        flag_bits = invert_shuffle(flag_bits, seed * (i + 1))

    flag = bits_to_bytes(flag_bits).decode()
    print(f"[+] Flag: {flag}")

if __name__ == "__main__":
    main()

Running the script recovers the intermediate plaintext I_LOVE_RNG and then reconstructs the flag by undoing the shuffle sequence.

</details>

---

signed by XESXOR