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

but we also have that

.

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

Finding the modulus

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

Instead, we can send , where is a random number, sufficiently small (here, works) to not cause overflow when . Alternatively, we can use a single bit, i.e. for some . 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 , for some integer . This is mostly for caching purposes, so that no redundant calls are needed to be made.

Define an upperbound and lowerbound on the plaintext , and , 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 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 ). Define the parity at step to be . Then, recursion will be as follows:

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 ). 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.