rkm0959

10 Solves in General Division. Author : Barkingdog

Solution

This is a RSA challenge. We see that menu1 generates primes that have equal upper 296 bits, i.e. $UPPER$. It then returns the value $lower$, which is the value of the lower 216 bits. If we can somehow find the value of $UPPER$, this leads us to knowing much more than half of the upper bits of $p$, so we will be able to factor $n$ via standard RSA attacks using coppersmith algorithm.

Now we focus on finding $UPPER$. Each time we are given $lower$, we know that $UPPER + lower$ is a prime. 

Therefore, for each small primes $p<700$, we actually have a relatively strong information $$UPPER + lower \not\equiv 0 \pmod{p}$$ or $$UPPER \not\equiv -lower \pmod{p}$$ which is good enough to remove one possible candidate of $UPPER \pmod{p}$. 

Given sufficient number of $lower$ such that $UPPER + lower$ is a prime, we will be able to remove all but one possible candidate for $UPPER \pmod{p}$ for each prime $p <700$. This essentially means that we can recover $UPPER \pmod{p}$ for each prime $p<700$.

Combining these information with Chinese Remainder Theorem along with the bound $UPPER < 2^{512}$ is strong enough to deduce the value of $UPPER$. This solves the problem. The code below is due to the challenge author barkingdog.

2 Solves in General Division. Author : rkm0959

Solution

There are four independent challenges that needs to be solved within 300 seconds. 

The flavor of the first two challenges and the last two challenges are a bit different.

For the first two challenges, there is fixed a secret key $k$ and a pseudorandom function $F_k(x)$ which outputs a "random" value in $\mathbb{F}_p$.

We have to distinguish this pseudorandom function with an actual random function. To do this, we can choose our inputs $x$ and then the server will give either $F_k(x)$ or a random value. We have to pass this distinguish test 64 times for each of the two challenges.

For the last two challenges, there is a fixed secret key $k$ and a pseudorandom function $F_k(x)$ which outputs a "random" value in $\mathbb{F}_p$.

We have to recover the secret key $k$. To do this, we can choose our inputs $x$ and the server will give $F_k(x)$. 

Generator 1

The pseudorandom function is $$F_k(x) = \left( \langle k, x \rangle \pmod{2} + \langle k, x \rangle \pmod{3} \right) \pmod{2}$$ with $k \in \{0, 1\}^{256}$ and $x \in \{0, 1\}^{256}$. We can choose whatever $x$ we want and get either $F_k(x)$ or some random $\mathbb{F}_2$ element. 

The most natural distinguishment we get is that $F_k(0) = 0$ regardless of $k$. If we query the output at $x = 0$ and get $1$ as the result, we can immediately conclude that our function is an actual random function. Are there any more inputs like this?

It turns out there are. If $x$ is a unit vector $e_i$ with $i$th coordinate $1$ and others $0$, then we can easily show that $F_k(x)$ must be $0$ regardless of $k$. Now the solution is straightforward - take $60$ of these $x$ values and send them to the server. If all return values are $0$, the function is extremely likely to be a pseudorandom function $F_k(x)$. If at least one return value is $1$, the function must be an actual random function. 

Generator 2

This time, the pseudorandom function is $$F_k(x) = \left( \langle k, x \rangle \pmod{5} + \langle k, x \rangle \pmod{7} \right) \pmod{5}$$ with $k \in \{0, 1\}^{256}$ and $x \in \{0, 1\}^{256}$. The problem is, now the input $x$ is SHA256 hashed first then encoded into $\{0,  1\}^{256}$.

Therefore, we can't really choose what value of $x$ to use - practically, we can only use random inputs to our mysterious function. 

The key idea is rather hard to find because it is surprisingly simple. The idea is that the output distribution of $F_k(x)$ is not uniform over $\mathbb{F}_5$. This can be either tested with some random trials with code or computed with some basic combinatorics, also with code.

The details of both methods are not hard, so I'll not go into the details here. In practice, if you send $6000$ random inputs, we can determine whether the function is $F_k(x)$ or actually random function by checking if the most frequent number appeared more than $1310$ times.

Computing the success probability relatively precisely left to the readers as exercise - this should not be difficult albeit a bit tedious.

Generator 3

