Tuesday, February 17, 2015

What books do programmers read?




Last week we ran a competition on our Codility Facebook page to ask developers from our community which books they have found the most useful in learning to code.

The winners will get a copy of ‘’Looking for a challenge? The Ultimate Problem Set from the University of Warsaw Programming Competitions”




In the end we decided to up the prizes and picked 3 winners. We will update the post with winners names once we have confirmed their contact details.

The winners were Filip Bartuzi, Daneil Drwiega and Neeraj Xavier (check your Facebook ''Other'' emails tab folks!)


The programming books our community chose


Filip Bartuzi I think The Pragmatic Programmer is the most valuable book for every programmer because of its versatility - no matter what programming language you know you still massively benefit from this book. What is more this book is perfect for both experienced, professional developers and newbies. For a newbie programmer its worth to go through this book not just once because with experienced he get he will learn new things from the book.

Konrad Dziedzic  Definitely The Pragmatic Programmer because it opened my eyes on how much I am missing, in terms of my habits and my willing to improve. I also noticed thanks to this book how easy it is for me and in general for ppl in our time to write software and to learn how be better. It definitely made me became a better programmer

Michał Hawełka Clean Code by Robert C. Martin. The best, easy to read book about ways to write good code 




Adam Sznajder Introduction to Algorithms by CLRS. It showed me in a quite simple way that choosing right data structures to your problem might be crucial and decide whether you'll succeed. It covers knowledge that's essential to become a proficient programmer - starting from typical algorithms, through their analysis and theory, to generic problem solving techniques.



Piotr Jarzemski Competitive Programming 3 by Steven Halim. A must read book for everyone who wants to improve their coding skills.

