UTCTF 2021 - Prove No Knowledge

Challenge

I’ve been trying to authenticate to this service, but I’m lacking enough information.

nc crypto.utctf.live 4354

Solution

As the name suggests, this challenge is centered around 0 knowledge proofs. Opening up the giving connection, we see that the user is requested to provide $ g^r \pmod p $, where g and p are provided. Additionally, the user is also provided $ y = g^x \pmod p $, where $ x $ is some secret. A quick google search leads to the wikipedia article on 0-knowledge proofs. In particular, there is a section about fooling another party into believing you can solve the DLP, namely, you know the secret x. So, the goal of this challenge will be to fool the server into believing we can always solve the DLP.

With this challenge, there are two scenarios that can happen. In either, the user is first requested to give the server $ g^r \pmod p $, which we can calculate, since we are given both $ g $ and $ p $. The question then becomes what $ r $ to use. In the first scenario, after sending $ g^r \pmod p $, the server requests $ r $ to verify if what you sent previously was correct. In this case, we can simply calculate $ r $ to be any value we want, send $ g^r \pmod p $, then $ r $. In the second scenario, after sending the first value, the server requests $ (x + r) \pmod{p-1} $ instead. The idea here is that $ g^{(x + r) \pmod{p-1}} \equiv g^x \times g^r \equiv yg^r \pmod p $, where the $ \mod(p-1) $ is just there to simplify by Fermat’s Little Theorem. So, the server intends to take our second input and check that it’s equal to $ yg^r $, which should only happen if we know $ x $. However, there is a way to fool the server: since we are given $ y $, we can simply calculate $ g^r = g^{r’}y^{-1} $, such that $ y * g^r \equiv yg^{r’}y^{-1} \equiv g^{r’} \pmod p $. Then, we can send this as $ g^r \pmod p $, and send $ (x + r) \pmod{p-1} = r’ $, so that the server will verify our inputs. So, we have a way to fool the server in either scenario.

The main issue with this is that you have to guess which of the two scenarios will happen so that you can precompute values accordingly. However, most proper implementations of this check will use several randomized rounds so that you successively have to win many 50-50s to convince the server that you know the secret. Thus, it’s normally effectively impossible to actually fool the server. However, this challenge doesn’t have that defense; some quick testing quickly shows that the rounds simply alternate between the two scenarios, so it’s trivial to fool the server on each check. I wrote the following script to do this automatically:

 1from pwn import *
 2from sympy import mod_inverse
 3from random import randrange
 4host, port = "crypto.utctf.live", 4354
 5
 6r = remote(host, port)
 7r.recvuntil("g: ")
 8g = int(r.recvline())
 9r.recvuntil("p: ")
10p = int(r.recvline())
11r.recvuntil("y: ")
12y = int(r.recvline())
13
14rn = 1
15
16while rn < 257:
17	if rn % 2:
18		r.recvuntil("Send g^r mod p.")
19		ran = randrange(p)
20		r.sendline(str(pow(g, ran, p)))
21		r.recvuntil("Send r.")
22		r.sendline(str(ran))
23	else:
24		r.recvuntil("Send g^r mod p.")
25		ran = randrange(p)
26		C = (pow(g, ran, p) * mod_inverse(y, p)) % p
27		r.sendline(str(C))
28		r.recvuntil("Send (x + r) mod (p - 1).")
29		r.sendline(str(ran))
30	rn += 1
31	print(f"round {rn} passed")
32r.interactive()

utflag{questions_not_random}