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}`
