Crypto - Many Xor Shift

Memories of long long ago. - KowerKoint

Full Implementation

Challenge

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, 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

# 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

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

$$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

$$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

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)

a1 ==a2[1:]
#True

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

Decryption

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

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

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

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}