Dachshund Attacks picoCTF 2021 Solution

Description

1. Step 1Collect e, n, and c

   Observation

   On connecting, the server prints the public exponent e, the modulus n, and the ciphertext c. Those are exactly the three inputs any RSA attack script needs, so capture them before the connection closes.

   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

   Observation

   The description asks what happens if d is too small, and the title puns on Wiener, since a dachshund is a wiener dog. That is Wiener's attack, which recovers a small private exponent d from the continued fraction expansion of e/n.

   Wiener's attack recovers the private exponent d when d < n^0.25 / 3. 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!

   Expected output

   picoCTF{proving_wiener_...}

   What didn't work first

   Tried: Try factoring n directly with sympy.factorint or an online factorization tool to recover p and q.

   At 1024 bits or more, factoring the modulus is infeasible: sympy.factorint hangs indefinitely and factordb returns nothing. Wiener's attack skips factorization altogether, exploiting the continued fraction structure of e/n to recover d without ever finding p or q.

   Tried: Run owiener.attack(e, n) and assume None means the wrong e and n values were used, so reconnect and try a different session.

   owiener returns None when d is not under the n^0.25 / 3 bound, not because your inputs are malformed. Reconnecting draws a fresh keypair, but this server always uses a vulnerable key, so None much more likely means e or n was miscopied, with digits dropped or swapped. Check both were pasted in full before retrying.

   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.

Flag

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