...Like PRNGS to Heaven - bi0sCTF 2025

AeroSol
2025-06-13
Crypto

tl;dr

  • ECDSA signing server with biased nonce
  • Exploitation by modelling a EHNP instance and using z3 Solver for breaking Mersenne Twister

Challenge Points: 818
No. of solves: 19
Challenge Author: AeroSol

Challenge Description

“You hunger to claim victory in a war that ended without you.”

Introduction

This is the challenge I made for bi0sCTF 2025. I wanted to make an EHNP based challenge for sometime now so I made it with some Ultrakill theme.

Given information

From the given files we know

  • There is ECDSA happening using secp256k1 curve.
  • The Private Key is generated using a custom prng function called supreme_PRNG().
  • The Nonce is generated using full_noncense_gen() which internally makes calls to the RMT via sec_real_bits() and partial_noncense_gen().
  • There is a small perform_deadcoin() mini-game happening where you solve a DLP problem.
  • There is a interface through which we can send JSON encoded “routines” to perform 5 different actions:
    • get_encrypted_flag -> gives you the AES-CBC encrypted ciphertext and IV.
    • perform_deadcoin -> gives you the chance to heal your HP bar if you solve a DLP problem.
    • call_the_signer -> signs any arbitrary message and returns r and s values along with nonce_gen_consts and heat_gen.
    • level_restart -> lets you restart the level and regenerates the Private Key and seed for the RMT.
    • level_quit -> well duh, let’s you quit the connection.
  • RMT which seems to have a different seed initialisation function when compared to python’s MT.

Analysis

From quite literally glancing through the signing system, we can tell that the nonce generation and private key generation has some inherent bias and moreover the chunks are non-continuous, so we can model the problem as a EHNP instance and perform LLL to solve it.
Note: the success probability of solving the EHNP from our approach is given in a paper further in this post.

But there seems to be a catch

1
2
3
elif v1_action == "call_the_signer":
    print(LEVEL.call_the_signer())
    V1.update(V1.current_health-20)

The HP will deteriorate by -20 for every message we sign thus limiting us to two signatures before we can query for the encrypted flag.

Now to approach the challenge, we need enough HP to sign at least 5 messages before we can find the private key using LLL.

PRNGS

Let’s analyse each of the PRNGS:

  1. RMT

    • The only difference between python’s MT and RMT is the seedMT() function or more popularly called as Ripley’s Seeding. This version of MT is used in the programming language R.
    • It uses a 32 bit seed and uses the same 32 bit parameters of a standard MT.
    • seedMT() tries to grow a value and update the internal state of the MT. 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      def seedMT(self, seed):
        num = seed
        self.index = self.n
        for _ in range(0,51):
            num = 69069 * num + 1
        g_prev = num
        for i in range(self.n):
            g = 69069 * g_prev + 1
            self.MT[i] = g & self.d
            g_prev = g
        
        return self.MT
    • MT is reversible with z3 Solver and as for seedMT() it can also be easily modelled in z3.

  2. supreme_RNG()

    • It uses the Middle Square Method to generate the next number.
    • MSM is not cryptographically secure as the generated values will decay and remain stagnant producing a very short cycle.

There is also a simple LCG which is used only once per restart as:

1
2
3
4
5
6
7
8
9
10
11
12
def privkey_gen(self) -> int:
    simple_lcg = lambda x: (x * 0xeccd4f4fea74c2b057dafe9c201bae658da461af44b5f04dd6470818429e043d + 0x8aaf15) % self.n

    if not self.cinit:
        RNG_seed = simple_lcg(CORE)
        self.n_gen = self.supreme_RNG(RNG_seed)
        RNG_gen = next(self.n_gen)
        self.cinit += 1
    else:
        RNG_gen = next(self.n_gen) 

        ... 
1
2
3
4
...
self.cinit = 0
self.d = self.privkey_gen()
...

it is only called when self.cinit is 0.

Other important funcs

  • perform_deadcoin() as we have previously established, let’s you play the mini-game where you solve a DLP problem in-exchange for a 32 bit value from the RMT but there is a hard limit of only being able to play this thrice.
  • Now, after analysing deadcoin_verification() and _dead_coin_params(), the mini-game seems to derive it’s exponent from supreme_RNG() which takes its seed from the simple LCG.
  • The simple LCG always produces the value 1569250000 as it is always seeded with CORE and is run only once per level.
  • This value specifically decays to 0 at the 375 cycle.

