Tags: vdf crypto 

Rating: 5.0

# Pow-Pow

**Points:** 299 (13 solves)

**Challenge Author:** defund

**Description:**

> It's a free flag, all you have to do is wait! Verifiably.
>
> `nc mc.ax 31337`

## Challenge

```python
#!/usr/local/bin/python

from hashlib import shake_128

# from Crypto.Util.number import getPrime
# p = getPrime(1024)
# q = getPrime(1024)
# n = p*q
n = 20074101780713298951367849314432888633773623313581383958340657712957528608477224442447399304097982275265964617977606201420081032385652568115725040380313222774171370125703969133604447919703501504195888334206768326954381888791131225892711285554500110819805341162853758749175453772245517325336595415720377917329666450107985559621304660076416581922028713790707525012913070125689846995284918584915707916379799155552809425539923382805068274756229445925422423454529793137902298882217687068140134176878260114155151600296131482555007946797335161587991634886136340126626884686247248183040026945030563390945544619566286476584591
T = 2**64

def is_valid(x):
return type(x) == int and 0 < x < n

def encode(x):
return x.to_bytes(256, 'big')

def H(g, h):
return int.from_bytes(shake_128(encode(g) + encode(h)).digest(16), 'big')

def prove(g):
h = g
for _ in range(T):
h = pow(h, 2, n)
m = H(g, h)
r = 1
pi = 1
for _ in range(T):
b, r = divmod(2*r, m)
pi = pow(pi, 2, n) * pow(g, b, n) % n
return h, pi

def verify(g, h, pi):
assert is_valid(g)
assert is_valid(h)
assert is_valid(pi)
assert g != 1 and g != n - 1
m = H(g, h)
r = pow(2, T, m)
assert h == pow(pi, m, n) * pow(g, r, n) % n

if __name__ == '__main__':
g = int(input('g: '))
h = int(input('h: '))
pi = int(input('pi: '))
verify(g, h, pi)
with open('flag.txt') as f:
print(f.read().strip())
```

## Solution

The challenge presents us with a verifiable delay function (VDF), which (if correctly implemented) requires us to compute

$$
h \equiv g^{2^T} \pmod n.
$$

This requires us to perform $T = 2^{64}$ squares of $g \pmod n$, which is totally infeasible for a weekend CTF! If we could factor $n$, we could first compute $a \equiv 2^T \pmod{\phi(n)}$, but as the challenge is set up, it's obvious we can't factor the 2048 bit modulus.

Another option would be to pick a generator $g$ of low order, for the RSA group $\mathcal{G} = (\mathbb{Z}/n\mathbb{Z})^*$, two easy options are $g=1$ or $g=-1$. However, looking at `verify(g,h,pi)`, we see that these elements are explicitly excluded from being considered

```python
def is_valid(x):
return type(x) == int and 0 < x < n

def verify(g, h, pi):
assert is_valid(g)
assert is_valid(h)
assert is_valid(pi)
assert g != 1 and g != n - 1
m = H(g, h)
r = pow(2, T, m)
assert h == pow(pi, m, n) * pow(g, r, n) % n
```

First `is_valid(x)` ensures that $g,h,\pi \in \mathcal{G}$ and then the additional check `assert g != 1 and g != n - 1` ensures that $g$ has unknown order.

So if we can't run `prove(g)` in a reasonable amount of time, and we can't cheat the VDF by factoring, or selecting an element of known order, then there must be something within `verify` we can cheat.

First, let's look at what appears in `verify(g,h,pi)` and what we have control over.

We choose as input any $g,h,\pi \in \mathcal{G}$ and from $g,h$ `shake128` is used as a pseudorandom function to generate $m$. Finally, from $m$ we find $r \equiv 2^T \pmod m$.

To pass the test in verify, naively we need to send integers from the output of `h, pi = prove(g)` such that the following congruence holds:

$$
h \equiv g^r \cdot \pi^m \pmod n.
$$

Although this congruence assumes the input $(g,h,\pi)$ have the relationship established by `prove(g)`, what if we instead view this as a general congruence? Let's try by assuming all variables can be expressed as a power of a generator $b$ and attempt to forget about `prove(g)` altogether! For our implementation, we make the choice $b = 2$, but this is arbitary.

$$
g \equiv b^M \pmod n, \quad h \equiv b^A \pmod n, \quad \pi \equiv b^B \pmod n.
$$

From this point of view, we need to try and find integers $(M,A,B)$ such that

$$
b^A \equiv b^{rM} \cdot b^{mB} \pmod n \Leftarrow A = rM + mB
$$

The integers $(m,r)$ are generated from

```python
def H(g, h):
return int.from_bytes(shake_128(encode(g) + encode(h)).digest(16), 'big')

# We can pick these
M, A, B = ?, ?, ?
g = pow(2,M,n)
h = pow(2,A,n)
pi = pow(2,B,n)

# Effectively random
m = H(g, h)
r = pow(2, T, m)
```

