# 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*qn = 20074101780713298951367849314432888633773623313581383958340657712957528608477224442447399304097982275265964617977606201420081032385652568115725040380313222774171370125703969133604447919703501504195888334206768326954381888791131225892711285554500110819805341162853758749175453772245517325336595415720377917329666450107985559621304660076416581922028713790707525012913070125689846995284918584915707916379799155552809425539923382805068274756229445925422423454529793137902298882217687068140134176878260114155151600296131482555007946797335161587991634886136340126626884686247248183040026945030563390945544619566286476584591T = 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
```pythondef 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
```pythondef H(g, h):    return int.from_bytes(shake_128(encode(g) + encode(h)).digest(16), 'big')
# We can pick theseM, A, B = ?, ?, ?g = pow(2,M,n)h = pow(2,A,n)pi = pow(2,B,n)
# Effectively randomm = 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.
```pythonfrom gmpy2 import mpz, is_primefrom 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}`