What’s the thumbnail? I sent it to rbtree after I sent him my solution on Yet Another PRNG and he responded “oh this works?”.

I am playing as a part of @blackb6a this time for perfect blue's annual pbctf. This time there are six crypto challenges and I first blooded 🩸 half of them. I solved five of them, and collaborated with TWY (who made 99% of the process) for Seed Me. In this blog post, I will cover Seed Me and Yet Another RSA. I tried to make the whole post beginner friendly, hence included more details than necessary.

I was originally going to discuss all of the crypto challenges, but I found it is too demanding and tiring.

Seed Me⌗

Challenge Summary⌗

We are asked a seed for the Java program. the random instance, rng, is defined by rng = new Random(seed). We will get the flag if the 2048-, 4096-, ..., 32768-th output from rng.NextFloat() are never less than $0.9801547$.

Solution⌗

Part I: Getting started⌗

To begin, we definitely need to look at Random class in Java by looking at its source code. Below is an excerpted Random class which includes only the functions we need to look at.

public class Random implements java.io.Serializable {
    private final AtomicLong seed;
    private static final long multiplier = 0x5DEECE66DL;
    private static final long addend = 0xBL;
    private static final long mask = (1L << 48) - 1;

    public Random(long seed) {
        if (getClass() == Random.class)
            this.seed = new AtomicLong(initialScramble(seed));
        else {
            // subclass might have overriden setSeed
            this.seed = new AtomicLong();
            setSeed(seed);
        }
    }

    private static long initialScramble(long seed) {
        return (seed ^ multiplier) & mask;
    }

    protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }

    public float nextFloat() {
        return next(24) / ((float)(1 << 24));
    }
}

From above, we can see that Java's random is a linear congruential generator with a 48-bit seed.

Given the seed $\text{seed}$, the internal state can be represented as

\[t_k = \begin{cases}\begin{aligned} \text{seed} \oplus \text{5DEECE66D}_{16} &\quad\text{if}\ k=0 \\ (\text{5DEECE66D}_{16} \cdot t_{k-1} + \text{B}_{16})\ \text{mod}\ 2^{48} &\quad\text{otherwise} \end{aligned}\end{cases},\]

and the outputs $r_1, r_2, ... \in [0, 1)$, being 24-bit floating point numbers, are defined by

\[r_k = \frac{\lfloor t_k / 2^{24} \rfloor}{2^{24}}.\]

Let's get back to our objective. The goal is to find a valid seed such that

\[r_i \geq 0.9801547\qquad \forall\ i = 2048, 4096, ..., 32768.\]

It is equivalent to the below statement:

\[t_i \geq 16444268\cdot 2^{24} \qquad \forall\ i = 2048, 4096, ..., 32768.\]

We will be working on $t_i$'s instead of $r_i$'s to make everything computed as a modular equation.

Part II: LLL FTW?⌗

2.1. Constructing a lattice for LLL⌗

The reason is evident: We want to have a closed form for $t_{2048}, t_{4096}, ..., t_{32768}$ in terms of $t_0$. It is also not difficult to derive a closed form of $t_n$ in terms of $t_0$. Let also $a = \text{5DEECE66D}_{16}$ and $b = \text{B}_{16}$:

\[\begin{aligned} t_n &= a t_{n-1} + b = a (a t_{n-2} + b) + b = a^2 t_{n-2} + b(a + 1) = ... \\ &= a^n t_0 + b(a^{n-1} + a^{n-2} + ... + 1). \end{aligned}\]

We can see that $t_n$ has an affine relation to $t_0$ and let us denote $t_n := a_n t_0 + b_n$ with $a_n = a^n$ and $b_n = b(a^{n-1} + a^{n-2} + ... + 1)$. It implied that we are actually solving a set of linear inequalities, under modulo $2^{48}$ however.

Now we are stuck. When in doubt, go lattice.

It is expected that for a set of $t_{2048}, t_{4096}, ..., t_{32768}$ generated by a $t_0\in \mathbb{Z}$, there exists $x_1, x_2, ..., x_{18}$ such that

