rkm0959

I participated in zer0pts CTF in Super Guesser, and we reached 1st place.

Since there are many challenges to cover, this writeup will be very concise.

The solution codes may be a bit messy, since I wrote this in a hurry :P

Also, r4j solved signme, so I'll leave that writeup to r4j :D

war(sa)mup

Solution

Writing $\lfloor m/2 \rfloor = x$, we see that $m$ is either $2x$ or $2x+1$. If $m = 2x$, we can perform the related message attack with polynomials $$p_1(x) = (2x)^e - c_1, \quad p_2(x) = x^e - c_2$$ Of course, in this case we would have $c_1 \equiv 2^e c_2 \pmod{n}$ and polynomial GCD would be useless. If $m = 2x+1$, we can do it with $$p_1(x) = (2x+1)^e - c_1, \quad p_2(x) = x^e - c_2$$ which works and gives our desired value of $x$. $m$ can be recovered as $2x+1 \pmod{n}$.

OT or NOT OT

Solution

The key idea is to make a small subgroup which the values of $x, y \in \mathbb{F}_p$ must belong to.

To do this, we wait until $p \equiv 1 \pmod{4}$, then take any $t \in \mathbb{F}_p$ with order $4$.

This can be done by taking some random $g \in \mathbb{F}_p$ and choosing $t = g^{(p-1)/4}$. 

Checking if order of $t$ is $4$ can now be done simply by verifying $t^2 \neq 1$ in $\mathbb{F}_p$.

Now we simply send $a = t$, $b = t^2$, $c = t^3$. Since $a^4 = b^4 = c^4 = 1$, we also have $u^4 = v^4 = 1$.

Therefore, we can see if $x = u$ and if $y= v$ by simply checking if $x^4=1$ and if $y^4=1$.

Of course, it should be noted that getStrongPrime does not generate a prime of the form $p=2q+1$ with $q$ prime. :wink:

janken vs yoshiking

Solution

The first observation is that if $g$ is a quadratic residue (QR), the commitment leaks the legendre symbol of $m$.

Indeed, if $g$ is QR, then the legendre symbol of $m$ is simply the legendre symbol of $c_2$.

We generate instances until we find a prime $p$ that not all $1, 2, 3$ are QR modulo $p$. 

In this case, by leaking the legendre symbol of $m$, we can reduce the number of candidates for yoshiking's hand from 3 to 2.

Therefore, we can at least force a tie, and occasionally win. This is enough to solve the challenge.

easy pseudorandom

Solution

It's clear that we just need to find the value of $v_0$. Denote $l = 256$. Using the given info, we can write $$\begin{equation*} \begin{aligned} v_0 &= w_0 \cdot 2^{l - k} + x \\ v_1 &= w_1 \cdot 2^{l-k} + y \\ v_1 & \equiv v_0^2 + b \pmod{n} \end{aligned} \end{equation*}$$ Combining, this gives us the key relation $$ w_1 \cdot 2^{l-k} + y \equiv w_0^2 \cdot 2^{2l-2k} + b + w_0 \cdot 2^{l-k+1} \cdot x + x^2 \pmod{n}$$ The key idea is to remove the quadratic term $x^2$. Denote $$\begin{equation*} \begin{aligned} A &= w_0 \cdot 2^{l-k+1} \\ B &= w_1 \cdot 2^{l-k} - w_0^2 \cdot 2^{2l-2k} - b \end{aligned} \end{equation*}$$ Note that $A, B$ are constants that we know. Our relation is now $$ Ax \equiv B + y - x^2 \pmod{n}$$ Since $x, y$ are all below $2^{l-k}$, we can see that $$ B - 2^{2l-2k} \le Ax \pmod{n} \le B + 2^{l-k}$$ which is a type of relation that can be solved. Check out my writeups for PBCTF Special Gift and SECCON crypto01.

Note that there are $2^{l-k}$ possible values of $x$, and there are approximately $2^{2l-2k}$ possible values of $Ax \pmod{n}$. 

Since $l-k + 2l-2k = 3l-3k \approx l$, we can decide that there must be fairly small number of $x$ that satisfy the desired inequality.

This type of analysis was done in both of writeups above, and recently highlighted by Mystiz in AeroCTF writeup.

Now that there are three challenges I solved with this method, I think I'll add this to my CVP repository as well...

3-AES

