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 be the public key modulus, and let be the ciphertext, where is the encoded flag and is the public key exponent. One thing we can immediately do is plug in to the oracle, and get the LSB of . Unfortunately, from here it’s not clear how to get the second least significant bit of and proceed in this direction. Instead, we will actually construct from the most significant bit inwards to the least significant bit.

Note that , so we can compute the encryption of for any choice of . In particular, we can ask the oracle for the LSB of . Ordinarily, this value should be , since is even, but this number is taken modulo before the LSB is returned. If , then there will be a carry, and (since is odd), the LSB of will be . We can therefore distinguish whether or via the LSB of .

We can repeat this logic inductively for higher powers of two to get more information about the high order bits of . Let’s say we know that lies in the interval . Then, by computing the LSB of , we can determine whether or . Repeating this times, we can recover the value of .

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}