# SharifCTF 7 – LSB Oracle

In this Crypto challenge, we are given an executable file which, given an input, returns the least significant bit of the decryption of the input (with respect to some RSA public key, which they also provide). They also provide an encryption of the flag, which we must decrypt.

Enter a valid ciphertext, and I'll return the LSB of its decryption. Enter -1 when you're done.
1
1
Enter a valid ciphertext, and I'll return the LSB of its decryption. Enter -1 when you're done.
2
1
Enter a valid ciphertext, and I'll return the LSB of its decryption. Enter -1 when you're done.
0
0
Enter a valid ciphertext, and I'll return the LSB of its decryption. Enter -1 when you're done.
-1
Ciao!


First of all, since the decryption is provided by an executable, it seems possible that you could recover the private key by reversing the executable. Reversing things is hard though, and this problem has a relatively straightforward solution that just exploits the LSB oracle.

Let $N=pq$ be the public key modulus, and let $C = f^e$ be the ciphertext, where $f$ is the encoded flag and $e$ is the public key exponent. One thing we can immediately do is plug in $C$ to the oracle, and get the LSB of $f$. Unfortunately, from here it’s not clear how to get the second least significant bit of $f$ and proceed in this direction. Instead, we will actually construct $f$ from the most significant bit inwards to the least significant bit.

Note that $(kf)^{e} = k^{e}f^{e} = k^{e}C$, so we can compute the encryption of $kf$ for any choice of $k$. In particular, we can ask the oracle for the LSB of $2f$. Ordinarily, this value should be $0$, since $2f$ is even, but this number is taken modulo $N$ before the LSB is returned. If $2f > N$, then there will be a carry, and (since $N$ is odd), the LSB of $2f - N$ will be $1$. We can therefore distinguish whether $f \in [0, N/2)$ or $f \in [N/2, N)$ via the LSB of $2f$.

We can repeat this logic inductively for higher powers of two to get more information about the high order bits of $f$. Let’s say we know that $f$ lies in the interval $[aN/2^{b}, (a+1)N/2^{b}]$. Then, by computing the LSB of $2^{b}f$, we can determine whether $f \in [2aN/2^{b+1}, (2a+1)N/2^{b+1})$ or $[(2a+1)N/2^{b+1}, (2a+2)N/2^{b+1})$. Repeating this $\log N$ times, we can recover the value of $f$.

Here is some Python code that implements the above attack.

from pwn import *
from Crypto.Util.number import *

N = 120357855677795403326899325832599223460081551820351966764960386843755808156627131345464795713923271678835256422889567749230248389850643801263972231981347496433824450373318688699355320061986161918732508402417281836789242987168090513784426195519707785324458125521673657185406738054328228404365636320530340758959
C = 2201077887205099886799419505257984908140690335465327695978150425602737431754769971309809434546937184700758848191008699273369652758836177602723960420562062515168299835193154932988833308912059796574355781073624762083196012981428684386588839182461902362533633141657081892129830969230482783192049720588548332813
E = 65537

p = process(['lsb_oracle.vmp.exe', '/decrypt'])
p.recvline()
p.recvline()
p.recvline()
p.recvline()
p.recvline()

def decrypt_bit(x):
p.sendline(str(x))
p.recvline()
return int(p.recvline())

int_st = 0
int_end = N

def get_first(st, end, f):
# finds first x in [st, end-1] s.t. (p*x)%N > N/2
left = st
right = end

while right-left > 1:
mid = (right+left)/2
if (f*mid)%N > N/2:
right = mid
else:
left = mid
return right

pow2 = pow(2, E, N)

cpow = pow2
f = 1
while int_end - int_st > 1:
print int_st, int_end, int_st-int_end

attempt = (cpow*C)%N
imid = get_first(int_st, int_end, f)
print imid

if decrypt_bit(attempt)==0:
int_end = imid
else:
int_st = imid

cpow *= pow2
f *= 2

print int_st
print long_to_bytes(int_st)

# SharifCTF{65d7551577a6a613c99c2b4023039b0a}