Category: Crypto
Challenge: The Shortest Crypto Chal

This challenge was a classic example of how a cryptography problem can actually be an algorithmic puzzle in disguise. The core task was not to break the AES encryption itself, but to find the correct key by solving an underlying mathematical equation efficiently.

---

Challenge Overview

We were presented with a small Python snippet that defined the entire problem:

from Crypto.Cipher import AES
from hashlib import md5
from secret import a,b,c,d, FLAG

assert a**4 + b**4 == c**4 + d**4 + 17 and max(a,b,c,d) < 2e4 and AES.new( f"{a*b*c*d}".zfill(16).encode() , AES.MODE_ECB).encrypt(FLAG).hex() == "41593455378fed8c3bd344827a193bde7ec2044a3f7a3ca6fb77448e9de55155"

The goal is to find four integers a, b, c, d that satisfy the diophantine equation \(a^4 + b^4 = c^4 + d^4 + 17\), with each integer being less than 20,000. Once found, their product is used to generate a 16-byte AES key to decrypt the flag.

---

The Naive Approach: Brute-Force (and Why It Fails)

The most straightforward idea is to check every possible combination of the four numbers:

# Infeasible Brute-Force
for a in range(1, 20000):
    for b in range(1, 20000):
        for c in range(1, 20000):
            for d in range(1, 20000):
                if a**4 + b**4 == c**4 + d**4 + 17:
                    # Solution found!

The complexity of this approach is \(O(N^4)\). With \(N=20000\), this leads to approximately \(20000^4 = 1.6 \times 10^{17}\) iterations. This would take thousands of years to run on a standard computer, so it’s not a viable path.

---

The Efficient Strategy: Meet-in-the-Middle

A much better approach is the meet-in-the-middle algorithm. We can rearrange the equation to isolate pairs of variables on each side:

\[a^4 + b^4 - 17 = c^4 + d^4\]

This allows us to split the problem into two halves:

1. Part 1: Calculate all possible values for the right side, \(c^4 + d^4\).
2. Part 2: Calculate all possible values for the left side, \(a^4 + b^4 - 17\).
3. Find the Match: Find a value that is common to both sets.

Implementation 1: The Memory Hog

A common way to implement this is to store the results of Part 1 in a hash map (a Python dictionary) and then look up results from Part 2.

# Memory-intensive approach
sums_cd = {}
for c in range(1, 20000):
    for d in range(1, c + 1):
        sums_cd[c**4 + d**4] = (c, d) # Store sum -> (c, d)

# Search for a match
for a in range(1, 20000):
    for b in range(1, a + 1):
        target = a**4 + b**4 - 17
        if target in sums_cd:
            # Solution found

While algorithmically sound (\(O(N^2)\)), this method consumes an enormous amount of RAM. The sums_cd dictionary would need to store about \(20000^2 / 2 \approx 200\) million entries, leading to memory exhaustion. Surprisingly, this approach failed even on my PC with 32GB of RAM.

Implementation 2: The Winning Solution (Sort and Search)

To overcome the memory issue, we can replace the dictionary with a sorted list and use a binary search. This is significantly more memory-efficient.

1. Generate a List: Create a list of tuples (value, c, d) for all \(c^4 + d^4\) sums.
2. Sort the List: Sort this list based on value. This is the crucial step that enables a fast search without high memory overhead.
3. Iterate and Search: Loop through a and b, calculate the target, and use a binary search (Python’s bisect module is perfect for this) to find the target in the sorted list.

This reduces the time complexity to \(O(N^2 \log N)\) (for sorting and searching) and the space complexity to \(O(N^2)\), which is manageable.

---

Final Script and Flag Recovery

The following script implements the sort-and-search strategy to find the numbers and decrypt the flag.

import bisect
from Crypto.Cipher import AES

def solve_challenge():
    N = 20000
    
    # Generate a list of (value, c, d) tuples
    print("Building list for c^4 + d^4...")
    sums_cd_list = []
    for c in range(1, N):
        for d in range(1, c + 1):
            sums_cd_list.append((c**4 + d**4, c, d))

    # Sort the list by the calculated value
    print("Sorting list... (This will take a moment)")
    sums_cd_list.sort()
    cd_values = [item[0] for item in sums_cd_list]

    # Iterate through a, b and use binary search to find a match
    print("Searching for solution...")
    solution_found = None
    for a in range(1, N):
        for b in range(1, a + 1):
            target = a**4 + b**4 - 17
            i = bisect.bisect_left(cd_values, target)
            if i < len(cd_values) and cd_values[i] == target:
                _val, c, d = sums_cd_list[i]
                
                # The key must be <= 16 chars long. This is a final check.
                if len(str(a * b * c * d)) <= 16:
                    print(f"\nSolution found! a={a}, b={b}, c={c}, d={d}")
                    solution_found = (a, b, c, d)
                    break
        if solution_found:
            break

    if not solution_found:
        print("\nCould not find a solution.")
        return

    # Decrypt the flag
    a, b, c, d = solution_found
    product = a * b * c * d
    key = f"{product}".zfill(16).encode()
    print(f"Derived AES Key: {key}")

    ciphertext_hex = "41593455378fed8c3bd344827a193bde7ec2044a3f7a3ca6fb77448e9de55155"
    ciphertext = bytes.fromhex(ciphertext_hex)
    
    cipher = AES.new(key, AES.MODE_ECB)
    decrypted_flag = cipher.decrypt(ciphertext)
    
    # Clean up padding and print the flag
    flag = decrypted_flag.decode('utf-8').strip()
    print(f"\nFLAG: {flag}")


if __name__ == '__main__':
    solve_challenge()

Running this script successfully finds the integers, derives the key, and decrypts the ciphertext to reveal the flag. Keep in mind, I still had to close absolutely every unnecessary process on my PC to get enough memory to run this.