It's Not My Fault 1 picoCTF 2021 Solution

Description

1. Step 1

   Solve the MD5 proof-of-work

   Observation

   I noticed the server immediately presents a challenge requiring a string whose MD5 hash ends with a specific suffix before sending any cryptographic data, which indicated a standard anti-automation gate that must be brute-forced by appending characters to the given prefix until a matching hash is found.

   The server opens with a proof-of-work gate: find a string that starts with a given 5-character prefix and whose MD5 hash ends with a given 6-hex-character suffix. This is a lightweight anti-automation measure. Brute-force it by appending random bytes to the prefix and hashing until you match.

   python

   python3 - <<'EOF'
   import hashlib, itertools, string, sys
   
   PREFIX = "XXXXX"   # replace with the 5-char prefix the server sends
   SUFFIX = "yyyyyy"  # replace with the 6-hex suffix the server sends
   
   chars = string.ascii_letters + string.digits
   for length in range(1, 8):
       for combo in itertools.product(chars, repeat=length):
           candidate = PREFIX + "".join(combo)
           if hashlib.md5(candidate.encode()).hexdigest().endswith(SUFFIX):
               print(candidate)
               sys.exit(0)
   EOF

   Copied!

   What didn't work first

   Tried: Trying to skip the PoW by just sending a blank line or the prefix alone to see if the server accepts it.

   The server parses your submission and compares the MD5 hash directly. Any string that does not end with the required 6-hex suffix is rejected and the connection is closed. You must actually brute-force the hash - there is no bypass.

   Tried: Using the prefix itself as the candidate answer without appending extra characters.

   The PoW contract requires the submitted string to start with the 5-char prefix AND have an MD5 ending with the 6-hex suffix. The naked prefix almost certainly does not satisfy the hash constraint. The loop must iterate over appended suffixes until a match is found.

   Learn more

   Why a proof-of-work gate? The challenge server will perform expensive computation once you submit p+q. The PoW ensures that only clients willing to spend a fraction of a CPU-second can even start, throttling automated hammering of the service.

   The expected search space is 256^3 candidates on average (the last 3 hex nibbles of the suffix constrain 1.5 bytes), so this completes in milliseconds on any modern machine.

2. Step 2

   Understand the RSA-CRT small d_p vulnerability

   Observation

   I noticed the challenge description explicitly states the attack is NOT a fault attack despite the RSA-CRT context, which suggested the vulnerability must lie in a parameter size weakness, specifically a small d_p exponent that makes the CRT private component brute-forceable via Fermat's little theorem.

   After the PoW, the server sends you a public modulus n and public exponent e. Behind the scenes, the private key was generated using the Chinese Remainder Theorem optimisation: the private exponent d was split into d_p = d mod (p-1) and d_q = d mod (q-1). The server deliberately chose d_p to be at most 20 bits, i.e. between 1 and 1,048,576. That tiny range is the crack in the armor.

   Learn more

   What is d_p? In standard RSA, decryption computes m = c^d mod n. Because n is huge, this is slow. The CRT trick splits the computation: compute c^(d_p) mod p and c^(d_q) mod q separately, then recombine with the CRT. Here d_p satisfies e * d_p ≡ 1 (mod p-1), i.e. d_p is the modular inverse of e modulo p-1.

   Why is small d_p fatal? By Fermat's Little Theorem, for any message m coprime to p: m^(p-1) ≡ 1 (mod p). Multiplying exponents, m^(e*d_p) ≡ m (mod p). Therefore m^(e*d_p) - m is divisible by p. If you compute gcd(m^(e*d_p) - m, n) for a random m, you will get p when your guess for d_p is correct, and 1 (almost always) when it is wrong.

   With d_p bounded by 2^20 = 1,048,576, you only need to try about a million candidates. Each candidate requires one modular exponentiation (m^(e*d_p) mod n) and one GCD, both of which are fast. In Python with multiprocessing this runs in under a minute; optimised with PyPy or C it finishes in seconds.