Mariusz Nosiński it's easy to learn programming language, but it's hard to learn programming. Then most valuable books for me are books about programming but above languages. For OOP it was Design Patterns authored by gang of four, for FP is actually Functional programming patterns in scala and clojure (http://amzn.com/1937785475).

Sirf Moonga Java How To Program by Paul Deitel and Harvey Deitel

Velu Shanmugam I've learned some languages java,php,html and css,etc,. All the language except java i used 'Dummies' book and for java I used Deitel

Fiero Vasquez Algoritmos en C++, de Robert Sedgewick. Fue el libro con el que empecé.

Pawel Paprocki Thinking in Java/C++ by Bruce Eckel


This is for me the best programming book I have ever read and would read


The books our Codility developers chose



The Codility library. You can check out any time you like, but you can never leave



Marcin Kubica, our Chief Scientist recommends The Pragmatic Programmer.

Grezgorz Jakacki, our CEO recommends The Pragmatic Programmer  and Programming Pearls by John Bentley

Kos, our Senior Software Engineer also recommends The Pragmatic Programmer

Monika, our Head of Sales recommends Python the Hard Way

Tomasz Walen, our Senior Software Engineer and Co-Founder recommends Clean Coder

Pawel Marczewski, our Tech Lead finds it hard to recommend just one...


A big Thank You! to everyone who added suggestions. Please add more in the comments if you found a particular programming book useful



Wednesday, February 11, 2015

Meet Paweł

Paweł Marczewski, our Tech Lead, keeps the full picture of our whole system and has the overview of everything we develop. But when he is not doing that, Paweł fulfills his dream of speaking Japanese, enjoys Japanese animation and games (such as Mahjong and Go) and focuses on his personal projects (mostly games).


Q: What does your typical day involve at Codility?
PM: It depends on the day, but mostly I’m just like any other developer at Codility. When I am on the tech support duty, most of my time consists of fulfilling small requests and making improvements to the system whenever I have time. The rest of the time, I usually work on 2-3 big things during a day. I work closely with other team members and I help out with everything that happens.



Q: What do you do besides coding?
PM: As a team leader, I am helping coordinate what we do and planning our iterations. I am talking with the Product Team about the best way we can solve customers’ problems. I also conduct interviews with candidates - it’s my team, so I want to talk with everyone I am going to work with. I am trying to get other team members to help me with that, so that together we can have the shared understanding of who we want to hire.

Q: How do you like the interviewer experience?
PM: I enjoy meeting people from a lot of different backgrounds. I often ask about interesting experience or project from their past -- it’s really fun to learn about these. When I give them technical problems, I find the experience similar to teaching – you give a task and let people solve it… but at the same time, of course I need to keep myself from giving too many hints. I also like when someone suddenly comes up with a way to solve a problem, you can really see things click for them.

Q: What has been your biggest achievement at Codility so far?
PM: The improvements I made in our teamwork. One such improvement was shared ownership of issues - before, we worked on our tasks more or less separately and did not communicate enough about them. Now we have a shared list of things to do during an iteration, and decide together how we will do it. Thanks to that we all have better understanding of our code, we work faster as a team and have more fun together.  

Q: In your opinion, what is the killer feature of Codility?
PM: The killer feature is our assessment quality. When I compare Codility to other similar services, we might not have the prettiest interface, but we give the most detailed and accurate results. Some of us worked on Olympiads and competitions, so we have expertise in assessing programming tasks.

Q: What is your growth plan? What do you want to achieve in your career?
PM: My plan is to learn as much as possible. I guess when you are a programmer, you can either go to management and coordinate other peoples’ work or keep programming, and for the time being I would like to keep programming. I don’t know what exactly my area is going to be in the future, though.

Q: Out of all potential employers, why did you choose Codility?
PM: I like it here because of the challenges -- we are learning something new every day, and all the problems are not solved yet. It turns out that what I really enjoy is building things, and here I have an opportunity to do that.
I also like that I can really influence everything we do. I do not feel constrained in making improvements – if something does not work well, I can change it. I imagine it could be more difficult in a bigger organization.

Q: You have a final 60 seconds. Brag about something.
PM: I have a story to share that happened when on my Japan trip last year. I was sitting in a backpackers’ hostel one day, and a guy comes to me and asks me if I am a programmer. It turned out he was a university student and wanted some advice about coding in the industry. We talked about different types of programming problems, and I ended up explaining what we do and what Codility is. I showed him Equi, our demo task (https://codility.com/demo/take-sample-test/). He had some trouble coming up with an efficient solution, but was delighted when I showed it to him - and happy to learn that we offer more tasks like this! So I was really happy to meet someone that appreciates what we do.

Feel like getting in touch with Paweł?
Drop him an email pawel@codility.com
or check his website http://pwmarcz.pl/

Tuesday, December 23, 2014

Meet Cezary

Our youngest team member and our first non-technical intern, Cezary Piwowarczyk joined us as our Product Intern from Rotterdam, where he is currently studying. He tries always to keep up to date with news from all over the world, appreciates a good beer and is always looking for interesting new flavors. In his free time he watches TV series and movies, and listens to music.
Q: What does your typical day involve at Codility?
CP: It depends on the day. Usually, I participate in the Development Team meetings, observe what the Dev Team is doing and present their progress to others at Codility. In a nutshell, I gather a lot of information and process it. Every day I try to learn more about product management as well, and improve the workflow of the Product Team.
Q: What have you learned during your internship?
CP: While not being a techie myself, I have managed to understand how a Development Team works in a product company.


Q: What has been your biggest achievement at Codility?
CP: So far, it has been a visualization of the Dev Team’s work and progress. Now, Greg and I are also working on a product roadmap.
Q: Why were you looking for an internship?
CP: I was given the choice between a student exchange, extra classes or an internship, and I decided that an internship would be the best option for me. I wanted to learn and learn quickly, and test myself in a fast-paced environment.
Q: Out of all potential employers, why did you choose Codility?
CP: What was most important to me was to learn more about the IT sector. I had a desire to get to know how IT companies work from the inside. And then I found Codility. I noticed that Codility’s recruitment process was different from all the other places I applied to. I needed to solve a recruitment task and had two one-hour interviews with Codility team members. Initially the internship was supposed to last for three months, but at the end of that time both parties were really happy with the arrangement and it was extended by another two months.
Q: What is the killer feature of Codility in your opinion?
CP: Codility’s culture and the team. Everyone gets along really well and works well together as a team. Everyone wants to constantly improve, and we work well at implementing new ideas. I like the cross-team cooperation between the Dev Team, Sales Team and Customer Support—it is really dynamic!
Q: How would you advise other companies to organize an excellent internship based on your experience at Codility?
CP: To give the interns as much freedom as possible to find different solutions to problems and to mentor them, as opposed to simply telling them what to do. The job cannot be repetitive. At Codility my job was never boring; I rarely repeated any task. Because of that, I could learn really a lot. It is good if the intern is given time to interact with people from different teams and is given the opportunity to speak up his/her mind at meetings and during discussions. It is also great to encourage interns to show some initiative.
Q: What is your growth plan? What do you want to achieve in your career?
CP: I would definitely like to graduate! ;-) Beyond that, I don’t have any very firm plans. My last year was full of surprises, so I think I can basically expect anything to happen. I know that I would like to come back to Codility at some point.
Q: What has been your funniest moment at Codility?
CP: The funniest moments always happen during lunch, when the whole team gathers and we have countless discussions about gluten-free diets and unhealthy food, or we vote for our favorite restaurants and someone tries to manipulate the scores. I always expect some kind of dispute about that! :-)
Q: You have a final 60 seconds. Brag about something.
CP: I threw myself in at the deep end, applied to and got in at a University abroad in Rotterdam. I think this has been my biggest achievement so far, and it enabled me to prepare for great changes. I challenged myself to find a great internship, and I got it at a great company that gave me a lot of opportunities. I always have that one bit of luck in life—for example, during my school years I always had Principal’s Honor Roll! :-) I have left my comfort zone so many times, and right now nothing really limits me.