\[\begin{aligned} & (t_{2048}, t_{4096}, ..., t_{32768}, 1) \\ & \quad = x_1 (b_{2048}, b_{4096}, ..., b_{32768}, 1) + x_2 (a_{2048}, a_{4096}, ..., a_{32768}, 0)\\ & \qquad + x_3 (2^{48}, 0, ..., 0, 0) + x_4 (0, 2^{48}, ..., 0, 0) + ... + x_{18} (0, 0, ..., 2^{48}, 0). \qquad [\spadesuit] \end{aligned}\]

We define the vectors into the $18\times 17$ matrix below. Assigning appropriate weights to the columns and performing LLL, we should be able to get $(t_{2048}, t_{4096}, ..., t_{32768})$ that is short enough.

\[\begin{bmatrix} b_{2048} & b_{4096} & ... & b_{32768} & 1 \\ a_{2048} & a_{4096} & ... & a_{32768} & 0 \\ 2^{48} & 0 & ... & 0 & 0 \\ 0 & 2^{48} & ... & 0 & 0 \\ && \vdots && \\ 0 & 0 & ... & 2^{48} & 0 \end{bmatrix}\]

One seed that I recovered from LLL is 267950572886646. The 16 numbers generated are 0.0725, 0.8592, 0.9784, 0.0967, 0.8805, 0.9965, 0.1111, 0.8909, 0.0022, 0.1116, 0.8857, 0.9908, 0.0937, 0.8606, 0.9582 and 0.0529. Note that the numbers generated by nextFloat ranges between 0 and 1. Instead of being small, I would say that the numbers are rather extreme. After all, we are looking for $a_{2048k} t_0 + b_{2048k}\ (\text{mod}\ 2^{48})$ (i.e. $t_{2048k}$) which has a small magnitude, but we did not care whether it is positive or not.

2.2. Improving the lattice⌗

The lattice above does not generate large $t_{2048k}$s. However, it is a good starting point because it can be adjusted to serve our purpose easily. How? Recall $[\spadesuit]$ we mentioned. Let's adjust this a bit:

