Pow-Pow
Authors: Jack
Tags: crypto, VDF
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
#!/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
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:
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.
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
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, reviewed in a paper by Boneh, Bünz and Fisch. 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, 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.
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}
