Fleissner-Grille-solved-bar

Last week I introduced a cryptogram made with a Fleissner grille. Blog reader Armin Krauß found the solution, although I had made a serious mistake in the encryption process.

First of all, I have to appologize! Last week I created a ciphertext using a Fleissner grille in order to present it as a challenge to my readers. To my regret, this cryptogram contained an error.

The Fleissner grille is named for Edouard Fleissner von Wostrowitz (1825–1888), who described it in one of his publications. However, this method had long been known before. Here’s how a Fleissner grille works:

Fleissner-Explanantion

The mistake I made happend in the third encryption step. I simply forgot to turn the grill (on my Powerpoint slide) before I filled in the third part of the message. I corrected this mistake immediately by turning the grille and by turning the grouped letters. Then I ungrouped the letters and turned them again. Now every letter was in a hole again, but I didn’t realise that the order of the letters was wrong now. Here’s the correct version of the challenge:

ENPAIGEZLANEDMTHSENF
EIORDEMATANNATMOOFSL
AEPLMHOIERITOECDMVNE
OXNPBROEDOIETRANEEIU
XPNPONRNTAREOMMYDWIT
IANHTNEIOODNSOUOTETD
MOOVEARPHRIOLAEGNALN
INATTFINOREATDNGWDDA
UHSIEURININGTTEDASTN
ATGHPEESAOMEISEADRMM
YANTSOEJOESYTERTHACH
BNINCALURDCHLEALLHLA
OIFWESTEHENGREERRTHE
SAAMSIBEIOVNSAINARLI
DTESGIIETTUCNARILYLO
ESENRUUISINEADSRANLA
COUWNEAUETCPOHRNSDTW
BYEOFNINGHERHIVNTOTE
MNTBERAEHEUNSPNSUTIX
NPOITYPFIKSAVULEATRA

Interesting comments from my readers

One of the first comments to my article came from Jim Gillogly, who is known as an excellent codebreaker. One of his masterpieces was the breaking of several hundred encrypted messages sent by the Irish Republican Army (IRA) in the 1920s. The details of this story are presented in the book Decoding the IRA co-written by Jim and IRA expert Thomas Mahon. Jim also broke one of the infamous “cryptograms from the crypt” created by parapsychologist Robert Thouless in order to prove that there is a life after death.

Gillogly

Concerning the Fleissner challenge Jim wrote:

Although it [the codebreaking program] came up with suspiciously coherent phrases like “[he?]unitedstatesarmy” and “[posedmany?]technicalchall”, it had less coherent suggestions like “fated on..export..need someone…” and “saint carlie droe sword.figh..” and “outjest befingers meant…”.

The “suspicously coherent phrases” UNITEDSTATESARMY and POSEDMANYTECHNICALCHALL turned out to be correct, as they actually appear in the cleartext. So, Jim was the first who presented a part of the correct solution.

Martin from Switzerland, Norbert Biermann and Tony Gaffney made interesting comments, too. Only minutes before I published this article, Hendrik posted another interesting comment. Thank you to all of the contributors and sorry for not going into detail about all your ideas.

 

Hill Climbing

In recent years codebreakers like George Lasry, Nils Kopal, Jim Gillogly and Dan Girard have shown that Hill Climbing is a powerful technique to break old encryptions. My expectation was that Hill Climbing would work in this case, too. Hill Climbing works (in this context) like this:

  • A Fleissner grille is constructed at random and used to decrypt the cipher text.
  • The result is fed to a function (“cost function”) that rates the correctness of the letter sequence (for instance, based on whether the bigram frequencies ressemble the ones of English text).
  • The grille is changed slightly (according to a “mutation rule”), and again the ciphertext is decrypted and rated. If the rating is better now, the current grille will be kept, otherwise the previous one is reloaded.
  • Again, the grille is changed slightly, used for decryption and the result is rated, and so on.

This procedure is carried on, until the rating doesn’t improve any more. If we are lucky, this maximum rating indicates that we have found the correct grille.