We now have to find the secret key $k$. The pseudorandom function is $$F_k(x) = \left( \langle k, x \rangle \pmod{5} \right) \pmod{2}$$ with $k \in \{0, 1, 2, 3\}^{64}$ and $x \in \{0, 1, 2, 3, 4\}^{64}$. The input $x$ is also SHA256 hashed. 

The key idea is linearization. If $F_k(x) = 1$, this implies that $\langle k, x \rangle \pmod{5}$ is either $1$ or $3$ - so $$ \left( \langle k, x \rangle - 1  \right) \left( \langle k, x \rangle - 3 \right) \equiv 0 \pmod{5}$$ Since we know the value of $x$, this gives a quadratic equation on $k$'s each coordinate values. We collect a few thousand such equations.

Now, this can be solved by considering each monomials of degree at most 2 as independent variables, and solving the linear equation. 

Generator 4

This time, $p$ and $q$ are very large - $p$ is 256 bits and $q$ is 128 bits. The pseudorandom function is $$F_k(x) = \left( \langle k, H(x) \rangle \pmod{p} + \langle k, H(x) \rangle \pmod{q} \right) \pmod{p}$$ where $k \in \{0, 1, \cdots , 2^{256}-1 \}^{16}$ and $H(x) = (h^1(x), h^2(x), \cdots, h^{16}(x))$ where $h^n(x)$ is $x$ after SHA256 applied $n$ times then converted into an integer. Note that we once again have no essental control over $H(x)$, so it's practically a random vector.

The idea is that $p$ is much larger than $q$, and $\langle k, H(x) \rangle \pmod{q}$ is between $0$ and $q$. Therefore, the result $F_k(x)$ gives us a range of length $q$ which the value $\langle k, H(x) \rangle \pmod{p}$ must lie. Since we can compute $H(x)$, each input $x$ gives us a precise range for a random linear combination of $k$'s values in mod $p$. Now this reduces to a simple lattice attack with CVP, and my repository is strong enough to solve this challenge. For details, check out https://github.com/rkm0959/Inequality_Solving_with_CVP, or Samsung Software Membership blog.

Background

A PRF takes a key $k$ and an input $x$ and deterministically outputs $y = F(k, x)$. 

A PRF is secure if no efficient adversaries can distinguish (with non-negligible probability) between $F$ and a truly random function between the input/output space. Here, the adversary may query any $x$ and read the output which is either $F(k, x)$ or a random value.

If an adversary who can only query random $x$ in the domain cannot distinguish (with non-negligible probability) between $F$ and a truly random function, the PRF $f$ is called weakly secure PRF, or weak PRF. So Generator 2, 3, 4 are all about (something similar to) weak PRFs.

PRFs and weak PRFs are building blocks of cryptography - Boneh & Shoup's book has an interesting exercise regarding them (18.16), and there are plenty of papers on them as well. The PRFs of the form given in the challenge, i.e. $$F(k, x) = \left( \langle k, x \rangle \pmod{p} + \langle k, x \rangle \pmod{q} \right) \pmod{p}$$ comes from the paper "Exploring Crypto Dark Matter: New Simple PRF Candidates and Their Applications" by Boneh, Ishai, and Passel`egue. This paper was in TCC 2018. The main idea was that these functions are relatively simple to calculate via secure multiparty computation - but since I'm not very knowledgeable in this area yet I cannot explain more details.  

Some attacks on this PRF is noted in the TCC 2018 paper - in page 7, where they mention the PRF with $p=2$ and $q=3$, they also note that in a constant-modulus regime the fact that the modulus is composite is important to prevent a direct linearization attack. Generator 3 covers this idea. They also note that lattice style attacks are possible (BKW) which is done in Generator 4. 

More details are found on page 36, where they outline more attacks. Remark 6.4 explains once again about possible lattice attacks (Generator 4) and Remark 6.5 is once again on linearization attacks (Generator 3). At the start of page 37, there is a note that there is construction is not a PRF - that vectors with Hamming weight 1 is enough for distinguishment. Finding this idea was given as a challenge via Generator 1. 