Feel like getting in touch with Cezary?
drop him an email: cezpiw@codility.com
or check his LinkedIn profile

Monday, December 15, 2014

Have you got 1337 programming skillz?

In this blog post our colleague Tomasz Idziaszek shares his impressions from participation in Capture the Flag contest organized last week by PGS Software.

Prologue

I have participated in various algorithmic contests (such as TopCoder or ACM ICPC) and I know what fun they are. But I have never tried taking part in a CTF competition before, so when two weeks ago my colleagues shared a link to an entry-level competition of this kind, I decided to give it a try. I had a really good time solving these computer-oriented puzzles and I recommend this to anyone who enjoys hacking. To start competing in CTFs you need general knowledge about practical computer science, have to know tools available in your system (I use Ubuntu) and have some programmers intuition. Also it was worth to assume that problems are really solvable and to use all hints the organizers give. And last but not least, you need some luck also.

There were 10 tasks and for each of them we were given one file. Files are available on the contest page. I will present the problems in the order I have solved them. Although organizers proposed some order of tasks starting (in their opinion) from the easiest to the hardest, but difficulty is a very subjective matter and usually such an ordering is based on how much technical knowledge you should know beforehand to solve a task, and not how tricky it is. So I began by opening all the tasks first, and then started solving the ones I find most promising. In later stages I ended up on thinking about 2–3 task simultaneously.

Task 5. 01

We have one file with a long string of 0s and 1s. If we open this file in a text editor which wraps rows, and resize the window, changing the number of characters in a row, we can get the impression that in fact this string encodes a two-dimensional picture. But what are its dimensions? The string has length 97343, so we must find two integers x, y such that x·y = 97343. Since this number is semiprime, we have only two possibilities (its not a novel idea, the Arecibo message broadcasted 40 years ago into space also had semiprime length).

Setting image size to 313 characters in a row, we get a picture that should be recognized by anyone who saw a QR code before:

The next thing to do is convert this string of 0s and 1s into an image file. This step is fairly easy if we are familiar with portable bitmap format (PBM). We simply add two rows (P1 and 313 311) before data in the file and then use some image-processing program (like GIMP) to open it and save as an image in some popular format. The last step is to find some online QR code converter and use it to get encoded text: PGS_PRIMENUMBERS. Not only this is in format of flag, but also organizers share the key idea used in solving the task, so we can be pretty sure that our first task is solved.

Task 4. deepspace

In this task we get an SVG file which depicts two humans and some symbols (the bottom ones resembling our solar system). If you are not familiar with fact that it's actually a Pioneer plaque, you can deduce from the name of the task and bottom symbols to google for graphics with "astronomy drawing man woman".

After opening our SVG and Wikipedia version, it's not hard to spot the difference: the sequence on the ray which touches Jupiter is different. On our SVG it is

|---- --||| |--|| ||||| |---- -|--| -|||| -|||- --|-| --|-| |--|-

That (treated as binary numbers where pipe is 1 and dash is 0) encodes the number sequence 80, 71, 83, 95, 80, 73, 79, 78, 69, 69, 82. This interpreted as ASCII codes gives us the flag: PGS_PIONEER.

Task 1. whereami

We get the following file:

51184646 17031207 (1)
51663598 16084613 (1)
53717124 19335107 (1)
_
50984155 23171832 (10)
50264888 19023722 (4)
50972438 18218128 (8)
51218633 18568923 (4)
50728694 18444701 (6)
52598551 15892477 (2)
54068038 14968824 (3)
51842555 18086852 (3)
53066035 19909063 (5)
52767355 17755542 (6)
51768751 15813327 (5)
54675984 18420687 (3)

