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