Now let’s look at full_noncense_gen()

  • It introduces k_m1, k_m2, k_m3, k_m4 which are cryptographically secure but add bias and k_ and _k which are generated from RMT along with benjamin1, benjamin2
  • k_ and _k are both 32 bit values and benjamin1 and benjamin2 are 16 bit values.
  • benjamin1 is split into chunks of one byte and is made to be every alternate chunk in the nonce except for the last alternate chunk where 12 lsb of benjamin2 is used.
  • Both the benjamin values are generated by partial_noncense_gen() and are of the form: $$y \gets b \ \oplus (b \ll s) \ \wedge \ a$$ where $b \in [0,2^{32}]$ and $y,a \in [0,2^{16}]$
  • The full_noncense_gen() also returns n1 and n2 values which are later given as nonce_gen_consts which are equation, _and value from partial_noncense_gen.
  • It also returns cycles which are later given out as heat_gen which denotes the number of calls to RMT before getting the right bit length.

In decor.py we can also see that there are no checks on going beyond 100 HP, so we can try to over-heal and get more signatures.

From all the above information, we can formulate our exploit.

Formulating exploit

  • Restart the level 375 times.

  • Now the exponent in deadcoin_verification() will be 0 so you can easily pass this check three times and get 3 RMT values and reconstruct the seed using z3 Solver. This also sets your HP to 160.

  • Now we sign any arbitrary message five times (our maximum limit) whilst simultaneously accounting for the number of RMT calls from the heat_gen. We can also rebuild both benjamin values using z3 Solver.

  • As there is some bias introduced in the private key, we assign it to the var xbar and also calculate kbar with the appropriate shifts.

  • We can now construct $\pi_{i}$ and $\nu_{i}$ from the below equation: $$d \ = \ \bar{d} \ +\ \sum_{j=1}^{m} 2^{\pi_{j}}d_{j} \ \ , \ \ 0 \leq d_{j} \leq \ 2^{\nu_{j}}$$ using the appropriate shifts and bit lengths

  • Similarly we can construct $\lambda_{i,j}$ and $\mu_{i,j}$ from the below equation: $$k_{i} = \bar{k_{i}} +\sum_{j=1}^{l_{i}}2^{\lambda_{i,j}}k_{i,j} \ \ , \ \ 0 \leq k_{i,j} < 2^{\mu_{i,j}}$$ using the appropriate shifts and bit lengths given in the code.

  • We can now convert this into a CVP instance and use LLL to solve it to find the private key.
    The basis: $$B = \begin{bmatrix}n \cdot I_{x}\\ A&X\\ R&&K \end{bmatrix}$$

    Each of the internal matrices can be referred from this amazing paper by Joseph Surin (EHNP part).

    • In essence let $$x = (r_{1},\dots, r_{x},d_{1},\dots,d_{m},d_{1,1}\dots,d_{x,l_{1}},\dots,d_{x,l_{x}})$$ We would have, $$xB = u$$
      $$u =( \beta_{1} - \alpha_{1}\bar{d},\dots,\beta_{x} - \alpha_{x}\bar{d}, \frac{d_{1}\delta}{2^{\nu_{1}}},\dots,\frac{d_{m}\delta}{2^{\nu_{m}}}, \frac{k_{1,1}\delta}{2^{\mu_{1,1}}},\dots,\frac{k_{1,l_{1}}\delta}{2^{\mu_{1,l_{1}}}},\dots,\frac{k_{x,1}\delta}{2^{\mu_{x,1}}},\dots,\frac{k_{x,l_{x}}\delta}{2^{\mu_{x,l_{x}}}})$$
      So we can let
      $$w = ( \beta_{1} - \alpha_{1}\bar{d},\dots,\beta_{x} - \alpha_{x}\bar{d}, \frac{\delta}{2},\dots,\frac{\delta}{2}, \frac{\delta}{2},\dots,\frac{\delta}{2},\dots,\frac{\delta}{2},\dots,\frac{\delta}{2}$$
      as $w$ is close to the lattice vector $u$, therefore solving a CVP instance with $w$ as the target vector may give us lattice vector $u$ which encodes the secret chunks $d_{j}$ in the $(x+1)^{st}$ to the $(x+m)^{th}$ entries.
      Note: x and d are interchanged from the paper, d here is the private key and x here is the number of equations.

  • Once the private key is found, we can now send {"event" : "get_encrypted_flag"} and can perform AES-CBC decryption on it, you will be left with 10 HP and you get the flag.

Exploit

solve.sage

The flag is bi0sCTF{p4rry_7h15_y0u_f1l7hy_w4r_m4ch1n3}

Aftermath

It looked like the 32 bit seed could be bruteforced and could be solved in an unintended way skipping z3 entirely for the solve (Dorian managed to solve that way) 💀 and Benjamin values not being necessary for the LLL part.