Crack the Power picoMini by CMU-Africa Solution

Description

1. Step 1

   Check if modular reduction occurred

   Observation

   I noticed the public exponent e was suspiciously small and the challenge name referenced 'crack the power,' which suggested the ciphertext might equal m^e as a plain integer with no modular reduction, making a direct integer root attack viable.

   If the exponent e is small (e.g., 3) and the message m is short, then m^e may be less than n, meaning c = m^e exactly - no reduction mod n took place. You can take the e-th integer root directly.

   Learn more

   In RSA, encryption computes c = m^e mod n. The mod n operation is what makes RSA a one-way function - it mixes the exponentiated value with the large modulus in a way that is hard to reverse without knowing the private key. However, this reduction only activates when m^e >= n. If the message is small enough that m^e < n, then c = m^e as a plain integer - the modular reduction never takes effect.

   When e = 3 and the message is a short ASCII string (say, 20 bytes), m is on the order of 2^160. Raising that to the 3rd power gives roughly 2^480. An RSA modulus is typically 2048 bits (2^2048), so the result is far smaller than n and no reduction occurs. This makes the ciphertext a perfect cube whose integer cube root directly yields the plaintext.

   This is why cryptographic standards (PKCS#1 v1.5, OAEP) require random padding to be added before encryption. The padding inflates the message to be close to the size of n, ensuring modular reduction always occurs and making the plaintext statistically indistinguishable from random.

2. Step 2

   Compute the integer e-th root

   Observation

   I noticed that confirming no modular reduction occurred meant c = m^e exactly, which suggested using gmpy2.iroot to take the exact e-th integer root since Python's built-in float math lacks the precision needed for thousands-of-bit numbers.

   Use gmpy2.iroot() which returns (root, is_exact). If is_exact is True, you have the plaintext m. Convert to bytes.

   python

   python3 -c "
   import gmpy2
   from Crypto.Util.number import long_to_bytes
   c = <ciphertext_integer>
   e = 20
   m, exact = gmpy2.iroot(c, e)
   if exact:
       print(long_to_bytes(m).decode())
   "

   Copied!

   Expected output

   picoCTF{...}

   What didn't work first

   Tried: Use Python's built-in pow() or float() to compute the e-th root directly

   Python's float type has only 64-bit precision, so c**(1/e) on a 3200-bit ciphertext silently rounds to the nearest float and gives a completely wrong integer. The result will not be exact and long_to_bytes will produce garbage. gmpy2.iroot is necessary because it operates on arbitrary-precision integers and returns an exact flag to confirm the root is perfect.

   Tried: Run the script without verifying the 'exact' flag and decode whatever iroot returns

   If modular reduction did occur (m^e >= n), iroot will still return a value, but exact will be False and the returned integer is not the plaintext. Decoding it anyway yields random-looking bytes or a UnicodeDecodeError. Always check exact before treating the root as valid plaintext.

   Learn more

   gmpy2 is a Python wrapper around the GMP (GNU Multiple Precision Arithmetic Library), which handles arbitrarily large integers efficiently. Python's built-in integers support arbitrary precision, but GMP is orders of magnitude faster for cryptographic-scale numbers (hundreds to thousands of digits).

   gmpy2.iroot(c, e) computes the integer e-th root of c - it returns the largest integer r such that r^e <= c, along with a boolean indicating whether the root is exact (r^e == c). The exact flag is critical: if it is False, the cube root attack does not apply and you would need a different approach (such as Coppersmith's method for partial modular reduction).

   long_to_bytes(m) from PyCryptodome converts a large integer back into its big-endian byte representation. RSA plaintexts are conventionally encoded as integers using big-endian byte order, so this function is the standard way to recover the original string from the decrypted integer.

3. Step 3

   Use RsaCtfTool for automation

   Observation

   I noticed a public key PEM file was provided alongside the ciphertext, which suggested RsaCtfTool could automate the small-exponent attack directly against the key file rather than requiring manual extraction of n and e.

   Alternatively, RsaCtfTool.py handles this attack automatically with the --attack cube_root flag.

   python

   python3 RsaCtfTool.py --publickey key.pem --uncipherfile cipher.bin --attack cube_root

   Copied!

   What didn't work first

   Tried: Run RsaCtfTool with --attack cube_root when the actual exponent is 20, not 3

   The --attack cube_root flag specifically targets e=3 and does not automatically generalize to e=20. The tool will report no plaintext found because its cube_root implementation computes iroot(c, 3) rather than iroot(c, e) for arbitrary small e. You need to run the manual gmpy2.iroot(c, 20) script instead, or check if the tool has a separate flag for the general small exponent case.

   Tried: Pass --attack wiener instead, assuming a small exponent means a small private key

   Wiener's attack targets a small private exponent d, not a small public exponent e. These are different weaknesses: small d leaks the private key via continued fractions on e/n, while small e causes the cube-root (or e-th root) shortcut when m^e < n. Wiener's attack will produce no output here because d is a normal 2048-bit value.

   Learn more

   RsaCtfTool is an open-source collection of RSA attack implementations designed for CTF competitions. It automates dozens of known RSA weaknesses including: small exponent attacks (e=3 cube root, Hastad's broadcast attack), weak moduli (Fermat factorization when p and q are close, smooth numbers, Pollard's p-1), common modulus attacks, Wiener's attack for small private exponents, and more.

   The tool accepts public keys in standard PEM format, raw n/e values, or several other formats, and attempts multiple attacks automatically or a specific one via --attack. It is the standard first step when approaching an unknown RSA challenge - running all attacks takes seconds and quickly rules out the most common weaknesses.

   Understanding why each attack works is more valuable than just running the tool. The cube root attack specifically: --attack cube_root checks if iroot(c, e) is exact, handling e=3, e=5, and other small exponents. If the root is not exact, it falls back to Coppersmith-style approaches for partial information.

Flag

Per-instance flag. Prefix confirmed across 2 independent instances (hashes seen: ..., 837d7226). The hash suffix varies per team/instance.