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:

1. Receive our original share, given by the server (we input that)
2. Calculate and print fakeShare1 (we take that share and give it to server as first input)
3. Take reveal value given by the server
4. Calculate and print secret (this we will use in the end when server asks for real coordinates)
5. 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.