Rekting Rektsa

This is a write-up for the Rektsa Challenge, featured in the qualifications for SIGSEGv2 conference. Being a total CTF noob but having some experience in solving crypto challenges this is the one I focused on and actually the only one I solved. I will explained how I proceeded.

The Challenge

For this challenge the source was given in the form of a python file, encrypt.py.

This is its content :

#!/usr/bin/python2.7

import sys
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG
from gmpy2 import invert
from math import log

p = getPrime(1024)
q = getPrime(1024)
r = getPrime(1028)

e =  0x10001
N = p * q * r
phi = (p -  1) * (q -  1) * (r -  1)

print  'N:', N
print  'phi:', phi %  2**2050
print  'r:', r

print  'Give me d: '

sys.stdout.flush()
try:
    d =  int(raw_input())
except:
    print  'Invalid input!'
    exit(1)

if d == invert(e, phi):
    print  'Congratulations: %s' $FLAG
else:
    print  'Nope!'
exit(1)

The challenge use a RSA-like system with 3 primes instead of the usual 2 and provide us with N, Phi mod 2**2050 and r (the third prime). The challenge itself doesn’t have a lot to do with cryptography in the end because the only task we have to achieve is to provide d, the modular inverse of 65537 by Phi. So the only thing that we need to achieve is finding the value of Phi.
As an addition to the challenge, the tcp socket that we will use to send the answer closes in 2 seconds.

Analysis

Finding Phi from its modulo is basically finding how much time do we need to add 2**2050 to get the initial value. We have a good idea on how big this value is gonna be because we know the size of the primes used to make phi (it is a value in the thousand of bits range which tells us that bruteforcing it is not an option). But more important than the size of the primes we have N.
Modifying the source code to print the value of log(N/(2**2050),2) gives us results around 1024 and we find similar results to the same operation applied to Phi. In fact if we print the difference between N//(2**2050) and Phi//(2**2050) we can find a very small offset which varies depending on the primes but is usually located in the range [3;7].

Solving

A nice person would try every possible offset of this range and check that they found the good Phi but I’m not a nice person so I picked one offset (5 seemed the one coming out the most) in the range and just ran my program 3 times for the flag to show up.
My final solution after parsing the output of the program is therefore:

socket.sendline(str(invert(65537,phi_mod+((n // 2**2050)-5)*(2**2050))))
print socket.recvline()

And flagged : Congratulations: sigsegv{th1s_1s_4_cr1m3...4_mult1cr1m3!!!}