# CTFZone 2018 -- PlusMinus> **Category**: PPC> **Description**:> To solve this task, you need to put arithmetic operators into expression inthe right order.> Allowed operators: + - / * (). Final expression must involve all the suppliednumbers and the number order must be the same as in original expression. Thelast nuber in the line should be an answer.> nc ppc-01.v7frkwrfyhsjtbpfcppnu.ctfz.one 2445> Example:> 2 3 5 4 > (2-3)+5
# Writeup
## PerformanceThe described algorithm is polynomial asymptotic, so it's **very slow** and due tothe fact of the time limit, exploit gets a flag just with some probability. The suggested below script should be run via thread pool until the flag is gotten.
## Design### RecursionRecursion is good enough to define an algorithm that generates all valid expressions.The arguments of a recursive function: possible movements, count of unclosedparenthesis, a stack of unused numbers, current solution, a needed value of the expression.
### Basic versionIf the stack of numbers is empty, we eval the current solution and return it if it's nearly equal to the needed value of the expression, otherwise return `None`.
### MovementsValid movements: `['+', '-', '\*', '/', '(', "POP"]`. They describes what can we do atcurrent point of solving. There's no `)` because it isn't a typical case, so, we decidedto put it basing on count of unclosed parenthesis. `POP` indicates we can pop num fromthe stack and put it at the end of the solution.
### The priorityI kept this putting order: `')', "POP", '+', '-', '\*', '/', '('`.`
The `(` has the least priority because we want to minimize the length of finding the solution. The rest of the priority order was chosen empirically.
### A little bit of optimizationsWe shouldn't put `)` if the last put operator is `(` because expressions like`a + (b)` don't make much sense.
Also, I didn't generate expressions with nested parentheses. I hoped the generating expressions by the server wouldn't be much difficult. I was lucky enough, so I got the flag after 2 hours of the running script in a thread pool.
## Numbers formatThe server sometimes sends numbers in a specific format (e.g. `.0`) and expects you send number back in the same format (not `0` or `0.`), so you shouldn't lose original numbers.
## Exploit[Here](./exploit.py) you can take a look at my exploit.
# SummaryI believe the best possible solution for this task exists. The suggested algorithmthat should be run on thread pool doesn't seem like the optimal.