Friday, 24 May 2019

Locksmith Writeup - Security Fest CTF 2019

This challenge is related to the concept of Lockpicking. In this challenge, we need to connect to remote service running at:

Once we connect, we are provided with the following information:

We are presented with two arrays of 9 numbers.

Array 1: This is the initial state of the numbers on the lock. Right now, it is in locked state.
Array 2: This is the target state of the numbers on the lock. This indicates the unlocked state.

We can send the inputs in the range 1 to 9 to the remote service. Based on each input, a specific value is added to each dial of the lock as shown below:

We need to keep sending the inputs till the numbers in Array 1 are the same as the numbers in Array 2.

And to solve the challenge, we need to unlock the lock 100 times. In each round, we are presented with a new initial and target state of the lock.

I used z3 and pwntools to solve this challenge.

pwntools was used to handle the network communication between my machine and the server.
z3 was used to solve the equations generated based on the responses received from the server.

Since each number (in the range: 1 to 9), adds a specific value to each number of the Array. I used this information to find out how many times each number has to be sent to the remote service to get the desired result.

For example, let the initial state of the lock be:

initial = [x1, x2, x3, x4, x5, x6, x7, x8, x9]

After we send the input number 1, the modified state becomes:

modified = [y1, y2, y3, y4, y5, y6, y7, y8, y9]

So, the diff is:

diff = [y1 - x1, y2 - x2, y3 - x3, y4 - x4, y5 - x5, y6 - x6, y7 - x7, y8 - x8, y9 - x9]

Le us denote, y1 - x1 with a1 which indicates the difference between the number in position 1 of the current array and the previous array when the input number is 1. Similarly,

y2 - x2 =b1
y3 - x3 = c1
y9 - x9 = i1

diff array for input 1 = [a1, b1, c1, d1, e1, f1, g1, h1, i1]

Similarly for other input numbers, the diff arrays will be:

[a2, b2, c2, d2, e2, f2, g2, h2, i2]
[a9, b9, c9, d9, e9, f9, g9, h9, i9]

if our target value in the lock is X, then we need to solve the equations of the form:

a1 * a + a2 * b + a3 * c + a4 * d + a5 * e + a6 * f + a7 * g + a8 * h + a9 * i == X
i1 * a + i2 * b + i3 * c + i4 * d + i5 * e + i6 * f + i7 * g + i8 * h + i9 * i == X

So, we have a system of 9 linear equations each containing 9 unknown values. This can be solved using z3.

Here is my code for solving this challenge:

Once all the rounds are successfully solved, the server responds with the flag as shown below:

Flag: sctf{1_gUeS5_tH4T_is_whY_th3Y_c4lL_iT_a_m0Nte_caRlO_bAnk}