Rating: 5.0
We get a stream cipher, meaning a keystream is created and xored to the flag to get the ciphertext.
Decrypting the ciphertext is equivalent to finding the keystream.
## Understanding the keystream derivation
The keystream derivation works as follows:
- let `ln` be the size of the flag. Generate `ln` linearly independent keys of `ln` bits, denoted `key[i]`.
- for every i, let `fake[i]` be the XOR of keys `key[j]` with `i+1 <= j <= min(i+ln//3, ln)`.
- generate a random keystream `ks` of `ln` bits. Define `public[i] = (fake[i], key[i]) if ks[i] == 1 else (key[i], fake[i])`
- then choose a permutation `pi`, the keystream used to encrypt the flag is `pi(ks)` and public released data is `pi(public)`.
## Retrieving the keystream
To retrieve the keystream, we only have to retrieve the set of different keys (the function to do that is even provided by the challenge description).
Because of how `fake` is created, we know that for the last index, `fake[ln - 1] = 0`.
This enables us to easily find the last key.
We also get a recurrence relation: if we know all keys `key[i+1], ..., key[ln - 1]`, then we can find `key[i]` by computing the `fake[i]` as the challenge does, then search this value in the public data and deduce `key[i]`.
Once we get all `key` values we can decrypt the flag.
## Code
Here is the full code, there are additional details in the full writeup.
```python
with open("output.txt", "r") as f:
c = bytes.fromhex(f.readline())
c = bytes_to_bits(c)
public = eval(f.read())
ln = len(public)
key = [0] * ln
keystream = [0] * ln
for i in range(ln-1,-1,-1):
fake = 0
for j in range(ln // 3):
if i + j + 1 >= ln:
break
fake ^= key[i + j + 1]
for k in range(ln):
if fake in public[k]:
if fake == public[k][0]:
keystream[k] = 1
key[i] = public[k][1]
else:
keystream[k] = 0
key[i] = public[k][0]
public[k] = [-1, -1]
break
flag = bits_to_bytes(xor(keystream, c))
print(flag)
```
