77790edcRobin Jadoul My ImaginaryCTF 2021 stuff a month ago

#ZKPoD

Category: Crypto Difficulty: Medium/Hard Author: Robin_Jadoul

#Description

Pointing at a butterfly Is this a zero knowledge proof of decryption?

#Distribution

• zkpod.py
• nc

#Deploy notes

Needs flag.txt, zkpod.py and private.txt

#Solution

The protocol provides an RSA-encrypted version of the flag, and offers to take any ciphertext, decrypt it and sign a fixed message with it as private key, by computing a Schnorr signature. The signature consists of $(r, s)$ with $r = g^k \pmod P$ and $s = k - m\cdot H(r || M)$, where $m$ is the decrypted message, $M$ is the fixed signature message and $k$ is a uniform random number in the range $[0, P - 1)$. With the Legendre symbol, we can deduce the parity of $k$. When $E = H(r || M)$ is not divisible by 2, the product $m\cdot E$ is only even when $m$ is. Combining these two observations allows us to deduce the parity of $m$ from the parities of $s$ and $k$, exactly when $E$ is odd, and so 50% of the time. If $E$ is even, we simply try the same RSA ciphertext again to try again.

From this, we can implement a standard LSB oracle attack on RSA to recover the flag.

#Some other solutions, found by players:

• Binary search $a$ such that $ax = N$ thanks to being able to distinguish $a < N < p - 1$ (due to A~Z)
• Extended version of the LSB oracle with partial Pohlig-Hellman (due to NeketmanX)
• Recover 1024 - bitlen(flag) bits of $k$ (since H hashes to only 1024 bits) and mount a lattice attack with HNP (due to vishiswoz and $in) • Get$g^x$and$g^{x/2 \mod N}$to recover a single bit at a time jby checking$g^x \overset{?}{=} \left(g^{x/2 \mod N}\right)^2 \mod p\$ (due to rbtree)