Clouds picoCTF 2021 Solution

Description

1. Step 1Identify the cipher and its round function

   Observation

   The challenge is called 'Clouds' and the source is a 5-round block cipher built from XOR, bit-reversal, and multiply. That is the Nimbus structure, which means a known cryptanalytic attack on Nimbus, not brute force, is 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 2Use the Delta = 2^63 - 2 differential

   Observation

   The round function applies a bit-reversal, the g function, which destroys most input differences. What survives is a difference whose binary form is a palindrome, such as Delta = 2^63 - 2, shaped 01...10. That passes through bit-reversal unchanged and stays 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, so it produces no consistent output difference after even one round. The pairs give no usable signal and subkey recovery collapses. Only a difference satisfying g(Delta) = Delta survives the round structure intact.

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

   The XOR and addition equivalence this attack leans on, Furman's Lemma 1, holds only when both values are even. Odd inputs break the commutative property with the multiply step, so the output differences no longer match C1 + C2 = Delta * K_odd. That is why the good-pair filter demands both values be even.

   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 3Recover the subkeys round by round and decrypt

   Observation

   Surviving ciphertext pairs satisfy C1 + C2 = Delta * K_odd. Solve that for the final subkey with the extended Euclidean algorithm, then invert each round inward from the ciphertext side to recover all five.

   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 its gcd with 2^64 is 2, not 1, and 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 that factor of 2 by yielding two candidate values for K_odd per round, and undoing the forced low bit doubles that again to four candidate subkeys, which the search prunes using survival counts.

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

   You only ever see final ciphertexts, never intermediate round outputs. Working inward from the ciphertext side lets you invert the last round as soon as you know the final subkey. Starting at round 1 would require intermediate states you cannot observe, so the attack has to 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 about a 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.