and we can effectively treat these integers as totally random. More importantly, the values are unknown until we make a choice for both $g,h$ (and therefore $M,A$).

Our first simplification will be $A = 0 \Rightarrow h = 1$, which simplifies our equation and is a valid input for $h$. Now we need to pick $(M,B)$ such that

$$
0 = rM + mB,
$$

where we remember that the values of $(r,m)$ are only known after selecting $M$, but $B$ can be set afterwards. It then makes sense to rearrange the above equation into the form:

$$
B = -\frac{rM}{m}
$$

To find an integer solution $B$, we then need to find some $rM$ which is divisible by a random integer $m$.

The VDF function which appears in the challenge is based off work by [Wesolowski](https://eprint.iacr.org/2018/623), reviewed in a paper by [Boneh, Bünz and Fisch](https://eprint.iacr.org/2018/712.pdf). There is a key difference though between the paper and the challenge. In Wesolowski's work, $m$ is prime, and finding a $M$ divisible by some large, random prime is computationally hard. The challenge becomes solvable because $m$ is totally random and so can be composite.

To find an integer $M \equiv 0 \pmod m$, the best chance we have is to use some very smooth integer, such as $M = n!$, or $M = \prod_i^n p_i$ as the product of the first $n$ primes. In the challenge author's [write-up](https://priv.pub/posts/dicectf-2022), they pick

$$
M = 256! \prod_i^n p_i,
$$

where they consider all primes $p_i < 10^{20}$. Including $256!$ allows for repeated small factors in $m$. In our solution, we find it is enough to simply take the product of all primes below $10^6$.

To then solve the congruence, we first generate a very smooth integer $M$ and set $g \equiv b^M \pmod n$. From this, we compute $m = H(g,1)$. If $M \equiv 0 \pmod m$ we break the loop, compute $r$ from $m$, then $B(M,r,m)$. Finally setting $\pi \equiv b^B \pmod n$ for our solution $(g,h,\pi)$. If the congruence doesn't hold, we square $g \equiv g^2 \pmod n$ and double $M = 2M$ for bookkeeping, and try again.

Sending our specially crafted $(g,h,\pi) = (g,1,\pi)$ to the server, we get the flag.

## Implementation

**Note:** We use `gmpy2` to speed up all the modular maths we need to do, but you can do this using python's `int` type and solve in a reasonable amount of time.

```python
from gmpy2 import mpz, is_prime
from hashlib import shake_128

##################
# Challenge Data #
##################

n = mpz(20074101780713298951367849314432888633773623313581383958340657712957528608477224442447399304097982275265964617977606201420081032385652568115725040380313222774171370125703969133604447919703501504195888334206768326954381888791131225892711285554500110819805341162853758749175453772245517325336595415720377917329666450107985559621304660076416581922028713790707525012913070125689846995284918584915707916379799155552809425539923382805068274756229445925422423454529793137902298882217687068140134176878260114155151600296131482555007946797335161587991634886136340126626884686247248183040026945030563390945544619566286476584591)
T = mpz(2**64)

def is_valid(x):
return type(x) == int and 0 < x < n

def encode(x):
if type(x) == int:
return x.to_bytes(256, 'big')
else:
return int(x).to_bytes(256, 'big')

def H(g, h):
return int.from_bytes(shake_128(encode(g) + encode(h)).digest(16), 'big')

def verify(g, h, pi):
assert is_valid(g)
assert is_valid(h)
assert is_valid(pi)
assert g != 1 and g != n - 1
m = H(g, h)
r = pow(2, T, m)
# change assert to return bool for testing
return h == pow(pi, m, n) * pow(g, r, n) % n

##################
# Solution #
##################

def gen_smooth(upper_bound):
M = mpz(1)
for i in range(1, upper_bound):
if is_prime(i):
M *= i
return M

def gen_solution(M):
# We pick a generator b = 2
g = pow(2, M, n)
h = 1
while True:
m = mpz(H(g, h))
if M % m == 0:
r = pow(2, T, m)
B = -r*M // m
pi = pow(2, B, n)
return int(g), int(h), int(pi)
M = M << 1
g = pow(g,2,n)

print(f"Generating smooth value M")
M = gen_smooth(10**6)

print(f"Searching for valid m")
g, h, pi = gen_solution(M)

assert verify(g, h, pi)
print(f"g = {hex(g)}")
print(f"h = {hex(h)}")
print(f"pi = {hex(pi)}")
```

## Flag

`dice{the_m1n1gun_4nd_f1shb0nes_the_r0ck3t_launch3r}`

Original writeup (https://org.anize.rs/dicectf-2022/crypto/powpow).