George Lasry hat die Challenge von Christoph Tenzer gelöst. Damit ist er der neue Träger des Friedman-Rings.
English version (translated with Deepl)
Wer das aktuelle Krypto-Rätsel als erstes löst, erstellt das nächste. Nach diesem einfachen Prinzip funktioniert der Friedman-Ring. Dabei handelt es sich um ein Spiel, das nach den Kryptologen William und Elizebeth Friedman benannt ist.
Alle bisherigen Preisträger gibt es auf dieser Webseite.
Inzwischen ist die vierte Runde des Spiels beendet. Das Rätsel kam von Christoph Tenzer (bekannt auch als “Narga”). George Lasry hat es als erster gelöst. Er ist damit der neue Träger des Friedman-Rings. Herzlichen Glückwunsch!
Christoph hat folgende Challenge erstellt:
George hat mir dankenswerterweise eine ausführliche Beschreibung der Lösung und des Lösungswegs zugeschickt. Hier ist sie:
I tried many ideas and directions, I am describing here only the main ones, and in particular, those that led to the solution.
1) I started with the wrong assumptions that there can be no more than 5 symbols per code, and that only the letters A-Z are encoded (no space, no punctuation). I developed an algorithm that enumerates all possible prefix-free trees (without the substitution) under those assumptions, and was able to solve my own simulated challenges. The algorithm did not solve Narga’s challenge, however. Narga later commented that there are codes that can have at least 7 symbols. So I dropped that direction, as the key entropy was too high to enumerate all options.
Since I did not have any other algorithmic ideas, I waited for the hints.
2) After a week, Narga gave three important hints, based on the blog readers’ suggestions:
a) 001100 is a code (Johannes’s idea)
b) Repetitions are important (Bill’s idea)
c) One of the repetitions is somehow related to the common word THE (Thomas’s idea).
3) I started by looking at repetitions. It became clear that the fact that a sequence is repeated, does not necessarily mean that it contains a complete sequence of codes (i.e., it starts at the beginning of a code, and ends at the end of another code), since those assumptions resulted in contradictions (e.g., remaining segments with only 2-5 symbols that are not prefix-free).
I then decided to look for specific repetitions that are long enough and appear at least 3 times. The most promising was:
It appears 3 times and has 31 symbols. It is also interesting because it starts and ends with 010100. While Thomas had suggested 01010 as a SPACE symbol, his idea of THE enclosed by two SPACEs, while very useful, made more sense with 010100. This means that 0011101100100001101 was THE. After some trial and error (looking at frequencies of all possible 3 parts), I reached the conclusion that T = 0011101, H = 1001000, and E = 01101. Note: When looking at frequencies of possible codes of different lengths, it is important to take into account not just the raw count, but also to factor in the probability of a code appearing in a random sequence.
4) The second sentence starts with
which can be decomposed as follows, since from the hints we knew that 001100 is a valid (unknown) code:
011110 001100 010100 0011101 1001000 01101 010100
So we have yx_THE_ , where _ represents the SPACE symbol, x the unknown code 001100, and y another unknown code 011110. yx could be IN, AT, ON, OF, as well as other 2-letter words, but IN made most sense, giving: IN_THE_
5) In the second sentence, we also have the sequence:
010100 0011101 10010000 1101 010100 001100 011110 001100 01101 0011101 01101 01101 001100 0011101 1001000 010100
which perfectly decodes as _THE_NINETEENTH_
This was strong evidence that the current direction was correct.
6) The third sentence starts with 0011101 1001000 011000 0011101 010100, which maps to
TH<011000>T_ , most probably THAT_, so 011000 was clearly A.
7) In the second sentence, After _THE_NINETEENTH_, the word CENTURY was expected, giving a few code options for C, U, R, Y.
8) With A, R, and Y known/guessed, and some trial-and-error, the sequence _LAST_YEARS_ OF_ could be decoded from the missing part of the second sentence. The full sentence is: IN_THE_LAST_YEARS_OF_THE_NINETEENTH_CENTURY.
9) Additional words could be deduced from other sentences, such as _HUMAN_AFFAIRS_ in the third sentence, _THE_TIME from the fourth one, NO_ONE_ in the first, giving away additional letters.
10) A search on Google for “no one in the last years of the nineteenth century that human affairs” quickly gave the full text:
No one would have believed
In the last years of the nineteenth century
That human affairs were being watched
From the timeless worlds of space…
11) All the remaining codes could easily be recovered.
12) The full code is:
13) I did not use any computerized search or hillclimbing/statistical algorithms, but it was convenient
(a) to look for repetitions using a simple Java program
(b) to test various deciphering hypotheses and print out all possible occurrences of guessed/known codes, using another simple Java program.
In all stages, the fact that there was a SPACE symbol was very useful. The hints were also critical. Still, overall, this was a quite tough challenge, I worked on it during a full weekend. I enjoyed it very much, and I also appreciate the fact no more than the right amount of hints was given.
Gratulation und Dank
Neben George haben auch Johannes, Bill Briere, Thomas Bosbach, TWO, Magnus Ekhall, Gerd, Gerry, YeS, farmerjohn, Hias, Tobias Schrödel, Basic, Bernd Adameit, mjw und m mit ihren Kommentaren zur Lösung beigetragen.
George bastelt bereits am nächsten Rätsel. Allerdings werden wir noch etwas warten, bevor die nächste Runde gestartet wird, denn die Sache soll sich ja nicht totlaufen.
An dieser Stelle noch einmal besten Dank und Glückwunsch an alle Beteiligten!
Further reading: Ein kryptologischer Cold Case: Die BND-Challenges von 2014