Since we know that all flags are in format PGS_[a-zA-Z0-9_]+ and are human-readable, we conclude that every row encodes one letter (and the first three encode characters P, G and S, respectively). It probably is not a coincidence that all the numbers in the first and second columns are around 52·106 and 18·106. The name of the task suggest some location and I remember from school that geographical coordinates of Warsaw are around 52°N 21°E. So we can add dots after second digits and try to find "51.184646 17.031207", "51.663598 16.084613" and "53.717124 19.335107" in Google Maps. It look like we have luck, since each time near the cursor we find a street which name starts with needed letter (Parkowa, Generała Władysława Sikorskiego and Słowiańska). This also suggests that the numbers in the third column specifies which letter from the name we are interested in.

But next coordinates are not so helpful, for some even we don't have street names on the map. The problem is that we are missing the most important information on the map, which is the name of the city or village our cursor is in. There are two ways to spot it: either remove the cursor from the map (but stay on the coordinates) or look for coordinates in Google and not in Google Maps. The names for rows are now Psary, Głogów, Susz, Krasnystaw, Katowice, Kluczbork, Wieluń, Dobrodzień, Międzychód, Pustkowo, Russów, Żuromin, Gąsawa, Siedlisko and Żelistrzewo. Combining these letters into flag get us: PGS_WORLDISSMALL.

Task 9. tweet(y)

The name of file data.raw suggests some file format without headers or any additional metadata; just plain data. Viewing it in a hex editor we see that it starts with 16-bit codes close to 0000 and FFFF, and later it becomes more random. That actually suggests raw audio data (with 16-bit signed precision codes close to 0000 and FFFF encode positive and negative numbers close to 0, which result in silence). Audacity program has an option to Import raw data, we only have to be sure to select Signed 16 bit PCM encoding. The data imports correctly, and we can hear Merrily We Roll Along song:

But where is our flag? So this time it is worth knowing one trick with audio (or with digital signals in general). The above image shows signal value in time, but also signal can be described by frequencies which it composes of, in a form of spectrogram. So let's see how frequencies of our signal look, by selecting Spectrogram log(f) option in Audacity. On the following image we show the interesting part of the sound file (starting approximately at offset of 2 seconds):

We clearly see that together with the main signal in frequencies up to 5 kHz there is also additional signal of frequency around 16 kHz (almost inaudible to human ear) which looks like it encoding some bit sequence. The sequence has length of 1.6 seconds and the smallest interval of continuous sound (or rest) has length of 0.01 seconds. We can treat it as a 160-bit sequence:

11111111010100000100011101010011010111110111001101101111011101010110111001100100
01101111011001100111001101101001011011000110010101101110011000110110010111111111

Now it's not so hard to see that after partitioning it into 20 8-bit chunks and discarding two sentinels (the first and the last chunk), we got a message encoded in ASCII: PGS_soundofsilence.

Task 6. matrioshka

In this task we are given a DLL file and a strong hint, since the task name (matrioshka) suggest that in this file is contained another file which itself can have more layers of files inside. One of the most important command which can help us working with files of different types is file command which tries to determine file type. In our case it acknowledges that the file is in fact PE32 executable (DLL) (GUI) Intel 80386, for MS Windows.

So let's examine the file closer and see what information we get from strings command which extracts the strings of printable characters in files. Most of extracted strings looks like garbage, but we also get JFIF and Created with GIMP which suggest that inside DLL there is a JPEG image (possibly as a resource). But what is more interesting is the 8 kB string which ends on ...ANgAAAOQYAAAAAA==. That should ring a bell to anyone familiar with Base64 encoding. So let's try to decode it using base64 -d command.

The file command says that decoded data is a Zip archive, and after unzipping it we get a data.bin file. This file is Microsoft Disk Image, Virtual Server or Virtual PC. We don't want to install software to actually run this image, and we already cut some corners with skipping the JPEG part, so let's try luck once more. Strings in this file suggest that it contains image of MSDOS 5.0 system using FAT16 file system. If we open the file in a hex editor we'll see that these strings appear in block at address 0x10a00, which looks like the boot sector of the file system:

