George Lasry is the new bearer of the Friedman Ring

George Lasry has solved the challenge of Christoph Tenzer. He is thus the new bearer of the Friedman Ring.

Deutsche Version

The first person to solve the current crypto puzzle creates the next one. The Friedman Ring works according to this simple principle. This is a game named after cryptologists William and Elizebeth Friedman.

All previous winners can be found on this website.

In the meantime the fourth round of the game is finished. The puzzle came from Christoph Tenzer (also known as “Narga”). George Lasry was the first to solve it. He is now the new bearer of the Friedman ring. Congratulations!

Quelle/Source: Schmeh

Christoph’s challenge

Christoph has created the following challenge:

Quelle/Source: Tenzer

The solution

George has thankfully sent me a detailed description of the solution and how to solve it. Here it is:

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:

`0101000011101100100001101010100`

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

`0111100011000101000011101100100001101010100`

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:

000 D
00101 M
001100 N
0011010 P
0011011 R
0011101 T
001111 U
0100 W
010100 _
010101 Y
011000 A
011001 C
01101 E
01110 F
011110 I
1000 B
1001000 H
1001001 L
1001010 S
1001011 V
101 O
11 G

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.

Congratulations and thanks

Besides George, Johannes, Bill Briere, Thomas Bosbach, TWO, Magnus Ekhall, Gerd, Gerry, YeS, farmerjohn, Hias, Tobias Schrödel, Basic, Bernd Adameit, mjw and m contributed with their comments to the solution.

George is already working on the next puzzle. However, we will wait a little longer before starting the next round, because we don’t want the whole thing to die.

Thanks again and congratulations to all participants!

If you want to add a comment, you need to add it to the German version here.

Further reading: Ein kryptologischer Cold Case: Die BND-Challenges von 2014