> For the complete documentation index, see [llms.txt](https://thr34dr1pp3r.gitbook.io/ctf/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://thr34dr1pp3r.gitbook.io/ctf/wanictf-2024/crypto-many-xor-shift.md).

# Crypto - Many Xor Shift

## [Full Implementation](https://github.com/kinasant/THR34DR1PP3R/blob/main/2024/WANICTF/cry-many-xor-shift/cry-many-xor-shift/sol.ipynb)

## Challenge

```python
def encrypt(m):
    state = [int.from_bytes(m[i:i+4]) for i in range(0, len(m), 4)]
    assert len(state) == N

    def xor_shift():
        nonlocal state
        t = state[0] ^ ((state[0] << 11) & WORD_MASK)
        for i in range(N-1):
            state[i] = state[i+1]
        state[-1] = (state[-1] ^ (state[-1] >> 19)) ^ (t ^ (t >> 8))

    for _ in range(M):
        xor_shift()

    return state
```

I couldn't solve this during the CTF, but found the concept interesting.

This challenge uses xor shifts to encrypt the flag. Before proceeding with the writeup, I highly recommend reading [this](https://s3v3ru5.github.io/notes/TWCTFxorandshift), as I use the code as well as the concepts explained there.

## Encryption

The xor\_shift() takes an input state and shifts the state upwards by one and adds a new state. We can express the state shift in the form of matrices.

Let Un and Ln be the left and right shift matrices respectively such that

```python
# copied from https://s3v3ru5.github.io/notes/TWCTFxorandshift
si << a = (Un**a) * tovec(si) # n = si.bit_length()
si >> a = (Ln**a) * tovec(si)
```

If we use GF(2) as our base ring, then we can define xor as addition.

```
ti ^ ri = tovec(ti) + tovec(ri)
ti << a = (Un ** a) * tovec(ti)
ti >> a = (Ln ** a) * tovec(ti)
```

First, let's see what new state is being added&#x20;

```python
t = state[0] ^ ((state[0] << 11) & WORD_MASK)
state[-1] = (state[-1] ^ (state[-1] >> 19)) ^ (t ^ (t >> 8))
```

Let U be the left shift matrix and L be the right shift matrix

Then t can be represented as follows&#x20;

$$
t = s0 + (U^{11} \* s0)\ t = s0\*(U^{11} + I) \quad \ t = s0\*A \ where \  A = (U^{11}+I)
$$

Then we can express the new state as&#x20;

$$
s7  = s6+(L^{19}*s6)+ t+ L^{8}*t \ s7  = s6 \* (L^{19} + I) \ + t*(L^{8} +I ) \ s7 = s6*Y + s0 \* A \*Z \ where  \ Y = L^{19}+I  \ and \  Z = L^{8} + I
$$

The reason for doing this is to express the state in a linear combination of s6 and s0, which makes it easier to design the matrix

We need to construct a matrix such that it takes (s0,s1,s2,s3,s4,s5,s6) and outputs (s1,s2,s3,s4,s5,s6, A\*Z\*s0 + s6\*Y)

For convenience, I add A\*s0 to start of the state so that the matrix multiplication comes out nicely

$$
\begin{pmatrix}N \&N\&A & \dots & N \\
N\&N& I  & \dots & N \\
\vdots & \dots& \dots &\ddots & \vdots \ N  & \dots  & \dots  & \dots & I\ Z & \dots &\dots &\dots &  Y   \\
\end{pmatrix}\_{8\times 8}  \times     \begin{pmatrix}  As0\s0\s1\ \vdots \s6 \ \end {pmatrix} \ =  \begin{pmatrix} As1\s1\ s2\ \vdots \A*Z*s0+ Y\*s6 \end{pmatrix}
$$

We then compare this with the xor\_shift function to check if it works

```python
size=32
Un = gen_left_shift_mat(size)
Ln = gen_right_shift_mat(size)
I = Matrix.identity(GF(2),32)
N = Matrix(GF(2),32)
A = Un^11+I
Y = Ln^19+I
Z = Ln^8 + I
def gmm(dimension):
    t1 = [N,N,A]
    t1+=[N for i in range(dimension-3)]
    block = [[N for _ in range(dimension)] for _ in range(dimension-2)]
    for i in range(6):
        block[i][2+i] = I
    t2 = [Z]+[N for i in range(dimension-2)]+[Y]
    block = [t1]+block+[t2]
    return block_matrix(block)
b=gmm(8)
b1=b^5*ints_2_state(s1,32)
a1=xor_shift(state,5)
a2=state_2_ints(b1,32)
```

```python
a1 ==a2[1:]
#True
```

A variant of this method was most likely used by the authors to encrypt

## Decryption&#x20;

We use the same idea, except we construct a different matrix to switch the input and output state.     To make it easier, we multiply by another matrix first to make it easier to deal with the last element

$$
\begin{pmatrix}
I \&N\&N & \dots & \dots \&N \\
N& \ddots & N  & \dots & \vdots & \vdots  \\
\vdots & \dots& \ddots \&N & \vdots & \vdots  \\
\vdots & \dots &\dots & \ddots & \vdots & \vdots \\
\vdots  & \dots  & \dots  & \dots \&I & N\\
N & \dots &\dots & \dots &-Y & I    \\
\end{pmatrix}\_{7 \times 7}\
\times \begin{pmatrix} s1\s2\s3\s4\s5\s6\A*Z*s0 + Y*s6 \end{pmatrix}
\= \begin{pmatrix} s1\s2\s3\s4\s5\s6\A*Z\*s0  \end{pmatrix}
$$

Code to generate the matrix

```python
def gmm3(dimension):
    block = [[N for _ in range(dimension)] for _ in range(dimension-1)]
    for i in range(6):
        block[i][i] = I
    t2 = [[N for i in range(dimension-2)] + [-Y,I]]
    block+=t2
    return block_matrix(block)
```

$$
\begin{pmatrix}
N & \dots &\dots & \dots &  N & A^{-1} \* Z^{-1}
\ I \&N\&N & \dots & \dots & N \\
N& \ddots & N  & \dots & \dots & \vdots \\
\vdots & \dots& \ddots \&N & \dots & \vdots\\
\vdots & \dots &\dots & \ddots & \dots & \vdots \\
\vdots  & \dots  & \dots  & \dots & I & \vdots\
\end{pmatrix}\_{7 \times 7}\
\times \begin{pmatrix} s1\s2\s3\s4\s5\s6\A*Z*s0  \end{pmatrix}
\= \begin{pmatrix} s0\s1\s2\s3\s4\s5\s6  \end{pmatrix}
$$

Code to generate the matrix&#x20;

```python
def gmm2(dimension):
    block = [[N for _ in range(dimension)] for _ in range(dimension-1)]
    for i in range(6):
        block[i][i] = I
    t2 = [[N for i in range(dimension-2)] + [N,A^-1*Z^-1]]
    t2 = t2 + block
    return block_matrix(t2)
```

Now that we have everything that we need, we can finally decrypt

```python
p1 = gmm2(7)
h1 = gmm3(7)
b2= (p1*h1)^(17005450388330379)*ints_2_state(state,32)
x1=state_2_ints(b2,32)
t1=b''
for i in x1:
    t1+= long_to_bytes(i)
print(t1)
#FLAG{m47r1x_!n_8inary_w0rld}
```