It has been a very long time that I've compiled a writeup. This time I have played on my own as @blackb6a. 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 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)⌗

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 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). \]

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.

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?

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.

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)⌗

Note: $+$ is once again the exclusive OR operator as we are discussing 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⌗

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} \]

(╯‵□′)╯︵┴─┴

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