Dachshund Attacks picoCTF 2021 Solution

Description

1. Step 1

   Collect e, n, and c

   Observation

   I noticed the server openly prints the public exponent e, modulus n, and ciphertext c when you connect, which are exactly the three values any RSA attack script needs as inputs and must be captured 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 2

   Apply Wiener's Attack

   Observation

   I noticed the challenge description says 'What if d is too small?' and the title references Wiener (a dachshund is a wiener dog), which directly pointed to Wiener's attack, the classic RSA exploit that recovers a small private exponent d using continued fractions 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.

   For a 1024-bit or larger modulus, integer factorization is computationally infeasible - sympy.factorint will hang indefinitely and online tools like factordb will return no factors. Wiener's attack sidesteps factorization entirely by exploiting the continued fraction structure of e/n, recovering d directly 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 below the n^0.25 / 3 bound, not because the inputs are wrong. Reconnecting generates a fresh keypair that may or may not have a small d - the server always uses a vulnerable key in this challenge, so a None result more likely means the e and n values were miscopied (digits dropped or swapped). Double-check that e and n 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.