Armin Krauß’s solution
Three days after I had published the Fleissner challenge, Armin Krauß posted the solution:
PLANS FOR MANNED MOON EXPEDITIONS ORIGINATED DURING THE EISENHOWER ERA IN AN ARTICLE SERIES WERNHER VON BRAUN POPULARIZED THE IDEA OF A MOON EXPEDITION A MANNED MOONLANDING POSED MANY TECHNICAL CHALLENGES BESIDES GUIDANCE AND WEIGHT MANAGEMENT ATMOSPHERIC REENTRY WITHOUT OVERHEATING WAS A MAJOR HURDLE AFTER THE SOVIET UNIONS LAUNCH OF THE SPUTNIK SATELLITE VON BRAUN PROMOTED A PLAN FOR THE UNITED STATES ARMY TO ESTABLISH A MILITARY LUNAR OUTPOST BY NINETEEN SIXTY FIVE
Armin Krauß is one of the best codebreakers I know. He has broken many of the challenges I presented on Klausis Krypto Kolumne in the last four years.
Armin found the solution with a Hill Climbing algorithm. Those who can read German can read his explanation here (an English summary follows):
Als Kostenfunktion habe ich Log-Trigramme verwendet. Als “Mutationsregel” für das Gitter habe ich einem zufälligen Loch eine zufällige Position in seinem Orbit zugewiesen (wobei ich mit Orbit die 4 Positionen meine, die ein Loch bei den 4 Drehungen einnehmen kann). Für’s Hill Climbing habe ich einen Simulated Annealing-Ansatz genommen. Das hat den Vorteil, dass man nicht sofort in einem lokalen Maximum hängen bleibt.
Ich testete den Algorithmus mit von mir selbst mit einem 20×20-Gitter verschlüsselten Texten, was sehr gut funktionierte. Daher wunderte ich mich, dass mein Programm mit deinem Text nicht zurecht kam.
Wie Jim Gillogly fand ich so auch nur einige Wortfolgen. Diese verwendte ich dann für einen Known-Plaintext-Ansatz: ich suchte alle Lochkombinationen, die eine solche Wortfolge als Lösung ergaben und drehte die entsprechende Maske um 180 Grad. Die Buchstaben in der gedrehten Maske bewertete ich mit der Kostenfunktion und konnte so wahrscheinliche Lochkombinationen und neue Klartextteile identifizieren.
Eine Google-Suche mit den so gefundenen Klartextteilen hat dann die Suche nach weitern Cribs sehr beschleunigt, da ich die vermutliche Quelle deines Klartextes finden konnte (ohne das hätte man einen Wörterbuchangriff starten können, aber zum Glück war das nicht nötig).
So konnte ich schliesslich die Positionen der 100 Löcher rekonstruieren und erhielt 3 sinnvolle Klartextzeilen. Nur die vierte Zeile war unleserlich, aber als ich das Gitter mit den Buchstaben der vierte Zeile ausdruckte war schnell klar, dass hier nur die Ausleserichtung anders gewählt werden muss.
Armin used the frequency of three letter groups (trigrams) to construct his cost function. His mutation rule took a random hole of the grille and shifted it by random to one of the three other positions it could take when the grille was rotated. In addition to Hill Climbing, Armin used the technique of Simulated Annealing.
Conclusion
Considering that Armin and the others mentioned in this article broke a 20×20 Fleissner encryption including an error in a ciphertext only attack, it is justified to say that the Fleissner grille is not secure. It is considerably weaker than the Double Columnar Transposition. This once again proves that it is very difficult to design a manual cipher that is both convenient and secure.
I would like to thank all those who have contributed to the discussion about this challenge. I’m very proud to have such great codebreakers among my readers.
Follow @KlausSchmeh
Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/
Further reading: How to Use a Rubik’s Cube for Encryption
Kommentare (5)