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.