Solution

Let's consider plaintexts/ciphertexts of one block first. Denote $E_k$, $D_k$ as ECB encryption/decryption with key $k$.

The encryption process can be written as $$ P \rightarrow E_{k_1}(P) \rightarrow E_{k_2}(E_{k_1}(P) \oplus IV_1) \rightarrow E_{k_2}(E_{k_1}(P) \oplus IV_1) \oplus E_{k_3}(IV_2) = C$$ The key relation is $$E_{k_1}(P) \oplus IV_1 = D_{k_2}(C \oplus E_{k_3}(IV_2))$$ For a fixed value of $C, IV_2$, the right hand side is fixed. Therefore, the left hand side is also fixed.

We start by using the decryption oracle with $C, IV_1, IV_2$ being all 16 bytes of \x00. Denote $P_0$ as the resulting plaintext. 

Then, we use the decryption oracle with $C, IV_1, IV_2$ all \x00, but $IV_1$ has the last byte \x01. Denote $P_1$ as the resulting plaintext.

Our observations lead to $$\text{bytes_to_long}(E_{k_1}(P_0) \oplus E_{k_1}(P_1)) = 1$$ This can be tested for all $2^{24}$ possible keys, and with that we find $k_1$. 

Now that we know $k_1$, we also know the value of $D_{k_2} \circ E_{k_3}$ applied to 16 bytes of \x00.

This is a perfect scenario for a meet-in-the-middle attack, and with this we can find $k_2$, $k_3$. 

retrieve data from server

find the first key

meet in the middle preparation

meet in the middle in C++

NOT Mordell primes

Solution

Denote $P = (u, v)$, $Q = (x, y)$. We can utilize the sum of points formula to get the x-coordinate of $R$ as $$ \left( \frac{y-v}{x-u} \right)^2 - (x + u)$$ Therefore, we have the relation $$ g(x, y) = x(y-v)^2 - (x+u)(x-u)^2 - N(x-u)^2 \equiv 0 \pmod{p}$$ We now have to combine this relation with $$y^2 \equiv x^3 + ax + b \pmod{p}$$ Initially I tried to calculate the resultant, but it bugged out (maybe due to incorrect parameters given) so I changed my approach.

If we print out the monomials of $g(x, y)$, we see that $y$ appears in two monomials, $xy^2$ and $xy$.

We can change $y^2$ as $x^3 + ax + b$ in the first one. Now we can drag the $xy$ term into the right hand side, square the equation, and change $y^2$ to $x^3 + ax + b$ to obtain a equation with only one variable $x$. For more details, please refer to the solution code.

This polynomial equation can now be solved, which gives us the candidates for the prime divisor of $N$. 

pure division

Solution

The required paper for this challenge is https://arxiv.org/pdf/2010.15543.pdf.

Basically, (like a few challenges this year) we need a homomorphism to a group we can efficiently calculate discrete logarithm on.

It turns out that the given elliptic curve over $\mathbb{Z}_{p^3}$ has a homomorphism to $\mathbb{Z}_{p^2}$.

UPD : It should also be noted that the binary operator in $\mathbb{Z}_{p^2}$ is sum, not product.

To calculate this, we need to know how to perform point multiplication in a projective curve/division free setting.

The formula for this can be found online, for example, here. I wonder if this computation can be done in sage...

Tokyo Network

Solution

The context of this challenge is quite nice - it's quantum error correction with Shor and QKD with BB84.

I realized the BB84 part of the program after I read the flag, but if you look at it knowing it's BB84, it's quite clear.

Working backwards, we observe the following and eventually find the solution

• our final goal is to find the AES key $k$
• we know $ba$ and $m$, and we are free to choose $bb$, so we know the array $l$ and $chosen$
• therefore, our goal is to find the bits of $ra$ in the indexes of $l \setminus chosen$
• note that in those indexes, we have $ba$ and $bb$ bits all $0$
• we see that this implies we don't need to worry about Hadamard gates
• we only need to check whether or not X gate was applied at the 0th qubit
• if there was no encoding and noise, we could just measure the 0th qubit to see whether 0 or 1 pops out
• however, we have encoding and noise : how do we deal with this?
• it turns out that the encoding part is simply the first part of Shor's quantum error correction code
• therefore, we can just send the remaining part of the Shor's quantum error correction code and be done with it
• note that our noise is single qubit, so we have no worries whatsoever
• however, we need Toffoli gates to make the circuit : we don't have that in our arsenal of gates
• this can be resolved by creating Toffoli gates with 2-qubit gates and single qubit gates : details are in Wikipedia.

