Decrypt the cipher text with a pinhole.

$ nc cry1.chal.ctf.westerns.tokyo 23464

pinhole.7z

**Summary:** attacking RSA using decryption oracle leaking 2 consecutive bits in the middle.

In this challenge we are given an access to a decryption oracle, which leaks only 2 consecutive bits in the middle of the decrypted plaintext:

b = size(key.n) // 2 def run(fin, fout): alarm(1200) try: while True: line = fin.readline()[:4+size(key.n)//4] ciphertext = int(line, 16) # Note: input is HEX m = key.decrypt(ciphertext) fout.write(str((m >> b) & 3) + "\n") fout.flush() except: pass |

We are also given an encrypted flag and our goal is to decrypt it.

Recall that plain RSA is multiplicatively homomorphic: we can multiply ciphertext by $r^e$ and the plaintext is the multiplied by $r$: we need only the public key to do it.

Let’s multiply the ciphertext by $2^{-e}$. Assume that the oracle gives bits $(a,b)$ for the ciphertext $C$ and $(c,d)$ for the ciphertext $2^{-e}C\pmod{N}$. Then there are two cases:

- If the message $M$ is even, then dividing by 2 is equivalent to shifting it right by one bit.
- Otherwise, $M$ is transformed into $(M + N) / 2$.

In the first case due to the shift we must have $d = a$. In the second case, depending on the carries it can be anything. However, if $d \ne a$ then we learn for sure the the LSB of $M$ is odd. As a result we get this probabilistic LSB oracle:

- $a,b = oracle(C);$
- $c,d = oracle(2^{-e}C);$
- If $d \ne a$ then $LSB(M) = 1.$

How can we use it?

Let’s assume that we confirm that $LSB(M) = 1$. Otherwise we can “randomize” the ciphertext by multiplying it by some $r^e$ (we will be able to remove this constant after we fully decrypt the message) until we get the condition hold.

Remember that we can multiply the message by any number $d$, what do we learn from the oracle when it happens that $LSB(dM \mod{N}) = 1$? Let $k = floor(dM/N)$, then:

$$dM – kN \equiv 1 \pmod{2}.$$

We know that $N$ is odd and $M$ is odd, hence

$$k = d + 1 \pmod{2}.$$

We also know $d$, therefore we learn parity of $k$. If $d$ is small, we can enumerate all possible $k$, since $k < d$. Each candidate $k_0$ gives us a possible range for the message (from the definition of $k$):
$$\frac{kN}{d} \le M < \frac{(k+1)N}{d}.$$
**Example**: assume that $LSB(5M \mod{N}) = 1$. Then $k$ is even and is less than $5$. The possible candidates are $0,2,4$. That is, the message $M$ must be in one of the three intervals:

$$0 \le M < N/5, \text{or}$$ $$2N/5 \le M < 3N/5, \text{or}$$ $$4N/5 \le M < 5N/5.$$ So we have reduced the possible message space. Note however that these intervals have size at least $N/d$. If we want to reduce the message space to only few messages, we would need large $d$. Then we will not be able to check all candidates for $k$!

But there is a nice trick, we can deduce the possible intervals for $k$ for given $d$ from obtained previously intervals for $M$! I learnt this trick from this article, explaining the Bleichenbacher’s attack (see section “Narrowing the initial interval”). Indeed, if $l \le M \le r$ then

$floor(\frac{dl}{N}) \le k \le floor(\frac{dr}{N}).$

To sum up, here is the algorithm structure:

- Set possible range for $M = [0,N-1]$.
- Set small $d$.
- Loop:
- If $oracle_{LSB}(dM \mod{N}) = ?$ then try another $d$.
- For each possible interval for $M$:
- Deduce possible range for $k$.
- Iterate over all $k$ with parity different from $d % 2$ and obtain union of possible intervals for $M$.
- Intersect these intervals with the previous intervals for $M$.
- Increase $d$, for example double it.

There is a small detail. If we keep doubling $d$, then number of intervals for $M$ grows quickly and makes the algorithm slower. To keep the number of intervals small, we can multiply $d$ by let’s say 1.5 instead of 2 when there are too many intervals.

Here’s python code (works locally by simulating oracle using the secret key):

from libnum import invmod, len_in_bits from libnum.ranges import Ranges # added recently from Crypto.PublicKey import RSA with open("secretkey.pem", "r") as f: key = RSA.importKey(f.read()) with open("publickey.pem", "r") as f: pkey = RSA.importKey(f.read()) nmid = len_in_bits(pkey.n) // 2 C = int(open("ciphertext").read()) n = pkey.n e = pkey.e i2 = pow(invmod(2, n), e, n) def oracle(c): m = key.decrypt(c) v = (m >> nmid) & 3 a = v >> 1 b = v & 1 return a, b def oracle_lsb(ct): a, b = oracle(ct) c, d = oracle( (i2 * ct) % n ) if d != a: return True return None rng = Ranges((0, n - 1)) assert oracle_lsb(C), "need blinding..." print "Good" div = 2 ntotal = 0 ngood = 0 while 1: ntotal += 1 div %= n C2 = (pow(div, e, n) * C) % n if not oracle_lsb(C2): div += 1 continue ngood += 1 cur = Ranges() for ml, mr in rng._segments: kl = ml * div / n kr = mr * div / n # ensure correct parity if kl % 2 == div % 2: kl += 1 k = kl while k <= kr: l = k * n / div r = (k + 1) * n / div cur = cur | Ranges((l, r)) k += 2 rng = rng & cur print "#%d/%d" % (ngood, ntotal), "good", div, "unknown bits:", len_in_bits(rng.len), "num segments", len(rng._segments) if rng.len <= 100: print "Few candidates left, breaking" break # heuristic to keep fewer intervals for M if len(rng._segments) <= 10: div = 2*div else: div = div + (div / 2) + (div / 4) M = int(open("message").read()) print "Message in the %d candidates left?" % rng.len, M in rng |

One interesting thing is that the success probability of the described LSB oracle depends on $N$ strongly. For some $N$ it is equal 50% and for some $N$ it is only about 10%. This happens due to different carry chances depending the middle bits of $N$. Have a look at @carllondahl‘s writeup, where he investigates more cases for the oracle.

## 1 comment

## Sharif CTF 2016 – LSB Oracle – Crypto Challenge – Capture the Swag says:

December 19, 2016 at 14:10 (UTC 3)

[…] Cool challenge that I’ve wanted a reason to solve for a while because I always miss these in CTFs of the past (Tokyo Westerners CTF had a good, harder one previously). […]