Dachshund Attacks picoCTF 2021 Solution

Description

1. Step 1Collect e, n, and c
   Connect to the server. It prints the public exponent e, modulus n, and ciphertext c. Copy these values for use in the attack script.
   Learn more

   In RSA encryption, the public key consists of two numbers: the modulus n (a product of two large primes) and the public exponent e. The ciphertext c is produced by computing c = m^e mod n, where m is the plaintext message as an integer.

   These three values - e, n, and c - are all that's needed to attempt an attack. The server gives them to you openly because e and n are part of the public key; only d (the private exponent) is supposed to be secret. The challenge is recovering d without factoring n.

2. Step 2Apply Wiener's Attack
   Wiener's attack recovers the private exponent d when d < n^0.25. The owiener Python library implements this attack. Install it with pip, then run the script to recover d and decrypt the ciphertext.
   bash

   pip install owiener

   Copied!

   python

   python3 << 'EOF'
   import owiener
   from Crypto.Util.number import long_to_bytes
   
   e = <e>
   n = <n>
   c = <c>
   
   d = owiener.attack(e, n)
   if d is None:
       raise SystemExit("Wiener's attack failed - d may not be small enough.")
   
   # Decrypt and verify the flag prefix
   m = pow(c, d, n)
   flag = long_to_bytes(m)
   assert flag.startswith(b"picoCTF{"), f"unexpected plaintext: {flag!r}"
   print(flag.decode())
   EOF

   Copied!
   Learn more

   Wiener's attack (1990) exploits a mathematical weakness in RSA when the private exponent d is too small relative to the modulus - specifically when d < n^0.25 / 3. In that case, a property of continued fraction approximations allows an attacker to recover d efficiently from the public values e and n alone.

   The attack works because RSA's key relationship e*d ≡ 1 (mod φ(n)) means the fraction e/n is very close to k/d for some small integer k. When d is small enough, the convergents of the continued fraction expansion of e/n include k/d as one of its early terms - making it directly recoverable.

   Verifying the recovered d. The script asserts the decrypted plaintext starts with picoCTF{. If owiener returns a non-None d but the assertion fails, you've recovered a continued-fraction convergent that's mathematically valid for the equation but isn't the real private exponent - retry with a tweaked search bound, or fall back to factoring n if it's small.

   Real-world significance: Developers sometimes choose small values of d to speed up RSA decryption (since modular exponentiation with a smaller exponent is faster). Wiener's attack demonstrates why this is catastrophic. Modern RSA implementations always use random, full-size private exponents. The long_to_bytes function from pycryptodome converts the recovered plaintext integer back into a readable string. For more on RSA attack patterns, see RSA attacks for CTF.

Alternate Solution

Flag

Wiener's attack exploits RSA when d < n^0.25 - always use d larger than the cube root of n.