It's Not My Fault 1 picoCTF 2021 Solution

Description

1. Step 1Solve the MD5 proof-of-work

   Observation

   Before sending any cryptographic data, the server demands a string whose MD5 ends with a specific suffix. That is a standard anti-automation gate: append characters to the given prefix until the hash matches.

   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 proof-of-work wants a string that starts with the 5-character prefix and whose MD5 ends with the 6-hex suffix. The bare prefix almost certainly fails the hash constraint, so the loop has to try appended suffixes until one matches.

   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.

   A 6-hex-character suffix pins 24 bits, so on average you hash about 2^24 (16.7 million) candidates before one matches. That is well under a second in C and only a handful of seconds in pure Python, which is exactly the size of throttle the gate is aiming for.

2. Step 2Understand the RSA-CRT small d_p vulnerability

   Observation

   The description says outright that this is not a fault attack, despite the RSA-CRT setting. So the weakness is in a parameter size: a small d_p exponent, which makes the CRT private component brute-forceable through 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. somewhere below 2^20 = 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 3Brute-force d_p to factor n

   Observation

   With d_p bounded to 20 bits, there are at most 1,048,576 candidates, and each tests in constant time via gcd(pow(m, e*dp, n) - m, n). A parallelized brute-force loop factors n well inside the 15-minute server window.

   Pick a random m (any integer in 2..n-2 works). For each candidate dp below 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 subtracting m, the GCD returns 1 whether or not dp is correct, because m^(e*dp) mod n is not itself divisible by p. The Fermat identity needs m^(e*dp) - m to be divisible by p, and dropping the minus-m term removes the very 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 has to avoid being divisible by p or q, which any small integer manages with overwhelming probability. m=2 is the natural pick, because the loop's runtime depends on the size of the d_p range, not on the base. Another base buys no speed and could in principle 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 4Submit p+q and receive the flag

   Observation

   The prompt asks for p+q rather than either prime on its own. Once the brute force outputs p and q, one addition gives the answer to paste into the waiting nc session.

   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? The sum is not a protective measure: anyone holding n and p+q recovers the primes immediately, since p and q are the roots of x^2 - (p+q)x + n = 0. It is simply a compact single number that proves you factored n, and one the server can check without you sending two values: it knows n = p*q, so it verifies that (sum)^2 - 4n is a perfect square and that the resulting roots multiply back to n.

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.