Catino

Our cat is cute right!

nc challs.nusgreyhats.org 10520

main.py:

#!/usr/bin/env python3

from secrets import randbits
from decimal import Decimal, getcontext

FLAG = '<REDACTED>'

ind = 100
randarr = []
maxRound = 5000
winTarget = 100000
winIncr = 1000

getcontext().prec = maxRound + 1000

def prep():
    global randarr
    print("\nGenerating random numbers....", flush=True)
    n = Decimal(randbits(2048))
    p = Decimal(1/4)
    k = str(n**p).split('.')[1]
    randarr = list(k)
    print("Generation complete!\n", flush=True)


def nextRand():
    global ind
    assert ind < len(randarr)
    res = int(randarr[ind])
    ind += 1
    return res


def menu():
    print("Hey there, I am catino! Meowww ~uwu~")
    print("Play a game with me and win the flag!\n")

    print("Game rule:")
    print("1. You start with $0")
    print("2. On each round, Catino choose a single digit secret number (0-9)")
    print("3. You try to guess Catino secret's number")
    print(f"4. If the guessed number matches the secret, then you earn ${winIncr}")
    print("5. If the guessed number does not match the secret, then you lose all of your money!")
    print(f"6. You win when you have ${winTarget}!")
    print(f"7. The game ends forcefully when the number of round exceeds {maxRound}", flush=True)

if __name__ == "__main__":
    menu()
    prep()

    round = 0; wrong = 0; player = 0

    while (player < winTarget and round < maxRound):
        round += 1
        print(f"Round: {round}")
        userIn = int(input("Guess the number (0-9): "))
        num = nextRand()
        if (num == userIn):
            print(f"You got it right! it was {num}")
            player += winIncr
        else:
            print(f"You got it wrong... it was {num}")
            player = 0
        print(f"You have ${player} left")
    
    if (player >= winTarget):
        print("Congratulations you are now rich! \(★ω★)/")
        print(FLAG)
    else:
        print("Sokay.. Try again next time (っ´ω`)ﾉ(╥ω╥)")

Challenge Overview

This challenge revolves around a number guessing game where the numbers we must guess are generated by taking digits from the decimal part of the fourth root of some large number. There are a total of up to 5000 rounds and to get the flag we must correctly guess the digit for 100 consecutive rounds. After each round, we are told what was the correct digit. Essentially, we may obtain an approximation of the decimal part up to 4900 digits and need to compute the next 100 digits.

Solution

There is a (famous?) paper which describes an approach to solving the problem we have in this challenge. The paper shows that the bits of algebraic numbers are not random, and that given an approximation of an algebraic number, we may recover its minimal polynomial (and hence, better approximations) using lattice reduction techniques. An algebraic number is a number that is a root of a non-zero univariate polynomial with rational coefficients. Let's show that the digits we are trying to recover form an algebraic number.

$k$ is an algebraic number

Let $n$ be the randomly generated 2048 bit number. Write $n^{\frac{1}{4}} = a + k$ where $a \geq 1$ and $k < 1$. Here, $a$ represents the whole part of $n^{\frac{1}{4}}$ and $k$ is the decimal part. Then,

And so,

Now, consider the polynomial $f \in \mathbb{Z}[x]$ given by

This polynomial has rational coefficients (since $a$ is an integer), and more importantly, has $k$ as a root. Therefore, $k$ is an algebraic number. Now, let's see how to recover $f$ given an approximation of $k$.

Recovering $f$

We want to recover $f$ because it will allow us to calculate $k$ up to arbitrary precision. Suppose we know an approximation $k_0$ of $k$ (say, the first $D = 4900$ digits¹). The key idea is that $f(k_0) \approx 0$, i.e.,

This is a nice property because it means lattices are likely around the corner! Consider the lattice with basis given by the rows of $\mathbf{M}$:

Notice that the linear combination

generates the lattice point

(i.e. $\mathbf{t} \mathbf{M} = \mathbf{a}$) where $s$ is relatively small, depending on how good of an approximation $k_0$ is. $s$ will dominate the length of $\mathbf{a}$ because of the scaling factor $10^D$, but it is still smaller than other non-zero lattice points. Omitting a proper analysis, we can conclude that LLL is likely to disclose $\mathbf{a}$ and hence we can recover $f$ by reading the coefficients off the entries of $\mathbf{a}$.

Solving the challenge

Of course, Sage has a function to do almost exactly what was described in the previous section, so we can use that to implement the solution. Since we need to gather close to 4900 digits, we need to send the guesses and parse the responses in batches to avoid the server timeout.

from pwn import *
from decimal import Decimal, getcontext
from sage.arith.misc import algdep

getcontext().prec = int(6000)

conn = remote('challs.nusgreyhats.org', 10520)
conn.recvuntil(b'Generation complete!')

k = '0.'
payload = b'\n'.join([b'0']*100)
conn.recvuntil(b'(0-9):')
for _ in range(49):
    conn.sendline(payload)
    lines = conn.clean().splitlines()
    for l in lines:
        if b'it was ' in l:
            k += l.decode().strip().split('it was ')[1]

f = algdep(Reals(16278)(k), 4)
k_full = f.change_ring(Reals(16800)).roots()[1][0]
k_next = str(k_full)[2+4900:2+4900+100]

for d in k_next:
    conn.sendline(d.encode())

conn.interactive()

grey{FunFact_OurGreyCatIsActuallyABlackCat_LFP9eux3884hd2ag}