• 연구 : 공부는 확실히 꽤 했고, 글도 블로그에 많이 썼다. 랩에서 받은 태스크 하나를 잘 수행했다. 연구 자체는 아직 어렵다...
• 대수적 정수론 : 많이 못 봤다. 3장까지라도 방학 기간에 빠르게 읽을까..
• Kaggle : 이건 딥러닝의 기초를 들으면서 병행하는 걸로 결정했다.
• 위상 : 4단원까지 읽었고, 실해석학과 병행하면서 읽으면 될 것 같다.
• CTF : 2월의 마지막 두 대회를 우승하면서 기분 좋게 마무리
• 암호학 책 리딩 : 2장, 18장, 19장을 읽고 특히 19장은 정리했다. 공부하고 싶은 건 일단 다 한듯.
• Rust 입문 : 당연히 아직 많이 부족하지만, 코드포스 Div 2를 순조롭게 칠 정도로 편해졌다.
• 봉사활동 : 다 채웠고 문제 없이 장학금을 받을 수 있을 것으로 기대한다.
• 건강 : 중간에 한 번 수치가 이상하게 나와서 정신적으로 충격을 받았는데, false alarm이었던 걸로.. 대신 몸에 더 신경쓰는 삶을 살기로 했다. 이 문제로 정신 없어서 일주일 정도 아무것도 못했다. 아무튼 폭식하지 않고 술도 가급적 안 마시는 걸로. 체중도 조금 줄일 생각...

2월에는 나름 잘 쓴 것 같은 좋은 블로그 글을 많이 쓴 것 같아서 기분이 좋다 :)

건강하고 재밌는 한 학기를 보낼 수 있었으면 좋겠다. 부담없이 과목을 수강하니, 재밌는 공부를 더 하고 싶다.

I participated in AeroCTF as a member of Super Guesser. We reached 1st place :)

We were able to grab first bloods on all three cryptography challenges.

Phoenix was solved by rbtree, and I solved horcrux and boggart.

Phoenix

Solution (due to rbtree)

Let's look at the encryption scheme. 

We have a key $k \in GF(2^{256})$ and known parameters $a, b \in GF(2^{256})$.

To encrypt a plaintext $m$, it is first converted to binary then padded at the front with zeros to have length 1024. 

Then, we take the first 10 bits of the polynomial representation of $a^i k +b$ for each $i$, and calculate $$xbit_i = \sum \text{(even index bits)}$$ $$ybit_i = \prod \text{(odd index bits)}$$ where calculations are done in $GF(2)$. 

Finally, we encrypt our text with a stream cipher, i.e. XOR our plaintext with $\{xbit_i \oplus ybit_i\}_{i \ge 1}$. 

We now make some observations.

• It's very likely that $ybit_i$ is $0$, since it is a product of 5 bits. Heuristically, it has a $31/32$ chance of being $0$. 
• The message bit length is guaranteed to be less than 256. This means the length of the padding is at least 768.
• If we write each 256 coefficients of $k$ as variables, then $xbit_i$ can be written as a linear combination of them (and $0, 1$)

Now we have our solution idea.

• If we assume that $ybit_i = 0$ and know the ptxt/ctxt bits, we can recover $xbit_i$. This gives us a linear equation over our 256 variables.
• Of course, we know 768 bits of the plaintext and all of the ciphertext, so we can do this for 768 different values of $i$.
• We take 256 equations out of those 768 and hope that the system of equations have a unique solution.
• If there is a unique solution, we can recover the key and perform the decryption process to get a candidate for our flag.
• If our recovered flag has "Aero{" in it, we can finish the challenge. If not, we try another set of 256 equations.

We need to have $ybit = 0$ for all 256 bits/equations we selected. This has a probability of $$(31/32)^{256} \approx 0.0003$$ of succeeding, and we also need our system to be uniquely solvable. Thankfully, our algorithm terminates in about 2000 trials, and each trial doesn't take too long. It seems like SageMath is very efficient when it comes to matrices over $GF(2)$ :) 

Here's the solution script, by rbtree. It runs in a few minutes.

Horcrux