These two challenge are very similar: the only difference is that in the first one we can do how many requests we want to the server, while in the second one we are limited to 5 requests. We’ll treat only the second, showing a solution that works in 4 requests.
print('Ho, ho, ho and welcome back!') print('Your list for this year:\n') print('Sarah - Nice') print('Bob - Nice') print('Eve - Naughty') print('Galf - ' + hex(flag_encrypted)[2:]) print('Alice - Nice') print('Johnny - Naughty')
for i in range(5): choice = menu()
if choice == '1': m = bytes_to_long(input('\nPlaintext > ').strip().encode()) used.append(m)
print('\nEncrypted: ' + str(encrypt(m)))
elif choice == '2': c = int(input('\nCiphertext > ').strip())
if c == flag_encrypted: print('Ho, ho, no...')
else: m = decrypt(c)
for no in used: if m % no == 0: print('Ho, ho, no...') break
else: print('\nDecrypted: ' + str(m))
elif choice == '3': print('Till next time.\nMerry Christmas!') break
print('Too many requests made... Disconnecting...')
The code looks very simple, basically we’re given the encrypted flag, encrypted with a secure RSA key with the standard exponent (as it is not specified when creating the key). We can encrypt whatever we want, but we can’t decrypt things that, when decrypted, are multiples of the flag or multiples of the things we’ve encrypted.
The first thing is to recover the modulus : suppose we encrypt two different integers obtaining , then we have that
and so , most likely with if we choose the integers such that .
Once we recovered the rest is trivial: take the least prime such that it divides the decrypted flag (I’m lazy so I waited for it to be equal to 2), so we have
then simply decrypt 2 to get and multiply it with the previous result to get the decimal value of the flag. Use whatever long_to_bytes function to get the string.
Here’s the Python code for the attack, I did the last part by hand using the interactive mode from pwntools, the script simply recovers .