# 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 ```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 $$ 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 ```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 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 ```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} ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://thr34dr1pp3r.gitbook.io/ctf/wanictf-2024/crypto-many-xor-shift.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.