The Accursed Lego Bin

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: integer_nth_root, permutation_inversion, textbook_rsa_exact_root

Summary

Walkthrough of the CUSTOM Crypto The Accursed Lego Bin. 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,

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.

Key Takeaways / Lessons

• Mastering integer_nth_root, permutation_inversion, textbook_rsa_exact_root was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-04-11 • CUSTOM • The Accursed Lego Bin • Difficulty: Medium