Internet Problem Solving Contest

IPSC 2007

Solution to Problem K – Know Your Crypto

In the easy problem we may start by a quick examination of the input file.

The letter frequencies seem to correspond to an English text. (The most common letters are t, e, and r.)

The last two words "rear ranger" seem pretty similar to the word "rearrange", don't they?

If we read the text backwards, at the end (i.e., currently at the beginning of the text) we will find "teihelet t erco unt". Disregarding the spaces we get two meaningful words: "letter count".

Disregarding spaces in the original string, one could find several meaningful substrings at the end, for example "grid now"

These were some of the hints that were trying to push you in the right direction.

The message contains exactly 169 letters. Is this number special? Yes, it is a square, namely 13×13.

Given some of the hints (meaningless spaces, letter count is 13×13, grid, [re]arrange), the important step was to arrange the message into a 13×13 grid:


Now we may notice that all the substrings we found so far are really horizontal. And the first column says "tis a perfect sq".

Thus the text flows around the square. The correct direction of reading is counter-clockwise, starting in the lower right corner. The solution is the word indifferent.

The problem statement for the hard problem was purposefully slightly misleading. We were pretending that the problem is unsolvable, and if it were solvable, the problem would be in the randomness of the rand function.

This was not the case. The problem was solvable, and the catch was elsewhere.

Our code had a bug that is not obvious at the first glance, but potentially lethal in software that relies on randomness (e.g., online casinos): To initialize the random seed we used the current time.

Moreover, the problem statement was pretty specific on the fact that the entire problem was prepared just a few days before the contest. One day has 86,400 seconds. This gives us several hundreds of thousands possible random seeds – and this number is small enough to try them all.

The best way to finish this problem was to filter the decoded texts. For example, only save those that have many 'e's and 't's, and contain the substring 'the'. Once you narrow down the number of candidates, find the correct one by hand.

The plaintext contained two clues: The answer is the thing most commonly hidden in a haystack. If you still don't know the answer, google for the words: haystack, hidden, and search.

Thus clearly the solution is needle.