pwnthem0le

Home Blog About GitHub

pwnthem0le is a Turin-based, hacking students group born out of CyberChallenge 2018. Read more about us!

19 March 2020

ångstromCTF 2020 - RSA-OTP Writeup

by matpro98

For this challenge we are provided with the server source:

from Crypto.Util.number import bytes_to_long
from Crypto.Random.random import getrandbits # cryptographically secure random get pranked
from Crypto.PublicKey import RSA
from secret import d, flag
# 1024-bit rsa is unbreakable good luck
n = 136018504103450744973226909842302068548152091075992057924542109508619184755376768234431340139221594830546350990111376831021784447802637892581966979028826938086172778174904402131356050027973054268478615792292786398076726225353285978936466029682788745325588134172850614459269636474769858467022326624710771957129
e = 0x10001
key = RSA.construct((n,e,d))

f = bytes_to_long(bytes(flag,'utf-8'))
print("Encrypted flag:")
print(key.encrypt(f,0)[0])

def otp(m):
	# perfect secrecy ahahahaha
	out = ""
	for i in bin(m)[2:]:
		out+=str(int(i)^getrandbits(1))
	return out

while 1:
	try:
		i = int(input("Enter message to sign: "))
		assert(0 < i < n)
		print("signed message (encrypted with unbreakable otp):")
		print(otp(key.decrypt(i)))
	except:
		print("bad input, exiting")
		break

At the beginning I was a little bit confused by the comments: usually when something is pointed to as secure, it is what you have to break; unfortunately not this time. So I spent some hours trying to factorize and to attack directly the otp function. Then I tried to modify one of our attempt to break otp: in fact it is an oracle and in particular it leaks the lenght of the decrypted message. The first thing to notice is that if we send to the server and , then (calling the decrypted ):

Don’t worry, we can still recover our flag: in fact is odd, thus if we could operate on the decrypted we ccould also change it from odd to even by adding . But what happens? We are working modulo , so we have and . This means that if at some point is even, then sending we know the length of , otherwise we know the length of .

We can extend the reasoning to more than one bit. Let’s construct $r$ in this way:

We can now notice that after steps we know the parity of (let’s call it ), so we can recover the last bits of as . That’s all: we can recover all the bits of , leading us to the flag actf{this_is_not_what_i_meant_when_i_told_you_to_use_rsa_with_padding}.

tags: crypto  oracle