Recon

This challenge had no hint and no downloadable part, it was just an ip address and a port. So let’s fire up a netcat instance and see what we’ve got:

$ nc 161.97.176.150 4449
Heres the flag!
848630917051893087050233654298398605870572417880786546004017
Enter a value for me to encrypt
> 

Ok, we’ve got the flag and it looks like it’s encrypted, so we’re gonna have to get a sense for what’s going on behind the scenes just by looking at plaintext/ciphertext pairs. Let’s go ahead and input some test values!

...
> 0
0
Enter a value for me to encrypt
> 1
1
Enter a value for me to encrypt
> 2
405518048190558088634310202493589629933137815074909354184258
Enter a value for me to encrypt
> 3
736006545906739541375355456172047521086543171458483024077845
Enter a value for me to encrypt
> 4
28287358476740482187432197716177875720480221862681611755228
Enter a value for me to encrypt
> 5
118164290266571816954914720950212104095415618051341152315626
Enter a value for me to encrypt
> 6
624812891132136026422679120907420745781542687268597375922197
Enter a value for me to encrypt
> 7
116537355815898013151362092320072496065628205811108848493645
Enter a value for me to encrypt
>

Figuring out the encryption algorithm

At first, it doesn’t look like it’s giving us much information, but after looking at it for some time we might notice something. Have you seen how e(0)=0 and e(1)=1?

By e(x) I’m denoting the encrypted value of x

Another interesting fact is that the output gets larger as the input grows and eventually it just shrinks a bit, then it starts growing again. All of this gives us the idea that there might be some modular arithmetic going on here. At this point, I’m guessing the encryption function looks something like this e(x) = f(x) mod n where f is an unkown function.

Before I go any further, let me state that all we’re doing here is just pure speculation. We don’t have the code that’s running in the backend, so we’re only guessing. With that out of the way, let’s keep on going.

It’s clear that f can’t be a linear function, since f(0)=0 and f(1)=1 (supossing our previous guess about how e looks is correct), and this would mean that f would have to be the identity function. Also, f looks pretty chaotic, it suddenly jumped from 1 to 405518048190558088634310202493589629933137815074909354184258 (at least, its remainder modulo n did). After trying with different families of functions I came to the conclusion that f(x) looks like x ^ r (I’m using the symbol ^ to denote exponentiation, due to the lack of mathematical notation capabilities in Markdown) where r is some unknown value. Why should this be the case? Well, the values for f(0) and f(1) give us the idea that f should be some kind of polynomial, but there can’t be a lot of additions and/or subtractions involved. Keep in mind, up to this point this is nothing but a wild guess.

Let’s review what we’ve got up to this point, we have the hypothesis that e(x) = x^r mod n for some unkown value of r and n. Ok, let’s try something, let’s input -1, if our hypothesis is correct, we should get back either 1 or n-1 (depending on whether r is even or not):

Enter a value for me to encrypt
> -1
943005855809379805541572246085636463198876208104363395594608

Cool, this number is larger than the ones we’ve seen up to this point, this should give us the idea that we’re on the right track (since n is the modulus, n-1 should be the greatest value we can get). Remember, if f(x)=-1, then e(x)=n-1, so adding 1 we should get the value for n. Now our encryption function is missing just one value: r. So let’s try and calculate it! We’re not doing anything too clever, let’s just take some known plain/cipher-text pair and test every possible value for r until we get the answer. The code for this looks like this:

pt = 2
ct = 405518048190558088634310202493589629933137815074909354184258
n = 943005855809379805541572246085636463198876208104363395594609

def encrypt(x, r):
	return (x ** r) % n

i = 0
while encrypt(pt, i) != ct:
	i += 1
print(i)

It took a few seconds, but it gave us the value 65537. So, with this value figured out, we should be able to reproduce the encryption algorithm used in the backend. Let’s test our hypthesis for a value we haven’t seen up to this point. Keep in mind our encryption function now looks like this:

r = 65537
n = 943005855809379805541572246085636463198876208104363395594609
def encrypt(x):
	return (x ** r) % n

After trying this out with some values we’re able to see that our predicted ciphertext does indeed match the actual ciphertext sent by the backend. We were successfully able to figure out the encryption algorithm!

Decrypting the ciphertext

We’ve got the encryption mechanism, and the encrypted value. Our equation now looks like this: f^r mod n = c where f denotes the flag’s value, c is the first ciphertext we got at the very beginning, and the other two are the constants we’ve just calculated in the previous section. On top of that, after a quick google search, we find that r is prime. This is the point where I thought: “Cool, I have one equation and one unkown, it’s just a matter of solving for the unkown! I can even use Fermat’s little theorem, knowing that r is prime!”.

After banging my head against the wall for a while, on of my teammates brought to my attention that this algorithm has a name: it’s called RSA, and it’s pretty robust (no wonder I wasn’t being able to solve it!). Anyway, playing with the equation for a while might be useful, if only because one gets to develop some intuition for the problem and what makes it interesting.

Quick sidenote on RSA: The idea behind RSA is that n should be the product of two (large) primes: p and q, those primes should be large enough to make it computationally unfeasible to factor n. The recipeint, on the other hand, should have those two primes, as they will be used for decryption. The number r (the exponent to which the plaintext is raised) should be co-prime to lcm(p-1, q-1), so that there exists a number d which is the multiplicative inverse of r modulo lcm(p-1, q-1). Then, when the intended recipient gets the encrypted message, all they have to do is raise c (the ciphertext) to the power of d and take it’s remainder mod n. That should give back the original plaintext. That was a lot of information, I know, so: TLDR; We need to find the prime factors of n

So the security of this algorithm depends on the difficulty of factoring n, but in this case n is not that big. It’s big enough so that a naive factorization will take too long, but it’s no bigger than that. So I googled a bit and found an online calculator that would let me get the primes p and q relatively quickly. After a few seconds' wait, we’ve got all the parameters we need to decrypt the ciphertext:

import math
from Crypto.Util.number import long_to_bytes

cflag = 848630917051893087050233654298398605870572417880786546004017

p = 882152190529044698706991746907
q = 1068983182191997868299760689187
n = 943005855809379805541572246085636463198876208104363395594609 
r = 65537

assert n == p*q

lcm = math.lcm(p-1, q-1)
d = pow(r, -1, lcm)

def encrypt(x):
	return (x ** r) % n

def decrypt(x):
	return (x ** d) % n

flag = decrypt(cflag)

print(long_to_bytes(flag))

After waiting for a somewhat long time it becomes clear that is code is not very efficient, but if we use Python’s pow function instead it becomes quite manageable:

import math
from Crypto.Util.number import long_to_bytes

cflag = 848630917051893087050233654298398605870572417880786546004017

p = 882152190529044698706991746907
q = 1068983182191997868299760689187
n = 943005855809379805541572246085636463198876208104363395594609 
r = 65537

assert n == p*q

lcm = math.lcm(p-1, q-1)
d = pow(r, -1, lcm)

def encrypt(x):
	return pow(x, r, n)

def decrypt(x):
	return pow(x, d, n)

flag = decrypt(cflag)

print(long_to_bytes(flag))

And we get the flag:

y0u_d0nt_n33d_4nyth1ng

Post written by @OctavioGalland