After a few years, Cheon et al (who taught me cryptography in univ, thanks) wrote about an statistical attack on this PRF in their paper "Adventures in Crypto Dark Matter: Attacks and Fixes for Weak Pseudorandom Functions". This paper was in PKC 2021. Their main idea was simple but very effective - the output distribution of the said PRF was surprisingly far from the uniform distribution. Their calculations are outlined on Section 4, starting at page 8 of the paper. Their calculations are on the PRF with the setting $p=2$ and $q=3$, but the result for arbitrary primes $p, q$ are on Remark 4.4, at the top of page 12. Reading this paper gave me the motivation for setting up this challenge.

Comments

• Note the cache is there to prevent same inputs giving different outputs in the case an actual random function is used.
• The server computes both $F_k(x)$ and the actual random function then returns the output to prevent timing attacks.
• Generator 1 is intended to be a soft introduction to the challenge, letting participants get a sense of what's going on.
• Generator 3's main idea (linearization) have appeared in multiple CTFs before. I can recall three of them.
• When writing the exploit, sending queries in batches is extremely important to fit the time requirements.

Super Guessers won SECCON CTF 2021, with a clean all-solve. I have repeated in this CTF, i.e. won this CTF two years in a row, last year with a strong union of (mostly) Korean cybersecurity professionals. The writeups from last year is at https://rkm0959.tistory.com/165.

This year, there is no collab, only Super Guesser, which is cool :)

Due to some other busy work, I didn't participate fully and solved 3 out of 6 cryptography challenges, and others were done by Baaarkingdog. I also finished one misc challenge, (it was our final solve) but it built on work of many others. (I just finished the challenge)

Challenges were very clean and good, and not painfully difficult (this is usually expected from Japan I think, :))

oOoOoO (by kurenaif)

Thinking about the effect of each "o" or "O" for the value of bytes_to_long(message), we see that this problem is essentially a subset sum problem over modulo $M$. Indeed, the problem is equivalent to solving the system $$ \sum_{i=0}^{127} [79^k \text{   or   } 111^k] \equiv S \pmod{M}$$ which is same as $$\sum_{i=0}^{127} [79^k \pmod{M} \text{   or   } 111^k \pmod{M}] \equiv S \pmod{M}$$ Since the left hand side is between $0$ and $128M$, we can just solve the following for $0 \le c \le 127$. $$\sum_{i=0}^{127} [79^k \pmod{M} \text{  or   } 111^k \pmod{M}] = (S \pmod{M}) + cM$$ which is now a standard knapsack problem, and can be solved via CJLOSS algorithm.

XXX (by theoremoon)

We have 796 bit prime $p$ and around 320 bit $x$, which is the flag.

We are given 6 parameters $(a_i, b_i)$ such that $y_i^2 \equiv x^3 + a_ix + b_i \pmod{p}$ and $y_i < x$. 

Subtracting, we see that $$(a_1 - a_j)x + (b_1 - b_j) \equiv y_1^2 - y_j^2 \pmod{p}$$ so $$-2^{640} < (a_1 - a_j) x + (b_1 - b_j) \pmod{p} < 2^{640}$$ which can be rewritten as $$ -2^{640} < (a_1 - a_j) x + (b_1 - b_j) + p c_j< 2^{640}$$ for $2 \le j \le 6$. Since we know all $a_j, b_j$ values, the only unknown is $x$ and $c_j$ values, and this can be plugged in my CVP repository. 

Sign Wars

There are two mistakes - one is the insecure random of "prequel" which fixes the middle 128 bits, and the insecure python random which is used in the "original". The natural plan is to attack the "prequel" first using the insecure random via standard LLL, find the python random seed using some library, then directly find the random $k$ values for the "original". The latter part can be done very easily with some libraries, so we'll focus on the first one. We write the system as follows. For each 60 equations, we have $$ks \equiv z_1 + rd \pmod{n}$$ $$k \equiv s^{-1}z_1 + rs^{-1}d \pmod{n}$$ $$k_1 + z_1 \cdot 2^{128} + k_3 \cdot 2^{256} \equiv s^{-1}z_1 + rs^{-1}d \pmod{n}$$ $$ 0 \le k_1 = z_1(s^{-1} - 2^{128}) + rs^{-1}d - k_3 \cdot 2^{256} \pmod{n} < 2^{128}$$ $$0 \le z_1(s^{-1} - 2^{128}) + rs^{-1}d - k_3 \cdot 2^{256} + cn < 2^{128}$$ and now this can be plugged in CVP repository. Note that $d, z_1$ is fixed and $0 \le z_1 < 2^{128}$, $0 \le k_3 < 2^{128}$. 

