# treasure, DownUnder CTF 2021, Wrietup

This is a pretty cool task where we need to break the secret sharing system to get the flag. We are given the source code and the server address. Let’s look inside the source.

We are looking for the flag and see that it is used only once in the code and it’s printed out in `main`

function on certain conditions. Let’s consider these conditions.

First of all, the flag is printed, when `real_coords`

variable, which is our input, equals to some `REAL_COORDS`

, which we don’t know. (See the green arrow and third bubble.) So first let’s note that we have to find `REAL_COORDS`

value.

But, before this check we have to pass three more `if`

constructions. First condition (bubble 1) is that value `secret_coords`

returned from function `run_combiner()`

is not coords (the call to `is_coords(secret_coords)`

must return `false`

). We will look at `run_combiner()`

later to see what we can do about it.

Second condition once again checks if `secret_coords`

returned from another call to `run_combiner()`

is coords (this time `is_coords(secret_coords)`

must return `true`

).

And the third condition, is the `secret_coords`

value equals to `FAKE_COORDS`

.

Note also, that function `run_combiner()`

requires value `shares`

that is returned from `create_shares(REAL_COORDS)`

call in the start of `main`

.

All right, now that we’ve considered conditions to get the flag, let’s think about how we can fulfill them. We need to find out what `create_shares()`

and `run_combiner()`

functions do. Code for `create_shares()`

is fairly simple:

It gets two random numbers `r1, r2`

and calculates three values using these numbers and secret passed to the function. Remember, that this function is called only once with value `REAL_COORDS`

. Let’s rewrite the calculation in a fancy mathematical notation to get the better view:

And values `s1`

, `s2`

and `s3`

are returned from the function as the array. `main()`

function later prints out `s1`

for us as our share, but values `s2`

and `s3`

are kept secret. To make things clear I point out that now we know `s1`

, but values `r1`

, `r2`

, `secret`

, `s2`

and `s3`

are unknown.

Okay, now let’s look at the `run_combiner()`

It just asks us to input our share and then calls to `reveal_secret()`

. `reveal_secret()`

performs some calculation with passed shares and returns the calculates `secret`

value. Let’s write that calculation down, I will rename `secret`

to `reveal`

here, you will see why.

Now, let’s say we input the share (`s1`

) we actually got from server, and values `s2`

and `s3`

are the same as were calculated in `create_shares()`

’cause we can’t control them. In this case the equation may be presented as follows

Gather similar values together

Open parentheses

Now terms r1 and r2 may be removed because

And we are left with

**Note: instead of writing negative powers I will just use fractions. That will make more compact and readable formulas, but I do not mean the actual division, remember that we cannot divide in modular arithmetic.**

In conclusion, if we input the valid share, function `run_combiner()`

will return the actual secret value, which is `REAL_COORDS`

. And after first call to `run_combiner()`

function `main()`

will print that value out. That’s great, because we want to know `REAL_COORDS`

value to pass one of the checks. Unfortunately, if we enter the valid share, function `is_coords()`

will return `true`

and we will fail the first check.

## Passing check 1

So we have to modify our share value before entering it. How exactly we will modify it? Well, when we enter it first time, we need it to be some value so that passing it with other shares to `run_combiner()`

will eventually return us the value with which we could calculate the secret. Why is that? Just because we will need `REAL_COORDS`

value and the only time we can get some information from server is after we enter our share the first time. When we enter our share the second time we need `run_combiner()`

to return `FAKE_COORDS`

and after that we will have to input `REAL_COORDS`

.

Let’s see now what value we want `run_combiner()`

to return for us so we can calculate `REAL_COORDS`

from it. Consider how our share is calculated:

To get the secret from it we would want to know value

so that we could do the following

and get the value of `secret`

, which is `REAL_COORDS`

. All right, now let’s think how ca we modify our share so that `run_combier()`

will return

Let’s look at how shares are combined

Note that, if instead of power 3 we had power 2, we would receive what we want.

So what we want, is to create `fakeShare1`

value such that

To do that, we can just raise our real share `s1`

to some power `x`

such that

And that yields us the equation

If you wounder why we changed the modulus, that’s because when we have modulo `n`

calculations with powers, powers are considered modulo `Phi(n)`

. Remember RSA scheme:

And that works because

Fortunately for us, we have `p`

that is a prime number, and Euler’s function for prime `p`

is just `p — 1`

. That’s why we do calculations modulo `p — 1`

.

Okay, now with value `x`

we can modify our share to make it `fakeShare1`

And when we are asked to enter our share the first time, we will put that value. `run_combiner()`

will perform some calculations and return us

`is_coords()`

will return `false`

for this value and we will pass first check.

## Passing check 2 and check 3

Cool, now we can calculate the secret value. But we also have to enter our share the second time. This time we need to modify this value so that `run_combiner()`

returns `FAKE_COORDS`

. This will get us through checks 2 and 3 ( `is_coords()`

will return `true`

and `secret_coords`

will be equal to `FAKE_COORDS`

).

Let’s consider `reveal`

calculation once again

What should we do to make `reveal = FAKE_COORDS`

?

One step at a time. First of all, let’s add `FAKE_COORDS`

to the equation (call it `fake`

). We will multiply our original share with `fake`

to make

We can remove terms `r1`

and `r2`

Second step would be to remove `secret`

term. For that, we need to have `secret`

to the power of 2, not 3. For that, we need to find the value `y`

such that

And this yields us the equation

Now we can multiply our share with `secret`

to the power of `y`

and get

And now we are left with

So let’s instead of multiplying our share with `fake`

in the first place we multiply it with `fake`

to the power of multiple inverse of `3`

modulo `p — 1`

, i.e.

Let’s call this power `z`

.

Finally, we can write the equation for `fakeShare2`

Putting it into `reveal`

calculation gives us the following

And that’s what we want.

## Getting it all together

Now that we are done with the math, we can write the auxiliary script to solve the challenge. We could fully automate it, but there is no need. So, what our script will do:

- Receive our original share, given by the server (we input that)
- Calculate and print
`fakeShare1`

(we take that share and give it to server as first input) - Take reveal value given by the server
- Calculate and print secret (this we will use in the end when server asks for real coordinates)
- Calculate and print
`fakeShare2`

(this we will give to server when it asks for second input).

And here is the script itself

And the solution process is presented on the screenshot below.