\[\begin{aligned} &(t_{2048} - K, t_{4096} - K, ..., t_{32768} - K, 1) \\ & \quad = x_1 (b_{2048} - K, b_{4096} - K, ..., b_{32768} - K, 1) + x_2 (a_{2048}, a_{4096}, ..., a_{32768}, 0)\\ & \qquad + x_3 (2^{48}, 0, ..., 0, 0) + x_4 (0, 2^{48}, ..., 0, 0) + ... + x_{18} (0, 0, ..., 2^{48}, 0). \qquad [\spadesuit'] \end{aligned}\]

That said, the below matrix would give us 16-tuples $(t_{2048} - K, t_{4096} - K, ..., t_{32768} - K)$ those are small. Equivalently, each of $t_{2048}, t_{4096}, ..., t_{32768}$ would be close to $K$.

\[\begin{bmatrix} b_{2048}-K & b_{4096}-K & ... & b_{32768}-K & 1 \\ a_{2048} & a_{4096} & ... & a_{32768} & 0 \\ 2^{48} & 0 & ... & 0 & 0 \\ 0 & 2^{48} & ... & 0 & 0 \\ && \vdots && \\ 0 & 0 & ... & 2^{48} & 0 \end{bmatrix}\]

I tried out the patched algorithm and got some good (yet not good enough) seeds:

  • $t_0 = 272174166229342$. The numbers generated are
    0.9792, 0.9879, 0.9934, 0.9963, 0.9970, 0.9960, 0.9939, 0.9910,
    0.9880, 0.9852, 0.9832, 0.9824, 0.9834, 0.9866, 0.9926, 0.0018
  • $t_0 = 272208525967710$. The numbers generated are
    0.9794, 0.9880, 0.9935, 0.9964, 0.9971, 0.9961, 0.9940, 0.9911,
    0.9881, 0.9853, 0.9833, 0.9825, 0.9835, 0.9868, 0.9927, 0.0019
  • $t_0 = 272242885706078$. The numbers generated are
    0.9795, 0.9881, 0.9937, 0.9965, 0.9972, 0.9963, 0.9941, 0.9913,
    0.9882, 0.9854, 0.9834, 0.9827, 0.9837, 0.9869, 0.9928, 0.0020
  • $t_0 = 272277245444446$. The numbers generated are
    0.9796, 0.9883, 0.9938, 0.9966, 0.9974, 0.9964, 0.9942, 0.9914,
    0.9883, 0.9856, 0.9835, 0.9828, 0.9838, 0.9870, 0.9930, 0.0021
  • ...

There is a point in common for the numbers generated - $r_{4096}, r_{6144}, ..., r_{30720} \geq 0.9801547$ but $r_{2048}, r_{32768} < 0.9801547$. When I had a closer look to those $r_i$'s, I found that the pattern are similar. Are there classes of seeds those generate similar values? Interestingly, for the above $t_0$'s, all of them satisfy

\[t_0 \equiv 10678616414\ (\text{mod}\ 2^{35}).\]

Part III: Brute force FTW!⌗

Anyway, let's cut the crap. TWY sent us the below seed:

The sixteen values generated being 0.9886, 0.9939, 0.9965, 0.9970, 0.9958, 0.9934, 0.9903, 0.9870, 0.9839, 0.9817, 0.9807, 0.9814, 0.9844, 0.9901, 0.9990, 0.0117. That said, all but the last one satisfy the condition. TWY suggested treating the current $t_0$ as the actual $t_{2048}$, i.e., revert the state 2048 times. With that, we are able to get a seed for the flag: 272526698751795 🎉. Submitting the seed to the server, we have the flag being

pbctf{intended_is_LLL_with_branch_and_bound_9ad09becbc4c7685}

But wait. Where did the seed come from? TWY actually wrote a CUDA script to exhaust the seeds...

Yet Another RSA⌗

Challenge Summary⌗

We are given a RSA public key $n, e$ and an encrypted flag $c$. Hereby $n$ is 1024-bit number which is a product of two 512-bit primes $p, q$ (they are both in the form of $a^2 + 3b^2$). It is also known that $d$ is 400-bit long.

Remarkably, the multiply operation is performed under a group $\mathcal{G}$ with

\[\mathcal{G} = \mathbb{Z}_n^2 \cup (\mathbb{Z}_n\times\{\varepsilon\}) \cup \{\varepsilon\}^2.\]

Also $|\mathcal{G}| = (p^2+p+1)(q^2+q+1)$. The objective is to recover the flag from $c$.

Solution⌗

Part I: Kickstarting the challenge⌗

Although it says that it is a RSA challenge, there are several things those looked strange:

  1. Primes are generated such that $p = a^2 + 3b^2$ for some $a, b\in \mathbb{N}$.
  2. The group is handcrafted and its order is $(p^2 + p + 1)(q^2 + q + 1)$.
  3. The private key $d$ is relatively small compared to $\phi$ (400 bits vs 2048 bits).

It seemed like a variant of the Wiener's attack from [3]. I tried the approximation

\[\frac{e}{n^2} \approx \frac{k}{d}\]

and of course it did not work (will be explained in the next part). Well, @RBTree_ would definitely not going to make such a straight forward challenge. Thus, I decided to study the group operation. This is the most regretable decision I have ever made in my life.

So what is the group? I don’t know. We spent a lot of time studying it. rkm0959 tweeted that it is defined on $\mathbb{F}_n[x]/(x^3 - 2)$.

Part II: Attacking on the small private key⌗

I have had too much on the group operation. I suggested hoifanrd to continue working on the group operation and I continued attacking on the small $d$.

There are two common attacks when the private key is small: Wiener's attack and Boneh-Durfee attack. Let's briefly describe them and how I patched them to make them work on the challenge setting.

2.1. Messing up with Wiener's attack⌗

This equation is crucial for the aforementioned attacks:

\[ed = k\phi + 1, \qquad\qquad[\dagger]\]

for some positive integer $k$. This is essentially $ed \equiv 1\ (\text{mod}\ \phi)$ but we are unwrapping the modular relation. Normally,

\[\phi = (p-1)(q-1) = n - (p+q) + 1 \approx n.\]

Thus $ed = k\phi + 1 \approx k\phi$ would imply

\[\frac{e}{n} \approx \frac{k}{d}.\]

Since $e$ and $n$ are known, we can list the convergents of $e/n$. Wiener's attack stated that $k/d$ would be one of the convergents of $e/n$. In our case, $\phi \not\approx n$ but

\[\phi = (p^2 + p + 1)(q^2 + q + 1) = p^2q^2\left(1+\frac{1}{p}+\frac{1}{p^2}\right)\left(1+\frac{1}{q}+\frac{1}{q^2}\right) \approx p^2q^2 = n^2.\]

Because of that, I checked if the convergents of $e/n^2$ contains $k/d$. It doesn't.

2.2. Patching Boneh-Durfee specifically for the challenge⌗

Since Wiener's attack did not work, it is natural to try Boneh-Durfee afterwards.

It is natural to try… Well it is not. At least I did not attempt to use Boneh-Durfee but instead went into a rabbit hole.

Let's take modulo $e$ on $[\dagger]$ and assume $\phi = (p-1)(q-1)$, i.e., the default RSA setting:

\[0 \equiv k\phi + 1 \equiv k(p-1)(q-1) + 1 \equiv \htmlStyle{color: yellow;}{k}[n+1-\htmlStyle{color: yellow;}{(p+q)}] + 1\qquad(\text{mod}\ e)\]

From above, $k$ and $p+q$ are the only unknowns. Boneh-Durfee attack attempts to find them if both of them are small. Normally, $p, q \approx \sqrt{n}$. The attack states that $d$ could be recovered if $e < n^{0.292}$.

Anyway, back to our case. Although our $\phi$ is different, we can do the same thing.

\[\begin{aligned} 0 &\equiv k\phi + 1 \equiv k(p^2+p+1)(q^2+q+1) + 1 \\ &\equiv \htmlStyle{color: yellow;}{k}[n^2+n+1 + (n+1)\htmlStyle{color: yellow;}{(p+q)} + \htmlStyle{color: yellow;}{(p^2+q^2)}] + 1\qquad(\text{mod}\ e) \end{aligned}\]

There are three unknowns: $k \approx d \approx 2^{400}$, $p+q \approx 2^{512}$ and $p^2 + q^2 \approx 2^{1024}$. Since $e \approx 2^{2048}$ and $400 + 512 + 1024 < 2048$, the attack might work. Anyway, let's try it out.

2.3. Implementing the variant of Boneh-Durfee attack⌗

I copied the code from defund/coppersmith as a starter. I also tried to increase the parameters $m$ and $d$ such that I could still perform LLL in a reasonable time. However, I could only recover $d$ when $d$ is up to 200 bits.

bounds = (2^400, 2^512, 2^1024)

R = Integers(e)
P.<k, p_plus_q, p2_plus_q2> = PolynomialRing(R)
f = k * (n^2 + n + 1 + (n+1) * p_plus_q + p2_plus_q2) + 1

print(small_roots(f, bounds, m=3, d=4))
# This generates a 256*245 matrix and took around 200 seconds to compute.

Part III: The final touches⌗

Well... I am a bit tired. I decided to play Legend of Zelda and found I am unable to solve the puzzles inside, too. Maybe the best thing I should do is to tweet.

Soon after I tweeted, I realised that $p^2 + q^2$ is actually $(p+q)^2 - 2n$. In that way I do not need to treat $p^2 + q^2$ as another unknown - 1024 bits of entropy reduced. Since the entropy is 912 bits, which is much smaller than 2048 bits. By intuition this should work!

bounds = (2^400, 2^512)

R = Integers(e)
P.<k, p_plus_q> = PolynomialRing(R)
f = k * (n^2 - n + 1 + (n+1) * p_plus_q + p_plus_q^2) + 1

print(small_roots(f, bounds, m=3, d=4))
# This generates a 64*58 matrix and took around 150 seconds to compute.
# Output: [(245962077700976781389651438762467784060458007726399012831680541230865888041508191613184353923990248850900264645309752826, 24061328198598730023892644418337616625129173971437927448877972244319015467758683782803490794256724311673381106878622466514439272631375460573992290498030162)]

It did! We have successfully recovered $k$ and $p+q$. We can solve for $p$ and $q$ with a quadratic equation (the roots of $x^2 - (p+q)x + pq = 0$ are $p$ and $q$). Following that, we can compute $\phi$ and the private key. Eventually we can recover the flag:

pbctf{I_love_to_read_crypto_papers_and_implement_the_attacks_from_them}

I love to read crypto papers and... I don't.