Categories
Cryptography hexionCTF 2020

“Really Smart Acronym”

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)

Leave a Reply

Your email address will not be published. Required fields are marked *