De1CTF 2019 Writeup === It has been a very long time that I've compiled a writeup. This time I have played on my own as _Black Bauhinia_. Let me write on some particular interesting ideas that I have learnt in the challenges. Bear with me if you find this writeup _too_ math-intensive. The solution scripts will be committed to [my Github repository](https://github.com/samueltangz/ctf-archive) sooner or later, after I've managed to prettify them. ## Babylfsr (Crypto, 338 points) This is an easy challenge. However I'll still document this as, surprisingly, I have never been able to play with LFSR before. ### Challenge Summary To summarize, 504 bits generated from the LFSR is given. It is also known that the LFSR is 256 bits long. The goal is to find the mask and the initial states that is stay hidden from the miserable players. ### Solution It took me quite a while to summarize what I should do to obtain the initial states of the LFSR (_See how rusty I am when dealing with them..._). In general, we need these conditions to be satisfied: 1. If we are able to obtain _n_ consecutive bits from the LFSR with a known mask, we could then obtain the prior states. 2. If we are given _2n_ consecutive bits from the LFSR, we could obtain the mask by solving a system of linear equations (in the binary field). Now we are missing the last byte of the puzzle -- I am 8 bits short from getting the mask. After a long thought, I knew I could simply exhaust 8 bits and append to the given state. After all, we have 256 possible masks and thus 256 possible initial states. ## Obscured (Crypto, 500 points) :::info **Note:** In this challenge, $+$ means $\oplus$, the exclusive OR operator. ::: ### Challenge Summary In the challenge, we are given an cipher that encrypts a message $A_0, B_0, C_0, D_0$ to a ciphertext $A_6, B_6, C_6, D_6$: $$ \begin{cases}\begin{matrix} A_{i+1} & = & A_i & + & B_i & & & & & + & S_i \\ B_{i+1} & = & A_i & + & B_i & & & + & D_i & + & S_i \\ C_{i+1} & = & A_i & & & + & C_i & + & D_i & & \\ D_{i+1} & = & & & & & C_i & + & D_i & + & S_i \end{matrix}\end{cases}\dots\dots(1), $$ where $S_i := \text{S}(A_i + C_i)$ with $\text{S}$ being a black-box function. Given a ciphertext, recover the plaintext with the use of the encryption oracle within 20 queries. ### Pointer This challenge is more or less equivalent to [this problem](https://nsucrypto.nsu.ru/archive/2017/round/2/task/2#data) from NSUCRYPTO, with a simple transformation. If you are satisfied with the 18-query solution, please check out the solution in given by NSUCRYPTO 2017. I am presenting a solution that uses 7 queries. ### Solution #### Part I: A transformation that makes our lifes easier It turns out that I have the same transformation as the solution from NSUCRYPTO: $$ \begin{cases}\begin{matrix} W_i & = & & & B_i & & & + & D_i & & \\  X_i & = & A_i & + & B_i & + & C_i & & & & \\  Y_i & = & A_i & & & + & C_i & & & & \\  Z_i & = & & & B_i & + & C_i & + & D_i & + & S_i \end{matrix}\end{cases} \dots\dots (2). $$ Why is that? Combining with $(1)$, the iteration is much simpler: $$ \begin{cases}\begin{aligned} W_{i+1} &= X_i \\ X_{i+1} &= Y_i \\ Y_{i+1} &= Z_i \\ Z_{i+1} &= W_i + \text{S}(Z_i) \end{aligned}\end{cases}\dots\dots(3). $$ :::info Not every transformation can be made in such a simpler way. $W, X, Y, Z$ are carefully picked. My approach was to observe how $A_i + C_i$ will iterate: * $A_{i+1} + C_{i+1} = B_i + C_i + D_i + S_i$, * $B_{i+1} + C_{i+1} + D_{i+1} = B_i + D_i$, * $B_{i+1} + D_{i+1} = A_i + B_i + C_i$, * $A_{i+1} + B_{i+1} + C_{i+1} = A_i + C_i$, and it completes a cycle of length 4 if we drop $S_i$. ::: Define a transformation function $\mathcal{F}: \mathbb{Z}_{2^{32}}^4\rightarrow\mathbb{Z}_{2^{32}}^4$ by: $$ \mathcal{F}(A, B, C, D) := (B+C+D, B+D, A+B+C, A+C). $$ Immediately we have $$ \mathcal{F}^{-1}(W, X, Y, Z) = (W+X+Z, Y+Z, W+X, X+Y+Z). $$ According to $(2)$, this shows that $(W_{i-1}, X_{i-1}, Y_{i-1}, Z_{i-1}) = \mathcal{F}(A_i, B_i, C_i, D_i)$. We call $(W_{-1}, X_{-1}, Y_{-1}, Z_{-1})$ the _transformed plaintext_ and $(W_5, X_5, Y_5, Z_5)$ the _transformed ciphertext_. If we define a sequence $t_0, t_1, ...$ by * Base cases: $t_0 = W_{-1}, t_1 = X_{-1}, t_2 = Y_{-1}, t_3 = Z_{-1}$, * Transition: $t_{i+4} = t_i + \text{S}(t_{i+3})\dots\dots(4)$. We have $(t_6, t_7, t_8, t_9) = (W_5, X_5, Y_5, Z_5)$ being the transformed ciphertext. This means that we could encrypt $(t_0, t_1, t_2, t_3)$ into $(t_6, t_7, t_8, t_9)$ in the transformed space. :::success **Meaning** If we are given the ciphertext $\overline{A_6}, \overline{B_6}, \overline{C_6}, \overline{D_6}$, we could obtain $\overline{W_5}, \overline{X_5}, \overline{Y_5}, \overline{Z_5}$. The goal is to compute $\overline{W_{-1}}, \overline{X_{-1}}, \overline{Y_{-1}}, \overline{Z_{-1}}$, that could be transformed inversely to the plaintext. ::: #### Part II: Inverse iterating the ciphertext - Substitution for the win During the game, I was thinking if it is possible for us to obtain $t_i$ from $t_{i+1}, t_{i+2}, t_{i+3}, t_{i+4}$ -- which means that we could "decrypt" the message by one round (out of six). Turns out it is a solid **yes**! To achieve this, we must realize that the current blocker is the black-box function $\text{S}$. We could not find $\text{S}(x)$ for an arbitrarily given $x$ _easily_... Or could we? :::info Recall on how $t_i$ is defined... and that the plaintext $(t_0, t_1, t_2, t_3)$ would be encrypted into the ciphertext $(t_6, t_7, t_8, t_9)$. In this section, we assume that we are **in control of the plaintext** and **have knowledge on the ciphertext**. ::: **First substitution.** Let $u_0 = u_1 = u_2 = u_3 = 0$ and $u_{i+4} = u_i + \text{S}(u_{i+3})$. We have the equations below: > $u_4 = \text{S}(0)$, > $u_5 = \text{S}(u_4)$, > $u_6 = \text{S}(u_5)$, > $u_7 = \text{S}(u_6)$, > $u_8 = u_4 + \text{S}(u_7)$, > $u_9 = u_5 + \text{S}(u_8)$. The fourth equation is particular interesting: $\text{S}(u_6) = u_7$. Since $u_6$ and $u_7$ is known, we knew a pair of $(x, y)$ with $S(x) = y$. Unfortunately we couldn't control what $x$ is. Yet, we can make use of this to make this happen. :::info **A bit of thinking.** We need to guess $v_0, v_1, v_2, v_3$ for the second substitution smartly. Is it possible to exploit the fact $\text{S}(u_6) = u_7$ as much as possible? For example, as $v_4 = v_0 + \text{S}(v_3)$, we could make $v_0 = u_7$ and $v_3 = u_6$, thus $v_4 = 0$. But then $v_5 = v_1 + \text{S}(v_4)$. It would be better if $v_4 = u_6$. Let's make $v_0 = u_6 + u_7$ instead of $v_0 = u_7$. We then have $v_5 = v_1 + \text{S}(v_4) = v_1 + \text{S}(u_6) = v_1 + u_7$. What's the use? On the next equation, $v_6 = v_2 + \text{S}(v_5) = v_2 + \text{S}(v_1 + u_7)$. Note that we have control for $v_1$ and $v_2$. Let's see what we have by substituting $v_1 = u_7 + x$ and $v_2 = 0$... ::: **Second substitution.** Let $v_0 = u_6 + u_7, v_1 = u_7 + x, v_2 = 0, v_3 = u_6$ and $v_{i+4} = v_i + \text{S}(v_{i+3})$. Here $x$ is an arbitrary element, and we have $\text{S}(x) = v_6$. We could compute $\text{S}(x)$ for given arbitrary $x$ now! Therefore, in such a way, we could decrypt the ciphertext with 7 oracle calls, one for knowing a pair of $\text{S}(x)=y$ and six for inverse iterating. ## Mini Purε (Crypto, 869 points) :::danger **Why?** I bet you are searching for solutions for _Mini Purε Plus_ in De1CTF 2020. Me too. ::: :::info **Note:** $+$ is once again the exclusive OR operator as we are talking under $\text{GF}(2^{24})$. ::: First of all, I could not believe that I can be one of the four teams solving the challenge. ### Challenge Summary Under $\text{GF}(2^{24})$, define $$ \begin{cases}\begin{aligned} L_{i+1} &= R_i \\ R_{i+1} &= L_i + (K_i + R_i)^3. \end{aligned}\end{cases} $$ The plaintext $(L_0, R_0)$ would be encrypted into $(L_6, R_6)$, i.e., 6 rounds. The primary goal is to compute $(K_0, K_1, ..., K_5)$, where each of the $K_i$'s has about 16 bit of entropy. There is an encryption oracle and we can encrypt approximately 3000 messages. ### Solution in a Simpler Setting :::info I guess it will be too cumbersome to explain it in a 6-round setting, so let me explain my solution in a 3-round setting instead. ::: First define $x_0 = L_0, x_1 = R_0$ and $x_{i+2} = x_i + (K_i + x_{i+1})^3$. This implies that $(x_0, x_1)$ is encrypting into $(x_3, x_4)$ (_Remember that we are in a 3-round game_). Let's write the transition explicitly: #### From $x_0, x_1$ and beyond > $\begin{aligned} > x_2 &= x_0 + (K_0 + x_1)^3 \\ > &= x_0 + K_0^3 + K_0^2 x_1 + K_0 x_1^2 + x_1^3 \\ > x_3 &= x_1 + (K_1 + x_2)^3 \\ > &= x_1 + (K_1 + x_0 + K_0^3 + K_0^2 x_1 + K_0 x_1^2 + x_1^3)^3 \\ > &= x_1^9 + x_1^8K_0 + x_1K_0^8 + K_0^9 + x_0x_1^6 + x_0x_1^4K_0^2 + x_0x_1^2K_0^4 + \dots (╯‵□′)╯︵┴─┴ > \end{aligned}$ :::danger **Question:** Wait, no! You are wrong! $(x + y)^3$ should be $x^3 + 3x^2y + 3xy^2 + 3y^3$! You are correct... but we are talking on $\text{GF}(2^{24})$, where $3 = 1+1+1 = 1$. ::: It would be very painful to express $x_4$ in terms of $x_0$ and $x_1$. But as we know $x_3$ and $x_4$, can we find $K_0, K_1, K_2$ via a meet-in-the-middle approach? #### From $x_4, x_3$ and within > $\begin{aligned} > x_2 &= x_4 + (K_2 + x_3)^3 \\ > &= x_4 + K_2^3 + K_2^2 x_3 + K_2 x_3^2 + x_3^3 \\ > x_1 &= x_3 + (K_1 + x_2)^3 \\ > &= \dots > \end{aligned}$ From the two ends, we knew that $$ \begin{aligned} x_0 + K_0^3 + K_0^2 x_1 + K_0 x_1^2 + x_1^3 &= x_2 \\ &= x_4 + K_2^3 + K_2^2 x_3 + K_2 x_3^2 + x_3^3, \end{aligned} $$ and end up having $$ x_0 + K_0^3 + K_0^2 x_1 + K_0 x_1^2 + x_1^3 + x_4 + K_2^3 + K_2^2 x_3 + K_2 x_3^2 + x_3^3 = 0 \dots\dots(5). $$ As I am very lazy, I would need about 10 plaintext-ciphertext pairs to find $K_0$ and $K_2$ by transforming it into a system of linear equations. How? #### The system of linear equation Suppose that we have ten plaintext-ciphertext pairs, given by $$ (x_{0,0}, x_{0,1}, x_{0,3}, x_{0,4}), (x_{1,0}, x_{1,1}, x_{1,3}, x_{1,4}), \dots, (x_{9,0}, x_{9,1}, x_{9,3}, x_{9,4}). $$ Define the following matrix: $$ A := \begin{bmatrix} x_{0,0} & 1 & x_{0,1} & x_{0,1}^2 & x_{0,1}^3 & x_{0,4} & 1 & x_{0,3} & x_{0,3}^2 & x_{0,3}^3 \\ x_{1,0} & 1 & x_{1,1} & x_{1,1}^2 & x_{1,1}^3 & x_{1,4} & 1 & x_{1,3} & x_{1,3}^2 & x_{1,3}^3 \\ &&&&& \vdots &&&& \\ x_{9,0} & 1 & x_{9,1} & x_{9,1}^2 & x_{9,1}^3 & x_{9,4} & 1 & x_{9,3} & x_{9,3}^2 & x_{9,3}^3 \end{bmatrix}. $$ Suppose that $A'$ is the reduced row echelon form for $A$, then you should be able to find $K_0$ and $K_2$ on columns 4 and 9 (one-indexed). It is easy to find $K_1$ afterwards. ### Expanding the Idea to Six Rounds In short, the challenge could be solved by the following steps in a 6-round setting: 1. Use meet-in-the-middle approach to figure out the two equations of $x_3$ (in terms of $x_0$ and $x_1$, and in terms of $x_6$ and $x_7$). 2. Collect 200 plaintext-ciphertext pair. 3. Plug $x_0, x_1, x_6$ and $x_7$ by the plaintext-ciphertext pairs into the equations. 4. Solve for $k_0, k_1, \dots, k_5.$ 5. Profit! I encrypted about 200 messages to find the $k$'s. ### The Intended Solution I had a short chat with the author in Telegram afterwards. He said that the intended solution is [interpolation attack](https://en.wikipedia.org/wiki/Interpolation_attack), which is new to me. I should have looked into that soon... ## The Last Words For sure I have went into numerous dead-ends to come up with the correct solution. Yet, the idea is also valuable and I think I shall document it someday. Probably after DEFCON finals. ###### tags: `CTF`, `Writeup`
Last changed by  
 
