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.
Enter a valid ciphertext, and I'll return the LSB of its decryption. Enter -1 when you're done.
Enter a valid ciphertext, and I'll return the LSB of its decryption. Enter -1 when you're done.
Enter a valid ciphertext, and I'll return the LSB of its decryption. Enter -1 when you're done.

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'])

def decrypt_bit(x):
    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
            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
        int_st = imid

    cpow *= pow2
    f *= 2

print int_st
print long_to_bytes(int_st)

# SharifCTF{65d7551577a6a613c99c2b4023039b0a}

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s