Secret Service

Description

Hello there,

In order for us to trust you, you must prove the you either have access to our RSA keys or already have the encrypted command: "FLAGPLX" (flag please thanks, in short).

Come back to us when you have the flag so we know who we're talking to.

http://secretservice.challenges.bsidestlv.com/index.php

Solution

The website provides 2 interfaces. The first one is called “Execute a Command”:

But in fact, it receives a base64-encoded number, returns the decrypted value, in text to format.

The second interface is called “Create Demo Commands”:

This interface presents a drop list of values, and encrypts them, returning a base64 string, as it should be sent to the first interface.

The goal is to send in the first interface, the encrypted value of “FLAGPLX”.

For this interesting challenge, we’ll propose 2 solutions: first the intended one, and then, an elegant one

  1. The intended solution

We don’t know what are private and public RSA keys used by this challenge. But we can see by the size of the encrypted strings received using the 2nd interface that it’s RSA-256.

Also, sending “1” (in base64: “MQ==”) to the decrypt interface returns “1”. This indicates the first vulnerability: no padding. From the size of the encrypted value “2” (as received in the second interface), we can deduce that the public exponent (“e”) is not 3, but probably the other classic value (65537). It can be in fact any value, but this is a safe bet, even if it doesn’t help for now.

Playing with the second interface with different values than the ones found in the drop-down list leads to something interesting. Some values returns some random values, and some returns real encrypted values. E.g.

http://secretservice.challenges.bsidestlv.com/index.php?action=demo&value=10
returns different values every time, and each of them are decrypted as gibberish.
But http://secretservice.challenges.bsidestlv.com/index.php?action=demo&value=11
returns every time the same encrypted value of 11.

How can we use that to construct the encryption of “FLAGPLX”? For that, we use another vulnerability that was left in the decryption interface: it doesn’t check that the encrypted value is less than “n”. Taking the value of the encrypted “2” and multiplying it by itself gives us:

(44950212844456690224840967364926980361299115474741976132427291503764555110057)2 = 2020521634761959213956959964170116468842444132795734683180575187844425880920275118393733286671080411387807242172023597551747229132837716407656271382543249

Sending this value (base64) for decryption returns: 4. This is because me * me = m2e mod n, but that shouldn’t be accepted by the decryption service, because it leads to the following forgery:
a message is encrypted by RSA after converting it to a big integer. So FLAGPLX is: 19787091622775896 and its factorization is: 2 * 2 * 2 * 83 *179 * 166479535091

So, by multiplying the encryption of these factors will give us a big numbers that when RSA decrypted as Cd mod n will return the “FLAGPLX”. And as it turned out, that is exactly what the “demo interface” was: out of the closed list, it was returning the encryption only of the prime numbers, so that it was possible to multiply their encryption, and achieve any encrypted message, without having the RSA keys.

That was the solution, as intended by its author. My comment to him was that it should have left the non-primes out of the demo list. The first reason was for coherence: having in the closed list only prime numbers (or strings that converted to prime numbers) would have been implemented as only one rule, and not two like in the case of the original problem. But there was another, better reason…

  1. The elegant solution

During the challenges, we were happy with the previous solution, and haven’t looked back. But after the CTF was closed, we discussed our solutions with our friends from other teams. RECLASS found a way to get the public key, and since it was only RSA-256, with an effort of a few minutes of computation.

The observation was that:

(Me mod n * Me mod n) mod n = M2e mod n
But x mod n means x+kn
So, (Me mod n * Me mod n) – (M2e mod n) = kn

Since the “demo list” includes composite numbers (4,6,8 and 9), it’s possible to get some kn (n being the RSA modulus and k an integer >= 0)

It was even possible to reduce k by calculating the GCD of two such calculations. At this point, RECLASS just factorized the rest, got p and q, multiplied them to get n and encrypted “FLAGPLX”.

In fact, it was not necessary to get p and q (and would have been impossible if a strongest version of RSA would have been used, like RSA-1024). By just doing one GCD and check for “little” factors (e.g. using msieve or just using “factordb” web site), we were left with one big composite number of ~256, and that was n, directly usable to calculate the encrypted message.

This second solution was possible only because there were composite numbers in the demo list. The fact that a “standard” e was used was also helpful.