Sep
05

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

#### 1 comment

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

[…] 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). […]