Codebreaking with Hill Climbing only works if small changes in the key cause small changes in the cleartext. This is the case for many classical encryption algorithms, including the Fleissner grille. In modern cryptanalysis Hill Climbing doesn’t play any role at all, as modern encryption algorithms like AES, DES, and PRESENT are designed to be random oracles. This means that if only one bit is changed in the cleartext or the key the ciphertext changes completely. This is also referred to as “avalanche effect”.

 

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.

Krauss-Armin

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.

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)

  1. #1 Thomas
    19. Januar 2017

    Perhaps the program can solve the “Kaliningrad-cryptogram” (if it is a transposition cipher).
    Here’s a transcription:

    en’ifvn d’t’öhn’fdê elhrikiracel etê deluwrs
    ured ganunt’ lnenên’lf r.s.f.d. fruustr d’e astf’
    uesr cfefdrr helcnunde uwsesd danunhhs c.f.
    d’enac s’eara efn’ ruhncfoiw m’am’mt. f.t.’f. wmet’t’cef
    dludn hro aul lel nenet’se. emnh mwie eiie iael’es
    esmdesrnt rnorunt’ er relfd’ r.l.b. scihss ne in’nw htouk
    sans eighcin möwidgn lw’ir’e örbns’n hran’ê uwesgnen’n
    ei sêk dloer’n’ua zn’el’et’ff s.n.c. lnee eradn’ wue
    êfht’iesn’n’f wrdihs zêusrs rf’uaf’np. ihr död’e srunrca
    e wehsnhdn’ mne fu oenin’f iftt’ kt’t’set’ wr’sfue ede ê
    ue er’rn dde eshse i an’er’e nunw tmnisen’t’ miabdhhncs
    r.b.n. fneezt’ rande hehrt’wr he ehfs mid’a ue inlg
    ft’eaveidn’ t’oa iuegnnz’w ngwsaetme. lel hul retn’h’
    dien’ i nelct’ eweas hlen’sr’ wiê ê eisr’e eomn’f
    glniftha usrualhseen ed’irt’n’l’ t’nifn’tn’ smwallssn d.s.z.r.
    d’repc r’l’iwt’ srehui i iufiee ihnrl n’ecnn’ hiuen ênfi
    sengnet’snr’ hgênww hn’ein’ üdnalgs’ eamdemn. lba wof’u
    i mud’n r’nuaht’ sêas’gnn bzereenn f’err di eg tnein
    erdsz’i isr’sn’n n’hee rêt iöe dhi ewgwt’mk n.t.d. mze
    i eir’ fnö r’eseeon’ ferisen’lcr’t’ hrhu l’nhu ewt’
    öfenuinrwe wen wertss cidi kereelrn”. sn’ehd’en i
    aind’ n’aêain. Albot’l f’laefdln’ m’n’eev s’e eedn’a
    tekezwn nie eenn’mn ndew giunn’ rferss i sr’ee ide
    ai’fefend’e wn’êd dresmrde gon’it’ iwêrw wurieheu.
    eimat”

  2. #2 Klaus Schmeh
    19. Januar 2017

    @Thomas: Thanks for the transcription! I hope somebody will take the chance and take a closer look at it.

  3. #3 Norbert
    20. Januar 2017

    Since Armin posted the solution, I have been trying to write a (pure) hill climber – without success. Now that I read that in fact, it was a simulated annealing algorithm that Armin used, I built that into my program, and it works and takes less than one minute to reveal the plaintext (coded in C++). Wow! Nevertheless, I don’t think I would have found the solution even if I had decided at the beginning to program a simulated annealing algorithm, because of Klaus’s unintentional extra hurdle. Again, congratulations to Armin!
    But I didn’t know that the simulated annealing algorithm is apparently subsumed under the term “hill climbing”. I considered them to be two different approaches.

  4. #4 Klaus Schmeh
    20. Januar 2017

    Bart Wenmeckers via Facebook:
    A good write up and well done to Jim and Armin on the solves.. I didn’t realise you had co authored a book Jim any other secrets?

    Has anyone come across a good in depth discussion on the mutation phase this is where i have a problem at the moment.

  5. #5 Klaus Schmeh
    20. Januar 2017

    Jim Gillogly via Facebook:
    Well, there’s this one from a few years ago: http://www.planetary.org/press-room/releases/2004/0415_Hidden_Mars_Messages_Found.html