00010A00 EB 3C 90 4D │ 53 44 4F 53 │ 35 2E 30 00 │ 02 01 02 00   < MSDOS5.0.....
00010A10 02 00 02 00 │ E8 F8 E7 00 │ 3F 00 FF 00 │ 80 00 00 00  ....   .?. . ...
00010A20 00 00 00 00 │ 80 00 29 93 │ 92 EF 62 4E │ 4F 20 4E 41  .... .)   bNO NA
00010A30 4D 45 20 20 │ 20 20 46 41 │ 54 31 36 20 │ 20 20 33 C9  ME    FAT16   3Ɏ

From the data in the boot sector we get some characteristics of the file system: 512 bytes per sector, 1 sector per cluster, 2 reserved clusters, 2 copies of FAT, 512 directory entries and 231 sectors per FAT. Since the order is: reserved sectors, FATs, root directory and then actual data, thus the address of the first FAT is 0x10a00 + 512·2 = 0x0e00 and the root directory starts at address 0x0e00 + 521·2·231 = 0x4aa00. Directory entry has size 32 bytes and first two clusters are not present, thus the address of the i-th data cluster is 0x4aa00 + 512·(32-2+i). Let's take a look at the root directory:

0004AA00 43 54 46 20 │ 20 20 20 20 │ 20 20 20 08 │ 00 00 00 00  CTF        .....
0004AA10 00 00 00 00 │ 00 00 A8 A0 │ 62 45 00 00 │ 00 00 00 00  ......  bE......
0004AA20 24 52 45 43 │ 59 43 4C 45 │ 42 49 4E 16 │ 00 AF DD A0  $RECYCLEBIN.. ??
0004AA30 62 45 62 45 │ 00 00 E0 A0 │ 62 45 02 00 │ 00 00 00 00  bEbE..  bE......
0004AA40 46 4C 41 47 │ 20 20 20 20 │ 42 49 4E 20 │ 18 6A 65 A1  FLAG    BIN .je 
0004AA50 62 45 62 45 │ 00 00 61 A1 │ 62 45 04 008A 00 04 00  bEbE..a bE.. ...

The most promising is file FLAG.BIN which has size of 0x4008a bytes and starts in cluster 4, so at address 0x4aa00 + 512·(32-2+4) = 0x4ee00:

0004EE00 42 4D 8A 00 │ 04 00 00 00 │ 00 00 8A 00 │ 00 00 7C 00  BM ....... ...|.
0004EE10 00 00 00 02 │ 00 00 80 00 │ 00 00 01 00 │ 20 00 03 00  ...... ..... ...
0004EE20 00 00 00 00 │ 04 00 13 0B │ 00 00 13 0B │ 00 00 00 00  ................
0004EE30 00 00 00 00 │ 00 00 00 00 │ 00 FF 00 00 │ FF 00 00 FF  ......... .. ..
0004EE40 00 00 FF 00 │ 00 00 42 47 │ 52 73 00 00 │ 00 00 00 00  .. ...BGRs......

It starts with BM magic number, so it probably is some bitmap image file. Let's also take a look at the FAT:

