Tokyo Westerns/MMA CTF 2016 – Pinhole Attack (Crypto 500)

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:

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