FISL10 Programming Arena

This is the third edition FISL organizes a programming contest called Programming Arena. This name came from the original idea that the participants had to stay inside a glass room in the middle of the event area without being allowed to exit (except for bathroom, which they had go accompanied). This year some of this restrictions were relaxed and participants could go in and out as they wish, with the only restriction they had to arrive before 10AM every day of the competition.

The competition consists in two phases: Qualifying, in which participants have to discover a nine letter code that’s needed for the inscription, and Insanifying, when participants spend three days working on a challenge proposed by the organization.

I wasn’t very excited about it at the beginning, since I didn’t want to spend a lot of time working on discovering the code and then spend almost the whole FISL programming (the same thing I usually do every day). But then, some weeks after the qualifying had started, they published a notice telling that no one had found out the right code yet. It was a cold friday night, I had gone to spend the weekend at my parents house, and after having some fondue and wine for dinner, I grabbed the remaining half bottle of wine, sat with my laptop by the fireplace, and decided to give it a try. I already knew that there were some hints for the code as comments in the HTML source of first link in this post, and then discovered one additional hint in the source of the second link on this post. About 4:00 in the morning, I’ve managed to find out that the code was hidden in a pseudo-echo server at arena.softwarelivre.org:1996, that when string “peixe” (a keyword on the Tux profile at the softwarelivre.org social network) is inputed, responds with a cyphered string. During the whole process, I had been chating with Padovan on IM, since he had spent some time working on the problem with his housemate, a few days before, with no success. We both agreed that it should be some simple cypher, some sort of substitution-based cypher, since there was no hints on cypher algorithms so far and that the string was short and had some blank spaces, resembling a phrase of a few words. At that moment Padovan stopped what he was doing before and said: “Let’s break that cypher!”. So I continued working on trying to find a key hidden somewhere else while he wrote a script for a dictionary-based attack using the Firefox portuguese dictionary. Since one of the words had 2 letters that repeated, he aimed at it and no much time latter he could guess that word: inscricao, the ascii-only version of the word inscription in portuguese (“inscrição”). With the mapping of this word and guessing some other letters we could find out almost the whole phrase, missing only one letter, exactly in the middle of the 9-letter code. There were only 12 letters not matched, so we could had tryed the inscription using brute-force, but we decided to have some sleep and try a bit more in the next day. In the next morning, someone had find out the key and posted it on a blog. The key was hidden as the TXT DNS record of arena.softwarelivre.org, and had the matching for the whole alphabet. The whole decyphered phrase was “parabens seu codigo de inscricao eh goosfabra” (congratulations your inscription code is goosfraba).

The second phase, during FISL, was even more interesting. The challenge was to implement DNSCurve, a security extension of the DNS protocol, both in a forwarder (server) and in a cache (client). Before the implementation started we saw a panel discussion about DNSCurve vs DNSSEC with Daniel J. Bernstein, the creator of DNSCurve (and also of djbdns and qmail). DJB was also responsible for judgin the code produced during the arena. There was a draw to group the participants in three groups of three people and one group of two people, and luckily me and Padovan ended in the same group, together with Rodrigo Tjäder, from UFSM. After three days of work, we had the following work done:

(1) DNS Server — pymdscurve.tar.bz2

We based our implementation on pymds, a modular python DNS server licensed under the MIT license. It’s a standalone DNS server, in terms it doesn’t resolve any names it doesn’t know. For the NaCl (crypto) functions, we used the slownacl lib from dnscurve. Despite it doesn’t says on the website, we contacted the authors (both Matthew and Angel) and both of them told us it’s public domain and a note on the project page is missing. Matthew even added a README to the code which says it’s public domain and updated some code on the lib to make it compliant with NaCl newer spec on DJB’s website.

(2) DNS Cache

For the cache we tried two different approaches.

(i) PyDNSCacheCurve.tar.bz2 — First we added the DNSCurve messages to PyDNSCache, which is a very simple DNS cache written in python and intended to be used as a python library. This code didn’t had any license note on the project page either, but we contacted the author and he licensed it under Creative Commons Attribution 3.0 United States License. Since it’s just a cache of DNS information, it used
gethostbyname() from the socket module. We changed it to use a function we implemented, gethostfromDNS(), to send the necessary DNS messages to get the information from a server. For the cryptography part we’ve also used slownacl from dnscurve. We didn’t implemented the ability to resolve names recursively on PyDNSCache, so we hardcoded the server public key inside the code.

(ii) dnspythoncurve.tar.bz2 — Since solution (i) was unable to resolve names recursively, we decided to use dnspython, which provides a lot of helper functions to deal with DNS. We’ve added DNSCurve extensions to it and also added a recursive resolver. dnspython is released under a BSD-style license. Since recursive resolution works we can get the server name to check if it a DNSCurve enabled server and, if so, obtain it’s public key. We’ve tested pymdscurve and dnspythoncurve under a scenery with two servers, one configured as authority for .com and other as authority for example.com, in order to test recursive resolution. Both config files are shipped in pymdscurve package.

So much work worth every line of code. Besides learning a lot and having fun, we also won the contest, getting an Android Dev Phone 1 for each participant of the team as a stipend (thanks google!) and lots of good words about our implementation from DJB. I will son add some photos and a video of the winners announcement.:

Explaining our implementation

The winner team with DJB

 

We gonna send patches back to all projects we’ve added code to. We have also added some code to some dns helper functions on dnscurve, outside of slownacl. The source code of our implementation can be found at http://www.las.ic.unicamp.br/~joaopaulo/dnscurve/ http://www.las.ic.unicamp.br/~jprvita/dnscurve/.