Mystiz
477

Read more

TokyoWesterns CTF 6th 2020 Writeup

urlcheck v1 (Web, 98 points) Solved by Ozetta. Objective: SSRF http://127.0.0.1/admin-status The input needs to fulfil the pattern '\A(\d+)\.(\d+)\.(\d+)\.(\d+)\Z' and the first octet cannot be 0 or 127, and some other patterns for internal IP addresses. For some reason, int("0177") is still 177 instead of 127 in Python, so we can use http://0177.0.0.1/admin-status urlcheck v2 (Web, 128 points) Solved by Ozetta. Objective: SSRF http://localhost/admin-status

9/23/2020
Google CTF 2020: Oracle

I was teamed-up with Black Bauhinia on Google CTF this time. I have solved 7 challenges alone and 3 challenges with my teammates. In particular, Oracle is a crypto challenge with 13 solves. It has got me spending 12 hours. All in all, it was a great experience in terms of learning, but my liver hurts. This piece of writeup may be very computation intensive, just because I would like to make everything clear. Challenge Summary There are two parts of the challenges. In the first part, we are required to recover an internal state for AEGIS-128L given the encryption oracle. For the second part, we are required to forge a ciphertext given an error oracle from decryption. Solution Part I: A brief summary for the state in AEGIS-128L AEGIS-128L has an internal state that is initially computed solely by the key and the IV. It is of 128 bytes, broken into eight 16-byte blocks. Let's $S_i$ is updated to $S_{i+1}$ given 32-byte payload $M$. Let's define $S_i = (s_{i, 0}, s_{i, 1}, ..., s_{i, 7})$ and $M = (m_0, m_1)$. We have:

9/7/2020
PlaidCTF 2020: A Plaid Puzzle

This challenge is solved with @R3x and @mahaloz as a part of Shellphish. Thanks @toshi and @perri for reviewing and giving me suggestions on this write-up. Challenge Summary A Plaid Puzzle is a RPG game written in PuzzleScript. In the game, you are able to control as the player and you could move around and mess with a string. The game is available online on PuzzleScript.net. Below is a screenshot of the game: Wait, where is the player? Although it is invisible, you can easily spot him out as he is always surrounded by the blue arrows. Moreover, the source code of the game is available over there. After all, we are able to deal with it in white-box. This is what we can see in the source code:

4/21/2020
PwnThyBytes 2019 Writeup

10/2/2019
Read more from Mystiz
Published on HackMD