easy pseudo random - zer0pts ctf 2021

challenge

The following code and the outputs was given. It seems that the flag is encrypted with random numbers. We can get the upper k bits of two consecutive values, named w0 and w1. We can get the flag when the prediction of pseudo random numbers can be achieved using these.

# task.sage
from Crypto.Util.number import*
from flag import flag

nbits = 256
p = random_prime(1 << nbits)
Fp = Zmod(p)
P.<v> = PolynomialRing(Fp)

b = randrange(p)
d = 2
F = v^2 + b

v0 = randrange(p)
v1 = F(v0)

k = ceil(nbits * (d / (d + 1)))
w0 = (v0 >> (nbits - k))
w1 = (v1 >> (nbits - k))

# encrypt
m = bytes_to_long(flag)
v = v1
for i in range(5):
    v = F(v)
    m ^^= int(v)

print(f"p = {p}")
print(f"b = {b}")
print(f"m = {m}")
print(f"w0 = {w0}")
print(f"w1 = {w1}")

solution

Let

$F(v)=v^2+b$ over

${\mathbb{F}}_p$ and

$n$ be the nbits. Then

$v_0$ and

$v_1$ are given by the following equations.

$$\begin{array}{rcl}{v}_0& =& 2^{n-k}{w}_0+x\\ v_1& =& 2^{n-k}{w}_1+y\end{array}$$
Here

$x$ and

$y$ are unknown quantities. If they are found, we can expect the pseudo random sequences. Expanding

$v_1$, we get further

$$\begin{array}{rcl}{v}_1& =& F(v_0)\\ & =& (2^{n-k}{w}_0+x{)}^2+b \end{array}$$
Thus, we get the following equation

$$\begin{array}{rcl}f(x,y)& =& 2^{n-k}{w}_1+y-((2^{n-k}{w}_0+x{)}^2+b)\\ & =& y+c_2{x}^2+c_{1}x+c_0\\ & =& 0\end{array}$$
where

$c_i(i=0,...,2)$ are suitable constants (They are explicitly depend on know parameters).
For easy understanding, the equation is written

$y+c_2{x}^2+c_{1}x+c_0\equiv 0\mathrm{mod}p$ as a congruence in integers.

Now,

$k=\lceil \frac{nd}{d+1}\rceil whered=\mathrm{deg}f$, and therefore we can believe that required roots are found by Coppersmith's method.

# solve.sage
from Crypto.Util.number import *
from small_roots import small_roots

nbits = 256
with open("output.txt") as f:
	while True:
		buf = f.readline()
		if not buf:
			break
		exec(buf)

Fp = Zmod(p)
P.<v> = PolynomialRing(Fp)
F = v^2 + b
Pf.<x, y> = PolynomialRing(Fp)

d = 2
k = ceil(nbits * (d / (d + 1)))
delta = float(1 / (d + 1))

bounds = (floor(p^delta), floor(p^delta))
f = (y + w1 * pow(2, nbits - k)) - ((x + w0 * pow(2, nbits - k))^2 + b)

# multivariate coppersmith
res = small_roots(f, bounds)
print(res[0])

x0 = res[0][0]
x1 = res[0][1]
v0 = x0 + w0 * pow(2, nbits - k)
v1 = x1 + w1 * pow(2, nbits - k)
print(v0, v1)

v = v1
for i in range(5):
    v = F(v)
    m ^^= int(v)
print(long_to_bytes(m))

Here is the flag zer0pts{is_blum_blum_shub_safe?}