Greed - Kinnaird CTF

Greed Challenge — RSA Low-Exponent Write-Up

Overview

This challenge revolves around a classic RSA weakness: using a small public exponent (e = 3) without proper padding. Under the right conditions, this allows direct recovery of the plaintext by taking an integer cube root of the ciphertext.

The task is to identify the real encrypted flag among several decoys and exploit this mathematical flaw.

Key Observations

RSA Parameters

• Public exponent: e = 3
  (Narratively hinted as the warden’s “three kingdoms”)

• Modulus size: ~254 bits

• Candidate ciphertext:

  0x1aadb93ce9a5704a83345e00
  

Critical Hint

“Sometimes the treasure is so light that it never touches the vault walls.”

This implies the plaintext m is small enough that:

m³ < N

When this happens, RSA encryption becomes:

c = m³

instead of:

c = m³ mod N

No modular reduction occurs — which is exactly what enables the attack.

Cryptographic Background

RSA encryption is defined as:

c = m^e mod N

If m^e < N, then:

c = m^e

For e = 3, recovering the plaintext is trivial:

m = ∛c

This is known as the RSA low-exponent attack and is why modern RSA implementations require padding (e.g., OAEP).

Identifying the Real Ciphertext

From vault_manifest.log, multiple encrypted values are listed:

• Reinforced gilded bars (large values)

• Bulk decoy storage (repetitive, patterned values)

• The “Relic” — described as “the lightest object in the vault”

The smallest ciphertext is:

0x1aadb93ce9a5704a83345e00

This aligns perfectly with the hint and the low-exponent condition.

Exploitation

Step 1: Convert Ciphertext to Integer

ciphertext = 0x1aadb93ce9a5704a83345e00

Decimal value:

8256629183588264188331712000

Step 2: Compute the Integer Cube Root

approx_root = round(ciphertext ** (1/3))

for offset in range(-5, 6):
    candidate = approx_root + offset
    if candidate ** 3 == ciphertext:
        print(candidate)

✔ Exact cube root found:

m = 2021161080

Verification:

2021161080³ = 8256629183588264188331712000

This confirms no modular reduction occurred.

Step 3: Recover the Plaintext

byte_len = (candidate.bit_length() + 7) // 8
plaintext_bytes = candidate.to_bytes(byte_len, 'big')
plaintext_bytes.decode()

Result:

b'xxxx'

Decoded string:

"xxxx"

Conclusion

This challenge demonstrates a textbook RSA low-exponent vulnerability:

• Small public exponent (e = 3)

• No padding

• Plaintext small enough that m³ < N

Under these conditions, RSA encryption degenerates into a simple cube operation, allowing direct plaintext recovery.

Final Flag

SkelerCTF{GREED_FRAGMENT_xxxx}

Lessons Learned

• Never use RSA without padding

• Small exponents are dangerous without safeguards

• Narrative hints often directly reflect cryptographic flaws

By SkelerSecurity