How we stormed the sapka contest, part one
A few days ago, the week of the Sapka contest ended, for those who missed the news about Sapka, this is a competition of programmers created as an analogue of the ICFPC contest, but for the Russian and Ukrainian segments of the network.
It has always been very interesting for me to read about the ICFPC decision process, so I cannot miss the chance to write a similar report from the first person, so meet the first part of the story about the storming of high heights from the small but proud minime team that took the 7th place in the contest :)
')
1st day
In which the minime team gets acquainted with the contest rules and takes the first steps
So, at 19-00 GMT + 3 information appears on the site stanfy.com.ua/contest about conducting a contest. To start participating, you need to download a server written on modified Java code and having received a set of keys in advance, try to implement the sapka device logic in it. What is sapka, how and where to get the keys and why they are needed is completely incomprehensible.
While the server is slowly being downloaded, I open the IRC client and connect to the sapka channel, which is already actively discussing the server internals. I unpack the server, start it and follow the instructions, connect with a telnet to port 20015 in order to see the server's invitation and request to specify the name of the team in the format team teamname; .
No sooner said than done. The result is zero. A few more attempts are similar. I switch to IRC there, this problem is already being actively discussed, it turns out that you need to add an additional semicolon at the beginning of each command. I specify - the system reports about successful registration and issuing a fare message prompts you to start configuring the device memory with the command memconfig; .
And here is the first task, memconfig to start asking for a password. From where to take it is completely incomprehensible, sapka, god, sex, love, password, etc. go into battle. The result is zero - it becomes sad because of such a fast plugging. In fruitless attempts, it takes almost an hour when suddenly it becomes clear that the password must also be started with a " ; ". All right, we repeat all the passwords in a new way and ... the " password " comes up. Well, quite logical password. Although lost time is very sorry. The “freshly broken” system offers to try your hand in two tasks: engine and lexinterpr
Here comes the sad news. The participants versed in java changed the original bootloader which turned the original (that is, non-standard) Java code into a normal one and received the entire set of tokens (that is, the keys), actually solving all the tasks in the first hour of the competition. This, of course, was very upset because I wanted to take part in the contest of programmers, and not in the contest of programmers in Java. There was a desire to leave the competition, but ... something stopped, the benefit of the task seemed interesting. But from the pleasant - it became clear the total number of keys.
Update server hover to version 1.1 and proceed to lexinterpr . As it becomes clear, this utility is able to decrypt information sent by the server if run in sapka-game mode, and the amount of decrypted data also depends on the number of tokens already activated. In addition, as a current data to decrypt a huge string of bilberd is loaded. Fortunately, the last part of the line carries clear information. It becomes clear that from this line it is necessary to cut out consistently the clear part marked with characters at the end! and * and perform the specified conversion. For the first step, take every third character.
A 10 line python program is quickly written to perform an operation, the output is another task, but now the rules for taking meaningful characters have changed. Ok, repeating the iteration 6 or 7 times I get my first pair of tokens at the output and a message that the rules can be interpreted differently. It is worth noting that in reality this was not the case, but it gave rise to the legendary missing second pair of tokens on which many participants spent a decent amount of time (and we including :)).
The interpreter solution allows access to the whole set of tasks: dnalab , sattelite , fifth , aar , clock
But I postpone these puzzles until the next day and proceeding to the solution of the engine , which, after launch, reports its version of Caesar-1-3ci.5p5-h.23e.r '' - '~' about itself and produces the next encrypted text. From the version you see the line Caesar cipher, i.e. Caesar's cipher and memory suggested that this is encryption shift, which was confirmed by Wikipedia. Ok, another 10 minutes and another python script runs through the text with all possible shifts. Here it becomes clear that everything is not so simple - only capital letters were deciphered, and there are only 1 line in the text. It takes another hour to try to find an error in the program or the logic of the work - the answer is not, and even a hint in the form of a letter Y encoded somehow does not help. I walk through the remaining text with frequency analysis and, armed with my own translation dictionary, I begin to collect the text character-by-character. The work is not going fast, instead of frequently occurring characters, trying to substitute "a" and "e" and an attempt to guess some frequently occurring word is tried. Then the substitution of characters from it and run the script in the text in the hope that the word is recognized correctly and that now you can solve more words. After almost two hours, the text surrenders and exposes a couple more tokens, as well as the rules of the hopping game.
It turns out that the final task of each team is to write an AI for a bomberman clone. The text contains the resulting points for the bombings of objects by bombs and commands for movement / installation of bombs.
On this first day ends, on the clock 4 nights.
Day 2
In which the minime team loses the evil virus in checkers and breaks its brains with brainfack and watches
So, I am breaking the passage to sattelite - the satellite captured the evil virus and demands to play checkers with it. Well, since it requires - we will play, the only complication, the playing field cannot be visualized after the first move and we have to mark the move in the open Excel. On the other hand, it becomes clear (from the boorish cries of the virus) that there is a trick in the game. After some time, the companion on the enchantner team reports that this is the case, winning the virus does not lead to anything and apparently should play in the giveaway. I understand that my method with excel is not as effective as flash checkers and continue to solve clock .
As it becomes clear later, clock is one of the tasks that made many participants swear long and viciously. Simple in essence, it made many people spend more than one hour on their decision.
So, the task - it is necessary to solve 2 puzzles, base clock and eXtended clOck Routines. From the second, it becomes clear that the task will contain XOR in one way or another. The source data is a string of the form \ 0 \ 39 \ 34 \ 20 ... (obviously encoding ASCII character codes) and the phrase "I came, I saw, I conquered." .
The first attempt to proxy the original line with a Caesar statement does not lead to success. This is followed by an attempt to proxy with all the symbols of the alphabet. Then the phrase "Veni, vidi, vici". Then the number 42. All without result. In IRC, people who solve the problem are slowly making fun of those who are in the process, and talk about a completely simple way.
By late evening it becomes clear that the task is simple, but it is impossible for us to understand how to solve it. Then a brilliant idea comes up, take the strings issued to teams with different names (and the tokens depend on the team name), find the different parts and assuming that all the tokens start in CFG and have a fixed length to determine the first 3 characters for XOR.
Five minutes later, I begin to fight in hysterics. The first three letters of the code word " Cae ". Xoriu ill-starred line Caesar and get another token. The basic part is solved, but the decoded line contains another line for analysis. Fortunately, everything at once becomes extremely simple - it is equal to the token in length, and the first three characters are 0. I will copy the string with the just received token and get a second token (three 0 at the beginning suggests that this is a CFG, because CFG xor 000 = CFG). The clock is solved, you can go to the IRC and watch the torment of the undecided.
Shortly before the end of the torment with the clock, enchantner brings the second good news - the evil virus has surrendered, and aar has also been resolved. To do this, it was necessary to swap operators on the advice of the virus from the satellite, run the resulting program in the breinfack interpreter, get another program, run it, and finally find out the token. This problem, in fact, could be easily solved without a hint of the virus, and it seemed to many too much. The initial code on a brainfuck person who familiarized with the operators of the language would immediately give a hint in the form of going beyond the limit of permissible memory in the very first operators.
On the clock again after midnight and we go to sleep.
It has always been very interesting for me to read about the ICFPC decision process, so I cannot miss the chance to write a similar report from the first person, so meet the first part of the story about the storming of high heights from the small but proud minime team that took the 7th place in the contest :)
')
1st day
In which the minime team gets acquainted with the contest rules and takes the first steps
So, at 19-00 GMT + 3 information appears on the site stanfy.com.ua/contest about conducting a contest. To start participating, you need to download a server written on modified Java code and having received a set of keys in advance, try to implement the sapka device logic in it. What is sapka, how and where to get the keys and why they are needed is completely incomprehensible.
While the server is slowly being downloaded, I open the IRC client and connect to the sapka channel, which is already actively discussing the server internals. I unpack the server, start it and follow the instructions, connect with a telnet to port 20015 in order to see the server's invitation and request to specify the name of the team in the format team teamname; .
No sooner said than done. The result is zero. A few more attempts are similar. I switch to IRC there, this problem is already being actively discussed, it turns out that you need to add an additional semicolon at the beginning of each command. I specify - the system reports about successful registration and issuing a fare message prompts you to start configuring the device memory with the command memconfig; .
And here is the first task, memconfig to start asking for a password. From where to take it is completely incomprehensible, sapka, god, sex, love, password, etc. go into battle. The result is zero - it becomes sad because of such a fast plugging. In fruitless attempts, it takes almost an hour when suddenly it becomes clear that the password must also be started with a " ; ". All right, we repeat all the passwords in a new way and ... the " password " comes up. Well, quite logical password. Although lost time is very sorry. The “freshly broken” system offers to try your hand in two tasks: engine and lexinterpr
Here comes the sad news. The participants versed in java changed the original bootloader which turned the original (that is, non-standard) Java code into a normal one and received the entire set of tokens (that is, the keys), actually solving all the tasks in the first hour of the competition. This, of course, was very upset because I wanted to take part in the contest of programmers, and not in the contest of programmers in Java. There was a desire to leave the competition, but ... something stopped, the benefit of the task seemed interesting. But from the pleasant - it became clear the total number of keys.
Update server hover to version 1.1 and proceed to lexinterpr . As it becomes clear, this utility is able to decrypt information sent by the server if run in sapka-game mode, and the amount of decrypted data also depends on the number of tokens already activated. In addition, as a current data to decrypt a huge string of bilberd is loaded. Fortunately, the last part of the line carries clear information. It becomes clear that from this line it is necessary to cut out consistently the clear part marked with characters at the end! and * and perform the specified conversion. For the first step, take every third character.
A 10 line python program is quickly written to perform an operation, the output is another task, but now the rules for taking meaningful characters have changed. Ok, repeating the iteration 6 or 7 times I get my first pair of tokens at the output and a message that the rules can be interpreted differently. It is worth noting that in reality this was not the case, but it gave rise to the legendary missing second pair of tokens on which many participants spent a decent amount of time (and we including :)).
The interpreter solution allows access to the whole set of tasks: dnalab , sattelite , fifth , aar , clock
But I postpone these puzzles until the next day and proceeding to the solution of the engine , which, after launch, reports its version of Caesar-1-3ci.5p5-h.23e.r '' - '~' about itself and produces the next encrypted text. From the version you see the line Caesar cipher, i.e. Caesar's cipher and memory suggested that this is encryption shift, which was confirmed by Wikipedia. Ok, another 10 minutes and another python script runs through the text with all possible shifts. Here it becomes clear that everything is not so simple - only capital letters were deciphered, and there are only 1 line in the text. It takes another hour to try to find an error in the program or the logic of the work - the answer is not, and even a hint in the form of a letter Y encoded somehow does not help. I walk through the remaining text with frequency analysis and, armed with my own translation dictionary, I begin to collect the text character-by-character. The work is not going fast, instead of frequently occurring characters, trying to substitute "a" and "e" and an attempt to guess some frequently occurring word is tried. Then the substitution of characters from it and run the script in the text in the hope that the word is recognized correctly and that now you can solve more words. After almost two hours, the text surrenders and exposes a couple more tokens, as well as the rules of the hopping game.
It turns out that the final task of each team is to write an AI for a bomberman clone. The text contains the resulting points for the bombings of objects by bombs and commands for movement / installation of bombs.
On this first day ends, on the clock 4 nights.
Day 2
In which the minime team loses the evil virus in checkers and breaks its brains with brainfack and watches
So, I am breaking the passage to sattelite - the satellite captured the evil virus and demands to play checkers with it. Well, since it requires - we will play, the only complication, the playing field cannot be visualized after the first move and we have to mark the move in the open Excel. On the other hand, it becomes clear (from the boorish cries of the virus) that there is a trick in the game. After some time, the companion on the enchantner team reports that this is the case, winning the virus does not lead to anything and apparently should play in the giveaway. I understand that my method with excel is not as effective as flash checkers and continue to solve clock .
As it becomes clear later, clock is one of the tasks that made many participants swear long and viciously. Simple in essence, it made many people spend more than one hour on their decision.
So, the task - it is necessary to solve 2 puzzles, base clock and eXtended clOck Routines. From the second, it becomes clear that the task will contain XOR in one way or another. The source data is a string of the form \ 0 \ 39 \ 34 \ 20 ... (obviously encoding ASCII character codes) and the phrase "I came, I saw, I conquered." .
The first attempt to proxy the original line with a Caesar statement does not lead to success. This is followed by an attempt to proxy with all the symbols of the alphabet. Then the phrase "Veni, vidi, vici". Then the number 42. All without result. In IRC, people who solve the problem are slowly making fun of those who are in the process, and talk about a completely simple way.
By late evening it becomes clear that the task is simple, but it is impossible for us to understand how to solve it. Then a brilliant idea comes up, take the strings issued to teams with different names (and the tokens depend on the team name), find the different parts and assuming that all the tokens start in CFG and have a fixed length to determine the first 3 characters for XOR.
Five minutes later, I begin to fight in hysterics. The first three letters of the code word " Cae ". Xoriu ill-starred line Caesar and get another token. The basic part is solved, but the decoded line contains another line for analysis. Fortunately, everything at once becomes extremely simple - it is equal to the token in length, and the first three characters are 0. I will copy the string with the just received token and get a second token (three 0 at the beginning suggests that this is a CFG, because CFG xor 000 = CFG). The clock is solved, you can go to the IRC and watch the torment of the undecided.
Shortly before the end of the torment with the clock, enchantner brings the second good news - the evil virus has surrendered, and aar has also been resolved. To do this, it was necessary to swap operators on the advice of the virus from the satellite, run the resulting program in the breinfack interpreter, get another program, run it, and finally find out the token. This problem, in fact, could be easily solved without a hint of the virus, and it seemed to many too much. The initial code on a brainfuck person who familiarized with the operators of the language would immediately give a hint in the form of going beyond the limit of permissible memory in the very first operators.
On the clock again after midnight and we go to sleep.
Source: https://habr.com/ru/post/55092/
All Articles