# Midnight Sun CTF 2020 Quals - Snake++ >###### tags: `coding` >[name=whysw@PLUS] ## Attachments `nc snakeplusplus-01.play.midnightsunctf.se 55555` ## Challenge There are two modes of snake game, for human and for AI. When you select AI mode, the log file which is zipped and base64 encoded is given. These are rules of snake game. ``` Instructions ------------ You are about to play a game of snake. The snake can be controlled with 4 actions with the following keys: '' (nothing, or just enter) Keep going ' ' (space) Fire 'L' Turn left 'R' Turn right In the world, there are 2 types of items you can eat by colliding with them: 'A' Apple Grows snake by 1 'B' Bad apple Shrinks snake by 1 The snake can shoot at one of these apples to make it disappear. To do so, the head of the snake must be facing the apple before you press Space. If the snake collides with the world boundary, you lose. If the snake reaches length 42, you win. Good luck! --- Press enter to continue --- ``` And snake AI is programmed by new language. Below is a description of the syntax of this programming language. ``` Snake++ Programming Language ============================ Using the Snake++ programming language, you can analyze the snake's environment and calculate its next move, just like in the regular game. Registers and memory -------------------- Snake++ operates on 8 registers and 3 memory areas. We distinguish between text and numbers. There are 4 registers than can hold text, named: apple, banana, cherry and date. There are 4 registers that can hold numbers, named: red, green, blue and yellow. All 3 memory areas are 30 by 20 cells in size (just like the map of the world). There is one RW memory area for text (TEXTRAM), and one for numbers (NUMRAM). There is also one readonly memory area for text (TEXTROM). Comments -------- Any line starting with the '#' character is ignored. Loading, storing and assigning ------------------------------ The following operators allow loading from and storing into memory: Loading from RAM: <register> ~<8~~~ <x> <y>; Storing into RAM: <register> ~~~8>~ <x> <y>; Loading from ROM: <register> ~<8=== <x> <y>; Note that there is no operator to store into ROM. The memory area is automatically selected based on the register and the operator. For instance, to load a number from NUMRAM row 7, column 5 into the blue register: blue ~<8~~~ 5 7; Likewise, to store a text from the apple register into TEXTRAM row 0, column 12: apple ~~~8>~ 12 0; Finally, since there is only ROM for text data: banana ~<8=== 5 6; Values can also be assigned to registers using the := operator: blue := 5; cherry := "abc"; Arithmetic ---------- The following arithmetic operations are defined on numbers: + - / * And for text, only + is defined. Formulas can be enclosed in parentheses. e.g.: blue ~<8~~~ (red+6) (green/2); red := blue + green * 2; banana := cherry + "x" + date; Statements ---------- A program in Snake++ consists of a sequence of statements, each ending with a semicolon. Each of the load, store and assignment operations described above are statements. There are also statements for logging numbers and text (log and logText respectively), returning a value to the game, if-then-else branching and sliding to a label. Logging Statements ------------------ to log the value of the blue register + 3: log blue+3; to log the banana text register: logText banana; Return Statement ---------------- Returning a text value will end the Snake++ program and hand control back to the Snake game in progress. The returned value can be used to control the snake, and should be "", " ", "L" or "R". (See game instructions). Only text values can be returned. example: return "R"; If-Then-Else Statement ---------------------- Works as you'd expect: if <condition> then <sequence of statements> fi; if <condition> then <sequence of statements> else <sequence of statements> fi; Of note is the condition. It is possible to compare numbers to numbers, or text to text. For numbers, the operators are: ==, <>, >, >=, <, <= For text, the operators are: == and <> In each case, <> means "does not equal". Example: if blue < yellow-3 then logText "Looking good"; else logText "This is not good"; blue := yellow - 3; fi; Labels and Slide Statement -------------------------- It is possible to label a statement by placing a label in front of it. Labels are sequences of characters enclosed with curly braces. For instance, the following statement is labeled {example}: {example} blue := 5; During execution, it is possible to slide over from the current statement to another labeled statement. Example: green := 0; {loop} green := green + 1; if green < 10 then log green; slide {loop}; fi; Caution: it is only possible to slide to a labeled statement in the same or the encompassing codeblock. Program execution ----------------- The execution environment for your Snake++ program is kept alive during the entire game. Before the game moves the snake, it will execute your (entire) Snake++ program to determine what to do. You should use the return statement to return one of "", " ", "R" or "L". For each execution of your program, only the TEXTROM and registers will be altered. TEXTROM will contain the worldmap, as also seen when playing the game as a human. All registers are wiped. The coordinates of the head of the snake are placed in the blue (X-coordinate) and yellow (Y-coordinate) registers. ``` ## Solution ### Algorithm - My team member coded BFS using Snake Language, but it was caught by the time limit. After that, he advised me that I should make a heuristic algorithm. - The algorithm that I thought was ![](https://i.imgur.com/B1GWdSZ.png) 1. snake goes up. 2. then hits the wall. 3. turn right. 4. move forward until it hits the right wall. 5. turn right and move forward until it hits the bottom wall. 6. turn right(therefore, looking to the left.). 7. Check if there is an apple on the vertical line. 1. if there is an apple(no matter it is bad or not), turn right. 2. else, move forward(then repeat step7). 8. while moving upward, check if the snake is facing an apple. 1. if it is facing good apple(A), eat it. 2. if it is facing bad apple(B), shoot it. 9. repeat! - The problem occurs when bad apples are at the bottom. But it's just -1 so I just ignored it. --- ### Solver #### python interact This file interacts with snake game. You should run it in debug mode(because flag doesn't have "Result: ")! ```python:interact.py= from pwn import * from base64 import b64decode import zipfile from os import getcwd p = remote("snakeplusplus-01.play.midnightsunctf.se",55555) p.sendlineafter("Your choice: ","2"); for _ in range(2): p.sendlineafter("--- Press enter to continue ---",""); with open("code.txt", "r") as file_code: p.sendafter("Enter your program code, and end with a . on a line by itself\n",file_code.read()) p.sendlineafter("--- Press enter to start ---",""); p.recvuntil("Result: ") data = p.recvline() p.close() with open("res.zip", "w") as res: res.write(b64decode(data)) res_zip = zipfile.ZipFile(getcwd()+"/res.zip") res_zip.extractall(getcwd()) res_zip.close() with open("game.log", "r") as game_log: print("game_log:") print(game_log.read()) with open("program.log", "r") as program_log: print("program_log:") print(program_log.read()) ``` #### my own snake ```= banana ~<8=== blue yellow; #get snake's status if yellow == 2 then #2, not 1 if banana == "^" then logText "up"; return "R"; fi; fi; if blue == 27 then #27, not 28 if banana == ">" then logText "right"; return "R"; fi; fi; if yellow == 17 then #17, not 18 if banana == "v" then logText "down"; return "R"; fi; fi; if banana == "<" then blue := blue - 1; #it must be blue-1 because snake is moving! {loop} yellow := yellow - 1; #check above banana ~<8=== blue yellow; if banana == "A" then #found return "R"; #turn right fi; if banana == "B" then #found return "R"; #turn right fi; if yellow == 1 then #not found return ""; #keep moving to left side fi; slide {loop}; fi; if banana == "^" then red := yellow - 1; banana ~<8=== blue red; #check in front of the snake logText banana; if banana == "B" then return " "; fi; fi; return ""; . ``` output : `midnight{Forbidden_fruit_is_tasty}`