Really Smart Acronym, of course, is RSA. Looking at the code, it uses PyCrypto to generate a RSA key to encrypt the flag. You also get one encryption and 1024 decrypts, but you only get the last bit of the decrypts. At first I thought it could be Franklin-Reiter related-message attack, but there is not enough information for that.
Google to the rescue! Using all the information we have, I googled “RSA LSB oracle” and found https://crypto.stackexchange.com/questions/11053/rsa-least-significant-bit-oracle-attack. From there, the method is given, but we still need to find e and N for the attack to work.
e is easy. Since it uses PyCrypto, e = 65537. As for N, that’s what the one encrypt is for. If you realize you can pass negative numbers for the encrypt, then it becomes easy. The encrypted message is m^e mod N, so if you pass -1, it is -1^65537 mod N = N – 1.
from pwn import * sh = remote('challenges1.hexionteam.com', 5000) sh.recvuntil('Flag: ') cipher = int(sh.recvline().decode().strip()) #print(cipher) sh.recvuntil('m => ') sh.sendline('-1') n = int(sh.recvline().decode().strip()) + 1 mult = pow(2, 65537, n) #print(mult) def get_lsb(num): sh.recvuntil('> ') sh.sendline(str(num)) return int(sh.recvline().decode().strip()) high = n low = 0 for i in range(1024): cipher *= mult cipher %= n lsb = get_lsb(cipher) if lsb == 0: high = (high + low) // 2 else: low = (high + low) // 2 print(high)