This is a similar challenge than Alkaloid Stream but with a harder to reverse key derivation.
More details are in the full writeup, but this summary is enough to understand the solution.
## Understanding the key 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 <= ln - ln//3`, let `fake[i]` be the XOR of `ln//3` randomly chosen different keys `key[j]` with `i+1 <= j <= 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)`.
Only lines 2 changes from the previous Alkaloid cipher.
## Retrieving the keystream
This time we don't have an explicit recurrence relation where we can deduce the `fake` values.
However we know that `fake` values are linear combinations of other keys, while `key` values are not (they are linearly independent).Thus we still have some kind of recurrence relation: if we know `key[i+1], ..., key[ln - 1]`, then we can find `fake` values that are a linear combination of those elements.We also know that `fake[i]` is one such element, so we will learn at least one new key on this round.
The question now is to understand how we can state if some element `v` is a linear combination of the known keys.To do so, I put all keys in a matrix of GF(2). This is a matrix of size `k * ln` where `k` is the number of known keys.Because keys are linearly independent and `k < ln`, the rank of this matrix is k.
Then I add a new row with the last row being `v`. I now have a matrix of size `(k+1) * ln`.If `v` is a linear combination of the keys, then my matrix will still have rank `k`.Otherwise they are linearly independent and so the matrix will have rank `k+1`.
The following code evaluates the rank of a GF(2) matrix (borrowed from [Stackoverflow](https://stackoverflow.com/questions/56856378/fast-computation-of-matrix-rank-over-gf2)):```pythondef gf2_rank(rows):    """    Find rank of a matrix over GF2.
    The rows of the matrix are given as nonnegative integers, thought    of as bit-strings.
    This function modifies the input list. Use gf2_rank(rows.copy())    instead of gf2_rank(rows) to avoid modifying rows.    """    rank = 0    while rows:        pivot_row = rows.pop()        if pivot_row:            rank += 1            lsb = pivot_row & -pivot_row            for index, row in enumerate(rows):                if row & lsb:                    rows[index] = row ^ pivot_row    return rank```
Given this function I can say if some value is a linear combination of the known keys:```pythondef is_linear_combination(keys, test_value):    rows = keys.copy()    rows.append(test_value)    n = len(rows)    return gf2_rank(rows) < n```
## Final exploit
```pythonwith 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] * lnkeystream = [0] * lnfor 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)```
It takes 5 min or so to run.