~robin_jadoul/ictf-pub

ictf-pub/ictf2021/ZKPoD/README.md -rw-r--r-- 1.7 KiB
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)