# Embrace the randomness

## Problem

This challenge involves reversing the encryption process to recover the original flag. The encryption uses bitwise operations that depend on randomly generated keys. Specifically:

* The `encrypt` function creates a ciphertext by applying bitwise AND, OR, and NOT operations between the flag and a random key.
* A large number of ciphertexts (6240) are generated for different random keys.
* The goal is to deduce the original flag using the fact that some bytes are missing from the ciphertext due to the encryption process.

```python
import random
from secret import flag


def encrypt(a, b):
    result = bytearray()
    for i in range(len(a)):
        result.append((a[i] & ~(b[i] % 0xff)) | (~a[i] & (b[i] % 0xff)))
    return result


for _ in range(624 * 10):
    key = [random.getrandbits(32) for _ in range(len(flag))]
    ct = encrypt(flag, key)
    print(ct.hex())
```

{% file src="<https://1160714615-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FSQLD7d7YuSCaHXDmYUeJ%2Fuploads%2FzM9m2VXOTc6zfoeyofcV%2Foutput.txt?alt=media&token=daf938ba-60f4-4295-977e-0433ea06c795>" %}
Encrypted Flag
{% endfile %}

## Solution

* **Analyze the Encryption**:
  * Each byte of the ciphertext depends on the corresponding byte of the flag and key.
  * Certain flag bytes will not appear in the ciphertext for any key, due to the specific bitwise operations.
* **Leverage the Missing Byte Property**:
  * For each position in the flag, identify the byte that does not appear in the corresponding position of all ciphertexts.
  * Use this "missing byte" and XOR it with `255` to derive the original flag byte.
* **Implement Flag Recovery**:
  * Parse the ciphertexts from the output file.
  * Iterate through each position in the ciphertexts, collect all seen bytes, and find the missing one.
  * Recover the flag byte by byte using the above approach.
* **Output the Flag**:
  * Decode the recovered flag and print it.

```python
def recover_flag(ciphertexts, length):
    flag = bytearray()
    for i in range(length):
        # Collect all possible bytes for this position
        seen_bytes = set(ct[i] for ct in ciphertexts)
        # Find the missing byte (the one that doesn't appear in the ciphertexts)
        missing_byte = next(b for b in range(256) if b not in seen_bytes)
        # XOR the missing byte with 255 to get the flag byte
        flag.append(missing_byte ^ 255)
    return flag

# Load ciphertexts from output.txt
ciphertexts = []
with open("output.txt", "r") as f:
    for line in f:
        ciphertexts.append(bytearray.fromhex(line.strip()))

# Recover the flag (assuming we know its length)
flag_length = len(ciphertexts[0])  # All ciphertexts are the same length
flag = recover_flag(ciphertexts, flag_length)
print("Recovered flag:", flag.decode())
```