Tags: misc dodge
Rating:
# 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.
