Norbert Biermann hat die Challenge von George Lasry 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 fünfte Runde des Spiels beendet. Das Rätsel kam von George Lasry. Norbert Biermann hat es als erster gelöst. Thomas Bosbach hat ebenfalls einen großen Anteil an der Lösung. George und ich haben daher überlegt, den Ring an beide zu überreichen. Thomas hat jedoch bescheidenerweise – mit Verweis auf die Spielregelen, die besagen, dass nur der Löser den Preis bekommt – von sich aus verzichtet.
Norbert Biermann ist damit der neue Träger des Friedman-Rings. Dass Thomas Bosbach wichtige Vorarbeit geleistet hat, sei noch einmal erwähnt. Auch Nargas Kommentare waren hilfreich. Herzlichen Glückwunsch alle drei und an alle anderen Beteiligten!
Georges Challenge
George hatte die folgende Challenge erstellt:
Quelle/Source: Schmeh, Lasry
Es handelt sich um einen Text, den George mit einer Wheatstone-Scheibe verschlüsselt hat.
Die Lösung
Norbert hat mir dankenswerterweise eine ausführliche Beschreibung der Lösung und des Lösungswegs zugeschickt. Hier ist sie:
First of all, thanks to George for this nice and cleverly chosen challenge! When it came out, I transferred the principle of the Wheatstone device into a C++ program and tried to find a solution via hillclimber. Honestly, if Thomas hadn’t come up with the isomorphs, I’d still be doing that! But with Thomas’ discovery, I quickly realized that
- George had built repeated long sequences into the ciphertext on purpose, and
- he did so because it is the intended and probably the only possible approach to crack the cipher.
I had written my assumption in the comments: the isomorphs can serve to strongly limit the number of possible ciphertext alphabets. Once the ciphertext alphabet is known, one knows for every letter by how many positions the plaintext alphabet is advanced and can convert the ciphertext into a monoalphabetic cipher (MASC). If there are a huge number of possible ciphertext alphabets, this work must probably be done by a computer, which then solves the resulting MASCs and sorts the results by n-gram scoring, for example.
My lists of possible ciphertext alphabets were computer-generated. The used algorithm is a recursive function: It is launched with a fixed initial letter ‘a’ (since the rotation of the alphabet has no influence on the solution path, one position can be set arbitrarily). Then the function decides which letter it will take care of next and moves it to position 2, 3 and so on until the last position. Each time it checks if the conditions defined by the isomorphs are met. If no, the next position is tried. If yes, then the function copies its current state and calls itself to process the next letter on the copy. If there are too few constraining conditions, this program will run for some million years, but beyond a certain limit it goes quite fast, and so it did in this case.
But then a serious problem arose concerning the possible ciphertext alphabets. Let’s take the following example:
adbehoiupzkfncjxmrtvqwysgl
Using this alphabet, the following MASC is derived from the original ciphertext:
_gpgdmxtsqoedz_cfhfaug_jfrfdkg dwtxgwfdmcpubieurkeqbqz_enyutr cgfnocur_kgfdbsrmnqtvtohunxtet rk_kgetfpardlwmq_yjgntqesbxayz hfpscahqhenyutrpfe_adgigbvhakg sgelovxltsyhehodzyxy
which reads at the three isomorphic places made out by Thomas:
pgdmxtsq... cur_kgfd... qhenyutr...
It can be seen that the isomorph conditions are not sufficient to obtain a MASC that has equal symbols at the three positions (which is our crucial assumption!).
At first, this seemed to be good news: The many candidates for ciphertext alphabets must not only meet condition A (isomorphs), but also condition B (derived MASC must yield identical letters at all three positions). This was going to shorten the list a lot!
I worked condition B into my program – and now the issue came to light: of all 576 candidates for the ciphertext alphabet resulting from condition A, none could also satisfy condition B at the same time. The shortlist had shrunk to 0 candidates. Narga had apparently encountered the same problem at about the same time.
My thought now was that maybe the plaintext was not exactly the same in the 3 isomorphic places. Therefore, I tried to gradually loosen the isomorph conditions by taking out letter triples that appeared only once.
From (see Thomas’ comment #23)
COENSQQVTZZOIZNJCZEMKQRETR KBAZQRRMXIIBEIZFKIACURJAXJ IGYOMCCNFBBGLBOUIBYZECKYFK
I took out S/Q/M, V/M/N, I/E/L, and K/U/E (as one of many tries) and kept J/F/U as the only single:
COENQQTZZOZNJCZEQRETR KBAZRRXIIBIZFKIARJAXJ IGYOCCFBBGBOUIBYCKYFK
This resulted in the impressive number of 14,999,040 possible ciphertext alphabets, of which 14,474 also fulfilled condition B.
I had the computer sort the resulting 14,474 MASCs in descending order of IC. Thus the following alphabet came on top:
algsymqvtrpxjcnfkzduiohebw
with the following derived MASC:
_siqsix_z_ajimkgc_aekscsvitumi qxzujtij_ivpgzukmsxfyizqsix_z_ fji_siqsix_zu_ihljfbz_djwbruhs tqhwz_kxm_ivmajzuvdkxpyiujeiki z_pl_vsiqsis_z_ajimkgc_aekxcsv itumiuzja_tdkgzimlki
and an IC of 0.061. This IC seemed too low to me, because my prepared corpus has an IC of 0.073. So I did not pay any further attention to this result and decided to investigate further, where on earth I could have made my mistake.
Then I noticed a detail. The MASC, which I had classified as incorrect, had an unexpected peculiarity: The repetitions of the long sequences seemed to start already from the first position in the text (“_siqsix … _siqsix …“), not only from position 3. Like Thomas (see the end of comment #23), I had assumed that the first two letters would not belong to the repeated sequence. Now it dawned to me that this is not necessarily the case, indeed that a repetition right from the beginning is more likely. But if my “wrong” MASC has already incorporated that, then maybe it’s not that wrong? A quick try with CryptoCrack yielded snippets of words that pointed to “Wheatstone”. This was very encouraging, and so I made a pen-and-paper attempt that got this far (and surprised me by the lack of word separators which I hadn’t anticipated at all):
thewheatstonecryptogrhphdevice wasinventedbysircha?leswheatst ?nethewheatsite?un??st?n???i?h vw??stractedconsid?rableingere stbutdhewhehtstonecryptographd eviceisnotv?rysecure
After a short internet research I went for “attracted considerable interest” in the middle part (see here: http://www.jproc.ca/crypto/wheatstone.html) and posted my solution.
Ring frei zur nächsten Runde
Norbert wird sich nun ein neues Rätsel für die nächste Runde ausdenken. Ich bin schon gespannt. In etwa drei Monaten heißt es es dann: (Friedman-)Ring frei zur nächsten Runde!
An dieser Stelle noch einmal besten Dank und Glückwunsch an alle Beteiligten!
Follow @KlausSchmeh
Further reading: Ein kryptologischer Cold Case: Die BND-Challenges von 2014
Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/
Kommentare (1)