# SEC-T CTF – likeason

On this years SEC-T CTF, I made three challenges. One of the challenges, likeason[1] was given as follows:

#! /usr/bin/env python
import sys

from secret import d, n

def oracle(c, x=1):
res = bin(pow(c, d * x, n)).count('1') & 0x1
return int(res)

while True:
try:
c = [int(x) for x in sys.stdin.readline().split(" ")]
if len(c) == 1:
sys.stdout.write("%d\n" % oracle(c[0]))
else:
sys.stdout.write("%d\n" % oracle(c[0], x=c[1]))
except Exception:
sys.stdout.write("Nope.\n")

sys.stdout.flush()

# e = 0x10001
# c = 32028315366572316530941187471534975579021238700122793819215559206747120150118490538115208229905399038122261293920013020124257186389163654867911967899754432511568776857320594304655042217535057811315461534790485879395513727264354857833013662037825295017832478478693519684813603327210332854320793948700855663229


As we can see, the oracle returns the parity of the bits in the decrypted plaintext. We also know that the ciphertext contained only {" ", ".", "-"}, followed by some random padding. A specific format is actually not needed, but it makes the challenge easier. The reader may notice that it has some resemblence with the Bleichenbacher oracle, but an easier way is to treat it as a regular (but unreliable) LSB (or MSB) oracle. We observe that for any unique query

$\mathbb{P}(\text{overflow}~|~\text{parity flip}) = 1$

but we also have that

$\mathbb{P}(\text{overflow}~|~\text{no parity flip}) = 1/2$.

We may assume random events, although this is not completely true.

Finding the modulus

First we need to find the modulus $n$. This is quite simple. Pick a number $k$ and send $(2^k)^e$ by sending the pair 2**k e to the oracle. We know that parity is always 1 if $2^k < n$. However, when $2^k \geq n$ and $2^{k-1} < n$, the decryption yields $2^k - n$. This may cause a parity flip, but not necessary. So, what can we do about that? Randomization!

Instead, we can send $2^k + r$, where $r$ is a random number, sufficiently small (here, $r < \sqrt{2^{k}}$ works) to not cause overflow when $2^k < n$. Alternatively, we can use a single bit, i.e. $r = 2^j$ for some $j < k$. In this manner, we can send queries and w.h.p detect the parity changes.

Finding the plaintext using known plaintext properties

An efficient way of determining the plaintext is as follows:

First, build a set of parities from sufficiently many queries of the form $\{ \mathcal{O}(c \cdot (2^e)^i : 0 \leq i \leq M \}$, for some integer $M$. This is mostly for caching purposes, so that no redundant calls are needed to be made.

Define an upperbound and lowerbound on the plaintext $m$, $U$ and $L$, respectively. Then, build a search tree using the ideas from attacking LSB (or MSB oracles). If we observe a parity flip, from previous step, then we record a new lowerbound $L \leftarrow \frac12(U + L)$ in its single child node. On the other hand, if there is no flip from previous we cannot be sure (which is the same problem as before, when determining $n$). Define the parity at step $i$ to be $b_i$. Then, recursion will be as follows:

$f(i, U, L) = \begin{cases} f(i+1, U, \frac12(U + L)) & \quad \text{if } b_i \neq b_{i-1}\\ f(i+1, U, \frac12(U + L)), f(i+1, \frac12(U + L), L) & \quad \text{if } b_i = b_{i-1}. \end{cases}$

So, to be certain, we need to investigate both paths (i.e., assuming an overflow and updating the lowerbound and no overflow, hence setting a new upperbound $U \leftarrow \frac12(U + L)$). We can do so, and prune paths by using that the bytes for which the upperbound and lowerbound agrees need to be in the alphabet for the message (see above). This was the intended solution, and probably easiest to find.

Finding the plaintext using randomization

Will be added when I have time to describe it in detail.

[1] An anagram for snakeoil in honor to Crown Sterling.