00010E00 F8 FF FF FF │ FF FF FF FF │ 05 00 06 00 │ 07 00 08 00          ........
00010E10 09 00 0A 00 │ 0B 00 0C 00 │ 0D 00 0E 00 │ 0F 00 10 00  ................
00010E20 11 00 12 00 │ 13 00 14 00 │ 15 00 16 00 │ 17 00 18 00  ................
00010E30 19 00 1A 00 │ 1B 00 1C 00 │ 1D 00 1E 00 │ 1F 00 20 00  .............. .
00010E40 21 00 22 00 │ 23 00 24 00 │ 25 00 26 00 │ 27 00 28 00  !.".#.$.%.&.'.(.
00010E50 29 00 2A 00 │ 2B 00 2C 00 │ 2D 00 2E 00 │ 2F 00 30 00  ).*.+.,.-.../.0.
00010E60 31 00 32 00 │ 33 00 34 00 │ 35 00 36 00 │ 37 00 38 00  1.2.3.4.5.6.7.8.
00010E70 39 00 3A 00 │ 3B 00 3C 00 │ 3D 00 3E 00 │ 3F 00 40 00  9.:.;.<.=.>.?.@.
00010E80 41 00 42 00 │ 43 00 44 00 │ 45 00 46 00 │ 47 00 48 00  A.B.C.D.E.F.G.H.
00010E90 49 00 4A 00 │ 4B 00 4C 00 │ 4D 00 4E 00 │ 4F 00 50 00  I.J.K.L.M.N.O.P.
00010EA0 51 00 52 00 │ 53 00 54 00 │ 55 00 56 00 │ 57 00 58 00  Q.R.S.T.U.V.W.X.
00010EB0 59 00 5A 00 │ 5B 00 5C 00 │ 5D 00 5E 00 │ 5F 00 60 00  Y.Z.[.\.].^._.`.

It looks like we again have luck: our file is stored in consecutive clusters 4, 5, 6 etc., so to extract it we simply copy 0x4008a bytes starting from address 0x4ee00. After opening this file with GIMP, we see that most of the file is black background with small white Almost done! message in the corner. But GIMP's Histogram tool shows that the image uses three shades of gray: pure white (255), pure black (0) and almost pure black (1). Replacing this almost pure black with some contrasting color reveals that the more important message is written using this color and it says PGS_formatmaster.

Task 10. noneshallpass

During the contest it looked like I had better luck with harder tasks (up to this point I had tried to solve tasks 2 and 3 with several approaches, but without success). So why not try with the hardest task now? We get an encrypted Zip file (the command unzip asks for a password), but since in Zip only the data is encrypted and not metadata (information about zipped files), we can see what was encrypted using unzip -v command:

Archive:  task10.zip
 Length   Method    Size  Cmpr    Date    Time   CRC-32   Name
--------  ------  ------- ---- ---------- ----- --------  ----
  653218  Defl:X   371475  43% 2014-11-12 02:23 fdb41d5f  flag
    2703  Defl:X     2218  18% 2014-11-12 02:06 c0b89d1b  pgs-logo.png
--------          -------  ---                            -------
  655921           373693  43%                            2 files

So we have two files, one presumably with flag, and the second one with pgs-logo.png image of size 2703 bytes. Googling for "pgs-logo.png" reveals that the logotype in the header of PGS Software website has exactly the same name and size. What if we assume that it's exactly this file? Well, it will allow us to perform a known-plaintext attack on the Zip file. There is already software that can help us in doing it, during the contest I used PkCrack (yes, I remember to send a postcard to its author). The program can do all dirty work for us, but there is one tricky bit. Since the program requires that the known plaintext should be compressed with the same compression method used for the encrypted file, we have to tweak compression level in order to get file of size exactly 2218 after compression.

After cracking we are informed by file command that that the type of unpacked file is Targa image data - RGB - RLE 500 x 375, and opening it with GIMP reveals that the flag is PGS_KNOWNTEXT.

Task 2. math...

In this task we are presented with the following arithmetic expression:

12.4-42+5-13.1/20-84*6-90.9/12*4+3.5+5.6*2.3/5.8+3.5-45-12.9-62/9-4-55/12-14+9-68-25/29.3-12.7/4.2+2.9*2.7/44.4/12.6+5.3-87.8/12-4-9+5-2/12.4-44+6.6/6.3/2.5*12.7+3.3-2/12.4/96.6=-746.127310172101

I had several attempts to solve this task, mostly trying to find out some mathematical properties of the expression. Since the goal is to extract a sequence of characters, I also tried to partition the expression into parts which correspond to subsequent characters. I had several candidates (like slashes or number 12 which occurs suspiciously often).

I was a little bit frustrated after several unsuccessful attempts, but then I thought to myself that since this task is supposed to be second easiest, there must be something simple I miss. I remembered that organizers published a sample task, so I read that for some inspiration. In this task one of key points was using Morse code. The characters PGS_ in this code are .--. --. ... ..--.- and in fact that is exactly what we get if we erase from our mathematical expression every character which is not dot or dash (and treat slashes as delimiters). That gives us

.--./--./.../..--.-/--/---/.-./..././..-./---/.-././...-/./.-.

Which turns out to be our flag PGS_MORSEFOREVER. By the way, I think that three dots in the name of this task is also a slight hint for Morse code.

Task 3. matrix

Here we are given GIF file with PGS Software logo. During the contest I thought that maybe there is some hidden data stored in the image using steganography. Since GIF format uses indexed color mode I also made sure to check the palette of the picture using Color palette option in GIMP. The most suspecting thing is that many randomly placed entries of the palette has black color. All these black entries are used in the image, so I spent good deal of time trying to see what parts of image each entry corresponds to, but it led me nowhere.

Finally I focused on the palette entirely but it was not until I arranged it in a 16×16 square (why GIMP doesn't do it by itself is beyond me), when things started to click:

It is definitely not coincidence that two edges of this square are black, and another two have black and non-black entries alternating. I am not familiar with all two-dimensional codes, but ultimately I found the suspect: it looked like a Data Matrix barcode. Now it is only a question of finding online decoder to get the flag: PGS_palFun.

Task 7. haxor

This time we are given an Android application package. I haven't got access to Android phone, so I decided to solve it like a real hacker. Since I have never developed an Android application, I had to get all the necessary information from the Internet. I disassembled the program into Dalvik bytecode using dexdump -d classes.dex command from Android SDK. I won't go into details here, the code itself is not long and with a help of list of opcodes it can be understood even by people who (like me) saw Dalvik bytecode for the first time. It turned out that this program performs xor operation on three arrays of length 17 (one stored directly in classes.dex file at offset 0x6c8, one stored in assets/b1.bin file and one encoded as string in resources.arsc file at offset 0xfb). The answer is PGS_LOVES_ANDROID.

Task 8. bigmem

In the final task we got an executable file (file command says ELF 32-bit LSB shared object, Intel 80386, version 1 (SYSV), dynamically linked, not stripped). Unfortunately the file was compiled for Haiku operating system, so running it on my Ubuntu results in segmentation fault. (I will admit that on some point during the contest I gave up and actually installed Haiku just to be able to debug the executable using gdb. It hadn't lead me anywhere, but at least I played with a new system.)

So let's try to disassemble the contents of the program using objdump command (with parameters objdump -d -M intel flag). The most interesting part is the main function of the program:

00000878 <main>:
 878:   55                      push   ebp
 879:   89 e5                   mov    ebp,esp
 87b:   83 ec 14                sub    esp,0x14
 87e:   53                      push   ebx
 87f:   e8 00 00 00 00          call   884 <main+0xc>
 884:   5b                      pop    ebx
 885:   81 c3 40 12 00 00       add    ebx,0x1240
 88b:   83 c4 f4                add    esp,0xfffffff4
 88e:   68 69 7a 00 00          push   0x7a69
 893:   e8 80 ff ff ff          call   818 <ctfdelay>
 898:   83 c4 10                add    esp,0x10
 89b:   83 c4 f8                add    esp,0xfffffff8
 89e:   68 c9 00 00 00          push   0xc9
 8a3:   68 c9 00 00 00          push   0xc9
 8a8:   68 c3 00 00 00          push   0xc3
 8ad:   68 e2 00 00 00          push   0xe2
 8b2:   68 c1 00 00 00          push   0xc1
 8b7:   6a 6d                   push   0x6d
 8b9:   68 e2 00 00 00          push   0xe2
 8be:   68 c7 00 00 00          push   0xc7
 8c3:   68 d7 00 00 00          push   0xd7
 8c8:   8d 93 d1 ee ff ff       lea    edx,[ebx-0x112f]
 8ce:   89 d0                   mov    eax,edx
 8d0:   50                      push   eax
 8d1:   e8 6e fc ff ff          call   544 <printf@plt>
 8d6:   83 c4 30                add    esp,0x30
 8d9:   31 c0                   xor    eax,eax
 8db:   eb 03                   jmp    8e0 <main+0x68>
 8dd:   8d 76 00                lea    esi,[esi+0x0]
 8e0:   8b 5d e8                mov    ebx,DWORD PTR [ebp-0x18]
 8e3:   89 ec                   mov    esp,ebp
 8e5:   5d                      pop    ebp
 8e6:   c3                      ret
 8e7:   90                      nop

After glancing at the contents of the function ctfdelay (not shown here), it looks like it does nothing except recursively invoke malloc to allocate big number of chunks of memory (what is actually suggested by the task name), so its sole purpose is not to allow to execute next instructions when program is simply run from the command line.

The more interesting thing is printf function. Before its invocation ten values are pushed on the stack, so we assume that the function has ten arguments: one string and nine integer values. Using strings command we can see that one string is particularly interesting: %c%c%c%c%c%c%c%c%c. It looks like a string format, so we can assume that the invocation is as follows:

printf("%c%c%c%c%c%c%c%c%c",0xd7,0xc7,0xe2,0x6d,0xc1,0xe2,0xc3,0xc9,0xc9);

But this prints some garbage on the screen, since it does not contain any ASCII characters (except 0x6d which is letter m). But let's assume that in fact this invocation corresponds to printing flag on the screen, using some unknown character encoding. Then we have the following mapping:

0xd7 → P
0xc7 → G
0xe2 → S
0x6d → _
0xc1 → x
0xe2 → S
0xc3 → y
0xc9 → z
0xc9 → z

Is there any English word that has five letters, the second letter is S and two last letters are the same? You will not find it in every English dictionary, but it exists and actually we have used it in this write-up. So a pretty strong guess for flag is PGS_ASCII. But how can we be sure? If the task is sensible, the unknown encoding shouldn't be a totally arbitrary one. An in fact it isn't, since it is IBM's encoding called EBCDIC.

Epilogue

I solved almost all tasks in about 10 straight hours of hacking, and later (when I got some sleep) I finished remaining ones. The whole event was a nice mixture of frustration and enjoyment. For additional information about CTF contests, I recommend to read what more competent people have to say in this subject. Following these two links may be a good beginning: How to get started in CTF, CTF write-ups repository, CTF write-ups from DragonSector team.

Wednesday, December 10, 2014

Meet Joanna

Her phone never stops ringing, but we are very happy to have our office manager Joanna Marciniak as she is the person who makes sure we have the best working environment. Thanks to her, every new teammate is treated to a welcome party, we have our homey loft office, and all the awesome Codility parties are amazingly organized. Need to have your business trip arranged? Feel like having some green tea or a new laptop? You’ve joined our team and need to rent a place in Warsaw? She will make it happen for you with silent efficiency!
Q: What does your typical day involve at Codility?
JM: I would say 50% of my tasks are repetitive (ordering lunch, making sure there are drinks, snacks and fruits in the office, sending Golden Awards to winners, taking care of office supplies) and 50% are completely new things that I have not done before, such as booking a room in Lagos for a job interview or arranging for a phone number to be redirected via the UK, to support new teammates with relocation and meet their needs.
Q: If you could come up with an alternative name for your position, what would it be?
JM: I guess I would be a Team-sitter.
Q: What has been your biggest achievement at Codility so far?
JM: I think it would be supervising the office renovations in the attic, creating the homey environment and designing an office that people want to come to every morning.

Q: Which home country of our co-workers would you most like to visit, and why?
JM: China. I have never been, and I will definitely go to visit some time soon. I have reached a moment when I can go on a trip like this.
Q: Out of all places you might have worked, why Codility?
JM: I learned about Codility through Magda (our Administrative Manager). She informed me that Codility was looking for someone who would supervise the office renovation. When I joined Codility, at the time there were just two small rooms, and I saw how much there was still to do! I loved the atmosphere in the office (those two small rooms at the time)—it all seemed very exciting and I saw a lot of challenges. I liked the level of teamwork and team engagement in creating the office space. Right now, I feel at home here, and honestly, compared to all of the jobs I’ve had so far, this one is the best!
Q: In your opinion, what is the killer feature of Codility?
JM: Without being very original—the people. Our team has grown 100% since I joined, and every person who comes really fits in here. With every new person, Codility gains something valuable. The team is better together: every day we are more integrated, and we work better together every day. We like and respect each other, and there are no politics, games, or unhealthy situations. Everyone comes to work happy. We have an option to work from home, but I have never seen anyone trying to find reasons not to come to the office. We also have a lot of freedom: nobody controls your working hours, and that is really motivating!
Q: What is your growth plan? What do you want to achieve in your career?
JM: I really love what I do and my job really fits my personality; there is no routine and there is always something new to learn. I see my future being with Codility: we are still growing really quickly, so I expect a lot of new challenges. The next office will blow your mind! :-)
Q: What has been your funniest moment at Codility?
JM: I remember one funny situation when I was organizing a Codility party and called a pub where we were supposed to meet. I made all the arrangements and everything seemed fine. When we got to the pub, the owners did not know what we were doing there. It turned out that I had called a pub in Wrocław instead of Warsaw! It was a really funny situation. Fortunately, we managed to reach an agreement with the pub in Warsaw quickly! Another thing I recall was when Marcin (our Chief Science Officer) made air balloons out of plastic bags on top of our radiators in the office.
Q: You have a final 60 seconds. Brag about something
JM: I think the thing I am most proud of is that I managed to open theatre buffet in Kalisz, my hometown. I really wanted to run it, so I went to the directors of the theatre and presented my idea. They loved it and even gave me full funding. I supervised the whole renovation and interior design, and had an opportunity to run the buffet. It was great; I ran it for 2½ years and within that time we hosted several events. I can proudly say that I created one of the most interesting and beautiful theatre buffets in Poland (that’s what actors and directors from other theatres have said…).