Math, math, and more math! :)
There was a loth of math in this picoCTF, and Tick Tock was a pretty cool one.
The problem was under the reverse engineering category, but it was definitely mor math related then reverse engineering, as all you had to understand in terms of verersing, was what the python script was doing.
If we remove all the visualization stuff, for spinning the clock all the problem revolves around these functions
1 2 3 4 5 6 7 8 9 10 11 12 13
the count() function: that is nothing but a modulus operation with some ascii art :)
1 2 3 4 5 6 7
and the powmod() function: which is nothing but a pow, again with some graphics for displaying the clock.
then the application does the following:
it takes the first argument number we supply, it takes the list named secretz, containing 17 tuples
1 2 3
and cycles over each tuple using the count() function, which as said earlier is nothing but a modulus operation.
1 2 3 4 5 6 7 8 9 10 11
it performs the modulus operation between the number we supplied and the second value of the tuple, and checks that the result of the operation matches the first value, if the result is correct it procedes to the next tuple, if it fails, it exits.
for example, if we assume that x is the first argument we submitted it checks that the following statement is true
and if it is, it performs the check for the next tuple.
So the first part of the problem was to find a value x that would satisfy the equivalence for every tuple in the secretz list.
This problem can be solved using the chinese residiant theorem which can be implemented in python as follows:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Once we find the number that satisfies the first part of the problem, the second function comes in play
1 2 3 4 5 6
and what happens here is that the last two modulus operand of the secretz list, are multiplied one another and used as a modulus to compute the following equation
- x is our first argument
- y is our second argument
- and N is the number obtained by the multiplication said above
Solving this second part is easy, because there is the Euler’s theorem stating
so.. Walfram Alfa to the rescue!
let’s calculate as this will give us the correct value to submit to the program as second parameter.
Unfortunately the clock script was buggy, and during the last step returned an exception, but in the end the calculated numbers were correct, and scored the flag successfully on the web site.