Clouds picoCTF 2021 Solution

Description

1. Step 1

   Identify the cipher and its round function

   Observation

   I noticed the challenge was named 'Clouds' and the source showed a 5-round block cipher with XOR, bit-reversal, and multiply operations, which matched the Nimbus cipher structure and indicated that a known cryptanalytic attack on Nimbus, rather than brute force, was the intended path.

   Each of the 5 rounds does: XOR the block with the round subkey, reverse the bits of the result (the g function), then multiply by an odd-forced version of the subkey modulo 2^64. This is the Nimbus cipher. The multiply and bit-reversal are what you exploit.

   Learn more

   Why differential, not brute force. The key is 40 bytes (five 8-byte subkeys), so brute force is hopeless. But Nimbus has a known weakness: a specific input difference propagates through the rounds with high, predictable probability, leaking subkey bits one round at a time. This is textbook differential cryptanalysis, and it is the intended (and essentially only) solution.

2. Step 2

   Use the Delta = 2^63 - 2 differential

   Observation

   I noticed the round function applies a bit-reversal (g function), which destroys most input differences; this suggested I needed a difference whose binary representation is a palindrome, such as Delta = 2^63 - 2 (the form 01...10), so the difference would pass through bit-reversal unchanged and remain exploitable across all five rounds.

   The differential Delta = 2^63 - 2 has the binary form 01...10, which is invariant under bit reversal. For even A and B, A XOR B = Delta if and only if A + B = Delta (Furman's Lemma 1). That gives a one-round iterative characteristic that survives each round with roughly 50% probability. Send chosen-plaintext pairs differing by Delta and keep the pairs whose outputs satisfy the relation.

   python

   python3 - <<'PY'
   from pwn import remote
   
   DELTA = (1 << 63) - 2
   
   io = remote("mercury.picoctf.net", <PORT_FROM_INSTANCE>)
   
   # Send ~64+ chosen-plaintext pairs (p, p ^ DELTA), record ciphertext pairs.
   # Keep "good" pairs where both halves are even and differ correctly:
   #   (a ^ b) % 4 == 2 and a % 2 == 0 and b % 2 == 0
   PY

   Copied!

   What didn't work first

   Tried: Trying a random XOR difference such as 0x01 or 0xFF instead of the specific Delta = 2^63 - 2 palindrome.

   A non-palindromic difference is scrambled by the bit-reversal step (the g function), so it does not produce a consistent output difference after even one round. The pairs yield no usable signal and subkey recovery collapses. Only a difference that satisfies g(Delta) = Delta can survive the round structure intact.

   Tried: Collecting plaintext pairs where one or both values are odd before querying the oracle.

   The XOR/addition equivalence used in this attack (Furman's Lemma 1) only holds when both values are even. Odd inputs break the commutative property with the multiply step, producing output differences that do not match the expected relation C1 + C2 = Delta * K_odd. The good-pair filter requires a % 2 == 0 and b % 2 == 0 precisely to exclude these.

   Learn more

   Why this difference is special. Bit-reversal (the g function) normally scrambles a difference, breaking any characteristic. Delta = 2^63 - 2 is a palindrome in binary, so g(Delta) = Delta: the difference passes through the bit-reversal untouched. Combined with the XOR/addition equivalence for even values, the difference also survives the multiply step often enough to be useful. That is the crack.

3. Step 3

   Recover the subkeys round by round and decrypt

   Observation

   I noticed that surviving ciphertext pairs satisfy the relation C1 + C2 = Delta * K_odd, which meant solving for the final subkey using the extended Euclidean algorithm and then recursively inverting each round inward from the ciphertext side to recover all five subkeys.

   From the good ciphertext pairs, solve C1 + C2 = Delta * K_odd for the final subkey (use the extended Euclidean algorithm, since a plain modular inverse may not exist). Partially decrypt one round, filter candidates by the expected differential counts, and recurse to recover all five subkeys (a DFS over the 4^5 candidate arrangements). Reconstruct the 40-byte key, then decrypt the encrypted flag block.

   python

   python3 - <<'PY'
   # Sketch of the recovery, following Furman's attack:
   # 1. collect good pairs (above)
   # 2. for the last subkey: C1 + C2 == DELTA * K_odd (mod 2^64) -> solve with ext. Euclid
   # 3. invert that round on all pairs, count surviving differentials to confirm
   # 4. recurse for subkeys 4..1 (DFS over candidate arrangements)
   # 5. rebuild key, decrypt the flag block
   PY

   Copied!

   The first plaintext set succeeds with roughly 50% probability; if you drew unlucky differentials, reconnect and rerun with fresh pairs. With all five subkeys recovered, decrypting the flag block is a single inverse-cipher call.

   What didn't work first

   Tried: Solving C1 + C2 = Delta * K_odd with a standard modular inverse (pow(Delta, -1, 2**64)) instead of the extended Euclidean algorithm.

   Delta = 2^63 - 2 is even, so gcd(Delta, 2^64) = 2, not 1. A standard modular inverse does not exist when the value shares a factor with the modulus. Python raises a ValueError. The extended Euclidean algorithm handles the 2-factor correctly by yielding two candidate subkey values per round, which the DFS prunes by checking survival counts.

   Tried: Attempting to recover subkeys starting from the first round rather than the last round.

   You only have access to final ciphertexts, not intermediate round outputs. Working inward from the ciphertext side means you can invert the last round directly once you know the final subkey. Starting from round 1 requires knowing all intermediate states, which are not observable. The attack structure must peel rounds from the outside in.

   Learn more

   The takeaway. Rolling an obscure or home-grown cipher (Nimbus never saw wide review) is exactly how this kind of break happens: a single structural property (a palindromic difference that survives bit-reversal) collapses a 320-bit key to a few thousand guesses. For the broader method see AES for CTF on why peer-reviewed ciphers resist this.

Flag

Clouds implements the Nimbus block cipher. The difference Delta = 2^63 - 2 is a binary palindrome, so it survives the round's bit-reversal and gives a high-probability differential. Collect chosen-plaintext pairs differing by Delta, recover each 8-byte subkey round by round, rebuild the 40-byte key, and decrypt the flag.