Super Guesser played N1CTF and got 1st place, also giving us a good amount of CTFtime points.

checkin 

There must be a more efficient solution, but here's a solution that took around 5 hours. 

From $p_0$, we get a range of $p$. From this range, we can calculate the possible range of $x$. After simple calculation, we see that $$ L \le x \le R $$ where $R-L < 2^{501}$. Now since we know the equation $$x^2 - hx + 1 \equiv 0 \pmod{n}$$ we can use Coppersmith's attack with $\epsilon = 0.01$. This gives a solution that requires LLL algorithm on a matrix of size 100 x 102, taking 5 hours to run. After finding $x$, we can calculate $p, q$ with quadratic equations. Interested in a faster solution.

n1ogin

The data (aes/rsa data) that the admin sent is given in a pcap file. The client file is also given to make lives easier.

In the cryptography world, there are a bunch of attacks that involve exploiting error messages. For example, there are padding oracle attack and Bleichenbacher's attack. There are a bunch of errors in this challenge as well, but Bleichenbacher's attack is guarded as PKCS padding error is simply ignored by taking some random bytes as the unpadded result.

It seems that the same goes for the padding check and HMAC check - there are a bunch of errors possible in the AES decryption (and content verification) but all of them simply return "Error!" making it hard to see which error was actually thrown. If we could decide whether AES padding was the issue, we could easily use padding oracle attack to recover the admin password, giving us the flag.

How can we achieve this goal? If we look at lines 71-84, the padding error is checked first, then the HMAC error. If padding error was found, then the server skips the HMAC computation. Because the HMAC function was applied 7777 times, that HMAC computation takes a significant amount of time, around 0.1 seconds. This means that with a stable server, we can decide whether or not padding error was found via timing attack. This solves the challenge :) To make the exploit more stable, I timed everything 5 times and took the median. 

n1token1

We have 1024 bit modulus $n$ and 920 tokens. To calculate the tokens, the following procedure took place.

• select 920 distinct small primes and store it in an array (this array is fixed)
• compute some product of these small primes which is just over 920 bits long and is a QR modulo $n$
• compute the square root of this value and multiply $c$ to it

We have to compute $c$ and also factorize $n$ from these data. 

Step 1 : Computing $c^2$.

Denote the token as $t$ and the selected product of primes as $X$. We have $$ t \equiv c \cdot \sqrt{X} \pmod{n} \implies t^2 \equiv c^2 \cdot X \pmod{n} \implies X \equiv t^2 c^{-2} \pmod{n}$$ Note that $n$ is 1024 bits and $X$ is less than 930 bits. Now this is just a hidden number problem, so LLL can solve it. 

Thanks to barkingdog for thinking of this idea and computing $c^2$! I had the idea for Step 2, but couldn't think of this.

Step 2 : Computing $c$ and Factorizing $n$.

Since we know $c^2 \pmod{n}$, we can now compute all $X$ values corresponding to each tokens. 

We can now easily factorize these values, as they are smooth. Consider the prime factorization of $X$.

$X$ is composed of prime factors that belong to the fixed set of 920 prime factors.

If we consider only the parity of each exponent in the prime factorization, we can regard each number as a binary vector of length 920. 

Since there are 920 vectors of length 920 over $\mathbb{F}_2$, it's tempting to look for kernels. Indeed, if we find a nontrivial kernel, we can multiply all equations corresponding to the kernel - and since the product of $X$'s will be a square, we can get some interesting results.

For example, if there are $l$ tokens such that the product of their $X$'s is a square, we get $$ \prod t^2 \equiv c^{2l} \cdot \prod X \pmod{n} \implies \prod t \equiv c^l \cdot \sqrt{\prod X} \cdot \text{(some square root of 1)} \pmod{n}$$

If $l$ is odd, we can get a candidate of $c$ that agrees with the found value of $c^2 \pmod{n}$. 

If $l$ is even, we can get some square root of 1. If this is $1$ or $-1$, we are out of luck. If not, we can factorize $n$ with GCD.

If turns out the the kernel is of dimension 2, one with $l$ odd and one with $l$ even. We are lucky on the $l$ even case as well.