3. Step 3

   Brute-force d_p to factor n

   Observation

   I noticed that with d_p bounded to at most 20 bits (at most 1,048,576 candidates), each candidate can be tested in O(1) using gcd(pow(m, e*dp, n) - m, n), which suggested a parallelised brute-force loop would factor n well within the 15-minute server window.

   Pick a random m (any integer in 2..n-2 works). For each candidate dp from 1 to 2^20, compute gcd(pow(m, e*dp, n) - m, n). When this GCD is strictly between 1 and n, you have found p. Parallelise across CPU cores to finish well inside the 15-minute window.

   python

   python3 - <<'EOF'
   from math import gcd
   from multiprocessing import Pool, cpu_count
   
   n = 0   # paste n from the server
   e = 0   # paste e from the server
   m = 2   # any fixed base works; 2 is fine
   
   def try_dp(dp):
       val = pow(m, e * dp, n) - m
       g = gcd(val, n)
       if 1 < g < n:
           return g
       return None
   
   if __name__ == "__main__":
       with Pool(cpu_count()) as pool:
           for result in pool.imap_unordered(try_dp, range(1, 2**20), chunksize=512):
               if result:
                   p = result
                   q = n // p
                   print(f"p = {p}")
                   print(f"q = {q}")
                   print(f"p + q = {p + q}")
                   pool.terminate()
                   break
   EOF

   Copied!

   What didn't work first

   Tried: Trying gcd(pow(m, e*dp, n), n) instead of gcd(pow(m, e*dp, n) - m, n) for each candidate.

   Without the subtraction of m, the GCD almost always returns 1 regardless of whether dp is correct, because m^(e*dp) mod n is not itself divisible by p. The Fermat identity requires m^(e*dp) - m = m*(m^(e*dp - 1) - 1) to be divisible by p; dropping the minus-m term removes the factor that makes the GCD non-trivial.

   Tried: Choosing an m that is a small multiple of 2 or a prime like 3, hoping a special base converges faster.

   The base m only needs to avoid being divisible by p or q, which any small integer satisfies with overwhelming probability. Using m=2 is optimal because the loop runtime depends on the d_p range size (2^20), not the choice of base. A different base adds no speed benefit and could theoretically fail if it happened to share a factor with n.

   Learn more

   Why does m = 2 always work? The GCD formula relies on gcd(m^(e*dp) - m, n) = p, which holds as long as m is not a multiple of p or q. Since p and q are large random primes, the probability that m = 2 is divisible by either is astronomically small. In practice, m = 2 works for every instance of this challenge.

   Parallelism. Python's multiprocessing spawns one worker per CPU core. Each worker tests a disjoint slice of the d_p range. The winning worker reports back and the pool is terminated immediately, so you don't wait for the remaining workers to finish.

4. Step 4

   Submit p+q and receive the flag

   Observation

   I noticed the server prompt explicitly asks for p+q rather than either prime individually, and once the brute-force script outputs p and q, their sum can be computed in one arithmetic step and pasted into the waiting nc session to satisfy the server's verification.

   Once you have p and q, compute their sum and send it back to the server. The server verifies that p*q = n and that your p+q matches, then calls get_flag() and prints the flag.

   bash

   # After running the brute-force script, paste p+q into the waiting nc session

   Copied!

   bash

   # The server will respond with the flag

   Copied!

   Learn more

   Why ask for p+q instead of p or q separately? Asking for the sum prevents a lucky guess from splitting the factor: an attacker who only knows p+q cannot easily recover p and q individually (it would require solving a quadratic). The server can still verify correctness because it knows n = p*q and can check whether the submitted sum satisfies (sum)^2 - 4n = (p-q)^2, a perfect square.

Flag

The flag text itself is the punchline: '17'5 n07 f4ul7 4774ck' reads as 'it's not fault attack', matching the challenge title. The real attack is small-d_p RSA-CRT bruteforce, not hardware fault injection.