# Dodge Writeup
### Defenit CTF 2020 - Misc 906 - 3 solves
> Dodge it! `nc dodge.ctf.defenit.kr 1357`
#### Hints
- This dodge is multi-tasking-dodge(4 tasks), get more than 120 points!- You will get your score after the game.- You can change the focused game with q, e and moving direction of the player with w, a, s, d.Focused game is marked with `*` next to the number.
#### Observation
To start the game, solve 3 byte PoW. Four dodge games start with following below rules.
1. Map    - Map with width 40, height 20.2. Player(Marked as `p` on Map)    - Player position randomly initialized with random velocity.    - Player cannot move diagonally. Only `wasd`.    - Player can only move one block at a time.    - If no input, player keeps its velocity.3. Bullet(Marked as `*` on Map)    - Bullets are spawned every 3 rounds starting with 2nd round.    - Bullets can move diagonally.    - Bullets can be overlapped, even when they are first spawned.    - Bullets have constant magnitude of speed.4. Collision    - If player/bullet collides with wall(Marked as `#`) will bounce with following [elastic collision](https://en.wikipedia.org/wiki/Elastic_collision).    - Each of bullets do not collide together. They just overlap.    - If player collides with bullet, game ends.
Each rounds give single point. If I get more than 120 points(pass more than 120 rounds), I win and get flag.
#### Exploit
Let me implement heuristic algorithm to dodge. The key point is that, **most of bullets can be deterministically tracked**.
First two rounds are free. No bullet is spawned. New bullet is added every 3 rounds, starting from third round(`i = 1`). Use these rounds to track player position and velocity. I can track and verify position and velocity of bullet by the following algorithm.
1. Round `3 * i`: New bullet is spawned.    - If new bullet is not detected, give up tracking, meaning that overlapping occured.    - If not, store new bullet position(`y1, x1`).2. Round `3 * i + 1`: New bullet moves.    - If new bullet is not detected, give up tracking, meaning that overlapping occured.    - If not, store new bullet position(`y2, x2`).3. Now estimate new bullet's position and velocity.    - Past two positions known, so velocity(`y2 - y1`, `x2 - x1`) known.    - Since velocity known, future position of new bullet can be estimated.4. Round `3 * i + 2`: Check estimated result is true.    - Let new bullet position be (`y3, x3`).    - Estimated position be (`y2 + (y2 - y1)`, `x2 + (x2 - x1)`)    - If estimated result is false, It means that at `3 * i + 1`th round, bounce occurred during previous round. Therefore position/velocity was wrong. Recalculate postition/velocity by using position(`y3, x3`) and (`y2, x2`), so velocity(`y3 - y2`, `x3 - x2`)
By iterating above algorithm, I could mostly track all position the bullets. After knowing position and velocity of bullets, future positions are deteministic. Using determined future bullet positions, I could send control commands to avoid bullets. I easily bypassed over 120 rounds, and got until more than 150. Example map while dodging 148th round:
```###########################################                                        ##     *                       **         ##  *                             *       ##                *      *                ##  *                                *    ##    *        *                          ##                         *              ##  *                      *              ##              *           *             ##      *                                 ##                             * **   *   ## *     *  *           *                 ##                 *    *       *         ##             *                   *  *   ##                 *p     *       *  *    ##    *            *                      ##       *** *                            ##          *  *                          ##    *       *                          *##      *   *                             ###########################################```
I get flag:
```Defenit{dodg3_d0dg3_d0dge_d0dge_dodge}```
Exploit code: [solve.py](solve.py)
#### Other interesting solution
`for i in {1..5000}; do {python a.py >/dev/null &} ; done;`. Wait until you get very lucky :P.